第26章 差分进化算法
差分进化算法是一种具有特殊“变异”“交叉”和“选择”方式且采用实编码的遗传算法。变异操作通过从种群中随机选择一个个体作为基向量和另外两个不同个体的差分向量加权和的线性组合产生变异向量；交叉操作通过变异向量和目标向量各维分量随机组合完成；选择操作是以“贪婪”方式选择比目标向量个体适应度值更好的新向量个体进入种群。本章介绍差分进化算法的原理、基本操作、实现步骤及差分进化算法的扩展形式等。
26.1 差分进化算法的提出
差分进化（Differential Evolution，DE）算法是1995年由美国学者Storn和Price提出的一种求解全局优化问题的实编码的进化算法[78]，[79]，又称为微分进化算法。最初用于解决切比雪夫不等式问题，后来发现它对于解决复杂优化问题具有计算过程更简单、控制参数少的优越性。目前，差分进化算法已广泛应用于化工、电力、机械设计、控制工程、机器人、人工神经网络、信号处理、数据挖掘、生物、运筹学、调度问题等领域。
26.2 差分进化算法的原理
差分进化算法的基本思想源于遗传算法，同其他进化算法一样也是对候选解的种群进行操作，而不是对一个单一解。DE算法利用实数参数向量作为每一代的种群，它的自参考种群繁殖方案与其他优化算法不同。DE算法是通过把种群中两个个体之间的加权差向量加到第三个个体上来产生新参数向量，这一操作称为“变异”；然后将变异向量的参数与另外预先决定的目标向量的参数按照一定的规则混合起来产生子个体，这一操作称为“交叉”；新产生的子个体只有当它比种群中的目标个体优良时才对其进行替换，这一操作称为“选择”。DE算法的选择操作是在完成变异、交叉之后由父代个体与新产生的候选个体一一对应地进行竞争，优胜劣汰，使得子代个体总是等于或优于父代个体。而且，DE算法给予父代所有个体以平等的机会进入下一代，不歧视劣质个体。
差分进化算法把一定比例的多个个体的差分信息作为个体的扰动量，使得算法在跳跃距离和搜索方向上具有自适应性。在进化的早期，因为种群中个体的差异性较大，使得扰动量较大，从而使得算法能够在较大范围内搜索，具有较强的勘探能力；到了进化的后期，当算法趋向于收敛时，种群中个体的差异性较小，算法在个体附近搜索，这使得算法具有较强的局部开采能力。正是由于差分进化算法具有向种群个体学习的能力，使得其拥有其他进化算法无法比拟的性能。
26.3 差分进化算法的基本操作
1. 个体编码方式
DE算法采用实数编码方式，直接将优化问题的解x1，x2，…，xn组成个体Xi，G=（x1，x2，…，xn），i=1，2，…，NP。每个个体都是解空间中的一个候选解，个体的变量维数D与目标函数决策变量的维数n相等，即D=n。
2. 种群初始化
初始种群用随机方法产生为
其中，rand为［0，1］之间的随机数。
种群大小NP直接影响算法的收敛速度，通常NP取问题维数（向量参数的个数）的3～10倍。
3. 变异操作
DE算法和其他进化算法的主要区别是变异操作，也是产生新个体的主要步骤。变异操作后得到的中间个体Vi，G+1表示为
其中，r1，r2，r3∈｛1，2，…，NP｝且r1≠r2≠r3≠i；F∈［0，1］为变异因子，它是DE算法控制差分向量的幅度，又称为缩放因子，通常F取值为0.3～0.7，初始值可取F=0.6；
为基点向量。
DE的中间个体是通过把种群中两个个体之间的加权差向量加到基点向量上来产生的，相当于在基点向量上加了一个随机偏差扰动。而且由于3个个体都是从种群中随机选取的，个体之间的组合方式有很多种，这使DE算法的种群多样性很好。由于进化早期群体的差异较大，使得DE前期勘探能力较强而开发能力较弱；而随着进化代数增加，群体的差异度减小，使得DE后期勘探能力变差，开发能力增加，从而获得一个具有非常好的全局收敛性质的自适应程序。目标函数为二维的DE算法变异操作示意图如图26.1所示，其中X1和X2分别表示目标函数的第一维和第二维变量。
变异因子F是变异操作中添加到被扰动向量上差异值的比率，其作用是控制差分向量的幅值。因此，又被称为缩放因子。
4. 交叉操作
交叉操作采用将变异得到的中间个体Vi，G+1=（v1i，G+1，v2i，G+1，…，vDi，G+1）和目标个体Xi，G=（x1i，G，x2i，G，…，xDi，G）进行杂交，如式（26.3）所示。经过杂交后得到目标个体的候选个体Ui，G+1=（u1i，G+1，u2i，G+1，…，uDi，G+1）。
图26.1 DE算法变异操作示意图
其中，i=1，2，…，NP，j=1，2，…，D；rnbr（i）为［1，D］范围内的随机整数，用来保证候选个体Ui，G+1至少从Vi，G+1中取到某一维变量；randb（j）∈［0，1］为均匀分布的随机数；交叉因子CR∈［0，1］为DE算法的重要参数，它决定了中间个体分量值代替目标个体分量值的概率，较大的CR值表示中间个体分量值代替目标个体分量值的概率较大，个体更新速度较快。交叉因子CR一般选择范围为［0.3，0.9］，通常CR初始值取0.5较好。DE算法交叉操作示意图如图26.2所示。
图26.2 DE算法交叉操作示意图
5. 选择操作
对候选个体Ui，G+1进行适应度评价，然后根据式（26.4）决定是否在下一代中用候选个体替换当前目标个体。
6. 适应度函数
适应度函数用来评估一个个体相对于整个群体的优劣相对值的大小。DE选择适应度函数有以下两种方法。
（1）直接将待求解优化问题的目标函数作为适应度函数。
若目标函数为最大优化问题，则适应度函数选为
Fit（f（x））=f（x）（26.5）
若目标函数为最小化问题，则适应度函数选为
（2）当采用问题的目标函数作为个体适应度时，必须将目标函数转换为求最大值的形式，而且保证目标函数值为非负数。转换可以采用以下的方法进行。
假如目标函数为最小化问题，则
其中，Cmax为f（x）的最大估计值，可以是一个适合的输入值，也可以采用迄今为止过程中f（x）的最大值或当前群体中最大值，当然Cmax也可以是前K代中f（x）的最大值。显然，存在多种方式来选择系数Cmax，但最好与群体本身无关。
假如目标函数为最大化问题，则
其中，Cmin为f（x）的最小估计值，Cmin可以是一个适合的输入值，或者是当前一代或K代中f（x）的最小值，也可以是群体方差的函数。
26.4 差分进化算法的实现步骤及流程
下面通过求解函数f（x1，x2，…，xn）的最小值问题来叙述DE算法的求解步骤及算法流程。其中（x1，x2，…，xn）∈Rn是n维连续变量且满足
，j=1，2，…，n，
和
分别代表第j维变量的下界和上界。目标函数f：Rn→R1可以是不可微函数。
假设DE算法种群规模为NP，每个个体有D维变量，则第G代的个体可表示为Xi，G，i=1，2，…，NP。
DE算法的主要步骤如下。
（1）随机产生初始种群，进化代数G=0。
（2）计算初始种群适应度，DE算法一般直接将目标函数值作为适应度值。
（3）判断是否达到终止条件。若进化终止，将此时的最佳个体作为解输出，否则继续。
终止条件一般有两种：一种是进化代数达到最大进化代数Gmax时算法终止；另一种是在已知全局最优值的情况下，设定一个最优值误差（如10-6），当种群中最佳个体的适应度值与最优值的误差在该范围内时算法终止。
（4）进行变异和交叉操作，得到临时种群。
（5）对临时种群进行评价，计算适应度值。
（6）进行选择操作，得到新种群。
（7）进化代数G=G+1，用新种群替换旧种群，转步骤（3）。
DE算法的流程如图26.3所示。DE算法采用下述两个收敛准则。
（1）计算当前代全体个体与最优个体之间目标函数值的差值，若在误差范围内，则算法收敛，否则继续生成新的种群。
（2）计算当前代和父代种群中最优个体之间目标函数值的差值，若在误差范围内，则算法收敛，否则继续生成新的种群。
图26.3 DE算法的流程图
26.5 差分进化算法的扩展形式
前面介绍的差分进化算法是一种基本形式。根据生成差分向量来实现变异操作的形式不同，R.Storn和K.Price提出了多种微分进化算法差分策略的改进形式。为了方便，改进策略采用符号DE/X/Y/Z来表示，其中X表示确定将要变化的向量，当X是rand或best分别表示随机在群体选择个体或选择当前群体中的最优个体；Y表示需要使用差向量的个数；Z表示交叉模式，Z是bin表示交叉操作的概率分布满足二项式形式，Z是exp表示交叉操作的概率分布，满足指数形式。Price和Storn对差分进化算法共提出10种策略：DE/best/1/exp、DE/rand/1/exp、DE/rand-to-best/1/exp、DE/best/2/exp、DE/rand/2/exp、DE/best/1/bin、DE/rand/1/bin、DE/rand-to-best/1/bin、DE/best/2/bin、DE/rand/2/bin。
显然，由于差向量的个数不同，差分进化算法的差向量有如下两种形式。
（1）一个微分差向量时：
。
（2）两个微分差向量时：
。
考虑到交叉操作的概率分布为二项式形式，微分进化算法的变异操作有如下形式。
（1）DE/rand/1/bin：
。
（2）DE/best/1/bin：
。
（3）DE/rand-to-best/2/bin：
。
（4）DE/rand/2/bin：
（5）DE/best/2/bin：
。