1.1.5 差分进化算法
1997年，为了求解切比雪夫多项式的拟合问题，R. M. Storn等人[23]提出了主要用于求解实数优化问题的差分进化算法（DEA）。DEA作为一种基于群体导向的自适应启发式全局随机搜索技术，包括初始化、变异、交叉及选择等操作；与其他优化算法的不同在于，DEA的进化个体扰动是通过多个个体的差分信息来体现的。
DEA的基本思想：首先，采用浮点向量进行编码随机产生初始种群；其次，把种群中任意两个个体的向量求差生成差分向量，乘以缩放因子与第三个个体求和来产生实验个体；再次，对父代个体与相应的实验个体进行交叉操作，生成新的子代个体；最后，在父代个体和子代个体之间进行选择操作，将符合要求的个体保存到下一代群体中去；通过不断地进化，保留优良个体，淘汰劣质个体，引导搜索向最优解逼近。
DEA主要的控制参数包括种群规模、交叉概率和缩放因子。
种群规模主要反映算法中种群信息量的大小，种群规模值越大，种群信息越丰富，但是带来的后果就是计算量变大，不利于求解。反之，使种群多样性受到限制，不利于算法求得全局最优解，甚至会导致搜索停滞。
交叉概率主要反映的是在交叉的过程中，子代与父代、中间变异体之间交换信息量的大小程度。交叉概率的值越大，信息量交换的程度越大。反之，如果交叉概率的值偏小，将会使种群的多样性快速减小，不利于全局寻优。
相对于交叉概率，缩放因子对算法性能的影响更大，缩放因子主要影响算法的全局寻优能力。缩放因子越小，算法对局部的搜索能力更好，缩放因子越大，算法越能跳出局部极小点，但是收敛速度会变慢。此外，缩放因子还影响种群的多样性。
差分进化的核心和关键是变异操作指导算法向全局最优处靠拢。变异向量由种群中的个体与其他不同个体的向量缩放差共同构成，主要分为基向量和差分向量两部分，根据生成变异向量的不同方法能够得到多种变异策略。DE/x/y是一种简易的表达变异策略的方式，其中x表示指定基向量的方式，rand表示基向量为种群中随机选取的一个向量，best表示基向量为种群适应度值最低的向量；y代表变异策略中差分向量的数目，一般为1个或2个。在种群规模n足够大的情况下，使用两个差分向量可以增加种群的多样性。
最常用的变异策略如下：
（1）DE/rand/1
（2）DE/rand/2
（3）DE/best/1
（4）DE/best/2
（5）DE/rand-to-best/1
（6）DE/rand-to-best/2
（7）DE/current-to-rand/1
其中，
是随机整数，彼此互不相同并且不同于i，范围为[1，n]。缩放因子F是控制种群发展速度的一个正实数，F没有上限，但是其最大值很少大于1。Xbest,g为第g代种群中适应度值最小的个体。K为（0，1）之间的随机数。
为了增加变异向量的多样性，实施交叉策略，将变异向量与目标向量进行交叉混合，得到试验向量。交叉概率参数用于控制试验向量由变异向量的元素组成的概率，这个值由用户自己定义，范围一般为[0，1]。交叉方式主要有两种，分别是二项交叉和指数交叉。
差分进化算法具有如下优点。
（1）结构简单：DEA采用浮点编码，控制参数少，主要的进化操作是差分变异策略，这使得向量间只存在简单的加减运算，让算法更加易于使用。
（2）性能优越：DEA具有较高的稳定性、较强的稳健性和较快的工作效率，在解决复杂的优化问题时也有不错的表现。
（3）自适应性：DEA对问题的特征信息不敏感，差分变异算子拥有搜索方向自适应的能力，能够动态地调整参数以适应不同的目标函数。
（4）“贪婪”选择策略：DEA在进化的最后一步执行选择策略，采用“贪婪”选择的方式选取进入下一代的个体，该方法大大提高了算法的搜索效率。
（5）时间复杂度低：基本的DEA的时间复杂度为O(n·m·Gmax)，其中，m表示个体维数，Gmax表示最大进化代数。较低的时间复杂度使得DE算法具有求解大规模全局优化问题的优势。
虽然DE算法具有许多算法没有的优势，但也无法完全避免智能进化算法普遍存在的不足。
（1）停滞：以种群为基础的算法，迭代很少的次数就收敛到了一个次优解，而种群的多样性仍然很高，这是由于种群在一定的时间内没有改善，使算法无法寻找到新的搜索空间以确定最优解。诱发停滞的因素有很多，其中最主要的因素是控制参数和决策空间维数的错误选择。
（2）早熟收敛：一些高等级的个体特性占种群的主导地位，种群无法产生比父代更好的子代，从而导致种群收敛到了局部最优。
（3）对控制参数敏感：算法的有效性和稳健性依赖于参数值的选择，最佳的参数值确定还与目标函数及收敛精度有关。
（4）缺乏处理约束问题的机制：在实际的优化过程中经常遇到DEA无法很好地解决约束优化问题的情况。
为了解决基本DEA的上述缺陷，目前主要的改进方法是针对种群结构、进化模式和控制参数的优化，还有一些改进方法是将DE算法与其他一些智能算法结合使用[24,25]。