余伟伟 谢承旺 闭应洲 夏学文 李雄 任柯燕 赵怀瑞 王少锋

科学研究与工程实践中不断涌现出要求同时优化4个或4个以上目标的问题,研究者一般将这类优化问题称为高维多目标优化问题(Many-objective optimization problem,MAOP),与优化目标数为2至3个的多目标优化问题(Multi-objective optimization problem,MOP)相比,MAOP问题的目标空间更大,搜索的难度也更大.其原因在于:随着目标空间维度的增加,种群中非被占优个体的数量将呈指数级增长,运用Pareto支配关系择优个体的方法面临失效的窘地,算法的搜索能力被极大地削弱;另外,由于Pareto支配关系在高维空间中效果变差,使得分布性保持机制成为算法选择个体的主导因素,但是由个体密度信息主导的选择机制不一定能有效地驱动近似Pareto前沿向真实Pareto前沿逼近,甚至可能对优化过程有负面影响[1−3].为解决高维多目标优化问题带来的挑战,各国学者从不同的视角提出了解决方法.陈振兴等[4]融合张角拥挤控制策略解决MAOP问题.巩敦卫等[5]基于目标分解的策略提出高维多目标并行优化方法.Drechsler等[6]提出了目标优胜关系的宽松Pareto支配关系:Favor关系,但该关系易受到目标函数量纲差别的影响.Di Pierro等[7]提出K-占优机制,但其只考虑了一个目标向量相对于另一个目标向量的改善目标数.Sato等[8]提出对解个体的支配区域进行缩放以改变解个体在目标空间中的位置,从而达到改变解个体支配关系的目的.需要指出,这种方法需要用户为每一个目标函数指定修正参数.Hernandez-diaz等[9]通过引入评判目标间优劣关系的阈值提出了ε-占优机制,但该策略依赖阈值的选取方法.Kang等[10]在总结新型占优机制优劣的基础上提出了E-占优,但E-占优方法在求解MAOP问题中的性能如何,文献中并未讨论.Zou等[11]提出了一种L-最优性,该占优方法不仅考虑了目标值得到改善的目标个数而且在所有目标具有同等重要性的情况下,改善的目标函数也考虑其中,但该方法随着目标个数的持续增加,仍面临着选择压力退化的问题.Farina等[12]将模糊理论引入到多目标优化算法中,但该策略亦存在产生循环支配之缺陷.毕晓君等[13]将模糊理论引入高维多目标进化算法模型,并结合模糊理论α-截集提出了新的环境选择策略.

粒子群优化(Particle swarm optimization,PSO)是Kennedy等[14]受到飞鸟集群活动的启发而提出的一种群体智能优化算法,其具有易于实现和收敛速度快等优势.近年来,PSO算法在多目标优化领域的研究取得了很大的进展,涌现出了不少的多目标粒子群算法(Multi-objective particle swarm optimization algorithm,MOPSO),但将其用于高维多目标优化问题求解的理论和方法还很少.

本文在已有多目标粒子群算法和宽松支配关系等研究的基础上,提出一种基于自适应模糊支配的高维多目标粒子群优化(Many-objective particle swarm optimization based on adaptive fuzzy dominance,MAPSOAF)算法,以求解复杂的MAOP问题.算法的创新点主要包括:1)以步长幅度自适应地调整模糊隶属度支配的阈值来改进模糊支配关系,在加强个体间支配能力的同时实现对种群选择压力的精细化调控,以改善算法的收敛性;2)增加扰动粒子改造基本PSO算法的速度更新公式,在克服种群早熟收敛的同时改善个体分布的均匀性;3)利用简化的Harmonic归一化距离评估个体的密度,在改善种群分布性的同时降低算法的计算代价.上述三种策略有机结合,形成了MAPSOAF算法的主要特点,这些策略在算法的不同阶段实施,以协同地提高MAPSOAF算法的总体性能.

论文的第1节简要介绍高维多目标优化问题相关概念.第2节描述构成MAPSOAF算法的若干重要组件和算法的流程,它是本文的重点章节.第3节是论文的仿真实验与结果分析.最后是本文的结论部分.

1 高维多目标优化问题相关概念

不失一般性,一个具有n个决策变量、m个目标函数的多目标优化问题,以最小化为例,可表述为式(1)的形式.

式中,x称为决策向量,X是n维的决策空间;y称为目标函数,Y是m维的目标空间;目标函数F定义了映射函数和需要同时优化的m个目标.当m≥4时,称式(1)为高维多目标优化问题.对于决策空间任意的两点x1,x2∈X,当x1的目标函数都不大于并且至少存在一个小于x2的目标函数时,称x1Pareto支配x2,记为x1≺x2.若x∗∈X不受种群中其他个体支配,则称x∗为Pareto非支配解,种群中所有非支配解组成的集合成为Pareto解集,其对应的目标函数构成的集合为Pareto前沿.

2 基于自适应模糊支配的高维多目标粒子群优化算法

2.1 自适应模糊支配关系

目前基于宽松支配关系的多目标/高维多目标进化算法大多采用变换目标函数值的方法,鉴于目标函数值是不可预测的,这就使得算法参数难以设定,而且目标函数值的改变,尤其在高维多目标优化中,会使寻优偏离真实的Pareto前沿.Farina等[12]将模糊理论引入高维多目标优化中,通过计算个体间目标优劣的数量来衡量个体的支配关系,提出(1−kF)支配策略.这种模糊支配关系的优点在于个体间的支配关系不再受到目标函数量纲和数值差异大小的影响,并使支配关系的复杂程度不受到目标数量的影响.但是该支配策略存在一个重要缺陷,即种群中的个体可能会陷入循环支配,从而使得种群中不存在非支配的解,导致算法各种择优策略无法实施,迫使算法停止.基于此,这里提出一种自适应的模糊支配关系,这种支配关系以步长幅度自适应地调整模糊隶属度支配阈值,在提高个体之间支配概率的同时,实现对高维多目标进化算法种群选择压力的精细化调控,以更好地促进算法收敛.

假设F(xi)和F(xj)分别表示种群中任两个个体xi和xj的目标向量,Bt(xi,xj)、Ws(xi,xj)和Eq(xi,xj)分别表示F(xi)中优于、劣于和等于F(xj)的目标个数,据此,xi和xj的模糊支配隶属度C(xi,xj)则可用式(2)表示,而模糊集CS可用式(3)表示.此外,为避免种群个体发生循环支配,借鉴文献[13]的做法,这里为种群中的个体xi赋予目标质量属性Q(xi),以刻画xi目标值的总体表现,其计算方法如式(4)所示.

其中,N表示种群的规模,zj为第j(j∈[1,m])个目标函数的最小值.当目标函数最小值已知时,zj取第j个目标函数真正的最小值;而当目标函数真正的最小值难以获得时,zj的值取当前种群对应的第j个目标函数的最小值.

由于目标质量属性Q是一个标量,满足传递性,即当Q(xi)

在高维多目标优化问题中,随着迭代次数的增加,种群中非支配解的数目急剧增多,导致种群的选择压力不断降低,严重地影响了算法的收敛性能,因而需要在进化过程中逐渐放宽个体的支配条件,减少群体中非支配解的数目,以增大种群的选择压力.基于此,这里尝试自适应地调整模糊隶属度的支配阈值来控制支配条件.

本文的自适应模糊支配关系可表述如下:假设xi和xj是种群中任两个个体,当Eq(xi,xj)6=m(m为MAOP问题的目标数),若利用式(5)计算得到的模糊隶属度C(xi,xj)满足大于等于阈值λ(λ∈(0.5,1])且λ随迭代次数的增加而递减时,则称xi自适应模糊支配xj.因此,当λ=1时,模糊支配关系成立需满足Ws(xi,xj)=0,且Bt(xi,xj)>0,即个体xi的所有目标都不劣于xj,并且至少存在一个目标函数要优于xj,此时模糊支配关系等价于Pareto支配关系;而当λ=0.5时,模糊支配关系成立需要满足Bt(xi,xj)>Ws(xi,xj),即xi优于xj的目标个数要大于其劣于xj的目标个数,此时模糊支配关系等价于†-支配;而当λ∈(0.5,1)时,此时的模糊支配关系实际上是一种宽松的Pareto支配关系.阈值λ越小则支配关系越宽松,这有利于减少种群中非支配解的数目,以增强群体的选择压力,促进算法较快收敛.因此,随着迭代次数t的增加,阈值λ应从1逐渐降至0.5附近,这里规定λ值依式(6)进行非线性递减.

其中,t为当前的进化代数,T为算法允许的最大迭代次数.

需要注意的是,现有宽松支配关系一般需要设置合理的参数以达到放宽支配条件,增大支配概率之目的,但这些支配关系的参数值与种群中非支配解的数量之间仅仅是一种定性关系,而非定量关系,因而在进化过程中难以精细化调整参数值.鉴于式(5)中分子(Bt(xi,xj))的最小值为1/m,分母(Bt(xi,xj)+Ws(xi,xj))的最大值为m,因此,模糊隶属度C(xi,xj)的最小值为1/m,阈值λ最小的有效调整步长可置为1/m.不妨令Bt(xi,xj)+Ws(xi,xj)=Ds,且设阈值λ的调整步长为1/Ds,则当λ值减少一个步长1/Ds时,意味着模糊支配关系降低了对较优目标个数所占比重的要求,使得群体中的个体更易形成支配关系,从而可提高支配的概率和种群的选择压力,促进算法收敛.一般地,在高维多目标进化算法的后期,Eq(xi,xj)的值会逐渐增大,种群中更容易产生非支配解,通过对相邻世代种群的模糊支配,隶属度阈值变化一个步长的大小,使得紧邻的下一代种群非支配解的数目可量化地减少.因此,这种以步长为幅度自适应地调整支配阈值的方法适于处理一些高维多目标优化问题.此外,由于黄金分割比例近年来被广泛应用于复杂系统优化中并取得了良好的效果,受此启发,这里将黄金分割点引入算法以执行种群规模的划分.

具体地,设种群规模为N,利用黄金分割点G将种群分割为规模不等的两个子群,则较小子群的规模为N−bG·Nc(b·c表示向下取整).当规模为N的种群中非支配解的数目不超过N−bG·Nc时,以1/Ds为步长降低支配阈值,以放宽支配条件;当种群中非支配解数目超过N−bG·Nc时,则增大支配阈值,以缩紧支配条件.算法1给出了按步长自适应调整支配阈值的流程.

算法1.按步长自适应调整支配阈值

输入.种群规模N,最大进化代数Tmax,黄金分割点G,初始支配阈值λ0.

输出.调整后的支配阈值.

以上自适应模糊支配关系将MAOP问题中个体之间m个目标的比较转化成模糊隶属度和目标质量属性两个值的比较,使得在目标个数很多时,也能容易地评价个体的优劣,并促进算法收敛.此过程没有加入任何的偏好信息,没有引入额外的参数,没有改变目标函数的数值,更没有对目标进行删减,而是利用了个体目标函数的完整信息.以步长为幅度调整支配阈值的大小,实现精细化调控支配的松紧程度,可满足不同情况下的需求,因而自适应模糊支配关系较适合MAOP问题的求解.

2.2 增加扰动项的粒子速度更新方式

在粒子群优化算法中,一个无质量的粒子i可视为MAOP问题的一个潜在解,粒子i在搜索空间内以一定的速度飞行,并根据其自身和集体的飞行经验来动态调整飞行速度.在基本PSO算法中粒子i的速度和位置的更新方程分别如式(7)和式(8)所示:

从式(7)可知,粒子i在第t代的移动速度的变化受其自身历史最优位置和全局最优位置Gbestt的共同影响,图1以2-目标优化问题为例,示意在多目标粒子群算法中当前粒子i速度的变化趋势.

图1 多目标粒子群算法中粒子的速度更新示意图Fig.1 Velocity updation of particles in MOPSO

在多目标粒子群算法的前期,粒子以较快的速度飞行,且具有较强的全局搜索能力,但在算法后期,若粒子自身的历史最优位置和全局最优位置Gbestt比较接近,则容易导致大量粒子的聚集,使得种群中粒子的多样性变差,可能会引起算法早熟收敛.基于此,这里考虑对多目标粒子群算法中粒子的速度公式进行改造,通过增加一扰动项来增强种群的多样性,从而有效避免算法陷入局部最优.其中的扰动粒子从外部档案(精英解集)中选择离当前粒子i的欧氏距离最近的个体.改造后的粒子速度更新如式(9)所示.

其中,在式(7)～(9)中,w为惯性权重,c1、c2和c3为学习系数,r1、r2和r3为区间[0,1]上服从均匀分布的随机数,和为第t次迭代时粒子i在n维搜索空间中的位置和速度,而分别表示第t代的粒子i在搜索空间第j维上的位置和速度.为第t次迭代时粒子i的自身最佳位置,为第t次迭代时整个种群的全局最佳位置,分别表示第t次迭代时粒子i在第j维上的自身最佳位置和全局最佳位置.表示第t次迭代时距离当前粒子i的欧氏距离最近的精英个体.在方程(9)的右边,第1部分为粒子当前速度乘以惯性权重进行加速,表示粒子对当前自身运动的信任,依据自身的速度进行惯性运动;第2部分为自我认知部分,表示粒子对自身历史的思考;第3部分为社会认知部分,表示粒子在群体中的信息共享和相互合作;第4部分为扰动部分,表示粒子受到档案精英粒子的影响.图2为增加一扰动项之后粒子i的速度更新示意图.

图2 增加扰动项之后算法中粒子的速度更新示意图Fig.2 Velocity updation of particles after adding turbulence item in MOSPO

从式(9)可知,增加扰动项后多目标粒子群算法中粒子i的速度变化将受其历史最优解、全局最优解Gbestt和离粒子i的欧氏距离最近的精英粒子的共同影响.而且从图2也可看出,加入扰动项之后的粒子可较好地逼近Pareto前沿.

从外部档案中选择距离当前粒子的欧氏距离最近的精英个体作为扰动粒子,原因有二:1)外部档案中的个体是算法迄今发现的较优秀的粒子,它们一般更加靠近Pareto前沿,新增精英个体引导粒子的移动将有利于粒子朝Pareto前沿靠近;2)选择离当前粒子的欧氏距离最近的精英个体作为扰动粒子相当于对搜索空间进行均匀划分,而且还能较好地引导粒子在多个子空间内进行深度搜索,种群中粒子的多样性和搜索能力都能得以改善,可有效防止算法早熟收敛.

2.3 全局最优位置的选取

在多目标粒子群算法中,全局最优位置在引导粒子群朝Pareto前沿逼近的过程中发挥着重要的作用.由于MAOP问题的结果是一个非劣解集,因此粒子i的全局最优位置有若干候选方案,而不像单目标优化问题那样可以直接确定.多目标粒子群算法中每个粒子的全局最优位置从外部档案(精英集)中产生,为防止档案中部分粒子被重复选取,致使粒子朝相同的方向进化而造成聚集,这里给档案集中的粒子赋予一定的选择概率,依概率选择粒子i的全局最优位置.如果外部档案中某个精英个体被选为粒子i的全局最优位置,则该精英个体再次被选中的概率将减少,其减少的概率将均匀分配给档案集中其他的个体.式(10)给出了档案个体被选为全局最优位置后其概率的变化方式.

其中,Pk表示外部档案集中的个体k被选中的概率,size(pop)和size(archive)分别表示粒子群和外部档案的规模,初始时外部档案中所有的非劣解的选择概率取值为1/size(archive).

2.4 改进的邻域拥挤密度估计方法

高维多目标优化问题的求解目标之一是要求获得的近似Pareto解集中的解个体不仅能均匀分布在Pareto前沿面上,而且要求它们的分布尽量广泛.实现该目标需要体现出种群个体在目标空间的分布情况,而个体之间的结构和联系主要表现为个体在目标空间中的疏密远近.这里采用一种简化的Harmonic归一化距离方法计算个体的拥挤密度,一方面可克服Harmonic平均距离存在的缺陷[15],另一方面可高效地维持群体的分布性.具体描述如下:

对于种群中的第i个个体,假设在目标空间中与个体i的距离由近及远的个体距离依次为di,1,di,2,···,di,N−1,则个体i的 Harmonic 平均距离如式(11)所示.

式(11)中的N为种群规模,即个体Harmonic平均距离的计算考虑了种群其他所有个体的距离,计算量很大.种群中相对距离较远的个体对所要计算邻域密度的个体的影响不应考虑在内,会引入不必要的偏差,造成资源浪费,这种情况在高维多目标优化问题中尤为明显.在不影响精度的情况下,这里提出减少参与计算平均距离的个体数量,即计算的数目由N−1降为k,并取k=blog2Nc,可得到式(12):

鉴于种群个体之间的距离d可能为任意的正数,为方便计算,对di,j(j=1,2,···,k)用归一化方法进行规范,可得相对距离为((di,k−dmin)/(dmax−dmin)),dmin和dmax分别为种群中个体之间的最小距离和最大距离,分布越好的个体其拥挤度应该越大.为了保持di和di,k的一致性,可得[1−(di,k−dmin)/(dmax−dmin)],而且一般距离越近的个体对该个体的拥挤度的影响越大,反之距离越远影响会越小.为了扩大这种差异,现对相对距离进行平方,即((di,k−dmin)/(dmax−dmin))2,由此可得个体拥挤距离的计算公式:

分析式(13)可以发现,该拥挤密度的计算方法只考虑了个体在局部邻域内相邻的blog2Nc个个体之间的距离,这种简化的Harmonic归一化距离方法相比于Harmonic平均距离减少了计算量.具体分析如下:设种群规模为N,搜索空间的维度为n,目标数为m.由于简化后的拥挤密度计算方法仅考虑了bNc个相邻的个体,其数量要少于Harmonic平均距离方法,所以时间复杂度要小于Harmonic平均距离的复杂度O(mnlog2n),减少量为O(N(N−1−blog2Nc)),其总复杂度为O(mnlog2n)−O(N(N−1−blog2Nc)).相比于循环拥挤排序方法,这里使用简化的Harmonic归一化距离无需反复计算个体的拥挤密度,仅需计算一次,大大降低了算法的计算复杂度.

种群中的个体由于具有共同的相邻个体而联系在一起,因此能在一定程度上反映出该个体在种群中的整体分布;同时,采取在该局部邻域内距离不同的个体对其拥挤度的影响不同的放大策略和归一化方法,保证了个体具有较好的邻域分布.由此可见,简化的拥挤密度估计方法能够从局部和全局两方面来维持种群的分布性.

2.5 高维多目标优化的环境选择策略

在高维多目标优化问题中,决策空间和目标空间的搜索范围极大扩张,自适应模糊支配关系虽然能在一定程度上增强选择压力,提高收敛性能,但如果环境选择策略设计不当,则可能导致种群陷入局部最优甚至收敛停滞.针对这一问题,本文利用文献[13]中改进的环境选择策略更新种群和外部档案,而且引入两个参数w1和w2分别表示支配度权重和拥挤距离权重,以协调收敛性和分布性.因此,粒子i的适应度计算方法变化如下:

其中,ri和di分别表示粒子i的支配度和拥挤距离,详情参见文献[13].

2.6 MAPSOAF算法流程

在前面第2.1～第2.5节的基础上,算法2给出了自适应模糊支配的高维多目标粒子群算法的流程.

算法2.MAPSOAF算法流程

输入.种群规模N,外部档案最大容量N0,黄金分割点G,初始支配阈值λ0,最大迭代次数Tmax,支配度权重w1,拥挤距离权重w2.

输出.外部档案集.

1.初始化规模为N的粒子群,对每个粒子,确定其初始位置和初始速度,粒子的自身历史最好位置Pbest设置为粒子本身,置外部档案集为空,令迭代器t=1.

2.WHILE(t≤Tmax)

3.计算粒子群中各粒子的目标向量,根据第2.1节的自适应模糊支配关系,将较好的N0个个体拷贝至外部档案中.

4.根据第2.2节和第2.3节为种群粒子选择扰动粒子和全局最优位置,并依式(9)更新粒子速度.

5.利用第2.4节中改进的拥挤密度方法为种群中的粒子计算拥挤距离.

6.利用第2.5节的方法更新粒子群和外部档案集.

7.t=t+1

8.END WHILE

9.输出外部档案集.

3 实验与结果分析

3.1 实验设置

3.1.1 对等比较算法

为检验MAPSOAF算法的性能,这里选取5个代表性的多目标进化算法作为对比算法,它们分别是:1)Deb等[16]提出的改进型非劣分类遗传算法NSGA-II;2)Nebro等[17]提出的基于档案的混合分散搜索算法AbYSS;3)Zitzler等[18]提出的改进型强度Pareto进化算法SPEA2;4)Nebro等[19]提出的限制速度的多目标粒子群算法SMPSO;以及5)Wang等[20]提出的自适应调整约束子问题MOEA/D算法,即MOEA/D-ACD算法.

3.1.2 高维多目标测试函数集

为检验本文算法的有效性,这里将MAPSOAF算法与上述5种对比算法一同在4,10,30目标的DTLZ测试函数集[21]上进行实验比较.选用可扩展为任意目标维数和自变量维数的通用测试函数DTLZ{1,2,4,5}.所有实验在硬件配置AMDA10-8700P CPU 1.8GHz主频8.0GB内存,Windows 7 64位操作系统的ThinkPad E565计算机上运行.1)当目标个数为4时,DTLZ函数集参数设置为:目标个数为4,决策空间的维度为10,算法的迭代次数为2000;2)当目标个数为10时,DTLZ函数集参数设置为:目标个数为10,决策空间的维度为20,算法迭代次数为5000;3)当目标个数为30时,DTLZ函数集参数设置为:目标个数为30,决策空间维度为50,算法的迭代次数为10000.

3.1.3 性能指标

反转世代距离(Inverted generational distance,IGD)[22]度量了真实的Pareto前沿到算法获得的近似Pareto前沿之间的距离.由于DTLZ函数集的真实Pareto解集是已知的,通过对真实Pareto解集进行多样性采样,计算这些采样点到近似Pareto解点之间的距离既反映了算法的收敛性又能反映出算法所获解集的多样性.一般而言,IGD指标值越小则说明近似Pareto前沿的收敛性和多样性越好.设P是多目标优化问题的真实Pareto解集,则IGD性能指标值可通过式(15)进行计算.

3.1.4 实验参数

5种对比算法的主要参数均采用对应参考文献中的建议值,如表1所示.

在表1中,N表示种群规模;Pc表示杂交概率;Pm表示变异概率;ηc=20和ηm=20分别是SBX和多项式变异的分布指数.对于AbYSS算法而言,NRefSet1和NRefSet2分别是RefSet1和RefSet2的规模.在MOEA/D-ACD算法中,T定义了在加权系数中邻域的规模,η为控制从T个邻域解中选择父本的概率,而nr表示父代个体被子代个体取代的最大数目.C1和C2是SMPSO算法中两个从区间[1.5,2.5]的范围内随机选取的控制参数.需要指出,对比算法的参数是经过适当调参后为解决本文实验中绝大多数的MAOP问题而设定的.为公平比较起见,本文MAPSOAF算法的主要参数参照其他对比算法进行设置,例如MAPSOAF种群规模为100,外部档案的最大容量为100,而计算个体适应度的支配度和拥挤距离的权重系数则参考文献[15]的研究,分别取w1=1.5,w1=0.5.

为减少随机误差对统计结果的影响,这里所有的实验各执行30次,每次使用不同的随机数种子,以统计IGD的均值和方差.此外,为了使获得的结论在统计上合理、可靠,这里采用Wilcoxon0s rank sum test来检验MAPSOAF算法和其他对比算法所获得的结果具有水平为α=0.5的显著性差异.

3.2 实验结果与分析

表2～表5分别统计了函数DTLZ{1,2,4,5}具有4、10和 30个目标时获得的IGD 均值(mean)和标准差(std),其中采用粗体显示不同算法在同一测试函数上获得的最好的IGD均值,表中的“+”,“−”和“≈”分别表示算法获得的结果要显著地优于、劣于和相似于MAPSOAF算法获得的水平为α=0.05的Wilcoxon秩和检验的结果.

从表2可以看出,MAPSOAF算法在10-目标和30-目标的DTLZ1问题上分别获得了最优的IGD均值,SMPSO算法在4-目标的DTLZ1问题上获得了最好的IGD均值,但本文的算法在该问题上获得的IGD值与SMPSO算法获得的IGD值具有相同的数量级(10−2),表明MAPSOAF算法在4-目标的DTLZ1问题上的表现仅稍逊于SMPSO 算法,而要优于AbYSS、SPEA2、NSGAII和MOEA/D-ACD算法.其次,通过统计各算法在DTLZ1(4,10,30)三个测试例上获得的IGD值的最终排序,表现最好的是MAPSOAF,然后依次是 SMPSO、AbYSS、SPEA2、NSGA-II和MOEA/D-ACD.从表2 的 “better/worst/similar”结果来看,各算法在DTLZ1(4,10,30)三个测试函数上只有SMPSO的结果是“1/1/1”,而其他4种对比算法的结果均是“0/3/0”,这表明MAPSOAF算法在这3个高维多目标的DTLZ1问题上较之其他对比算法具有显著的IGD性能优势.由于DTLZ1问题的Pareto前沿具有线性、多模态的特征,说明MAPSOAF算法在求解此类问题特征的MAOP问题时较其他算法更具优势.

表3给出了各算法在 4、10和 30目标的DTLZ2问题上获得的IGD值.MAPSOAF算法

分别在10-目标和30-目标的DTLZ2问题上获得了最好的IGD均值结果,而NSGA-II算法则在4-目标的DTLZ2问题上获得了最佳的IGD均值.需要指出的是,MAPSOAF算法在4-目标的DTLZ2问题上获得的IGD值仅略差于NSGAII算法 (二者处于相同的数量级 10−2),而要优于 SMPSO、AbYSS、SPEA2和 MOEA/D-ACD算法.此外,通过统计各算法在DTLZ2(4,10,30)三个测试例上获得的IGD值的最终排序,表现最好的是MAPSOAF,然后依次是NSGAII、SMPSO、AbYSS、SPEA2和MOEA/D-ACD.从表3的“better/worst/similar”来看,各算法在DTLZ2(4,10,30)三个测试函数上只有NSGA-II的结果是“1/1/1”,而其他4种对比算法的结果均是“0/3/0”,这表明本文算法在这3个高维多目标的DTLZ2问题上较其他对比算法而言具有显著的IGD性能优势.由于DTLZ2问题具有凹状Pareto前沿,表明MAPSOAF算法能够较好地求解具有这类问题特征的MAOP问题.

表1 5种对比算法的参数设置Table 1 Parameter settings of all the algorithms compared

表2 各算法在DTLZ1函数上获得IGD值的比较Table 2 Results of IGD for algorithms compared based on DTLZ1

表3 各算法在DTLZ2函数上获得IGD值的比较Table 3 Results of IGD for algorithms compared based on DTLZ2

从表4可知:MOEA/D-ACD算法在DTLZ4(4,10,30)三个高维目标测试问题上均获得了最优的IGD均值,而MAPSOAF算法在4-目标的DTLZ4问题上排名第2,在10-目标和30-目标的DTLZ4问题上均排名第3.通过统计各算法在DTLZ4(4,10,30)三个测试例上获得的IGD值的最终排名,表现最好的是MOEA/D-ACD,然后依次是NSGA-II、MAPSOAF、SMPSO、AbYSS和SPEA2.从表4的“better/worst/similar”来看,MOEA/D-ACD获得的结果是“3/0/0”,而NSGAII获得的结果是“0/2/1”,而其他两种对比算法的结果均是“0/3/0”.由此可见,在DTLZ4(4,10,30)三个测试函数上,MOEA/D-ACD算法的IGD性能是最佳的,而MAPSOAF算法的表现只能处于中游位置.DTLZ4问题的Pareto前沿为凹形、有偏的特点,说明本文算法在求解具有这类问题特征的MAOP问题时性能尚待提高.

从表5可以看出,MAPSOAF算法在DTLZ5(4,10,30)三个测试函数上均获得了最优的IGD均值.通过统计各算法在DTLZ5(4,10,30)三个测试例上获得的IGD值的最终排序,表现最好的是MAPSOAF,然后依次是SMPSO、NSGAII、SPEA2、AbYSS和MOEA/D-ACD.从表5最末一行的“better/worst/similar”来看,各算法在DTLZ1(4,10,30)三个测试函数上只有NSGA-II的结果是“0/2/1”以及SMPSO的结果是“0/3/1”,而其他两种对比算法的结果均是“0/3/0”.表5的结果表明MAPSOAF算法在DTLZ5(4,10,30)三个测试问题上较之其他几种对比算法具有显著的性能优势.DTLZ5问题具有凹形且退化的Pareto前沿,而MAPSOAF算法能在该MAOP问题上获得较好的结果.

综观表2～表5的实验结果,MAPSOAF算法相对其他5种代表性MOEA算法总体上具有显著的收敛性和多样性上的优势.究其原因,MAPSOAF算法通过定义步长幅度自适应地调整模糊隶属度支配的阈值,实现了对种群选择压力的精细化控制,能较好地改善算法的收敛性能;其次,MAPSOAF算法在粒子飞行速度的更新公式中新增了一扰动项,而且扰动粒子来源于外部档案中不重复的精英解,这种策略一方面能克服种群早熟收敛的缺点,另一方面也能改善群体分布的均匀性;此外,MAPSOAF算法采用简化的Harmonic归一化距离方法评估个体的拥挤密度,既改善了种群的分布性,同时减小了计算代价,提高了算法的效率.这三种策略相同协同,有效地提高了算法在求解高维多目标优化问题时的总体性能.

表4 各算法在DTLZ4函数上获得IGD值的比较Table 4 Results of IGD for algorithms compared based on DTLZ4

表5 各算法在DTLZ5函数上获得IGD值的比较Table 5 Results of IGD for algorithms compared based on DTLZ5

4 结论

高维多目标优化问题巨大的目标空间使得一些经典的多目标优化算法面临困境,迫切需要发展新型高维多目标优化算法应对挑战.论文提出一种基于自适应模糊支配的高维多目标粒子群算法MAPSOAF,该算法以步长为幅度,自适应地调整模糊隶属度支配阈值,实现对种群选择压力的精细化控制;其次算法在粒子速度更新公式中新增一扰动项,实现在克服种群早熟收敛的同时改善群体的分布性;最后,算法采用简化的Harmonic归一化距离评估个体的密度,实现改善群体分布性的同时降低算法的计算代价.MAPSOAF算法与其他5种代表性的MOEA算法在12个基准高维多目标测试函数上进行IGD性能实验,结果表明本文的算法具有较显著的收敛性和多样性的性能优势.

未来将利用MAPSOAF算法求解实践中如雷达优化问题、水资源优化问题、翼行设计问题和护士排班等典型高维多目标优化问题,以进一步测试和改善算法的性能;另外,考虑将一些新近提出的进化范例引入到高维多目标优化算法的框架中,以不断提高解决复杂MAOP问题的能力.