自适应交配限制概率的自组织多目标演化算法

李桂英，王述洋，宋申民，张 虎

(1.东北林业大学 机电工程学院，哈尔滨 150040； 2.黑龙江大学 机电工程学院，哈尔滨 150080；3.哈尔滨工业大学 控制理论与制导技术研究中心，哈尔滨 150001)

实际工程中存在大量的多目标优化问题(multiobjective optimization problem,MOP).带约束的典型MOP表达式如下[1]：

minF(x)=(f1(x),…,fm(x))T,

s.t.x=(x1,…,xn)T∈Ω.

多目标优化问题不同于单目标优化问题，其优化的各个目标往往是相互冲突的，因此对于多目标问题求解有一定的难度.目前较常用的求解方法是同时优化多个目标，对相互冲突的目标进行折衷.MOP存在大量的权衡所有目标的折衷解，即Pareto最优解.对于决策空间的一个解xi∈Ω，如果决策空间其他所有的解都不能支配xi，则称xi为决策空间Ω中的Pareto最优解.所有Pareto最优解组成Pareto解集(Pareto set, PS)，Pareto最优解的目标值形成Pareto前沿(Pareto front, PF).求解多目标优化问题时不可能求出其所有的Pareto最优解，决策者希望搜索到的有限逼近解所对应的目标向量不仅要靠近PF，并且要均匀覆盖整个PF.

为了更好地解决多目标优化问题，学者们提出了多目标演化算法(multiobjective evolutionary algorithm, MOEA)，该算法通过单次运算就能获得一系列非支配解，并且具有应用领域广、并行性好、鲁棒性高等特点.个体重组与环境选择是MOEA重要的组成部分.就个体重组而言，MOEA有运用模拟二进制交叉[2]、多项式变异[3]、差分进化[4]等针对单目标优化问题提出的重组算子.这种算子产生后代有一定的局限性.考虑到Pareto解集具有的规则特性，学者们提出了基于模型的多目标演化算法.其典型的代表有Zhang等[5-6]在2008年提出的基于规则特性的RM-MEDA和2009年提出的通过建立概率模型同时逼近PF和PS的MMEA.也有学者提出了基于解分布结构的重组算子.基于环境选择，近年来的多目标演化算法主要有3类：以NSGA-II等[7]为代表的基于支配的多目标演化算法，以SMS-EMOA等[8]为代表的基于指标的多目标演化算法，以MOEA/D-DE[9]等为代表的基于分解的多目标演化算法.目前多目标演化算法的性能可以用不同特性的数值优化问题进行测试[10]，并逐渐被应用于大规模优化问题[11]、动态优化问题[12]以及实际工程问题[13].

多目标演化算法在演化过程中应恰当地平衡开采和勘探能力有助于获得分布广泛的代表性逼近解集.许多研究成果表明，差异较大个体之间进行重组有利于勘探，相似个体之间进行重组利用了Pareto解集的连通性和规则特性[14]能够增强局部搜索.目前，学者们已经提出了多种交配限制策略来平衡搜索过程中的开采和勘探，但是这些限制策略往往需要设计额外的、使用者进行调节的控制参数，或者采用复杂的判断准则来决定勘探或开采[15-16].因此需要设计一种交配限制概率，使算法能够简单、自适应地确定所需要的交配限制概率.此外，聚类是一种能够挖掘Pareto解集分布结构的有效方法[17]，根据聚类识别的种群结构信息利用交配限制概率控制父代来源，可以平衡搜索过程中的开采和勘探.自组织映射(SOM)算法作为一种无监督学习方法，其能够对输入的高维训练点产生低维表征[18].即SOM可以保持输入数据间的近邻关系，从而进行聚类.受此启发，本文提出一种基于自适应交配限制概率的自组织多目标演化算法 ASMEA.在每一代ASMEA利用SOM聚类算法挖掘当前种群分布结构，根据此种群结构以一定交配限制概率控制父代来源于邻居或整个种群以分别加强开采和勘探，根据以整个种群为交配池和以邻居为交配池，在过去一定代数产生后代个体的效用，更新算法的交配限制概率.

1 自适应自组织多目标演化算法

1.1 SOM聚类算法

SOM算法能够实现高维数据特征在低维空间进行表示，并保持拓扑结构不变.SOM首次训练时每个神经元的初始特征向量从训练点集合中随机挑选，随后特征向量的迭代更新由距离这些特征向量最近的训练数据点完成，通过训练输入数据找到每个神经元的特征向量，从而进行特征识别.在训练中，SOM根据更新获胜神经元及邻近神经元的特征向量，将输入的训练数据映射到输出层的神经元上，并保持其拓扑结构不变，根据此结构对输入数据进行聚类划分.SOM的具体算法见文献[18].

1.2 ASMEA算法框架

算法1给出了ASMEA的算法框架.在ASMEA的每一代，SOM首先添加一些新的训练数据到S中(第1行)，随后ASMEA演化了T代(第2～24行).更新训练参数(第3～8行).根据学习结果实现每个个体关联一个神经元(第9～14行).以概率β为个体xu设置交配池由邻居种群组成，以1-β的概率设置交配池由整个种群组成(第17行).基于交配池Q，利用重组算子为xu产生一个新解y(第18行).通过环境选择更新种群P(第19行).更新训练数据集S，训练数据集由新添加到种群中的个体组成(第21行).基于重组效用更新交配限制概率β(第22行).在ASMEA算法中，训练数据是每一代中新产生的个体.如果采用一个新的数据集，并不会用SOM重新进行学习，而是使用先前训练过的数据结构信息，这样减少了反复训练大量数据所带来的计算开销.

1.3 新解生成

ASMEA利用差分进化(differential evolution, DE)算子和多项式变异(polynomial mutation, PM)算子生成新解.新解产生的具体步骤见算法2.以配对池Q作为父代来源，从Q中随机地挑选两个个体p1和p2为父代个体(第1行)，然后利用差分进化算子产生后代基因(第2行)，并利用多项式变异算子进一步演化后代基因(第4行)，为确保新解可行性，对差分进化生成的新解和变异操作的新解分别进行修补(第3、5行).在挑选父个体时，如果交配池为当前解的邻居且邻居数目小于2，则从整个种群中选择父个体.

1.4 环境选择

环境选择可以在每一代新解y产生后从P′挑选出优秀的解作为后代演化的父代种群.ASMEA采用快速非支配排序和超体积环境选择相结合的环境选择方法.这种环境选择方法促使种群保持收敛性和多样性.具体算法见算法3.

ASMEA利用快速非支配排序法衡量P′中个体的收敛性，Pareto等级最差的个体收敛性最差，最先被舍弃.按照Pareto等级划分P′中个体到L个不同的非支配前沿{B1,…BL}中.其中B1为最优等级，BL为最差等级.

算法1ASMEA算法框架.

Input:N为种群大小；τ0为初始SOM学习率；σ0为初始邻居半径；H为邻居交配池大小；β为交配限制概率；HL为历史时长.

Output: 优化种群P.

1)初始化种群P={x1,x2,…,xN}，初始训练数据集S=P，初始化神经元权向量集合P={w1,…,wN}.

2)fort=1,…,Tdo

3)foreachxs∈S,s=1,…,|s|do

4)更新训练参数：

6)确定邻近神经元：

U={u|1≤u≤NΛ‖zu-zu′‖2<σ}.

7)更新所有邻近神经元的权向量(u∈U)：

wu+τ·exp(-‖zu-zu′‖2)(x-wu).

8)end

9)设置A=P以及U={1,…,N}.

10)whileA≠Φdo

11)随机选择x∈A且设置A=A{x}.

13)设置U=U{u}.

14)end

15)设置A=P.

16)foreachu∈{1,…,N}do

17)为xu设置交配池：

rand为在[0,1]之间产生一个均匀分布的随机数，uk是在隐空间中距离神经元u的第k个最近神经元.

18)产生一个新个体y=SolGen(Q,xi,F,CR,pm,ηm).

19)通过环境选择，保存优良解P=EnvSel(P，y).

20)end

21)更新训练数据集：S=PA.

22)基于重组效用更新交配限制概率β.

23)end

24)return种群P.

算法2SolGen(Q,xi,F,CR,pm,ηm)算法框架.

Input:当前演化个体xi；交配池Q；差分进化算子参数F,CR；多项式变异概率pm；变异分布指数ηm.

Output:新解y=(y1,…,yn)T.

1)从Q中挑选两个父个体p1和p2.

3)修补新解：

4)变异新解:

算法3环境选择算法框架.

Input:新解y，种群P.

Output:优化种群P.

1)新解y添加到种群P，辅助种群P′，用快速非支配排序衡量P′中个体的收敛性，划分为L个等级{B1,…，BL}.

2)如果l>1时

①计算P′中支配每个个体x*的个体数目d(x,P′).

②移除P′中具有最大d(x,P′)的个体x*.

3)如果l=1

①计算P′中每个个体x*的超体积贡献度Δφ(x,P′).

②移除P′中超体积贡献度最小的个体x*.

4)将P′赋给P，P=P′.

5)输出P.

当L>1时，P′中包含多个等级，则需要移除最劣等级中具有最大d(x,P′)的解，其中d(x,P′)表示在P′中支配x的点的数量.当L=1时，P′中只包含一个等级，删除具有最小超体积贡献度Δφ(x,B1)的个体，计算超体积贡献度Δφ的具体方法见文献[19].

1.5 交配限制概率更新

在ASMEA中，用于产生新个体的父个体来源于邻居的优点是利于开采，缺点是在进化的早期阶段，容易丢失种群多样性.产生新个体的父个体来源于整个种群的优点是可以提高算法的勘探能力，产生的后代能够具有很好的多样性，但在演化后期产生高质量解的能力较弱.所以需要在演化过程中恰当地控制父代来源. 此外，实际工程中为了更有效地求解多目标优化问题，不同的优化问题需要设置不同的β值控制父代来源以平衡全局搜索与局部搜索，在演化过程的前期和后期也需要不同的β值.设置一个合适的β值对ASMEA是合理且有效的.因此，ASMEA基于聚类设计一种交配限制策略控制父个体来源，从而平衡算法求解过程中的勘探和开采.β在演化过程中自动更新方法如下，在第t+1代：

1.6 计算复杂度分析

ASMEA中SOM算法和环境选择算子的计算复杂度高于重组算子与交配限制概率更新算子，因此主要考虑SOM算法和环境选择算子的计算复杂度.ASMEA运行SOM算法的计算复杂度为O(nND)，其中N为种群大小，n为变量维度，D为神经元数.环境选择算子结合了快速非支配排序和超体积，前者的复杂度为O(mN2)，后者为O(Nm).其中，m为优化目标个数.因此，环境选择算子的时间复杂度为O(mN2+Nm).综上可知, ASMEA算法的计算复杂度为O(nND+mN2+Nm).

2 分 析

2.1 标准测试实例及性能指标

为了验证ASMEA的性能，本文选取具有复杂Pareto前沿结构和Pareto解集的多目标优化问题GLT1-GLT6[20]对ASMEA算法进行测试.选用反转世代距离IGD[21]和超体积HV[22]两个常用性能指标，可以同时有效地评估解的收敛性和多样性.并且IGD指标值越小逼近前沿的收敛性和多样性越好，HV指标值越大，表明算法搜索到的逼近前沿越好.

使用HV指标值评估算法性能时需要设定恰当的参考点，本文求解GLT1-GLT6测试题，在计算HV指标值时设置参考点分别为r=(2,2)T，r=(2,11)T，r=(2,2)T，r=(2,3)T，r=(2,2,2)T和r=(2,2,2)T.

2.2 参数设置

为了检验ASMEA的搜索性能，本文选择了5种具有代表性的多目标演化算法与其进行对比实验.对比算法分别是：NSGA-II、SMS-EMOA、RM-MEDA、MOEA/D-DE和TMOEA/D. 本文基于原始文献并通过多次实验对算法中的主要参数进行了调节优化.各算法具体参数设置见表1.

表1 求解GLT测试题的NSGA-II、SMS-EMOA、RM-MEDA、MOEA/D-DE、TMOEA/D及ASMEA的参数值

表1中各主要参数调节方法为：1)选择一个被调节的参数，根据经验把其他参数设置为固定值；2)调节当前被调节参数的参数值，使算法性能最优的值被赋给当前参数.反复调节直到任何参数的变化都无法显著提高算法的整体性能.ASMEA中的控制参数F，CR，H和HL按照上述方法进行调节，SOM结构是根据种群大小确定不需要调节.根据参数灵敏度分析，算法性能对τ0=0.7和β0=0.5并不敏感，可以按照经验估计，亦可用上述方法进行调节.

2.3 对比实验结果

2.3.1 搜索质量

分别由算法NSGA-II、SMS-EMOA、RM-MEDA、TMOEA/D、MOEA/D-DE以及ASMEA在GLT测试集上获得的23个逼近前沿的IGD和HV的均值和标准差结果见表2. 6种算法获得的平均IGD指标值按照升序，平均HV指标值按照降序进行排序，并将排序结果置于表2的方括号中.在ASMEA和每个对比算法之间采用了显著性水平5%的Wilcoxon秩和检验.表中“†*”、“§”、“≈”3个符号分别表示ASMEA的性能在5%显著水平上优于、差于和类似于比较算法.每种算法求解所有测试题获得的平均秩见表2.

从表2可以看出，根据5%显著性水平的Wilcoxon秩和检验，ASMEA与其他5种对比算法相比，分别获得了12、12、12、10和11个显著更优的平均性能评估指标值.按照综合排名将6种算法性能从优到劣的排序为ASMEA、TMOEA/D、SMS-EMOA、RM-MEDA、NSGA-II及MOEA/D-DE.虽然TMOEA/D在求解GLT2及GLT1时稍优于ASMEA，但是在对6道测试题的求解过程中及与5种对比算法的12次Wilcoxon秩和检验中，根据最佳平均指标值及平均秩的结果，ASMEA对于GLT测试集求解性能最佳.

进一步利用box-plot描述算法的统计性能， 6种算法对GLT测试集独立运行23次获得的IGD指标值的箱线图如图1所示，从图1中可看出ASMEA在求解GLT1，GLT3-GLT6时获得了最小的中位IGD指标值和四分位距，在求解GLT2时获得第2小的中位IGD指标值.结果说明ASMEA对于GLT能稳定地求解出具有良好多样性和收敛性的解.

2.3.2 搜索效率

从搜索效率的角度比较ASMEA与5种对比算法.图2绘制出了ASMEA、TMOEA/D、SMS-EMOA、RM-MEDA、NSGA-II及MOEA/D-DE获得的IGD的均值和标准差的演化曲线.图2中显示，对于GLT1、GLT3-GLT6，ASMEA能以最高的搜索效率获得最小的IGD指标值，对于GLT2，ASMEA与TMOEA/D获得了相似的IGD值.ASMEA总体上能以最快搜索效率获得最小的IGD值.

表2 NSGA-II、SMS-EMOA、RM-MEDA、TMOEA/D、MOEA/D-DE以及ASMEA在GLT测试题上获得的统计结果

2.3.3 可视化比较

从表2中可知ASMEA和TMOEA/D是表现最好的两种算法，将TMOEA/D和ASMEA进行单独的可视化对比实验.图3绘制出TMOEA/D和ASMEA求解GLT1-GLT6时独立运算23次获得的全部逼近前沿和代表性逼近前沿.从图3(a)、图3(b)可以看出，对每道测试题ASMEA获得的全部逼近前沿都能够很好地覆盖整个的Pareto前沿并收敛， TMOEA/D获得的逼近前沿没有覆盖GLT5-GLT6整个的Pareto前沿，且无法全部收敛到GLT4-GLT6的Pareto前沿.从图3(c)、图3(d)可以看出，对于GLT1-GLT2以及GLT4，TMOEA/D和ASMEA获得代表性逼近前沿能收敛并且均匀覆盖整个Pareto前沿.对于GLT3，ASMEA找到更多的Pareto解.ASMEA对于GLT5-GLT6获得的代表性逼近前沿比TMOEA/D具有更好的多样性.

图1 IGD指标值箱线图

图2 平均IGD值的平均值和标准差演化曲线

图3 TMOEA/D和ASMEA获得的全部逼近前沿和代表性逼近前沿

3 进一步分析

3.1 WFG测试集检验求解性能

用具有复杂的Pareto前沿形状复杂Pareto问题特性的WFG[24]测试题来进一步验证ASMEA的性能.将ASMEA及对比算法NSGA-II、SMS-EMOA、RM-MEDA、TMOEA/D、MOEA/D-DE的参数值见表3.对于WFG测试题，计算HV指标值时的参考点均选择r=(3,5)T.ASMEA和对比算法独立计算WFG测试题23次获得的统计结果见表4.

从表4的统计结果得出，与NSGA-II、RM-MEDA、TMOEA/D及MOEA/D-DE各自的23次比较中，ASMEA分别获得了13、14、11和10个明显较优结果.虽然相对SMS-EMOA而言，ASMEA获得了5个更优，但SMS-EMOA与ASMEA在考虑最优解和次优解时性能相似.最优平均秩的结果表明ASMEA略差于SMS-EMOA.但ASMEA在求解GLT测试集的性能优于SMS-EMOA，所以ASMEA拥有整体最优性能.

表3 求解WFG测试题的NSGA-II、SMS-EMOA、RM-MEDA、TMOEA/D、MOEA/D-DE及ASMEA的参数值

表4 NSGA-II、SMS-EMOA、RM-MEDA、TMOEA/D、MOEA/D-DE以及ASMEA在WFG测试题上获得的统计结果

3.2 参数灵敏度分析

用带有不同参数的ASMEA算法对GLT的每道测试题独立运行23次，运用获得的IGD指标值的均值和标准差分析参数灵敏度.

3.2.1 邻居交配池大小

分析ASMEA对H=5,10,15,20,25的灵敏度.ASMEA算法采用不同H值时获得的IGD指标值的均值和标准差绘制于图4(a)中.通过图4(a)可以看出，采用H=5的ASMEA对所有GLT测试题有最佳的求解效果.

3.2.2 历史长度

设置HL=5,10,15,20,25，在每个GLT测试题上独立运行ASMEA算法23次，利用不同HL的ASMEA算法获得的IGD值绘制于图4(b)中.如图4(b)所示，当HL=15时，综合所有GLT测试题上的结果发现此时ASMEA表现最优.

3.2.3 初始交配限制概率

设置β0=0.1,0.3,0.5,0.7,0.9，在GLT测试题上独立运行ASMEA算法23次，将β0取不同值时ASMEA算法获得的IGD的均值和标准差如图4(c)所示.从图4(c)中可看出，取β0=0.9时，ASMEA对于所有测试题均有较优异的性能，表明ASMEA性能对于β0的取值不敏感.

3.2.4 初始学习率

设置学习率τ0=0.1,0.3,0.5,0.7,0.9，将ASMEA在每道测试题上独立运行23次，绘制IGD指标值的均值和标准差如于图4(d)中.从图4(d)中观察到，当τ0=0.7时，ASMEA求解决所有的GLT测试题均有较好的性能.图4(d)的结果表明ASMEA的性能对于初始学习率τ0的设置并不敏感.

图4 采用不同H，HL，β0或τ0值的ASMEA在GLT1-GLT6上独立运行23次获得的IGD值的均值和标准差

4 结 论

1)本文设计了交配限制概率自适应更新策略以及聚类-演化融合策略，进而提出了一种自适应自组织多目标演化算法(ASMEA).在ASMEA的每一代，运用SOM聚类算法将种群划分为几个类.根据交配限制概率，控制每个个体从邻居或差异较大的整个种群选择父代，进行交配产生新个体，从而加强开采或者勘探.此外，在每一代，根据邻居和整个种群产生新个体的效用，进而对交配限制概率进行自适应更新.

2)将ASMEA与代表性算法NSGA-II、SMS-EMOA、RM-MEDA、TMOEA/D、MOEA/D-DE进行对比实验.6种算法分别求解了具有复杂Pareto前沿形状的GLT和WFG标准测试题.求解结果表明ASMEA具有整体更优的求解性能.参数灵敏度实验结果表明ASMEA的性能未明显受到其使用参数变化的影响.