基于事件触发的自适应邻域多目标进化算法

王学武， 夏泽龙， 顾幸生

（华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 200237）

工业生产中经常存在多个目标的优化问题，多目标优化算法为此类问题提供了解决办法，因此多目标进化算法成为近些年的研究热门[1-2]。在对多目标问题进行优化时，主要考虑两个问题[3]：一是解的收敛性；二是解的多样性。

为了有效地解决上述两个问题，众多学者提供了解决思路。李笠等[4]提出了基于网格排序的多目标粒子群优化算法，利用网格排序的方法对粒子群算法非劣解的储备集进行优化，有效地增强了算法的多样性。Zhang 等[5]提出了一种基于分解的多目标粒子群优化算法(MOPSO/D)，将基于分解的多目标算法与粒子群结合，利用改进变异算子增强解的多样性，利用储备集的方式对非劣解进行储存。Jaimes等[6]指出采用多种群策略对多目标优化问题进行求解，利用种群间的信息交流，不仅能够提高搜索效率，而且能够增加种群的多样性。Li 等[7]提出基于差分进化算法的分解多目标优化算法(MOEA/DDE)，利用差分进化算法收敛速度快、实现简单等特点来改进算法。Qi 等[8]提出基于自适应权重调整的分解多目标进化算法(MOEA/D with Adaptive Weight Adjustment，MOEA/D-AWA)，采用自适应的方法改变权重，使解在空间上的分布更加均匀。Yuan 等[9]提出了基于距离更新策略的分解多目标进化算法(MOEA/D with a Distance-Based Updating Strategy，MOEA/D-DU)，采用改进的切比雪夫聚合函数，利用子问题的垂直距离作为指导，提高算法在高维目标中的应用效果。毕晓君等[10]提出了基于双种群的约束多目标优化算法，采用两个种群交流和改进的Harmonic 距离对算法进行改进，提高算法优化效果。

以上算法在逼近真实前沿面上具有较好的效果，但解的多样性不足且在空间上分布不够均匀。为了提高解的多样性，改善解在空间分布不均匀的问题，协调算法搜索过程的收敛性与多样性，本文提出了基于事件触发的自适应邻域多目标进化算法(MOEA/D-ET)。采用事件触发策略协调全局搜索与局部搜索，网格法进行全局搜索为局部搜索作指导，MOEA/D 算法进行局部搜索，并且针对解分布不均匀的问题，采用自适应邻域的方法进行改进。

1 MOEA/D-ET 算法

在搜索过程中，MOEA/D-ET 算法通过事件触发机制改变种群全局搜索与局部搜索功能，且产生的子代直接与父代比较、替换，不通过储备集的方式，可以在保证算法收敛性与多样性的同时减少计算消耗。

1.1 网格法寻优

面对多目标问题时[11]，通常使用笛卡尔坐标系(Cartesian Coordinate System)。网格法则是将笛卡尔坐标系下的粒子坐标进行网格化，并对每个网格中粒子间的相对距离进行定义。根据粒子间的相对距离以及非支配关系对网格内的粒子进行管理。

定义1[12]网格的上下边界：在m 个优化目标下，设 fmax(x) 为当前种群的最大适应度值， fmin(x) 为当前种群的最小适应度值，网格的上下边界为 ub与 lb。

式中，div 为网格划分系数。

根据所建立的网格坐标系，计算所有粒子在网格上的坐标。第i 个粒子的网格坐标计算如下：

其中 Gip为网格坐标。求解的坐标进行向下取整操作，则为第i 个粒子的坐标。

在网格坐标系下，粒子间的相对距离为两粒子横纵坐标相差之和，例如图1 中粒子A、B 的相对距离 DAB为4。

图 1 网格坐标系示意图Fig. 1 Schematic diagram of grid coordinate system

在网格坐标系上，根据各个粒子的非支配关系选择父代。首先选择非支配粒子，若两个不同粒子同为非支配解且在网格坐标系中有相同坐标，如图1 中D、E 所示，则计算它们的网格坐标点距离(GCPD)[12]，计算公式如下：

选择GCPD 较小的作为父代，可以免去计算当前个体对所有其他粒子的距离，大大减少计算量。

1.2 基于分解的多目标进化算法

MOEA/D 算法将多目标问题分解成一组若干子目标问题进行求解。考虑的目标为两目标和三目标问题时，采用切比雪夫(Tchebycheff)聚合函数进行求解，描述如下[6]：

其中： λ =(λ1,λ2,···,λk) 为子问题的权重； fi(x) 为第i 个优化目标函数值； z*为理想参考点。理想参考点的更新公式如下：

如此可将迭代过程中的历史极小值信息保存下来，使算法收敛速度更快，解的精度得以提高。

采用切比雪夫法求解多目标问题时，需要利用切比雪夫方法找出子问题 g (x|λ,z*) 的最大值。通过改变决策变量 x ，使最大的 g (x|λ,z*) 接近理想参考点，则其余子问题也相应接近理想参考点。

1.2.1 自适应邻域MOEA/D 在MOEA/D 算法中，子代粒子的产生受其父代邻域粒子的影响，邻域的大小对算法有很大的影响。若邻域设置为固定大小会导致解的分布不均匀，尤其是在凹凸性较大的Pareto 前沿面。如图2 所示，解在前沿面的中心区域分布较密集，边界附近相对稀疏。

图 2 固定邻域MOEA/D 非劣解分布图Fig. 2 Distribution of non-inferior solutions of MOEA/D with uniform neighborhood

若邻域设置过大，在更新过程中，父代与邻域内的其他个体比较次数太多，浪费计算资源。此外，过大的邻域虽然会提升算法的多样性，但同时会产生偏离Pareto 前沿的新解，导致种群退化。邻域设置较小，虽然有利于寻找局部最优解，逼近真实Pareto 前沿，但无法保证算法的多样性。基于以上分析，对邻域进行自适应调整，自适应调整方式如下：

1.2.2 MOEA/D 变异策略 MOEA/D 算法将多目标问题分解为多个子目标问题进行求解，Li 等[7]阐述了差分进化策略有利于提高MOEA/D 算法的性能。采取如下方式进行变异：

其中： xi为当前迭代粒子； xr2,xr3为当前种群随机选择的差分向量；F 为变异步长；为通过重组产生的新个体。

变异步长F 的大小对解的精度有很大影响。若F 设置较大，每次产生的新个体相对父代变异步长大，算法的多样性增加，局部搜索能力减弱；F 设置较小则相反。为了在搜索过程中不至于太快陷入局部最优，本文设置F 如下：

式中：k 为缩放系数。通过这种调节方式使搜索分为3 个阶段：第一阶段F 较大，保证了搜索初期种群的多样性；第二阶段F 不断减小，为过渡阶段，保证第三阶段不至于太早陷入局部最优；第三阶段F 设置较小，寻找最优解，提高搜索精度。变异策略中交叉概率CR 设为1，可提高种群多样性，并且使解具有旋转不变的特性。

1.3 选择策略

1.3.1 全局搜索选择策略

定义2Pareto 支配关系： x1， x2∈x ，若fi(x1)≤fi(x2),i=1,2,···,m 且存在 k ∈{1,2,···,m} ，使fk(x1)＜fk(x2) ，则称 x1支配 x2或 x2受 x1支配，此时的 x1为非支配解。

父代与子代混合，根据支配关系进行排序，将非支配解的粒子序号定为1，仅受1 个粒子支配的序号为2，依次类推。排列序号靠前的个体根据网格法进行选择，选出与种群大小相同的粒子数。若序号为1 的粒子数量小于初始种群大小，则从序号为2 的粒子中引入，以此类推。如此选出的种群在空间上分布较为均匀，同时也相对贴近真实Pareto 前沿面(PF)，可为接下来的局部搜索提供一个较好的指导作用。

1.3.2 局部搜索选择策略 通过全局搜索选择的粒子仍存在分布不均匀、不够贴近真实PF 的问题，因此还需要进行局部搜索。局部搜索采用MOEA/D 算法进行搜索，为了使搜索到的非劣解尽可能贴近真实PF，并且在空间上分布均匀，需要对父代的替换策略进行改进。MOEA/D 算法替换策略如下：

（1）利用自适应方式设置可替换父代的邻域大小。

（2）计算父代及其邻域的支配关系、拥挤距离。

（3）通过变异策略方式生成子代。

（4）子代替换父代邻域内的粒子，替换策略流程图如图3 所示。

图 3 替换策略图Fig. 3 Substitution strategy

图3 中，dis(p,o)为父代与邻域其他粒子的总距离，dis(c,o)为子代与邻域其他粒子的总距离，fitness为适应度函数。若邻域内替换的粒子数过少，种群更新缓慢，收敛速度慢；如果替换数量较多，收敛速度快，容易陷入局部最优，计算成本增加。

1.4 事件触发机制

若全局搜索次数过多，虽然解分布广泛，但无法有效地逼近真实PF。若搜索次数过少，就开始进行局部搜索，会陷入局部最优，并造成不必要的计算消耗。因此设计事件触发机制对全局搜索与局部搜索进行协调与平衡。

采用更新粒子比率（ r atio ）对全局搜索与局部搜索进行协调与平衡， r atio 计算公式如下：

其中： n um_c 为全局搜索中更新粒子的数量；N 为种群大小； n um 为局部搜索中更新粒子的数量。当更新粒子所占比率较大时，说明所产生的非劣解相距PF 较远，或解在空间上分布不均匀。当更新比率较小时，说明解已经逼近PF，此时需要对解的精度与分布性进行提高。

ratio 的大小对算法的分布性与收敛性有一定影响。采用三维测试函数DTLZ2，在10 维决策空间情况下，改变ratio 的大小对算法HV 与IGD 指标的影响结果如表1 所示。测试指标IGD 和HV 可以综合评判算法的收敛性与多样性，其中IGD 为反转世代距，HV 为非支配解集中所有非支配解与参考点围成的超立方体的体积。

表 1 ratio 对算法性能的影响Table 1 Influence of ratio on algorithm performance

从表1 可以看出，ratio 为0.55 时，算法的HV 值最大，解分布较广，但此时不够贴近真实PF。ratio 为0.25 时，IGD 值最小，解的分布最贴近真实PF，且此时HV 值为次优，说明算法在空间分布上较广。尝试选择ratio＞0.55 时触发全局搜索，ratio＜0.25 时触发局部搜索，通过实验得出此时的HV 为0.416 098 11，IGD 为0.051 974 819，算法效果反而下降。综合分析ratio 参数设置为0.25 较为合适。

1.5 MOEA/D-ET 算法流程

（1）初始化：初始化网格大小div，种群大小N，子代更新比率 r atio ，构造权重向量w，初始化种群，迭代次数。

（2）更 新： G ene={1,2,···,Generations} ，判 断ratio的大小以及目标数，根据事件触发机制选择触发全局搜索机制或局部搜索机制。

（3）输出：若算法满足停止条件，则停止并输出Pareto 前沿及相应的评价指标值，否则返回步骤（2）继续执行。

MOEA/D-ET 算法流程如图4 所示。

图 4 MOEA/D-ET 算法流程图Fig. 4 Flow chart of MOEA/D-ET algorithm

2 仿真实验与分析

为了验证本文算法在求解多目标优化问题上的性能，选取3 个系列的测试函数如表2 所示。其中ZDT、WFG 为二目标测试函数，DTLZ 为三目标测试函数，Dim 为决策变量空间维数。测试环境为Intel(R)Core(TM) i5-4200H CPU @ 2.80 GHZ。

表 2 ZDT、WFG、DTLZ 测试函数Table 2 Dimension of decision space in ZDT, WFG and DTLZ

选择4 个经典的多目标算法CMPSO[13]、MOEA/D[5]、NSGA-II[14]、PSEA-II[15]以及2 个最新的多目标算法LG_MOPSO[16]、NSGA-III[17]作为对比算法。其中CMPSO 为基于密集距离的多目标粒子群优化算法；MOEA/D 为基于分解的多目标优化算法；NSGA-II 为带精英策略的快速非支配排序遗传算法；PSEA-II 为利用遗传算法的机理和基于Pareto 包络选择的多目标优化算法；LG_MOPSO 为利用聚类选择指导粒子的多目标粒子群算法；NSGA-III 为一种基于参考点的非支配排序算法。

2.1 实验参数设定

在相同条件下对每个算法进行对比，每个算法进行20 次独立实验。算法的种群规模均设为100，迭代次数为400。在MOEA/D-ET 中，网格大小div在二目标中设置为45，在三目标中设置为20。局部搜索中，子代替换父代个数设置为10，其余参数设置如文中所述，其他算法的参数均参考相应文献。

2.2 实验结果分析

表3～表5 列出了各种算法在IGD 均值（IGDm）、IGD 方差(IGDstd)、HV 均值(HVm)上的实验结果，其中的黑体为最优结果。在IGD 均值上，本文算法在13 个测试函数中有10 个测试函数的均值都要优 于CMPSO、MOEA/D、NSGA-II、PSEA-II、LG_MOPSO、NSGA-III。在另外两个测试函数DTLZ1、DTLZ2 上，NSGA-III 效果最好，在本文算法的测试结果为次优。在DTLZ7 测试函数上LG_MOPSO 效果最好。IGD 方差上，在本文算法在13 个测试函数中有9个测试函数的方差都小于其他算法。在ZDT1、ZDT2、ZDT3、WFG4、DTLZ2、DTLZ3 测试函数上的方差远远 小 于 CMPSO、 MOEA/D、 NSGA-II、 PSEA-II、LG_MOPSO、NSGA-III。在其他测试问题上，虽然本文算法的IGD 方差结果并不是最好，但都达到了10-5，说明算法鲁棒性较好。HV 性能指标上，本文算法在13 个测试函数中有10 个测试函数的测试结果要 优 于 CMPSO、 MOEA/D、 NSGA-II、 PSEA-II、LG_MOPSO、NSGA-III。在ZDT3 问题上，LG_MOPSO测试结果最好，在WFG1、DTLZ1 问题上，NSGAIII 测试结果最好，本文算法表现为次优。这说明虽然通过自适应邻域方式对算法进行了改进，改善了算法在寻优过程中解出现中间区域密集、两端稀疏的问题，但面对边缘凹凸性较大问题时，相较于NSGA-III 算法，本文算法在搜索能力上仍需要改进。

表 3 7 种算法的IGD 均值比较结果Table 3 Comparison of the mean value of IGD index for seven algorithms

表 4 7 种算法的IGD 方差比较结果Table 4 Comparison of IGD index variance results for seven algorithms

表 5 7 种算法的HV 均值比较结果Table 5 Comparison of the mean value of HV index for seven algorithms

从表3～表5 可以看出，本文算法在大部分测试函数上都优于CMPSO、MOEA/D、NSGA-II、PSEAII、LG_MOPSO、NSGA-III，尤其在HV 指标上的测试结果较好。虽然对于测试函数ZDT3、WFG1、DTLZ1问题上为次优，但与最优指标仅仅相差10-4～10-2，说明本文算法在空间上分布范围广，多样性较好。在IGD 指标上表现出的效果大部分要优于其他算法，在DTLZ7 测试问题上，LG_MOPSO 算法在IGD 均值及方差测试上得到较好的结果，但在HV 均值上结果较差，说明该算法在该问题所找出的非劣解空间分布范围有限，而本文算法在IGD 均值及方差测试上为次优，但在HV 均值上结果最优。综合分析，在DTLZ7 问题上，本文算法也要优于LG_MOPSO。NSGA-III 算法在WFG1、DTLZ1 问题上测试效果较好，但本文算法均为次优且与最优值相差很小，可通过继续深入研究邻域关系提升算法的性能。以上分析表明，本文算法搜索到的非劣解空间分布广，多样性好，在保证解的精度与算法收敛性的同时减少了不必要的计算消耗。

为了更直观地展示本文算法所获得非支配解的质量和分布情况，绘制非支配解集的分布图与真实PF 对比，如图5、图6、图7 所示。图5 示出了ZDT系列部分测试函数图，图6 示出了WFG 系列部分测试图，图7 示出了DTLZ 系列部分测试函数图。从图中可以看出，本文算法与真实PF 吻合度较高，解的分布空间广泛，较好地平衡了求解多目标问题中的收敛性与多样性。

2.3 固定邻域与自适应邻域对比分析

设置固定邻域大小为10、50、100；自适应邻域设置如文中所述。两种邻域方式的种群大小设置为100，迭代次数为400。

在ZDT1 上的测试结果如表6 及图8 所示。从图8(a)、(b)、(c)可以看出，固定邻域情况下，将邻域大小设置较小、适中、较大，非劣解在空间上的分布依旧存在两端分布稀疏、中心区域分布集中的现象。从图8(d)可以看出，采用自适应邻域策略后，非劣解在空间上的分布更加均匀，改善了固定邻域下非劣解相对集中于中心区域的问题，使解在空间上分布更加均匀。

图 5 ZDT 系列部分测试函数图Fig. 5 Part of ZDT series test function diagrams

图 6 WFG 系列部分测试函数图Fig. 6 Part of WFG series test function diagrams

图 7 DTLZ 系列部分测试函数图Fig. 7 Part of DTLZ series test function diagrams

从表6 可以看出，自适应邻域在IGD 均值上的表现优于固定邻域，说明采用自适应邻域方式寻找的非劣解更加逼近真实PF。在HV 均值上自适应邻域的表现同样优于固定邻域，说明采用自适应邻域方式寻找到的非劣解空间分布广。

表 6 4 种邻域策略在ZDT1 问题上IGD、HV 指标对比Table 6 Comparison of IGD and HV indexes for 4 neighborhood strategies on ZDT1 problem

图 8 固定邻域与自适应邻域在ZDT1 问题测试对比Fig. 8 Comparison of fixed neighborhood and adaptive neighborhood in ZDT1 problem

3 结束语

本文提出了基于事件触发的自适应邻域多目标进化算法，采用更新粒子比率作为事件触发的条件对全局搜索与局部搜索进行调节。全局搜索主要采用网格法，旨在保证解的多样性的情况下在较短时间逼近真实PF。局部搜索采用自适应邻域MOEA/D方法提高解的精度，使解在空间分布更加均匀。全局搜索与局部搜索产生的非劣解通过事件触发机制相互交流，相互指引，大大提高了算法性能。通过对标准测试函数进行仿真实验，并与6 个多目标优化算法进行比较，结果表明本文算法所得出的非劣解在多样性与收敛性上有很大的提升。分析了固定邻域与自适应邻域对算法的影响，通过测试结果可以看出，采用自适应邻域方法在前沿面的逼近与非劣解的分布上都有着很好的效果。接下来会将此算法离散化，应用于焊接机器人[18]轨迹、能耗、变形等参数的多目标优化中。