一种基于邻域改进的分解多目标进化算法

谭 玮，邱启仓，俞 维，王丽萍

1(浙江工业大学 管理学院，杭州 310023)2(之江实验室，杭州 310023)3(浙江工业大学 计算机科学与技术学院，杭州 310023)

1 引 言

解决多目标优化问题的主要目的是为了实现目标值的最小化.一般情况下，多目标优化问题可以描述为:

minf(x)=(f1(x),f2(x),…,fm(x))Tsubjecttox∈Ω⊆Rn

(1)

其中Ω是决策空间，f:Ω→Θ⊆Rm是m维的目标向量，x=(x1,x2,…,xn)T是决策空间中的一个n维决策向量.

多目标优化问题的求解算法有多目标进化算法[1]、多目标粒子群算法[2]、模拟退火算法等[3].多目标进化算法可以有效求解多目标优化问题.近年来，国内外学者提出了大量多目标进化算法，根据选择机制，主要可分为以下3类：1)基于传统Pareto支配关系，通过Pareto支配关系指导解集的选择[4]；2)基于指标函数，该类算法通过性能评价指标来引导算法的搜索方向[5]；3)基于分解，通过将多目标优化问题分解为若干单目标优化子问题从而进行求解[6].

自Zhang等人[7]2007年提出基于分解的多目标进化算法MOEA/D，基于分解的多目标进化算法逐渐成为众多学者处理多目标优化问题的首选算法框架，得到了广泛应用，并涌现出大量研究.在分解方法方面，Zheng等人[8]提出了一种结合加权和法和切比雪夫的分解方法，提高了算法的求解性能.在权重向量生成方面，Qi等人[9]通过分析切比雪夫分解方案下权向量与最优解之间的几何关系，提出了一种新的权向量初始化方法和自适应权向量调整策略.对权重进行周期性调整，使得子问题的权重自适应重新分布，从而获得更好的解的均匀性.在算法资源分配上，Zhang等人[10]根据算法中每个子问题的聚合函数值的提升率进行资源分配.Lin等人[11]针对以往资源分配策略仅注重收敛性，提出了一种给个体稀疏区域分配较多计算资源的多样性增强的资源分配策略IRA，使算法多样性得到兼顾.此外，在考虑种群更新方面，Li等人[12]在2014年提出了一个稳定匹配模型来协调MOEA/D中子问题与解之间的相互选择.在邻域选择机制方面，由于不同邻域对算法性能具有显著影响，Wang等人[13]提出一种考虑全局替换的MOEA/D-GR算法，允许新解在全局范围内替换邻域解，保证每个解都对应其最合适的子问题，然而该策略没有限制新解替换解的个数，当替换邻域较大时可能导致解集多样性的缺失.Yuan等人[14]提出基于距离更新的算法，利用解到子问题的垂直距离维持目标空间解集的均匀分布.

根据上述研究，可知在传统MOEA/D算法中，邻域大小对算法的性能会产生一定影响.对于不同目标函数，每个子问题的计算复杂度不尽相同.MOEA/D算法中采用固定邻域为子问题分配计算资源，资源分配不够合理.本文基于算法总体流程的研究，进一步分析了固定邻域存在的缺陷，进而提出了一种新的改进方法，针对选择邻域和替换邻域大小分别进行适应性调整，提出了改进算法MOEA/D-INS.旨在为不同子问题合理分配适当大小的邻域，平衡算法的收敛性和多样性.

2 背景知识

2.1 分解方法

在MOEA/D框架[15,16]中，已研究出许多分解方法.其中常用的分解方法有加权和法、切比雪夫法、基于惩罚边界交叉法.本文采用的是改进切比雪夫分解方法，其公式如下:

(2)

式中，Z*为理想点，λ=(λ1,λ2,…,λk)为当前子问题在目标空间中均匀分布的权重向量，若λi=0，则设置λi=10-6.

改进切比雪夫分解方法相比原始切比雪夫分解方法主要有以下两个优势[17]：1)均匀分布的权重向量能在目标空间中产生均匀分布的搜索方向；2)每个权重向量均对应位于Pareto前沿上的唯一解.这两个优势对算法多样性有所提升.

2.2 固定邻域缺陷

MOEA/D算法中，对不同的子问题设置固定邻域，而后通过交叉变异产生新解，用于替换邻域内旧解.在生成新解和替换解过程中都采用固定邻域，忽视了进化过程中随着解集的变化，生成新解会出现资源分配不均的问题，以及杂交过程生成的新解与子问题不协调的问题.因此采用固定的选择邻域和替换邻域不利于提升解集的多样性和收敛性，若不考虑解集在进化过程中迭代更新，容易导致MOEA/D算法陷入局部最优，影响解的多样性和收敛性.

图1 MOEA/D固定邻域分析示意图Fig.1 MOEA/D fixed neighborhood analysis diagram

以二维ZDT1测试函数为例进行说明，取固定邻域20，迭代300次后，其MOEA/D算法结果如图1所示，小圆圈表示Pareto最优解的位置.可以看出，固定邻域下的进化结果，一般在中间区域最优解较多，边缘区域最优解较稀少.若只采用固定邻域，则使边缘区域最优解多样性下降，导致Pareto最优解不能均匀分布在PF上，不利于提升算法性能.

3 改进算法MOEA/D-INS

3.1 算法改进策略描述

MOEA/D算法进化过程中用到两个不同的邻域：选择邻域和替换邻域[18].选择邻域用来进行父代解的选择，替换邻域用来确定哪些旧解可能会被新解替换.选择邻域的大小会影响解在繁殖操作时选择解的个数，选择邻域越大，可选择参与繁殖的解集范围越大，产生新解多样性就大，收敛性较弱.替换邻域的大小会影响解在替换操作时替换解的个数，替换邻域越大，可替换的解个数就越多，就会产生较多相同的解副本，多样性较弱.

本文在对邻域分析过程中考虑了解所在不同区域对进化的影响.通过表示子问题距离中心区域的偏离程度，具体公式如下：

(3)

λmid={λp|p=argminwi}

(4)

λbou={λp|p=argmaxwi}

(5)

其中子问题λ的最大值减去最小值来表示偏离程度wi，公式(4)中的λmid表示该权重向量位于种群中间位置，结合公式(3)此时wi取得最小值；公式(5)中的λbou表示该权重向量位于种群边界位置，此时wi取得最大值.采用此方法获取解所在区域信息与采用角度或距离公式计算方式相比，可减小算法计算量从而加快计算速度.

由图1可知采用固定邻域情况下，边界区域最优解稀疏，解多集中在中间区域.而在算法进化过程中，初期应注重种群的多样性，避免陷入局部最优.中后期，应注重算法的收敛性，使种群更好地收敛到Pareto前沿.

因此从均衡算法的多样性、收敛性及节约计算资源的角度考虑，针对选择邻域，边界区域子问题邻域应该增大，扩大子问题的搜索方向范围从而找到更多最优解，提高解集的多样性，中间区域反之适当减小以节约计算资源，同时结合算法的进化初期选择邻域Tm值应较大以维持种群的多样性，随着进化代数的增加，Tm逐渐减小以提升收敛速度，提出选择邻域公式(6)，其效果如图2(a)所示，在算法初期，选择邻域较大，提升解集多样性，随着进化代数的增加，中间区域邻域变小，边界区域邻域较大.针对替换邻域，中心区域应适当增大对应子问题的邻域，加快算法的收敛更快的找到最优解.边界区域反之减小以保留更多边界解，保证算法的多样性.同时结合算法的进化代数，初期替换邻域Tr值应较小以维持种群的多样性，随着进化代数的增加，Tr逐渐增大以提升收敛速度，提出替换邻域公式(7)，其效果如图2(a)所示，在算法初期，替换领域较大，提升算法收敛性，随着进化代数的增加，中间区域邻域较大，边界区域邻域较小.

(6)

(7)

T为一个最小邻域，防止邻域过小导致个体过少影响进化，Tmax表示设计的最大的邻域值，gen表示进化代数，Maxgen表示对应问题进化的最大代数，通过wi来表示子问题相对中心区域的偏离程度.

图2 邻域分配示意图Fig.2 Neighborhood allocation diagram

3.2 改进算法流程

输入:种群规模N；均匀分布的权重向量：W←{λ1,λ2,…,λN}；邻域大小T，变异概率Pm，交叉概率Pc；最大进化代数Maxgen

输出:PF:{F(x1),F(x2),…,F(xN)}

Step 1.初始化:

Step 1.1.计算任意两个权重向量之间的欧氏距离，为每个权重向量选出最近的T个权重向量作为其邻域.设B(i)={i1,i2,…,iT},i=1,2,…,N,其中λi1,λi2,…,λiT是距离λi最近的T个权重向量；

Step 1.2.初始化种群P←{x1,x2,…,xN};

Step 1.3.初始化理想点Z*←{Z1,Z2,…,ZK}T;

Step 2.更新:Fori=1toN，do

Step 2.1.根据公式(6)在每代更新之前计算每代的选择邻域Bm(i),根据公式(7)计算替换邻域Tr值，计算Br(i)；

Step 2.2.繁殖:从Bm(i)中随机选择两个邻居xk,xl,y←GenticOperators(xk,xl)进行交叉变异生成新解；

Step 2.3.修正：应用问题特定的修正或启发式的改进策略作用于y生成y′；

Step 2.4.更新Z*:若Zj

Step 2.5.更新解：采用更新函数UpdateNeighborINS(Z*,Br(i),y,P,W)

Step 3.停止判断：若满足停止条件，则输出PF，否则返回Step 2继续执行.

4 算法仿真实验及结果分析

为验证本文提出算法的性能，本文选取的测试函数为二维ZDT[19]测试函数ZDT1-ZDT4、ZDT6和三-五维DTLZ1-4[20]系列测试函数.将MOEA/D-INS与MOEA/D、MOEA/D-GR、MOEA/D-DRA和MOEA/D-DU这4种经典算法，进行仿真实验比较.仿真实验在IntelCorei5-7200UCPU-@2.50GHz的环境下进行.

4.1 参数设置

种群大小：二维测试问题设置为100，三维设置为105，四维设置为120，五维设置为126.交叉变异算子：变异概率Pm=1/n，其中n为测试函数的决策变量个数，交叉概率Pc=0.99，选择邻域的概率δ=0.9.终止条件：ZDT系列测试函数的最大迭代次数设置为300代，DTLZ2、DTLZ4最大进化代数为500，三维DTLZ1、DTLZ3测试函数的最大进化代数为1000，四维DTLZ1、DTLZ3测试函数的最大进化代数为2000，五维DTLZ1、DTLZ3测试函数的最大进化代数为3000.算法在每个测试函数上独立运行20次，以降低算法随机性对实验结果的影响.

4.2 性能评价指标

本文采用如下算法性能评价指标，进行算法性能对比：

IGD(Inverted Generational Distance，IGD)[21]是一种评价解集整体质量的指标.通过测量理想Pareto前沿面PFknown上的子集P*和近似Pareto前沿面PFture上的子集P的趋近程度，PFknown与PFture越接近，算法求得的IGD值就越小，解集整体性能也就越优.

超体积指标(hyper volume，HV)[22]是一种能够同时衡量算法收敛性和多样性的综合性指标，表示非支配解集覆盖的目标空间区域大小，算法求得的HV值越大，解集质量也就越高.

4.3 改进算法在ZDT系列测试函数性能对比分析

与传统使用固定邻域的MOEA/D算法在二维ZDT系列测试函数上进行对比实验，检验文中提出的MOEA/D-INS算法性能.表中黑色粗体数据表示对比实验结果中最优值.

表1为MOEA/D-INS与MOEA/D在IGD指标上的实验结果.由表1可知，在ZDT1、ZDT2、ZDT3、ZDT4这4个测试函数上，MOEA/D-INS的IGD指标优于MOEA/D，在ZDT6测试函数上，MOEA/D-INS所求解集的IGD指标略劣于MOEA/D.由此可以看出在以上测试函数中，文中提出的MOEA/D-INS对算法整体性能的提升具有明显的效果.

图3为两种算法在ZDT系列测试函数上的前沿效果图.采用黑色实线表示对应问题中真实Pareto前沿，方形和圆圈分别对应MOEA/D和MOEA/D-INS算法的Pareto最优解值.从图3改进前后算法的Pareto前沿对比图可看出，MOEA/D-INS算法求出的解集比MOEA/D求出的解集更贴近真实Pareto前沿面，且解集分布更均匀，在ZDT4测试问题上尤其明显，而MOEA/D的解集对应真实Pareto前沿面距离较远，原因在于进化的迭代次数不够，未能很好的收敛.

表1 改进前后算法在ZDT测试函数上指标对比Table 1 Comparison of indicators on the ZDT test function before and after improvement

图3 改进前后算法在ZDT测试函数上Pareto前沿对比图Fig.3 Comparison chart of Pareto front edge on ZDT test function before and after improvement

在ZDT1、ZDT2、ZDT3测试问题上MOEA/D-INS均优于MOEA/D，ZDT6测试问题上，MOEA/D-INS与MOEA/D算法性能总体相当.可以看出，改进算法MOEA/D-INS求解的整体质量比MOEA/D更高.

4.4 改进算法在DTLZ系列测试函数性能对比分析

为更深入验证本文提出算法的性能，对DTLZ1-4测试问题进行仿真测试，目标维度分别为三、四、五维，并使用IGD和HV指标对算法求出的解集进行分析.选取对比算法MOEA/D、MOEA/D-GR、MOEA/D-DRA和MOEA/-DU.

表2为各算法求得的IGD指标仿真实验结果，其中粗体表示对应算法所得解集整体质量优于其它四种算法.由表2可知，在实验结果中，在三维DTLZ1和五维DTLZ1中MOEA/D算法的均值虽然不是最优，但具有最好的稳定性，在四维DTLZ2中MOEA/D也具有最好的稳定性.在五维DTLZ2中MOEA/D-DU求解的性能最稳定，在五维DTLZ4中MOEA/D-DU算法IGD均值和MOEA/D-INS相同最优，原因可能在于MOEA/D-DU算法在进化更新过程中，考虑新解到权重向量的距离，避免过分强调聚合函数值而使得解偏离对应权重向量，这种基于距离的更新策略能较好的维持解集的多样性.从仿真实验结果整体上看MOEA/D-INS所得IGD指标的均值最小，表明算法整体性能最优.原因在于，相比MOEA/D、MOEA/D-GR、MOEA/D-DRA和MOEA/-DU算法，MOEA/D-INS算法为不同位置的子问题分配不同的选择邻域和替换邻域，并根据算法进化状态而动态调整邻域，从而使算法求得解集的整体质量更高.

图4是IGD指标走势图，图中三角形、星形、圆形、矩形、菱形分别对应MOEA/D-INS、MOEA/D、MOEA/D-DRA、MOEA/D-GR和MOEA/D-DU 5种算法.在DTLZ1和DTLZ3测试函数上MOEA/D-DRA算法在进化的前期曲线下降速度最快，因为该算法从每个子问题的聚合函数值相对提升率来分配计算资源，提升率高的子问题接下来也更容易被选择参与进化，因此在算法进化初期具有较好的收敛性.MOEA/D-INS算法对应的IGD值在算法进化前期也有着较快的收敛速度，在进化后期数值更是逐渐减小至小于其它4种对比算法.在DTLZ2和DTLZ4测试函数上，MOEA/D-INS算法对应的IGD数值在进化中始终小于其它4种对比算法，且随着进化代数的增加变化趋势稳定平缓，可见MOEA/D-INS针对这类测试函数具有较好的表现.结合表2,图4通过5种算法在DTLZ系列测试函数上的表现，发现MOEA/D-INS具有较好的整体性能.这主要是因为MOEA/D-INS将选择邻域和替换邻域分开考虑，分别提出不同的邻域规模，在确保算法进化收敛性的同时，也有助于提高算法的多样性，因此较好提升算法整体性能.对于具有复杂性质的测试问题，MOEA/D-INS仍具有较大提升空间.

表2 5种算法在三-五维DTLZ测试函数的IGD指标测试结果Table 2 IGD value test results of five algorithms in 3-5 D DTLZ test function

图4 5种算法在三-五维DTLZ测试函数的IGD指标走势图Fig.4 Change of IGD value on DTLZ3-5 D by five different algorithms

表3为各算法求得的HV指标均值和标准差.从实验结果发现，MOEA/D-DRA在五维DTLZ3测试函数上表现优于其它算法，MOEA/D-DU、MOEA/D-INS次之.MOEA/D-DU在三、四维DTLZ3及五维DTLZ4测试函数上的表现最优，MOEA/D-INS、MOEA/D-DRA次之.MOEA/D-GR在五维DTLZ1测试函数上性能最优.而在其余测试函数上，MOEA/D-INS算法求得指标HV值优于其它算法.已知，测试函数DTLZ1的最优解前沿是一个线性超平面，较难收敛到全局的复杂多模态问题.DTLZ2是一个相对简单的测试问题，通常用于研究算法在大量目标中性能提升的能力.DTLZ3是一个多峰问题，在解集收敛到Pareto前沿之前，易陷入局部最优.DTLZ4是简单连续的单模态测试函数，研究算法保持解集的分布性的能力.MOEA/D-INS在求解DTLZ2、DTLZ4测试函数上表现严格优于其它算法，因此在求解算法分布性上有着较强的优势，能够得到收敛性好，分布广的解集.

表3 5种算法在三-五维DTLZ测试函数的HV指标测试结果Table 3 HV indicator test results of five algorithms in 3-5D DTLZ test function

图5 5种算法在三-五维DTLZ1-4测试函数上的HV盒图Fig.5 HV box diagram of the five algorithms on the 3-5D DTLZ1-4 test function

由图5可以看出，在四维DTLZ1上，MOEA/D-GR虽然有最大的HV均值，但是从盒子的长度可以看出算法的稳定性较差，这可能是因为MOEA/D-GR注重收敛性，而DTLZ1是一个多峰的问题，在进化过程中新解替换邻域内多个旧解，使得算法陷入局部最优，性能下降.在四维DTLZ3，五维DTLZ3上，MOEA/D-DRA的HV均值最大，但是算法性能不够稳定.MOEA/D-INS相较于其它4种对比算法所对应的中位数位置即图中盒子中间的横线明显高很多，并且从图5中可以看出该算法的盒子长度是最短即算法对应的HV指标四分位距离是最小的，即该算法的HV值的最大值和最小值相比相差不多指标更为集中.表明了MOEA/D-INS相比其它4种对比算法求出的解集整体质量更高，并且有更好的稳定性即算法求解的性能更优.

综上结合表2、表3、图4、图5通过5种算法在DTLZ系列测试函数上的表现，证明MOEA/D-INS具有较好的整体性能.这主要是因为MOEA/D-INS将选择邻域和替换邻域分开考虑，提出不同的邻域规模，在确保算法进化过程中收敛性的同时，也有助于提高算法多样性，因此较好提升算法的整体性能.对于简单连续的测试问题，性能提升显著，对于一些具有复杂性质的测试问题，仍具有较大提升空间.

5 总 结

本文从MOEA/D选择邻域和替换邻域的角度分别进行研究，针对不同区域子问题分配不同邻域的策略，并将其融入到多目标进化算法中提出MOEA/D-INS算法.该算法首先对不同区域子问题分配不同的选择邻域和替换邻域，再随着进化代数的迭代，动态调整选择邻域和替换邻域的大小，合理分配计算资源，提高算法的求解有效性.算法仿真实验结果表明，MOEA/D-INS与其他算法相比能更加有效的利用算法资源，在保证解集收敛性的情况下，提高解集分布均匀性，求解出整体质量更高的解集，有效平衡了算法多样性与收敛性之间的不平衡.在后续研究中，将关注高维多目标优化问题和动态多目标优化问题，并将其应用在车辆路径规化、物流配送中心选址等实际应用中.