差分演化算法（Differential Evolution ）是曾经一度非常热门的算法，该算法简单易用，收敛速度快。这篇文章对其进行总结。

 

算法简介

所谓的演化算法是一种自适应，并行的全局优化算法，还包括遗传算法等。

差分演化算法与其他演化算法的最大区别在与差分变异算子的应用。

差分演化算法主要用于求解实数优化问题，一般不用于求解离散问题。

 

算法流程

算法流程图如下。

伪代码流程如下。

下面对每一个具体的阶段进行说明。

在初始化阶段，对于每个个体的每一维在其自变量范围内采用均匀随机初始化。

在变异阶段，采用差分变异算子，经典差分算子DE/rand/1的公式如下：

在交叉阶段，采用离散重组，常用的二项式杂交算子如下（就是让子个体和父个体交换某些维度的坐标值）：

其中的v是变异之后的个体，此处的条件j==jrand是为了避免交叉后的子个体与父个体完全相同，交叉的效果如下图。

在选择阶段采用锦标赛一对一选择，就是父个体和自己的子个体比较，谁优秀谁留下。

 

实例代码

随手撸的简易版差分演化代码，目标函数为f=x^2+y^2。对于每个个体都要进行变异操作，所以不设置变异率这个常量。

#include<iostream>
#include<vector>
#include<time.h>
using namespace std;

const int SIZE = 10;                                 //种群规模
const int DIMENSION = 2;                             //目标函数维数
const double F = 0.6;                                //缩放因子
const double CROSSOVER_RATE = 0.2;                   //交叉率
const int ITER_NUM = 30;                             //进化20代    
const vector<double> LOWER_BOUND = { -100,-100 };    //每一个维度的上限	
const vector<double>  UPPER_BOUND = { 100,100 };     //每一个维度的下限



struct Single{                                       //个体结构
	vector<double>m_xreal;                           //n维坐标
	double m_fitness;                                //适应度
	Single(){                                        //构造函数
		m_xreal = vector<double>(DIMENSION, 0);      //初始化坐标
		m_fitness = 0;                               //初始化适应度
	}
};

vector<Single>parentpop(SIZE);                       //父种群
vector<Single>childpop(SIZE);                        //子种群

double RandReal(int left, int right);                //得到一个随机实数
double RandInt(int left, int right);                 //得到一个随机整数
void Print();                                        //打印群体情况
void InitPop();                                      //初始化群体
double CalculateFitness(vector<double>realx);        //计算适应度
void ParentSelection(vector<int>&index);             //选择三个不相同的父亲个体
void Mutation(vector<int>&index,int i);              //变异操作
void BinCrossover(int i);                            //交叉操作
void Selection(int i);                               //根据一对一锦标赛选择个体

int main()
{
	srand((unsigned)time(NULL));                     //随机数种子

	InitPop();
	Print();
	cout << endl;
	for(int i=0;i<ITER_NUM;i++)
	{
		for (int j = 0; j < SIZE; j++)               //对每一个个体进行操作
		{
			vector<int>index;

			ParentSelection(index);
			
			Mutation(index,j);

			BinCrossover(j);

			Selection(j);
		
		}
		Print();
		cout << endl;
	}
	cin.get();
}
void Print()
{
	for (auto var : parentpop)
		cout << "coordinate:" << var.m_xreal[0] << "," << var.m_xreal[1] << " fitness:" << var.m_fitness << endl;
}
double RandReal(int left, int right)
{
	int range = right - left;
	double result(0);
	result = rand() % range - 1 + (float)(rand() % 1000) / 1000.0 + left + 1;
	return result;
}
double RandInt(int left, int right)
{
	int range = right - left;
	double result(0);
	result = rand() % (range + 1) + left;
	return result;
}
void InitPop()
{
	for ( int i=0;i<SIZE;i++)
	{
		for (int j = 0; j < DIMENSION; j++)
			parentpop[i].m_xreal[j] = RandReal(LOWER_BOUND[j], UPPER_BOUND[j]);

		parentpop[i].m_fitness = CalculateFitness(parentpop[i].m_xreal);
	}
}

double CalculateFitness(vector<double>realx)//计算适应值
{
	//目标函数f=x1^2+y^2
	double result = realx[0] * realx[0] + realx[1] * realx[1];
	return result;
}

void ParentSelection(vector<int>&index)//挑选三个不同的父亲个体的索引
{
	for (int i = 0; i < 3; i++)
	{
		int r(0);
	    bool flag (false);
		do
		{
			flag = false;
			r = RandInt(0, SIZE - 1);
			for (auto var : index)
				if (r == var)flag=true;

		} while (flag);
		index.push_back(r);
	}
}
void Mutation(vector<int>&index, int i)
{
	int r1 = index[0], r2 = index[1], r3 = index[2];
	for (int j = 0; j < DIMENSION; j++)
	{
		//根据差分变异算子进行变异
		childpop[i].m_xreal[j] = parentpop[r1].m_xreal[j] + F*(parentpop[r2].m_xreal[j] - parentpop[r3].m_xreal[j]);
		//如果越界，随机取一个值
		if (childpop[i].m_xreal[j] < LOWER_BOUND[j] || childpop[i].m_xreal[j] > UPPER_BOUND[j])
			childpop[i].m_xreal[j] = RandReal(LOWER_BOUND[j], UPPER_BOUND[j]);
	}
}
void BinCrossover(int i)
{
	    //设置一个temp值，保证子个体不会与父个体完全相同
		int temp = RandInt(0, DIMENSION - 1);
		for (int j = 0; j < DIMENSION; j++)
		{
			if (RandReal(0, 1) > CROSSOVER_RATE && j != temp)
			{
				childpop[i].m_xreal[j] = parentpop[i].m_xreal[j];
			}
		}
}
void Selection(int i)//锦标赛选择
{
	
		parentpop[i].m_fitness = CalculateFitness(parentpop[i].m_xreal);
		childpop[i].m_fitness = CalculateFitness(childpop[i].m_xreal);
		if (childpop[i].m_fitness <= parentpop[i].m_fitness)
			parentpop[i] = childpop[i];
}

http://www1.icsi.berkeley.edu/~storn/code.html#c++c

这个网站是DE算法的官网，有正儿八经的各种语言的DE算法代码。

谢谢观看：）