差分进化算法

高效的全局优化算法

差分进化算法(Differential Evolution Algorithm，DE)是一种高效的全局优化算法。它也是基于群体的启发式搜索算法，群中的每个个体对应一个解向量。差分进化算法的进化流程则与遗传算法非常类似，都包括变异、杂交和选择操作，但这些操作的具体定义与遗传算法有所不同。

历史发展

差分进化算法(Differential Evolution，DE)由Storn和Price于1995年首次提出。主要用于求解实数优化问题。该算法是一类基于群体的自适应全局优化算法，属于演化算法的一种，由于其具有结构简单、容易实现、收敛快速、鲁棒性强等特点，因而被广泛应用在数据挖掘、模式识别、数字滤波器设计、人工神经网络、电磁学等各个领域。1996年在日本名古屋举行的第一届国际演化计算(ICEO)竞赛中，差分进化算法被证明是速度最快的进化算法。

和遗传算法一样，差分进化算法也是一种基于现代智能理论的优化算法，通过群体内个体之间的相互合作与竞争产生的群体智能来指导优化搜索的方向。该算法的基本思想是：从一个随机产生的初始种群开始，通过把种群中任意两个个体的向量差与第三个个体求和来产生新个体，然后将新个体与当代种群中相应的个体相比较，如果新个体的适应度优于当前个体的适应度，则在下一代中就用新个体取代旧个体，否则仍保存旧个体。通过不断地进化，保留优良个体，淘汰劣质个体，引导搜索向最优解逼近。

为了使更多研究者了解和研究差分进化算法，Storn和Price于1997年建立了差分进化算法的官方网站，该网站的建立得到了广大研究者的关注和支持，为相关人员进行差分演化算法的理论和应用研究提供了极大的方便。此外，Store和Price在差分进化算法上没有申请任何形式的专利，这也为推动差分进化算法的研究和应用起到了重要的作用。

基本原理

DE算法通过采用浮点矢量进行编码生成种群个体。在DE算法寻优的过程中，首先，从父代个体间选择两个个体进行向量做差生成差分矢量；其次，选择另外一个个体与差分矢量求和生成实验个体；然后，对父代个体与相应的实验个体进行交叉操作，生成新的子代个体；最后在父代个体和子代个体之间进行选择操作，将符合要求的个体保存到下一代群体中去。

进化流程

其具体进化流程如下：

(1)确定差分进化算法控制参数，确定适应度函数。差分进化算法控制参数包括：种群大小NP、缩放因子F与杂交概率CR。

(2)随机产生初始种群。

(3)对初始种群进行评价，即计算初始种群中每个个体的适应度值。

(4)判断是否达到终止条件或进化代数达到最大。若是，则终止进化，将得到最佳个体作为最优解输出；若否，继续。

(5)进行变异和交叉操作，得到中间种群。

(6)在原种群和中间种群中选择个体，得到新一代种群。

(7)进化代数g=g+1，转步骤(4).

控制参数

DE算法主要的控制参数包括：种群规模(NP)、缩放因子(F)和交叉概率(CR)。

NP主要反映算法中种群信息量的大小，NP值越大种群信息包含的越丰富，但是带来的后果就是计算量变大，不利于求解。反之，使种群多样性受到限制，不利于算法求得全局最优解，甚至会导致搜索停滞。