自适应二次变异的改进差分进化算法及其应用

胡福年 董倩男 吕 璐

(江苏师范大学电气工程及自动化学院 江苏 徐州 221116)

0 引 言

差分进化(Differential Evolution，DE)算法[1]是一种基于群体差异的随机搜索算法，其原理与遗传算法类似，但不包括编码和解码，受控参数少，同时因其本身具有强大的鲁棒性和全局寻优能力，因而在约束优化[2]、电力系统调度[3]等领域得到广泛运用。

与常用进化算法类似[4-7]，DE算法也存在容易陷入局部最优和过早收敛的问题。因此，学者们对DE算法进行不同方面的改进，以提高算法收敛精度并跳出局部最优。改进方法大致分为以下几类。

一是控制参数的改进，主要涉及种群规模、变异策略、交叉策略等。文献[8]对变异因子、交叉概率进行自适应控制，增强了算法的寻优性能。文献[9]对变异策略进行改进，采用随机选择的方式在两种变异策略之间进行选择。文献[10]使用动态加权因子对两种变异策略进行权值动态分配，增强算法的全局寻优性能，同时采用了控制参数的自适应方法。

二是种群结构的改变，如种群重构、多种群差分。文献[11]提出一种基于平均熵的初始化策略，将种群拆分为两个群体，分别采用不同的变异策略，进行种群间的信息交流。文献[12]将种群以适应值大小进行分类成为多个种群，采用不同的策略进化，实现全局优化。文献[13]将种群随机动态分为多个子群体，增强个体间的信息交换。

三是与其他算法交叉使用，结合不同算法的寻优思想对DE进行改进。文献[14]将粒子群算法与差分进化算法结合使用，充分发挥两种算法的优点，改善了差分算法的收敛性能。文献[15-16]将人工蚁群算法与差分进化算法混合使用，增强了算法的搜索性能和寻优速度。文献[17]将免疫克隆算法与差分进化算法结合，增强算法的搜索能力。

DE进化算法的改进方式多样，为进一步增强算法的寻优性能和收敛精度，本文结合现有的几种改进方法的思想，充分利用各种改进策略的优势，提出一种基于自适应二次变异的改进差分进化算法。通过记录最优解连续不更新的次数，自适应地对种群进行二次重构。为证明该算法的有效性，对9个测试函数进行仿真，并且选用3种常用的改进差分进化算法与其进行对比，对算法性能进行分析。将算法实际应用于38机组的电力系统调度问题中，验证算法的收敛性能。

1 差分进化算法

差分进化算法的基本思想是从某一随机种群开始，按规则进行迭代，对个体进行一定操作，最后淘汰适应值差的个体，保留优秀个体。对于最小值优化问题描述如下：

(1)

(1) 初始化。DE基于实数编码，在可行域中随机生成NP个D维的初始种群：

xi,0=(xi1,0,xi2,0,…,xiD,0)

(2)

(3)

(2) 变异。DE通过差分策略实现个体变异，利用两个不同的父代向量做差，产生相应的差分向量，将其向量差缩放后与待变异个体进行向量合成，这也是差分进化算法和遗传算法之间的差异。在DE中最常用的变异策略是DE/rand/1、DE/best/1、DE/current-to-rand/1、DE/current-to-best/1等。具体操作如表1所示。

表1 变异策略

其中：r1、r2、r3为两两互不相同的随机整数且r1≠r2≠r3≠i；F为缩放因子，取值在0～1之间；vi,G+1表示变异后个体；xi,G表示第G代第i个个体；xr1,G、xr2,G、xr3,G表示当前种群中随机选取的不同个体；xbest,G表示第G代最优个体。

(3) 交叉。对第G代个体及变异个体进行交叉操作。DE算法的交叉操作有两种方式：二项式交叉和指数交叉。一般选取较为简单的交叉方式，即二项式交叉，具体操作如式(4)所示，得到实验个体:ui,G+1=(ui1,G+1,ui2,G+1,…，uiD,G+1)。

(4)

式中：CR为交叉率，取值在0～1之间；jr指1,2,…，D上的随机整数。

(4) 选择。选择操作的主要目的是选择一个好的个体作为下一代的父代。通常，采用贪婪算法选择进入下一代群体的个体。对于最小化问题，选择具有小适应度函数值的个体作为下一代群体的成员。

(5)

式中：xi,G+1表示选择操作后，进入下一代的个体。

2 自适应二次变异的改进差分进化算法

2.1 变异策略

传统DE进化算法仅使用单一的变异策略，使得每下一代个体的产生都通过父代个体之间不变的变异操作，容易过早聚集收敛陷入局部最优。因而在差分算法进化的开始阶段，应当保证种群的多样性。DE/rand/1具有较大的寻优范围，它有利于全局搜索，故适用于算法初期。而到了算法进化中后期，因前期已经完成了全范围的搜索，此时应重点关注最优个体及其附近区域。DE/current-to-best/1寻优速度较快，有利于局部的精确搜索，故适用于算法进化后期。针对各种策略在各阶段所发挥的作用不同这一特点，采用多变异策略，将DE/rand/1与DE/current-to-best/1相结合，加入动态权重因子平衡两种策略的权重，充分发挥两种变异策略的优势。

w=wmin+(wmax-wmin)·(G/Gmax)

(6)

vi,G+1=(1-w)·(xr1,G+F·(xr2,G-xr3,G))+

w·(xi,G+F·(xqbest,G-xi,G)+F·(xr4,G-xr5,G))

(7)

式中：w为权重因子，wmin=0，wmax=1；Gmax为总进化代数。

w值随着进化种群数的增加呈线性递增趋势，有利于平衡两种变异策略的权重。在算法进化初期，w值较小，DE/rand/1策略起主导作用，有利于增加解空间的搜索范围；在算法演化的中后期，w值较大，DE/current-to-best/1策略起决定性作用，有利于局部精确搜索。

结合RMDE[18]中扰动策略的思想，设置一个调和参数Mr，随机选择现有的变异操作和扰动策略，称为小概率扰动，进一步增强算法跳出局部最优的能力，Mr一般取大于0.9的值，部分伪代码为：

ifrand

w=wmin+(wmax-wmin)·(G/Gmax)

vi,G+1=(1-w)·(xr1,G+F·(xr2,G-xr3,G))+

w·(xi,G+F·(xqbest,G-xi,G)+F·(xr4,G-xr5,G))

else

end

2.2 自适应二次变异

针对差分进化算法的早熟问题，并提高算法跳出局部最优的能力，本文通过记录算法进化过程中适应值连续不更新的次数来及时检测算法的停滞状况，以便进行自适应二次变异。设定一个停滞代数最大值Max_count，当最优适应值连续Max_count代不更新时，即认为之后的算法进化是无用的停滞迭代，采用二次变异策略打破停滞，并提供更好的进化方向。

二次变异策略中利用全局最优信息和柯西分布，决定算法跳出局部最优的方向和步长。柯西分布与正态分布的概率分布对比如图1所示，其中正态分布服从N～(0,1)，柯西分布服从Cauchyi～randci(μ,λ)，μ和λ是局部参数，分别取μ=0,λ=1。图2显示了取200个数，柯西随机数Cauchyi～randci(μ,λ)的数值，分别取μ=0,λ=0.01。由图知，相比于正态分布，柯西分布降低了取值为0的概率，能够增加取除0以外其他值的概率。

图1 概率分布对比图

图2 柯西随机数

自适应二次变异的伪代码为：

count=0;

forG=1:Gmax

ifxbest,G+1=xbest,G

count=count+1;

else

count=0;

end

ifcount=Max_count

fori=1:NP

end

count=0;

end

end

2.3 选择策略

为进一步加大算法的寻优范围，加入反向学习策略，可以增加算法解的多样性，增加在搜索过程中找到全局优解的机会，并加快算法收敛速度。选择策略时，在交叉后得到的实验个体与反向个体之间进行选择，反向个体的产生过程如下：

(8)

根据适应值的大小，选择下一代的个体。

(9)

2.4 控制参数

控制参数F和CR直接影响下一代群体的搜索方向和搜索范围，在传统的差分进化算法中通常取固定值。但是这样无法满足算法在进化的各阶段中对控制参数的不同要求，如算法多样性、鲁棒性等，因而渐渐产生了参数自适应的改进差分进化算法。参数自适应使得算法能够在进化的不同时间段内，根据自身种群的分布情况与适应值之间的相对位置关系，改变自身的搜索范围与搜索方向，以增强整个算法的寻优性能。参数F和CR通常取0～1以内的值。

本文考虑将产生优秀个体的参数值保留，将产生淘汰个体的参数值重新设定，根据个体适应值来决定是否将参数值保留至下一代，具体表达式如下：

(10)

(11)

(12)

CRi,1=0.9

(13)

式中：Fi,1、Fi,G、Fi,G+1分别表示第一代缩放因子、第G代缩放因子、第G+1代缩放因子；Fmin、Fmax表示缩放因子的最小值和最大值；CRi,1、CRi,G、CRi,G+1分别表示第一代交叉概率、第G代交叉概率、第G+1代交叉概率。

ASVDE算法流程如图3所示。

图3 ASVDE算法流程

3 电力系统经济调度模型

电力系统经济调度[19]问题是指在满足系统的约束条件下对机组的发电功率进行合理分配，降低发电成本，从而达到经济性最高的目标。主要内容包括目标函数的设定和约束条件的处理。

3.1 目标函数

以机组发电成本为目标函数，在T时间段内，常规发电机组的发电成本主要考虑发电机组燃料成本而不考虑阀点效应的情况下，机组燃料成本可表示为：

(14)

式中：Cj表示第j台机组的发电成本；aj、bj、cj表示第j台机组的发电成本系数，通常取正的常数。

3.2 约束处理

约束条件主要考虑两方面约束，一是所有发电机组的发电输出等于系统总的负荷需求，忽略电能的传输损耗；二是考虑发电机组输出功率的上、下边界。对约束条件的处理采用最常用的方法——惩罚函数法。

FP=FC+M·p(x)

(15)

(1) 功率平衡约束。

(16)

式中：PL表示系统总的负载需求，Pj表示第j台机组的输出功率。

(2) 发电机组输出功率的上、下边界。

(17)

4 仿真实验

4.1 函数与参数设置

为了验证ASVDE算法的搜索能力，选用9个函数对其进行测试，并且另外选取3种差分进化算法作为对比。测试函数的类型分为单峰函数和多峰函数，它们的优化均为最小值问题。使用的对比算法有DE算法、RMDE算法、HSDE算法[20]，根据各种算法在参考文献内的描述，将参数设置如下。

(1) DE算法中，缩放因子F=0.5，交叉概率CR=0.3。

(2) RMDE算法中，缩放因子F=rand，交叉概率CR=0.3，扰动因子Mr=0.9。

(3) HSDE算法中，缩放因子Fmax=0.9，Fmin=0.1，交叉概率CR=rand。

(4) ASVDE算法中，缩放因子Fmax=1，Fmin=0.1；扰动因子Mr=0.99，Max_count=5。

表2给出了测试函数的定义、自变量范围与理论最优值。算法的种群规模NP=100，每种算法均独立运行30次，迭代次数为1 500代，分别计算四种算法在20维、50维、100维中得到的平均值、标准差。通过30次运行获得的平均值、标准差和以显著性水平为0.05的Wilcoxon rank-sum test指标[21]可得出ASVDE算法与其他3种对比算法性能的优劣。Wilcoxon秩和检验和T检验均可用于测试两组独立样本的差异性，但是Wilcoxon秩和检验不要求数据必须符合正态分布。测试结果存在两种情况：差异显著和差异不显著。结果用p值表示，当两组数据完全相等时检验结果为NaN。但若有显著性差异，则无法比较两组数据所对应的算法的优劣。因此，为进一步判断算法的优劣，采用“胜率”作为下一步的分析方案。“胜率”，即两种算法每次运行得出的最优值两两进行比较。若胜，加1分；若平，加0.5分；若败，加0分。将每个算法得到的分数除以比较的次数(30×30=900)，得到的值就是它们各自的胜率。此外，对每个算法测试函数在各个维度获得的平均值进行排序，以便得出更直观的结论。仿真实验使用MATLAB软件编程实现。

表2 测试函数

4.2 测试函数的实验结果

根据文中所述的参数设置及采用的分析指标，对4种算法优化测试函数的结果进行分析。表3为4种算法在20维、50维、100维三种的情况下搜索得到的平均值、标准差，表4为秩和检验结果，其中最优解加粗标记。

表3 实验结果

续表3

表4 秩和检验结果

续表4

从表3和表4可以看出，与其他3种算法相比，ASVDE算法的优化性能占绝对优势。对于20维的测试函数，除了在函数f5上ASVDE与DE取得并列最优解，其余函数上ASVDE算法的平均值和标准差均达到最优水平；除函数f2、f6和f7外，ASVDE算法均能找到全局最优解，因此，在低维时，ASVDE算法具有较好的平均优化性能、稳定性和鲁棒性。根据Wilcoxon rank-sum test和胜率指标来看，除函数f4和f5外，ASVDE算法明显优于其他算法且胜率达到100%。在50维和100维时，除函数f2、f6和f7外，ASVDE算法均找到了全局最优解，且ASVDE算法在所有的测试函数上的标准差均为最优值。因此，在中、高维时，ASVDE算法的优化性能也显著优于对比算法。根据Wilcoxon rank-sum test和胜率指标来看，除函数f5外，ASVDE的胜率均达到了100%。

综上所述，ASVDE算法不仅对低维函数有着良好的优化性能，随着维数的升高，ASVDE在中、高维函数上仍然占据绝对的优势。相较于对比算法，ASVDE具有较强的稳定性，对各维数的函数均具有较好的全局寻优能力。为了更直观地凸显ASVDE算法的性能，现对4种算法在各维度取得的最佳平均值进行排序，结果如表5-表7所示。

表5 最佳平均值排序(D=20)

表6 最佳平均值排序(D=50)

表7 最佳平均值排序(D=100)

为直观地显现出ASVDE算法的搜索性能，现选取6种情况的优化收敛曲线，如图4-图6所示，即在低、中、高维度各选取2个测试函数。图中，横坐标为迭代次数，纵坐标为平均函数值，表示了测试函数的30次运算的均值随迭代次数增加而变化的过程。

(a) f1

(b) f5图4 测试函数的收敛曲线(D=20)

(a) f2

(b) f4图5 测试函数的收敛曲线(D=50)

(a) f6

(b) f9图6 测试函数的收敛曲线(D=100)

可以看出，ASVDE算法的所有曲线下降最快，能够快速准确地找到全局最优解，而DE、RMDE和HSDE算法的收敛速度明显低于ASVDE。在整个进化过程中，ASVDE算法在各维度都能避免陷入局部最优并快速收敛到全局最优解，具有更好的稳定性，收敛性能远远超过其他3种方法。因此可以认为，ASVDE算法能够有效地增加种群多样性，提高算法找到全局最优解的可能性，是一种有效的优化算法。

4.3 算子性能分析

为了对ASVDE算法中双策略自适应二次变异算子(ASV)的作用进行分析，在此算法的框架上，另外选择两种经典的算子(DE/rand/1、DE/current-to-best/1)与其作对比。将3种算子在每个测试函数上运行得到的平均值和标准差分别进行排序，再将算子在每个函数上的名次相加然后除以函数的个数就可得到算子的平均排名，结果如表8所示。

表8 3种算子排序

平均排名的数值越低，证明算子的性能越好，3种算子的平均排名如图7所示。

图7 三种算子平均排名

由图可知，相比其他两种算子，无论是平均值还是标准差，ASV算子的平均排名最低，这说明改进算法中ASV算子的平均优化性能和稳定性最好。

5 电力系统经济调度仿真

建立38机组火电机组经济调度模型，进行30次独立计算。将ASVDE算法的计算结果与文献[22]的几种算法结果进行对比，结果如表9所示，其中种群规模为40，最大迭代次数为1 500。ASVDE算法的最优解为(220.000 0,359.314 9,500.000 0,500.000 0,500.000 0,500.000 0,500.000 0,500.000 0,137.000 0,114.000 0,114.000 0,114.000 0,110.000 0,90.000 0,82.000 0,120.000 0,65.000 0,65.000 0,65.000 0,306.824 1,390.602 0,110.000 0,80.000 0,10.000 0,60.000 0,136.259 0,35.000 0,20.000 0,20.000 0,20.000 0,20.000 0,20.000 0,25.000 0,18.000 0,8.000 0,25.000 0,20.000 0,20.000 0)。

表9 不同方法优化38机组电力系统经济调度问题的对比

由表9可知，在满足约束的条件下，ASVDE算法得到的最优目标函数值为9 489 279.336 2，比其他四种算法得到的最优目标函数值都要小。由此可知，ASVDE算法可以优化出发电成本最小的值，有较优的寻优性能。

6 结 语

本文提出了一种自适应二次变异的改进差分进化算法。改进算法采用了多变异策略，加入动态权重因子，能够有效地平衡算法全局搜索和局部搜索的能力。利用二次变异对种群结构进行更新，通过记录适应值保持不更新的次数并在其达到设定值时自适应地进行二次变异，保证种群的多样性。变异策略利用全局最优信息和柯西扰动，控制算法及时跳出局部最优，进一步提高了算法的全局寻优能力。选择策略中加入的反向学习能够增加算法解的多样性，提高算法的收敛速度。将改进算法应用在测试函数和电力系统经济调度问题中进行仿真测试，并与其他算法的测试结果进行对比，结果证明ASVDE有着更高的收敛精度。