邓峻 魏文红* 张宇辉 李清霞

(1.东莞理工学院 计算机科学与技术学院，广东东莞 523808；2.东莞城市学院 计算机与信息学院，广东东莞 523419)

演化算法是通过模拟达尔文生物进化论的自然选择和遗传学的生物进化过程，构建出来的仿生算法。它可以通过模拟自然进化的迭代过程，搜索评价函数的最优解。而差分进化算法(Differential Evolution，DE)[1]是进化算法的一个重要分支，它采用实数编码，适用于解决实数参数优化问题，并成功应用于现实世界的各种优化问题[2-3]。如今，人们已经对它做了许多改进[4-6]。

一般情况下，优化问题常常被定义为最小值优化问题，最大值优化问题则可以转成最小值优化问题。全局优化问题的目标是找到一个向量，使得目标函数评价值最小。一般地，向量由D个变量组成，D是目标函数的维度，每个变量由其下界和上界定义。

在单目标优化问题中，目标函数可能有多个局部最优，而一个好的优化算法则需要找到全局最优。如果算法陷入局部最优，则有两种可能。一是跳出局部最优，寻求更优解；另一种是沦陷于局部最优，直到算法结束。其中，算法跳出局部的能力与算法的搜索路径将一定程度上影响算法求解最优值的计算时间。通常在一些复杂的优化问题上，往往将会花费大量的计算时间。

DE算法与其他优化算法一样容易陷入局部最优，存在过早收敛的问题。为了提高DE算法的性能，许多DE的改进算法被提出。具有最优外部存档的自适应差分进化算法(Adaptive Differential Evolution with Optional External Archive，JADE)[7]引入了额外存档以及新的自适应参数机制，增加了种群的多样性，一定程度上缓解了过早收敛的问题。自适应差分进化算法(jDE)[8]虽然往往能较快的收敛到一个解，但可能会陷入局部最优。而针对100位挑战赛自适应差分进化算法(Self-adpative Differential Evolution Algorithm for 100-Digit ChallengejDE100)[9]是jDE算法的改进算法，它加强了算法跳出局部的能力。它使用双种群演化策略，大种群负责勘测，小种群负责探索，在一定条件下会重新初始化种群从而跳出局部陷阱。jDE100算法是CEC2019的100位挑战赛[10]中唯一取得满分的算法，但在部分函数上花费了较多时间。jDE100算法虽然不易完全陷入局部，但它在一些优化问题中有较大的时间开销。

受jDE100算法思想的启发，本文针对jDE100算法进行了改进，提出了一种具有三个种群进行演化的自适应差分进化算法jDE-3，该算法在保障较强的全局搜索能力的前提下，缩短了计算时间。针对CEC2019的100位挑战赛的实验测试，与其他采取差分进化策略的算法进行比较，该算法成功地通过了CEC2019的100位赛的挑战。此外，还试着通过实验探讨该算法面对高维问题下的参数调整。

1 算法背景

1.1 差分进化算法

差分进化算法[1]是一种依赖于种群的进化算法，它的种群由NP个个体组成，每个个体拥有D个变量，随着迭代数的改变，种群也随之变化，最终算法会在最大迭代数下终止。

(1)

Pg表示第g代的种群，表示第g代种群中第I个个体的基因向量。

每一个个体向量由D个变量构成：

(2)

D是每一个个体向量的维度，每一个个体由D个变量组成，表示第g代种群下第I个个体中的第j个变量。

差分进化算法的流程如下：

1)初始化：在迭代开始之前，种群会被随机初始化，每个个体向量中的变量，会对应其值的上下界随机生成均匀分布的值。xj_low，xj_upp分别代表变量在维度j下取值的下界与上界，具体如式(3)：

xi,j=xj_low+rand()*(xj_upp-xj_low)，

(3)

2)变异：一个变异向量将会通过DE的变异策略产生。例如‘DE/rand/1’策略：

(4)

3)交叉：种群中的每一个个体将会与对应的变异向量进行交叉操作。

(5)

4)选择：在第g次迭代中，经历变异，交叉操作后，种群产生了NP个，称为尝试个体。这些尝试个体将会与种群的原本个体进行评价值比较，拥有更优秀的评价值者会被保留。这些保留者会组成新的种群，进行下一次迭代。

(6)

1.2 jDE算法

jDE算法[7]继承了DE算法的基本策略，但对两个控制参数，即缩放因子F和交叉率CR采用自适应机制。每个个体都有属于自己的控制参数值F和CR。新增控制参数Fl和Fu，表示F的上下界；控制参数CRl和CRu，表示CR的上下界。

(7)

(8)

1.3 JADE算法

与jDE算法相似，JADE算法[10]，除了控制参数自适应机制有所改变，还增加了新的存档机制以及变异策略。每个个体都有属于自己的控制参数值F和CR，其变化与uCR和uF相关。uCR和uF一定程度上代表整个种群在某一迭代中，控制参数CR和F较为合适的中间值。而存档机制是在选择阶段，存储评估值交叉的个体基因向量，在变异阶段中，有机会采用存档中的基因向量，以达到基因多样性的目的。

1.4 jDE100算法

jDE100算法[6]是jDE算法的改进算法。与jDE算法不同的是，它有两个演化种群，一个大的种群Pb负责全局探索，一个小的种群Ps负责局部开发。两个种群都采用jDE的基本策略，大的种群在变异阶段有概率获取小种群的基因向量，若在大的种群发现了当代全局最佳，则小种群的某个个体会被取代，以达到大小种群基因交流的目的。其中若种群收敛到一定程度，则会触发种群重新初始化的机制，重新搜索。jDE100算法流程图如图1所示。

图1 jDE100 算法流程图

2 jDE-3算法描述

2.1 算法思想与改进

jDE-3算法是针对jDE100的改进算法。相较于jDE100算法，jDE-3算法采用三个种群进行演化。前期先用单个种群Pt按照jDE策略进行探索，探索后如果条件未满足，则大种群Pb将继承Pt探索的基因向量。这样设计的目的是为了提高算法前期的探索效率，由于Pt种群远小于Pb，不会过于影响Pb的多样性，这样既加快了探索效率，又不会过于影响探索精度。大种群Pb以及小种群Ps将继续探索。其中小种群重新初始化的条件和大种群一样增加了生命周期作为限制，以防止小种群陷入若干个局部最优，无法继续探索。

2.2 算法步骤

根据算法思想，jDE-3的算法具体步骤如下：

准备:Pt试探种群，tNP试探种群的个体数

准备:Pb大种群，bNP大种群的个体数

准备:Ps小种群，sNP小种群的个体数:bNP=m×sNP, m ∈ 1, 2, …

1: 初始化种群，随机产生Pt={x1,x2,…,xtNP}

2: 初始化种群，随机产生Pb={x1,x2,…,xbNP}

3: 初始化种群，随机产生Ps={x1,x2,…,xsNP}

4: 初始化Fi= 0.5;CRi= 0.9; (i∈ {1,tNP+bNP+sNP})

5: while 当终止条件1未满足

6: for each i ∈Ptdo

7: 执行 jDE 变异策略

8: 执行 jDE 交叉策略

9: 执行 jDE 选择策略

10: end for

11: end while

12:Pt覆盖Ps前tNP个个体

12: while 当终止条件2未满足

13: 检查种群Pb

14: 检查种群Ps

15: for each i ∈Pbdo

16: 执行 jDE 变异策略

17: 执行 jDE 交叉策略

18: 执行 jDE 选择策略

21: end if

22: for k ∈ 1, 2, …, m do . repeat m-times

23: for each i ∈Psdo

24: 执行 jDE 变异策略

25: 执行 jDE 交叉策略

26: 执行 jDE 选择策略

27: end for

28: end for

29: end while

在算法中，有以下几个方面是需要值得注意的：

1)终止条件1：当最优解达到10位正确精度或者评价次数超过1e5；

2)终止条件2：当最优解达到10位正确精度后或者评价次数超过1e10则跳出；

3)检查种群Pb指的是如果种群中最佳个体与种群种个体相似数在种群种占比大于等于myEqs%(最佳个体评价值与种群个体评价值的差值小于等于EPS=1e-16为相似)，则种群会被重新初始化。或者如果种群评价次数超过生命周期(大种群生命周期age1=1e9)，则同样会重新初始化；

4)检查种群Ps指的是如果种群中最佳个体与种群种个体相似数在种群种占比大于等于myEqs%(最佳个体评价值与种群个体评价值的差值小于等于EPS=1e-16为相似)，则种群会被重新初始化。或者如果种群评价次数超过生命周期(小种群生命周期age2=1e8)，则同样会重新初始化。但会保留种群Ps的最佳个体。

5)Pb种群的jDE变异策略与原本略有不同，它额外增加了Ps的第一个成员作为可选择成员，让Ps的基因向量能在Pb中流通。

6)复制策略是当Pb探索种群搜索到当前最优解的时候，将该成员覆盖Ps的第一个成员，让种群Ps开发这一个优质解。

7)种群Ps在每一轮迭代中，重复执行了m次。这里设定，它的jDE策略和原始jDE策略一致。

3 实验分析

3.1 实验描述

实验主要围绕不同算法在CEC2019特别会议上10个基准函数的测试表现。在表1中，描述了这10个函数的基本信息。函数的维数从9维到18维不等，但大多数函数都是10维。在这个挑战赛中，所有基准函数的最优解值都为1，但需要达到十位精度，即1.000 000 000。在以往的竞赛中，目标功能评价的最大数量是有限的，但这一挑战赛对时间或功能评价的最大数量都没有限制。

在100位数字挑战赛中[9]有10个问题，目标是在不受时间限制的情况下计算每个函数的最小值到10位的精度。该挑战赛要求参赛者用一种算法解决十个问题，允许对每个函数进行有限的控制参数调优。对于每个函数，需要50次连续测试，且每个算法具有不同的初始种群。在50次的实验测试中，我们最优的25次结果，则该函数的分数是最优的25个试验中正确数字的平均数目。如果超过一半或一半以上的试验找到所有正确的10位数，那么该函数的得分是10分，10个函数的总分最高为100分。

由于100位数字挑战赛中没有高维测试函数，为了探讨jDE-3在高维问题下的参数选择，将测试集中第四个测试函数Rastrigin’s Function进行扩展(无偏移和旋转)：

(9)

分别测试jDE-3在该测试函数30维、50维、80维和100维下达到10位正确精度，即1.000 000 000所花费的评价次数。对每一种情况进行30次测试。

表1 CEC2019 100-digit函数介绍

3.2 实验结果

在该挑战赛中，DE算法获得43.72分，jDE算法获得68.08分，JADE算法获得46分，jDE100算法获得100分，jDE-3算法获得100分。表2至表6分别为DE算法、jDE算法、JADE算法、jDE100算法和jDE-3算法针对各函数挑战所得的详细分数。其中DE算法的参数CR和F默认为0.9和0.5；jDE算法的参数CRinit=0.9，Finit=0.5，tau1=0.1，tau2=0.1；JADE算法的参数uF=0.5，uCR=0.5，c=0.1，p=0.1；jDE100算法的参数与文献[8]中的一致；jDE-3算法的参数与jDE100算法基本一致。所有种群大小Pt为80，调整的参数CRl与Fl详见表9。

表2 DE算法详细得分

jDE-3不同参数下优化高维问题见表7，其中CRl取值为0。

表3 jDE算法详细得分

表4 JADE算法详细得分

表5 jDE100算法详细得分

表6 jDE-3算法详细得分

表7 jDE-3算法在不同参数下优化高维问题所花费的评价次数

3.3 实验对比与分析

在所有比较的算法之中，只有jDE100算法和jDE-3算法取得了100分。下面将比较这两个算法直接花费的评价次数。表10为jDE-3算法的在各函数中所花费的评估数分析，其中取50次连续运行中最好的25次作为统计数据。表8为jDE-3算法与jDE100算法的评估数比较，比较方式为jDE100算法的评估数与jDE-3算法的评估数差值除以jDE算法的评估数，+50%表示jDE-3算法比jDE100算法花费的评价次数要少50%。由表可以看出，如果通过迭代次数的中值进行比较，jDE-3算法在函数F1、F2、F3、F5、F7、F8和F10花费的评价次数更少；如果通过迭代次数的平均值进行比较，jDE-3算法在函数F1、F2、F3、F7、F8和F10花费的评价次数更少。表9为jDE-3算法的参数设置，只允许调整Fl和CRl两个参数。图6至图7分为各算法在函数F1、F2、F3、F7、F8、F10收敛图对比，其中横轴代表评估数，纵轴代表达到的精度位数。

在jDE-3算法中，主要调整的参数为Fl和CRl，分别为缩放因子和交换概率的下限，在一般情况下，Fl的取值影响较大。由于采取jDE策略，每个个体对应的参数F和CR将根据演化过程自适应。当Fl取值过小，种群的个体可能因为jDE中的贪婪策略，使个体对应的F长期保持较小值，影响种群的全局搜索，陷入局部；当Fl取值过大，F的取值受限，不能取到较小值，种群可能难以较快收敛到足够的精度。

由表7可以看到，当Fl取值过低，jde-3在面对高维多局部值的优化问题中容易多次陷入局部，需要花费更多的额外代价跳出局部寻求全局最优。而Fl也不是越大越好，应是一个适中的值。

表8 jDE-3算法和jDE100算法在评价次数比较 %

表9 jDE-3算法的参数设置

表10 jDE-3算法在所有50次运行中的25次最佳记录，包含函数评估数(FES)的最佳、最差、中位数、均值和标准差值

图2 函数F1收敛图对比

图3 函数F2收敛图对比

图4 函数F3收敛图对比

图5 函数F7收敛图对比

图6 函数F8收敛图对比

图7 函数F10收敛图对比

4 结语

为了在保证单目标优化问题中精度的前提下减少时间代价，受jDE100算法启发，提出了一种基于三种群演化策略的自适应差分进化算法jDE-3来解决CEC2019中100位挑战的问题。jDE-3算法采用自适应控制参数F和CR，利用三个种群进行演化，第一个种群在前期进行快速勘测，后两个种群负责长期的探索与开采。在整个算法的进化过程中，小种群的重新初始化机制被修改，使其更容易跳出局部最优。最后经过实验证明，jDE-3算法不仅能精确地求解CEC2019中函数F1-F10的全部问题，还在绝大部分函数上比其他DE算法及其变种节约了求解时间。