差分进化算法介绍

一、差分进化算法简介

差分进化算法（Differential Evolution，DE）是基于种群的智能优化算法，种群中的每个个体对应一个解向量。差分进化算法由Storn和Price于1995年首次提出。主要用于求解实数优化问题。该算法是一类基于群体的自适应全局优化算法，属于演化算法的一种，由于其具有结构简单、容易实现、收敛快速、鲁棒性强等特点，因而被广泛应用在数据挖掘、模式识别、数字滤波器设计、人工神经网络、电磁学等各个领域。

由于差分进化算法具有以下诸多特点：
  1. 简单易行；
  2. 性能强悍；
  3. 参数较少；
  4. 较低的空间复杂度；
因此受到了广泛的关注和应用。

二、差分进化算法原理

DE采用了和标准进化算法几乎一样的计算步骤：即由父代个体产生子代个体，二者中较好的一个作为新的父代进入下一代进行后续的循环迭代过程。然而又不同于传统的演化算法，DE首先执行变异过程，即在当前种群中随机选择三个个体，将其中两个相减得到差分向量（Difference vector）并叠加在第三个个体，即基个体（Base Vector）上以得到变异个体，再执行交叉操作，即将变异个体与目标个体做交叉得到对应的子代个体，最后执行选择操作，将子代个体与目标个体进行适应值比较，较好的一个进入下一代继续重复迭代过程，直到满足算法的终止条件。

在DE中, 通常将问题的解 (Solution) 表示为一个包含D维元素 (Element) 的向量 (Vector) 或者称为个体 (Individual): x。对于连续实参数优化问题，向量中的每一个元素都是一个实数。而该向量解质量的好坏，需要通过计算对应的目标函数值 F(x)来定量地评价。

DE算法的选代搜索过程需要三个种群(Population), 每个种群包含NP个个体, 分别称之为当前种群 (Current Population)、变异种群 (Mutation Population ) 和试验种群(Trial Population )。当前种群用 Px,g来表示, 表示由后续迭代过程中的成功个体所构成的种群。变异种群使用Pv,g表示，表示由当前种群中的个体经过变异操作后产生的变异个体组成的中间种群。试验种群用Ｐu,g表示，表示由当前个体和变异个体进行交叉操作后产生的试验个体组成的子代种群。

经典差分进化算法的流程图和步骤说明如下：

- 初始化：
随机生成个体每一维元素；同时设置与算法相关的参数，包括个体的维数、最大迭代数、变异系数和交叉系数；
- 变异操作:
当前种群中随机选择三个个体，将其中两个相减得到差分向量(Difference Vector)并叠加在第三个个体（基个体，Base Vector)上得到变异个体；
- 交叉操作：
将变异个体与目标个体做交叉得到对应的子代个体；
- 选择操作:
将子代个体与目标个体进行适应值比较，较好的一个进入下一代继续重复迭代过程，直到满足算法的终止条件；

参数设置：

1. 个体的维数：将问题的解表示为一个包含D维元素（Element）的向量（Vector）或者称为个体（Individual）
2. 最大迭代数 ：g_max 
3. 变异系数：

         F>0 缩放差分向量，通常取自 (0,1)

         v_(i,g)=x_(r1,g)+F(x_(r2,g)-x_(r3,g) )

     4. 交叉系数：

        CR是 (0,1)  内的预设实数，控制交叉过程

算法伪代码：

三、经典差分进化算法类型介绍

为了简单明了地表示这些不同经典算法版本，DE 的发明者 Price 和 Storm 使用符号“DE/x/yz”来代表不同的 DE 进化策略，即包含变异和交叉的操作过程。其中“DE”表示差分进化算法,“x”表示变异算子中的基向量,“y”表示变异算子中差分向量的个数,“z”表示交叉操作的方法。因为 bin 交叉算子使用得较为广泛, 所以往往不考虑交叉算子的选择，于是“DE/x/y”就被用来表示变异策略。下面列出经典DE算法家族中的变异操作策略及其介绍： 

四、参考资料：

深入了解更多差分进化算法内容，可参考：

1. 董赟. 差分进化算法研究及在港口物流调度中的应用[D]. 东北大学, 2015.
2. Storn R, Price K. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of global optimization, 1997, 11(4): 341-359.
3. Price K, Storn R M, Lampinen J A. Differential evolution: a practical approach to global optimization[M]. Springer Science & Business Media, 2006.
4. Das S, Suganthan P N. Differential evolution: A survey of the state-of-the-art[J]. IEEE transactions on evolutionary computation, 2010, 15(1): 4-31.
5. Das S, Mullick S S, Suganthan P N. Recent advances in differential evolution–an updated survey[J]. Swarm and Evolutionary Computation, 2016, 27: 1-30.