基于小生境中适应度共享的改进DE算法

汤恺祥 许峰

摘 要：将小生境技术和适应度共享思想引入DE算法中，用于改进种群替代中子代选择的优化问题，具体做法是：首先根据DE算法中的变异、交叉及选择操作得到子代种群，其次将这些子代种群通过小生境技术划分为若干个小种群，并在每个小种群中利用适应度共享方法选择或剔除个体，最后将得到的子代和原父代合并作为下轮算法的父代种群。通过测试函数对改进算法进行了数值试验与性能测试，并与其他算法进行了比较。结果显示，改进算法可在一定程度上提高最优解的分布性。

关键词：多目标优化;DE;小生境;适应度共享;分布性

中图分类号：O224;TP301.6  文献标识码：A  文章编号：1673-260X（2021）02-0001-05

2006年，Deb[1]和Brockhoff[2]指出，现实中的许多优化问题是多目标优化问题（Multi-objective Optimization Problem， MOP），而其中的高维多目标优化问题（Many-dimensional Multi-objective Optimization Problem， MOP）的比重越来越高。由于实际操作表明MOEA在处理MOP时的能力不足，其表现在处理问题时性能的低下，对真实的Pareto前沿表示不准确，结果分布性不均匀和稳定性不理想等问题。

差分进化算法（DE Algorithm）[3]，在解决多目标问题时表现良好，有着效率高、全局搜索强和PF表现良好等[4]。但大量的实验DE算法在处理更为复杂的问题时，仍存在局部最优、对PF表示不准确以及解集分布不均匀等问题。

2005年，Rainer Storm[5]和Kenneth Price[5]在他们提出差分进化算法的基础上进一步改进了DE算法;2016年，Blasco[6]在进行高维Pareto前沿分析时引入了相似距离;2017年，Bi[7]将小生境方法引入进MOEA中;2018年，Monalisa[8]将聚类思想引入进DE算法中;2019年，许峰[9]等提出了通过聚类操作约减DE算法的目标函数。

在DE算法中并没有考虑到：择优选择操作后对得到的个体进行进一步优化，剔除相似个体。本文将小生境技术与适应度共享方法引入进DE算法中，是为了优化子代种群，以达到分布性改进。

1 DE算法

DE算法可以解决连续变量的全体优化问题，主要包含突变、交叉、选择三种操作。当使用DE算法求解最小化问题时，问题可以表述为：minf（x），XL≤X≤XU，其中XL，XU为变量X取值上的上限和下限。之后其主要概念及关键步骤如下：

1.1 种群初始化

设进化代数G=（0，1，2，…，Gmax），其中Gmax为最大代数，当前代种群中第i个体为：

Xi，f=（X1i，G，X2i，G，…，XDi，G）  （1）

其中，D为个体向量的维数，Xi，G为目标向量。其初始化公式如下：

Xi（0）=XiL+rand（）·（XiU-XiL）  （2）

其中rand是[0，1]上的随机数，之后Xi（0）表示为第0代群体上的第i个的个体。

1.2 变异操作

DE算法的变异操作基本流程为：在当前种群中，随机选取三个目标向量，差分得到新的个体向量，称之为变异向量。具体方法如下：

Xi，G=X+F·（X-X）  （3）

其中，F∈[0，2]称之为变异尺度因数，作用是对变异向量进行缩减操作，以此达到限制探索步长。通常情况下，F=0.5。

公式（3）被称为DE/rand/1策略，其他的常用策略還包括以下内容：

（1）DE/best/1策略

i，G=best，G+F·（-）  （4）

（2）DE/rand/1策略

i，G=+F·（-）+F·（-）  （5）

（3）DE/best/2策略

i，G=+F·（-）+F·（-）  （6）

（4）DE/current-to-best/1策略

i，G=+F·（-）+F·（-）  （7）

其中，为当前种群中的最优个体。

根据不同问题选择适合的策略，可以得到变异个体。由于是随机选择三个个体，这保证了父代种群组成丰富，更能保证种群的多样性。群成员个体之间：随着迭代次数的增加，变化程度减小，DE算法效率得以提升。

1.3 交叉操作

个体间的交叉操作定义：个体Vi（t+1），对此个体进行交叉操作，得到的个体称之为实验个体，记为Ui（t+1）。在交叉操作中，至少保证有一组变异因子的维度，而其余维度则由交叉因子决定。交叉方式如下：

Uij（t+1）=Vi，j（t+1），rand（j）≤CR或j=kxij（t），其他  （8）

其中，xij（t）表示目标个体Xi（t）中第j维向量，Ui，j（t+1）为突变个体且j=1，2，…，D，rand（j）∈[0，1]为随机数，CR∈[0，1]表示交叉概率因子，K∈[1，2，…，D]代表第i个体对应的系数。交叉操作可以通过控制参数来控制实验中个体自变异的更新内容，由此控制种群个体的进化程度。综合上述操作，变异和交叉操作对DE算法的一些性质如：收敛速率等的改变方向是一致的。

1.4 选择操作

DE算法类似于其他进化算法，都是通过“优胜劣汰”法则对个体进行选取。其过程如下：首先对目标个体与实验个体进行适应度评价，其次对不同个体的适应度值进行区分，最后根据目标优化问题择优选取。其公式如下：

Xi（t+1）=Ui（t+1），f（Ui（t+1））

DE算法求解优化问题时需要设定参数：

（1）种群规模NP，就是群体中所包含个体的总个数，一般由用户根据实际问题的需要设定，NP越大，种群的多样性越高，就有更高的概率获得最优解，但所需计算时间也越长;

（2）变异因子F。选取范围0～2，一般初始值取 0.5;

（3）交叉概率CR，选取范围0～1，设定初始值为0.4。

2 表现型适应度共享方法

适应度共享策略[10]的提出，为了解决解集分布不均匀的问题，提高种群多样性。从启发上来看这种方法，可以理解为：在一个资源有限的目标空间中，如果生物个体众多的话，会导致生物个体由于竞争资源而难以生存。对应算法的表现为：种群分布性和多样性变差以及进化的效率变缓慢。这时我们可以将种群个体的适应度按如下调整：

fi*=fi/sharing（dij）  （10）

其中：fi代表为未修正种群个体与修正后种群个体的亲密度，n为种群个体数目，其中dij为抗体i与j之间的距离，共享函数的定义如下：

sharing（dij）=1-di，j/？滓share，dij<？滓share0，其他，  （11）

其中？滓share代表着和共享参数，即种群个体之间保持距离的期望值。

在距离方面，Goldberg[11]指出表现型适应度共享策略要优于基因型适应度共享策略。这代表着，个体i与个体j之间亲密度的欧式距离要优于个体间的距离，也就是个体i，j在目标空间里的距离。如图1所示。

3 基于小生境中适应度共享的改进DE算法

DE算法从变异和交叉的方向分析，该算法的优点是个体都是随意选取的，这保证了父代有多种组织方式，使得能确保算法中种群的多样性。群成员中的个体之间随着迭代次数的增加程度减小，这使得DE算法收敛速度增加。DE算法可以在PF复杂（如不连续的PF或具有尖峰的PF）的情况下，很大程度上保证实验种群的均匀性和确保解集均匀分布在PF上。

但是从种群个体择优选择的方向分析，该算法中，交叉变异产生一个好子代可以取代大部分差的子代，并且在选择操作中好的子代被选择的概率大大增加，这就导致种群多样性变差，即种群替换方向存在缺陷。因此，在利用该算法时，要确保算法在变异交叉的步骤不变的情况下，改进选择操作后的步骤以达到合理的互补。所以，本文提出了一种基于小生境中适应度共享的改进DE算法，这使得满足原优点的同时，尽可能确保种群多样性和解的分布性。具体定义及流程如下：

定义清除算法（小生境）相关距离：

D（A，B）=1- （12）

其中A=（a1，a2，…，an）T，B=（b1，b2，…，bn）T为n维向量，且D（A，B）∈[0，2]。

个体i=（x1，x2，…，xn）与个体j=（y1，y2，…，yn）的距离公式为：

d（i，j）=  （13）

（14）

小生境中心点为X1，X2，…，Xm，其余个体为Y1，Y2，…，YM，D（Xm，YM）表示中心点与个体间的相关距离。相关距离越大，个体与中心点越近。

基于小生境中适应度共享的改进DE算法步骤如下：

步骤1 初始化，得到初始种群P，设置变异因子和交叉因子;

步骤2 根据DE算法流程更新操作;

2.1 对父代种群Pt，根据DE算法流程变异交叉择优选择的操作得到U;

2.2 对U采取清除算法（小生境）操作，即首先对U中个体根据适应度值进行降序排列，将第一个个体作为第一个小生境中心。其次利用上述相关距离方法判断当前个体到所有小生境中心的最短距离是否大于自定义数值，是则形成新的小生境，不是则加入最近的小生境中。最后小生境生成完毕，多出的个体降低其适应值;

2.3 将生成的每个小生境进行适应度共享操作，即首先，将每个小生境中的个体根据先前得出的适应度优劣排序;其次，设置共享函数中期望值的范围（即两个个体之间亲和度的欧拉距离），如果两个个体之间期望值越大，则亲和度越近，即两个体相似，将这两个个体保留较好的，舍弃较差的;最后重复上述操作直到遍历完所有的点;

2.4 将每个小生境中剩余的个体合并得到子代种群Qt;

2.5 将Pt和Qt合并且根据聚合函数更新父代种群Pt+1;

步骤3 若满足终止条件，则输出最终的解，否则重复步骤2。

4 数值实验与算法性能评测

4.1 算法性能评测指标

MOEA性能评测指标分为四种，具体为容量指标、收敛性指标、多样性指标、收敛性和多样性综合指标[12]。根据本文新算法的优化点为分布性的改进，考虑采用分布性指标（S）与综合指标（IGD）。定义如下：

S（A）=  （15）

其中dx=|fi（x）-fi（x*）|，=dx，|A|表示集合A个体总数，k表示目标函数个数。S指标越小，空间内解集分布越均匀，即算法分布性越好。

IGD（P*，P）=  （16）

其中P*表示理想PF，P表示算法求得的近似PF，d（v，P）表示个体v到P中个体的最小欧几里德距离。IGD指标越小，算法分布性越好。

4.2 数值实验结果

为了评测本文提出的基于小生境适应度共享的DE算法分布性，用此算法对两个标准测试函数Osyczka2和Viennet4进行数值实验，并将实验结果与经典的DE多目标进化算法[12]的優化结果进行了比较。

（1）Osyczka2函数

F（x）=（f1（x），f2（x））f1（x）=-25（x1-2）2+（x2-1）2+（x3-1）2   +（x4-4）2+（x5-1）2f2（x）=x12+x22+x32+x42+x52+x620≤x1，x2，x6≤103≤x3，x5≤51≤x4≤60≤x1+x2-20≤6-x1-x20≤2+x1-x20≤2-x1+3x20≤4-（x3-3）2-x40≤（x5-3）2-x6-4

（2）Viennet4函数

F（x）=（f1（x），f2（x），f3（x））f1（x）=++3f2（x）=+-13f3（x）=++15-4≤x1，x2≤4x2<-4x1+4x1>-1x2>x1-2

为了更准确、定量地衡量本文算法的性能，下面给出本文算法和常规DE算法的S和IGD的对比数据。由于计算结果有随机性，下列数据为10次计算结果的平均值。

5 结论

图4～图5直观显示，基于小生境适应度共享的DE算法在解的分布性和均匀性方面均明显优于常规DE多目标进化算法。表1和表2中的指标很清楚地进一步表明，本文改进算法的S指标和IGD指标均明显占优。

综上，可以得出明确的结论：基于小生境适应度共享的DE多目标进化算法较常规DE多目标进化算法在分布性和均匀性方面有了明显的提高。

——————————

参考文献：

〔1〕DEB K， SAXENA D. Searching for Pareto-optimal Solutions through Dimensionality Reduction for Certain Large-dimensional Multi-objective Optimization Problems [C] // Proceedings of the World Congress on Computational Intelligence （WCCI-2006）， 2006， 3352–3360.

〔2〕BROCKHOFF D， ZITZLER E. Are All Objectives Necessary？ On Dimensionality Reduction in Evolutionary Multi-objective Optimization [C] // Parallel Problem Solving from Nature PPSN IX， Springer， 2006， 533-542.

〔3〕STOM R，PRICE K，LAMPINEN J. Differential evolution： a practical approach to global optimization[M]. Berlin： Springer-Verlag， 2005.

〔4〕STOM R，PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Global optimization， 1997， 11（04）：341-359.

〔5〕SUN J，ZHANG Q. DE/EDA： a new evolutionary algorithm for global optimization[J]. Information science，2004，169（3-4）：249-262.

〔6〕BLASCO X， REYNOSO-MEZA G. Asymmetric Distances to Improve n-dimensional Pareto Fronts Graphical Analysis [J]. Information Sciences，2016， 340： 228-249.

〔7〕Xiaojun Bi， Chao Wang.A niche-elimination operation based NSGA-III algorithm for many-objective optimization [J]. Applied Intelligence， 2017， 48：118-141.

〔8〕MONALISA P， SRIPARNA S， SANGHAMITRA B. DECOR： Differential Evolution Using Clustering Based Objective Reduction for Many-objective Optimization [J]. Information Sciences，2018， 423： 200-218.

〔9〕车旭，许峰.基于聚类的目标约简高维多目标差分进化算法[J].安徽理工大学学报（自然科学版），2020，40（01）.

〔10〕GOLDBERG D E， RICHARDSON J. Genetic algorithms with sharing for multimodal function optimization[C] //Proceedings of the 2nd International Conference on Genetic Algorithms. Hillsdale： L. Lawrence Erlbaum Associates， 1987： 41-49.

〔11〕DEB K， GOLDBERG D E. An investigation of niche and species formation in genetic function optimization[C] //Proceedings of the 3rd International Conference on Genetic Algorithms. San Francisco， California： Morgan Kaufmann Publishers， 1989： 42-50.

〔12〕鄭金华.多目标进化算法及其应用[M].北京：科学出版社，2007.