基于分解的演化多目标优化算法综述.pdf

基于分解的演化多目标优化算法综述*高卫峰1,刘玲玲1,王振坤2,3,公茂果41(西安电子科技大学数学与统计学院,陕西西安710126)2(南方科技大学系统设计与智能制造学院,广东深圳518055)3(南方科技大学计算机科学与工程系,广东深圳518055)4(西安电子科技大学电子工程学院,陕西西安710071)通信作者:公茂果,E-mail:gongieee.org摘要:基于分解的演化多目标优化算法(MOEA/D)的基本思想是将一个多目标优化问题转化成一系列子问题(单目标或者多目标)来进行优化求解.自 2007 年提出以来,MOEA/D 受到了国内外学者的广泛关注,已经成为最具代表性的演化多目标优化算法之一.总结过去 13 年中关于 MOEA/D 的一些研究进展,具体内容包括:(1)关于MOEA/D 的算法改进;(2)MOEA/D 在超多目标优化问题及约束优化问题上的研究;(3)MOEA/D 在一些实际问题上的应用.然后,实验对比几个具有代表性的 MOEA/D 改进算法.最后,指出一些 MOEA/D 未来的研究方向.关键词:多目标优化;演化算法;分解;MOEA/D中图法分类号:TP18中文引用格式:高卫峰,刘玲玲,王振坤,公茂果.基于分解的演化多目标优化算法综述.软件学报,2023,34(10):47434771.http:/ on Multiobjective Optimization Evolutionary Algorithm Based on DecompositionGAOWei-Feng1,LIULing-Ling1,WANGZhen-Kun2,3,GONGMao-Guo41(SchoolofMathematicsandStatistics,XidianUniversity,Xian710126,China)2(SchoolofSystemDesignandIntelligentManufacturing,SouthernUniversityofScienceandTechnology,Shenzhen518055,China)3(DepartmentofComputerScienceandEngineering,SouthernUniversityofScienceandTechnology,Shenzhen518055,China)4(SchoolofElectronicEngineering,XidianUniversity,Xian710071,China)Abstract:Thebasicconceptofthemultiobjectiveoptimizationevolutionaryalgorithmbasedondecomposition(MOEA/D)istotransforma multiobjective optimization problem into a set of subproblems(single-objective or multiobjective)for optimization solutions.SinceMOEA/Dwasproposedin2007,ithasattractedextensiveattentionfromChineseandinternationalscholarsandbecomeoneofthemostrepresentative multiobjective optimization evolutionary algorithms.This study summarizes the research progress on MOEA/D in the pastthirteen years.The advances include algorithm improvements of MOEA/D,research of MOEA/D on many-objective optimization andconstraintoptimization,andapplicationofMOEA/Dinsomepracticalissues.Then,severalrepresentativeimprovedalgorithmsofMOEA/Darecomparedthroughexperiments.Finally,thestudypresentsseveralpotentialresearchtopicsofMOEA/Dinthefuture.Key words:multiobjectiveoptimization;evolutionaryalgorithm;decomposition;MOEA/D很多现实世界的工程优化问题都需要同时考虑多个相互冲突的目标,这些问题通常都被建模成多目标优化问题(multiobjectiveoptimizationproblem,MOP).一个连续 MOP 可以表述为:*基金项目:国家自然科学基金(61772391,62106186);陕西省自然科学基础研究计划(2022JQ-670,2020JM-178)收稿时间:2020-09-07;修改时间:2021-04-13,2021-07-10;采用时间:2021-07-28;jos 在线出版时间:2022-05-24CNKI 网络首发时间:2023-04-06软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(10):47434771doi:10.13328/ki.jos.006672http:/中国科学院软件研究所版权所有.Tel:[phone]minmize F(x)=(f1(x),.,fm(x)T Rms.t.x=(x1,x2,.,xn)T(1)RnRmF(x):Rmm Rn其中,为决策空间,为目标空间,是具有个目标函数值的目标向量.这里的是一个连通的闭集.通常一个 MOP 不存在一个唯一的最优解,取而代之的是一组折衷最优解.这组折衷最优解在决策空间被称为帕累托集合(Paretoset,PS),在目标空间称为帕累托前端(Paretofront,PF).下面给出几个相关的概念.x1x2x1x2x1 x2i=1,2,.,mfi(x1)fi(x2)j=1,2,.,mfj(x1)fj(x2)定义 1.支配关系.,为决策空间中的两个决策变量,支配(记为),当且仅当对于所有的都有,且存在一个使得.x x xx定义 2.帕累托最优解.如果不存在任何一个决策向量能够使得,则是一个帕累托最优解(Paretooptimalsolution).定义 3.帕累托集合.所有帕累托最优解组成的集合称为帕累托集合.定义 4.帕累托前端.所有帕累托最优解映射到目标空间中的目标向量组成的集合称为帕累托前端.如图 1 所示,PS 为多目标优化问题在决策空间的最优解集合,PF 为对应于目标空间中的最优解集合.决策空间目标空间帕累托最优解帕累托集合(PS)f2帕累托前端(PF)f1(a)PS(b)PF图1PS 和 PF示意图在没有先验信息的情况下,决策者(decisionmaker,DM)需要得到整个帕累托前端的近似解集合,后续再根据需求从中选出一个最适合的.演化多目标优化算法(multiobjectiveoptimizationevolutionaryalgorithms,MOEAs)一次运行就可以逼近整个 PF,并且 MOEAs 不受限于目标函数的不连续性、不可微性等性质14.这些优良的性质使得 MOEAs 受到了越来越多的关注.当前的 MOEAs 主要可大致分为以下 3 类.(1)基于支配关系的演化多目标优化算法基于支配关系的演化多目标优化算法利用支配关系将种群中的个体分为不同的层级.越靠近底部层级的个体,适应度值越高,在进行环境选择的时候被选中的机会就越大.同一层级中的个体互不支配,需要通过拥挤度距离或小生境等机制来选择个体.代表性的算法有 NSGA-II5、PESA-II6和 SEPA27等.基于支配关系的演化多目标优化算法在目标个数为 23 个时有比较好的性能.然而,随着目标个数的增加,种群中非支配解的数量急剧上升,最后种群中绝大多数的个体都是非支配解.这会导致基于层级的选择机制失效.同时,由于目标空间增大,为了确定种群中解的拥挤程度,需耗费很大的计算量.因此在高维情况下,基于支配关系的演化多目标优化算法面临很大的挑战.(2)基于性能指标的演化多目标优化算法基于性能指标的演化多目标优化算法通过性能指标来指导整个种群的演化优化.超体积(hypervolume,HV)指标由于具有良好的理论支撑,成为最常用的指标之一.然而,随着目标个数的增加,HV 指标的计算代价会呈指数级增长,这阻碍了 HV 在高维多目标优化问题上的应用.为了解决这一问题,学者们提出一些快速计算HV 的方法8,9,但截至目前,仍然没有一个特别有效的算法来显著地降低其在高维多目标优化问题上的计算复杂度.4744软件学报2023 年第 34 卷第 10 期(3)基于分解的演化多目标优化算法(MOEA/D)MOEA/D10的核心是通过分解方法将一个多目标优化问题分解成一系列子问题来进行求解,这些子问题可以是单目标优化问题也可以是多目标优化问题.然后利用子问题之间的邻域关系,以协作的方式同时优化所有的子问题,并得到整个 PF 的近似解集合.这类算法通常使用子问题的目标函数值作为适应度值,有效避免了随着目标个数的增加个体的选择压力失效的状况.此外,子问题目标函数值计算不会呈现指数级增长.MOEA/D 自提出以来,吸引了越来越多学者的关注,出现了许多 MOEA/D 的改进算法,MOEA/D 也被应用到许多问题上.根据谷歌学术中的统计,到目前为止 MOEA/D 被 SCI 他引已经高达 4643 次.图 2 是 MOEA/D 每年被引次数的统计情况,可以看到近年来 MOEA/D 被引次数一直在不断地增长.Trivedi 等人11在 2016 年对这些算法进行了总结.然而,从 2016 年至今,一些新颖的 MOEA/D 改进版本被提出,这些改进算法解决了不同领域的一些通用问题.Xu 等人12在 2020 年进一步对 MOEA/D 的改进以及近几年来新的发展进行了系统的研究.而国内还没有对这类算法进行总结的文章,鉴于 MOEA/D 近年来发展迅速以及在许多实际问题上的成功应用,本文我们对 MOEA/D 的发展做出详细讨论.与已有综述文章相比,本文的工作主要有以下 4 个贡献:(1)结合 MOEA/D 近年来的发展,对 MOEA/D 的基本框架进行总结;(2)对 MOEA/D 的演化过程进行划分,并给出明确的定义;(3)详细介绍 MOEA/D 在 6 项典型实际问题中的具体应用;(4)给出 6 个具有代表性的算法在多组测试问题上的对比实验.01002003004005006007008009002008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021引用次数年份1 000图2MOEA/D 被引次数本文第 1 节简要介绍 MOEA/D 的基本框架.第 2 节对 MOEA/D 的研究方向进行详细地讨论.第 3 节介绍关于 MOEA/D 的热点研究.第 4 节介绍 MOEA/D 在一些实际问题上的应用.第 5 节实验分析具有代表性 MOEA/D改进算法性能.第 6 节提出一些 MOEA/D 需进一步研究的方向和问题.1 MOEA/D 概述 1.1 MOEA/D 基本框架如图 3 所示,在 MOEA/D 的初始化阶段,需要预先生成一组均匀分布的方向/权重向量.这组方向/权重向量通常由单纯形网格设计方法13生成.利用这些方向向量/权重向量,MOEA/D 可以将一个多目标优化问题转换成一组单目标优化问题(如线性加权14)或者一组简单多目标优化问题(如空间划分15).u+1u+uu+在 MOEA/D 的迭代阶段,算法往往利用方向/权重向量之间的邻域关系以及它们与种群分布的关系来执行重组操作.这里重组操作可以是的,即稳态(steadystate)模式,也可以是或的,即代际(generational)模式.稳态演化模式是指产生一个新解后就更新整个种群.代际演化模式是指生成整个子代种群后再与父代种群竞争得到下一代种群.在新的子代产生以后,算法执行替换策略.这里的替换原则通常是基于种群个体的子问题目标函数值以及它们与方向/权重向量的距离来执行的.高卫峰等:基于分解的演化多目标优化算法综述4745算法不断迭代直至达到停机条件.达到停机条件之后,算法输出获得的非支配解,并将其作为这个多目标优化问题的近似解.开始输入初始化迭代更新输出结束停机准则是否基于子问题函数和方向/权重向量的替换策略基于方向/权重向量的重组操作图3MOEA/D 流程图 1.2 常用的分解方法在迭代更新过程中,使用不同的分解方法能够得到不同的子问题函数,在 MOEA/D 中,常用的分解方法有以下 3 种.(1)加权和(weightedsum,WS)方法=(1,.,m)Ti 0,mi=1i=1,i=1,.,m(f1(x),.,fm(x)T假设是一个权重向量,满足.为目标向量,则加权和方法定义的子问题如下:min gws(x|)=mi=1(ifi(x)s.t.x (2)使用不同的权重向量,可以得到一组不同的子问题.在问题具有凸 PF 的情况下,该方法具有良好的性能.然而,在非凸 PF 的情况下,并不是每个帕累托最优解都可以通过该方法得到.(2)切比雪夫(Tchebycheff,TCH)方法切比雪夫方法可以求解任意 PF 形状的 MOP,所以在许多 MOEA/D 改进算法中得到了广泛使用.切比雪夫方法构造的子问题如下:min gte(x|,z)=max1imi|fi(x)z|s.t.x (3)z=(z1,.,zm)Ti=1,.,m,zi 0d1d2d1d2d1d2其中,z 与公式(3)中相同,是一个预先设定的惩罚参数.为解映射到目标空间中的目标向量在权重向量上的投影距参考点的距离,为解映射到目标空间中的目标向量距权重向量的距离.因此具有更小的和值的解被认为是更好的解.和的平衡通过参数控制,对于不同的 MOP 设置合适的值能优化 PBI 方法性能.如图 4 所示,是对应 3 种分解方法分解机制示意图.4746软件学报2023 年第 34 卷第 10 期等高线PF搜索方向等高线搜索方向PF等高线搜索方向PFd2d1zzf1f2f1f1f2f2(a)加权和法(b)切比雪夫法(c)PBI 法图43 种分解方法示意图 2 研究方向MOEA/D 因其简单高效的特点吸引了许多学者对它进行研究.最初版本的 MOEA/D 考虑的是一组具有 23个目标的无约束优化问题和一组具有 24 个目标的背包问题.随着测试问题的多样性增加和复杂性提高,出现了许多基于 MOEA/D 的改进算法.这些算法主要针对问题的不同特性,对最初版本的 MOEA/D 进行改进.具体地,关于这方面的研究可总结为 5 个方向:(1)权重向量;(2)分解方法;(3)重组策略;(4)替换策略;(5)计算资源分配机制.下面将对这 5 个方向逐一展开介绍.2.1 权重向量MOEA/D 的一个关键特征是,种群的多样性由一组权重向量(或一组由权重向量决定的参考点/参考向量)引导.每个权重向量定义一个子问题,在理想情况下,每个子问题的最优解为一个帕累托最优解.对于不同的优化问题,经典的权重向量生成方法13存在以下问题.(1)生成权重向量的数量受目标函数个数的限制,无法产生任意指定数量的权重向量.(2)对于 PF 规则的多目标优化问题,均匀分布的权重向量能够引导 PF 近似解的一致性;当优化问题的 PF 不规则(如不连续的、退化的等)时,均匀分布的权重向量所引导的近似解在 PF 上不一定是一致分布的.(3)在高维目标空间中,生成的方向/权重向量大多集中在目标空间的边界,分布并不均匀.将目标个数达到 4个及以上的优化问题称为超多目标优化问题(many-objectiveoptimizationproblem,MaOP).针对上述问题,从以下两个方面对权重向量的研究进行总结:(1)生成均匀分布的权重向量策略;(2)自适应权重向量生成方法.2.1.1生成均匀分布的权重向量Tan 等人16提出了基于均匀设计的 MOEA/D(uniformdesignMOEA/D,UMOEA/D)算法,该算法通过构造均匀设计的混合实验(uniformdesignforexperimentswithmixtures,UDEM)来生成权重向量.在 UDEM 中,设置了一个参数 M 作为权重向量非一致性的度量,M 的值越小,权重向量的分布越均匀,在该方法下,生成的权重向量分布偏差最小,与单纯形网格设计方法相比,得到的权重向量在目标空间中分布更均匀.N1N2针对利用 MOEA/D 求解 MaOP 时,权重向量主要分布在权重空间的边界,Ma 等人17提出了一种权重向量初始化方法,该方法下可以生成任意数量的均匀分布权重向量,进而发展了 MOEA/D-UDM 算法.该算法结合UDEM16和单纯形网格设计方法,生成备选的权重向量.将权重向量主要产生在权重空间的内部,部分留在边界.然后,从备选权重向量中选择所需权重向量数量.Li 等人18提出生成双层权重向量,使用单纯形网格设计方法,分别在目标空间的边界和内部生成一组大小分别为和的权重向量.然后利用坐标变换,缩小内部权重向量的坐标.最终的权重向量集合为边界和内部所有的权重向量.2.1.2自适应权重向量生成方法Harada 等人19提出为难求解的子问题自适应增加权重向量的方法.首先通过 EP(外部存档,用于存储非支配高卫峰等:基于分解的演化多目标优化算法综述4747解)和已有的权重向量找到比较难搜索到的子问题,然后分配多个权重向量给这个子问题,将该子问题进一步细分为更多的子问题,使得更多的计算资源用于该子问题.Li 等人20提出通过识别浪费计算资源的权重向量来自适应的调整权重向量.具体地,当子问题对应的解在目标空间中的向量陷入局部最优或者处于 PF 的不连续区域时,继续优化该子问题会浪费计算资源,此时就需要对权重向量进行调整.Jiang 等人21提出一种基于帕累托自适应的权重向量生成方法.该算法根据问题的 PF 特征自动调整权重向量.它有两个重要的特点:(1)采用混合均匀设计方法22,生成任意数量的权重向量;(2)利用超体积指标4评估权重向量与 PF 的交点,调整权重向量使得超体积达到最大和交点沿 PF 的分布更均匀.进一步,Jiang 等人23提出了一种具有快速超体积存档的新型 MOEA/D 算法,用于自适应调整权重向量以适应 PF 形状的变化.该算法定义了一个存档,存储演化过程中产生的非支配解,并通过最大化存档集合的超体积更新存档,最后根据存档中的解周期性地调整权重向量.Gu 等人24提出了一种基于自组织映射(self-organizingmap,SOM)的权重向量设计方法.具体地,该算法利用 N(N 为种群大小)个当前个体的目标向量训练 SOM 网络中的神经元,然后根据神经元的权值更新权重向量,这样权重向量是根据种群中个体分布进行的调整,因而得到的解在不完整的 PF 上分布也是均匀的.该方法可以与大多数基于分解的 MOEAs 结合求解 MaOP.f1+f2+.+fm=1 mf1+f2+.+fm=1针对 PF 形状不连续,有尖峰或低尾的问题,Qi 等人25提出了一种采用自适应权重向量调整的改进算法(MOEA/Dwithadaptiveweightadjustment,MOEA/D-AWA).该算法提出一个两阶段策略调整权重向量的生成.在第 1 阶段,根据 TCH 方法生成的权重向量和最优解之间的几何关系,提出了一种权重向量初始化方法:WS 变换.WS 变换将一个子问题的权重向量进行映射,由 WS 变换的可逆性,可得到一组均匀分布在超平面(为目标函数数量)的权重向量.但当问题的 PF 与超平面不一致时,子问题权重向量的均匀性并不能保证 PF 上最优解的一致性.故在第 2 阶段,提出使用自适应权重向量调整策略(adaptiveweightadjustment,AWA),使得生成的权重向量与 PF 形状相适应.AWA 策略主要通过离解最近的 m 个邻居解来判断PF 上解的稀疏性.进一步,Qi 等人26使用狄洛尼三角网为子问题定义了一种新的邻域关系,其 PF 上解的稀疏性由解之间的欧式距离和解之间的分布共同决定.Li 等人27提出一种在演化过程中逐步调整权重向量的方法(approachtoadaptweights,AdaW).该方法根据种群在演化过程中产生的信息周期性地更新权重向量,为给定的问题寻找合适的权重向量.具体地,当种群迭代一定次数后,对权重向量进行更新,生成新的权重向量,删除解拥挤处的权重向量.此外,当算法接近演化过程的终点时,权重向量的变化可能会导致沿着指定的搜索方向(权重向量)演化不够充分.因此,该方法不会在最后的 10%代评估期间更新权重向量.2.1.3小结基于分解的算法中最终近似解集的分布和权重向量的分布是密不可分的.因此,如何根据问题特点生成均匀分布的权重向量是这一部分工作的研究目标.根据上面的讨论,可以得到以下结论.(1)MOEA/D-UDM17和双层权重向量生成方法18,不仅使得权重向量的生成摆脱了目标数量的限制,而且克服了在高维目标情况下边界解稀少的局限性.但它们在进化过程中权重向量是固定的,只能在问题 PF 规则的情况下有较好的性能.(2)如何在不预先知道问题的 PF 情况下确定一组合适的权值是一个开放问题,利用进化过程中的信息自适应的调整权重向量是主要的解决方法.其中,进化过程中的信息包括子问题的求解程度19、问题 PF 特征21,23、种群分布情况24,25等.(3)值得注意的是 AdaW 方法27,该方法通过细化权重自适应过程中的几个关键部分,即权重生成、权重添加、权重删除和权重更新频率,逐步为给定问题分配合适的权重.实验结果表明,AdaW 适用于 PF 形状非常复杂的问题,包括高度非线性,不连续的,退化的问题等.2.2 分解方法传统的 3 种分解方法(即 WS、TCH、PBI),在求解一些 MOP 时存在一定的缺陷,如解的改进区域过大,种群4748软件学报2023 年第 34 卷第 10 期多样性被破坏.近年来不少学者对分解方法进行了深入研究,这些研究主要可分为以下 3 个方面:(1)改进法;(2)混合法;(3)划分目标区域法.下面对这 3 类算法进行简要概述.2.2.1改进法分解方法的效果往往受所优化问题的影响.由于优化问题的复杂性和多样性,传统的分解方法在求解一些问题时存在一定的缺陷.改进法即根据演化搜索过程中的特点,对传统分解方法进行改进以更好地求解不同的优化问题.在 TCH、PBI 分解方法中,种群中的解在目标空间中朝着参考点 z 演化(通常 z 是在搜索过程中找到的理想点).当种群趋向于 PF 的某一区域时,搜索找到的理想点和真实的理想点之间的距离会变大,导致最后得到的种群无法逼近整个 PF.针对这一个问题,Sato28对传统的 PBI 分解方法进行扩展,提出了反向 PBI(invertedPBI,IPBI)分解方法.与传统的 PBI 通过最小化子问题函数值使得解向理想点 z 演化相反,IPBI 以当前种群中最差目标值构造的 w 为参考点,通过最大化子问题函数值演化解.在该方法中,随着权重向量的改变,最大子问题函数值对应的解也会改变,使得 IPBI 能够搜索目标空间中更广泛的区域.另外,与 PBI 类似,IPBI 也通过参数来平衡种群收敛性和多样性.PBI 方法的一个缺点是惩罚参数需要用户指定,没有唯一的适用于不同类型的问题.Yang 等人29根据对PBI 中惩罚参数进行分析,提出了两种新的惩罚策略来平衡种群收敛性和多样性.一种为自适应惩罚方案(adaptivepenaltyscheme,APS),APS 对所有子问题分配相同的惩罚值,但惩罚值随着搜索进行不断增加.因此,在搜索早期,惩罚值较小,有利于快速收敛;在搜索后期,惩罚值变大,更强调多样性.另一种为基于子问题的惩罚方案(subproblem-basedpenaltyscheme,SPS),SPS 根据不同子问题权重向量的位置指定不同惩罚值,对边界子问题采取严格惩罚,对中间子问题采取宽松惩罚,从而边界解得到保留,PF 上解的分布更广泛.对两种策略进行比较的实验结果表明,SPS 策略优于 APS.进一步将 SPS 融入两个 MOEA/D 改进算法(即 MOEA/D-ACD30和 MOEA/D-STM31)中,验证了 SPS 的有效性.ixixiiiimKm1mmWang 等人提出的 MOEA/D-ACD30中定义子问题 的当前解在目标空间中改进区域为所有优于的解向量构成的集合.分析表明,对于传统的分解方法(WS,TCH,PBI),解的改进区域对一些问题来说过大,导致一个新的解可以取代几个旧的解,使得多个不同子问题有相同的解,破坏了种群多样性.为了克服这个问题,提出了约束分解方法,即对子问题添加约束.该方法通过控制参数来调整子问题 的改进区域,其中的值在演化过程中自适应调整,达到平衡种群收敛性和多样性的作用.Cai 等人32提出一种基于网格的约束分解方法(constraineddecompositionwithgrids,CDG),该方法将目标空间划分成多个网格.在划分的网格系统中,通过约束分解定义了个子问题(为目标函数的数量,K 为划分的区间数),其中相同的解最多可以分配给个子问题,有效缩小了解的改进区域.另外,网格系统很容易反映解之间的邻域关系,使得解之间的匹配选择更有效.lpplpppMa 等人33提出基于方向向量范数约束的切比雪夫分解方法(-Tch).在该方法中每个子问题由方向向量的范数构成.分析表明,值的增加能够使得对各子问题改进区域的划分更均匀.进一步,通过分析-Tch 和其他切比雪夫分解方法之间的关系,定义了一个广义子问题,这个广义子问题可以在竞争中调整子问题的重要性,使得偏好的子问题获得更多更新机会,从而提高算法性能.=0聚合函数等高线的形状和位置,对算法搜索起着至关重要的作用34.Jiang 等人35提出两种等高线可控的聚合函数,分别为乘法标量化函数(multiplicativescalarizingfunction,MSF)和基于惩罚的标量化函数(penalty-basedscalarizingfunction,PSF).在 MSF 和 PSF 中,均设置了一个参数调整解的改进区域大小,其中更小的值有利于算法收敛,对应解的改进区域更大.所以在搜索的不同阶段调整值,能够有效改进算法性能.此外,当时,两种标量化函数都退化为 TCH.2.2.2混合法不同的分解方法具有不同的搜索特性.混合法就是将两种或者及以上的分解方法相结合,以充分利用不同分解方法的搜索特性来有效解决 MOP.如何选择不同的分解方法进行合理地融合是这类算法的关键.Ishibuchi 等人14提出同时使用 TCH 和 WS 分解方法计算个体适应度值.并提出两种方式对这两种分解方法高卫峰等:基于分解的演化多目标优化算法综述4749进行组合.一种是多网格策略,其中每个分解方法都有各自完整的权重向量网格系统.另一种是单网格策略,交替为网格中的权重向量分配这两种不同的分解方法.Zhend 等人36提出直接将 WS 和 TCH 进行加权组合得到一个新的加权混合方式(weightedmixture-style,WM)的分解方法,由于 WS 方法集中于全局搜索,而 TCH 方法关注个体搜索,从而 WM 方法能够充分利用搜索信息,有效提高算法性能.传统的 WS 和 TCH 方法对目标函数尺度比较敏感,结合文献 13 中基于方向的分解方法:正常边界交叉方法(normalboundaryintersection,NBI)和传统的 TCH 方法,Zhang 等人37提出了一种新的分解方法:NBI 方式的切比雪夫方法,用于处理目标函数尺度不同的 MOP.该方法根据目标空间中的极值点(即对应单个目标函数值最小的点),生成了一组在极值点连线上均匀分布的参考点.然后通过最小化解距参考点的最大距离使得解向参考点演化,进而逼近 PF.WS 方法适合问题 PF 为凸的情况,当问题 PF 非凸时需要选择其他的分解方法.Ishibuchi 等人38提出了一种自动选择 WS 和 TCH 方法策略.该方法的特点是,在每一代,若解的目标向量位于 PF 的非凸区域则使用 TCH 方法.否则,使用 WS 方法.融合该方法的 MOEA/D 算法在改进的非凸 PF 多目标背包问题上进行了实验,验证了该方法的有效性.MOEA/D 对问题 PF 的形状很敏感,主要是因为分解方法中参考点和子问题公式的设置对各种问题适应能力不强.Wu 等人39提出学习分解(learning-to-decomposition,LTD)范式,首次在基于分解的 MOEAs 中同时自适应地设置子问题公式中的参考点,等高线和搜索方向.具体地,LTD 范式由两个相互依赖的部分组成,即:学习模块和优化模块.学习模块使用优化模块中的非支配解作为训练集,通过高斯回归(GP)40学习估计 PF 的模型.然后通过学习模型中的信息,优化模块自适应地设置:(1)符合估计 PF 形状的有效参考点;(2)合适的等高线和搜索方向.优化模块可以是任何一种基于分解的 MOEAs.LpLpp=1p pLppLppppppWang 等人41分析了一类常用分解方法的性质:加权方法.在加权方法中,当时,即为 WS 方法;当时,即为 TCH 方法.分析表明,随着值的增加,的搜索性能下降,但在 PF 几何上的鲁棒性增加,即值可用于调节方法搜索性能及其 PF 几何上鲁棒性之间的平衡.进一步,如果知道 PF 几何结构,则可通过 PF 的曲率来确定一个合适的值,这验证了文献 42 中最优分解方法的存在性.基于这个观点,提出基于帕累托自适应分解方法的 MOEA/D 改进算法,该算法首先初始化一组值,然后在每一代,使用参考曲线族21近似 PF 来评估每个子问题的值,将不同的子问题与不同的值联系起来.在此基础上,Wang 等人43中提出了一种在线改进方法:PaS 逼近,用于选择最优的值.该方法并不需要对 PF 进行评估,更简单高效.2.2.3划分目标区域法MOEA/D 及其改进版本大多数通过子问题的多样性来实现种群的多样性.在更新过程中,新解是否替换旧解完全取决于它们的聚合函数值.在某些情况下,这种替代会错过一些搜索区域,导致种群多样性丢失.另外,这些算法取得好的性能需要选择适当的分解方法和权重向量,这对于很多问题来说并不容易.为了减缓这些缺陷,Liu 等人15提出一种将多目标优化问题分解为一组多目标优化子问题的方法.该方法推广了 MOEA/D 的框架,得到的算法为 MOEA/D-M2M.具体地,首先选择 K 个单位向量,将目标空间划分为 K 个子区域.然后将种群中的解分配到这 K 个不同的子区域.基于这种划分,将多目标优化问题转化为 K 个带约束的多目标优化子问题,其中目标函数不发生改变,K 个子区域定义了这 K 个子问题的约束空间.2.2.4小结分解方法决定了算法在演化过程中的搜索行为,根据上述研究,将现有工作总结如下.(1)分解方法主要由参考点28、控制参数29,33、等高线的位置和形状34,35等因素决定.通过调整这些因素,能够有效提高算法性能.(2)为了打破传统分解方法的限制,MOEA/D-ACD30、CDG32通过添加约束的方式提出了新的分解机制,能够更加灵活地调整旧解被新解替换的范围.这类方法的关键是制定合适的约束方案以适应不同的优化问题.(3)不同的分解方法具有不同的搜索特性,充分利用不同分解方法的优点,将分解方法的特点与演化过程相匹配,融合多种分解方法可有效提高算法求解问题的性能.(4)MOEA/D-M2M15提出的空间划分策略拓展了分解的定义,该方法利用权重向量将目标空间划分为一组子4750软件学报2023 年第 34 卷第 10 期区域,为研究分解方法提供了新的思路.2.3 重组策略关于重组策略的研究主要包括两部分:第 1 部分是父本的选择方式;第 2 部分是子代的产生方式.最初版本的 MOEA/D 根据目标空间中权重向量之间距离定义子问题邻域结构,每个解的匹配父本是在其邻域解中随机选择的.1GenGenLi 等人44提出允许父本以的概率从整个种群中选择来提高种群多样性,得到的算法为 MOEA/D-DE.在此基础上,Chiang 等人45进一步提出一种自适应策略来调整父本选择范围.在该策略中,首先根据子问题在连续代的改进情况,将子问题分为已解决的和未解决的,在演化过程中只选择未解决的子问题进行演化.同时,为了保证收敛性和多样性,保持了个拥挤度距离最大的解总是被选择.然后,在代后开始调整父本选择范围(为最大迭代次数),根据当前解之间的欧式距离确定邻域结构,而不是根据目标空间中权重向量之间距离,从而避免了在目标空间中接近的解可能在决策空间中相距很远的情况,实现了更有效的局部调整.基于邻域的选择可能会产生一些重复解,导致种群多样性下降.Jiang 等人46引入小生境技术来指导父本选择.该方法计算每个解在 T 个邻域解中小生境计数,如果一个解的小生境计数超过了给定阈值,意味着这个解与其邻域解很相似,此时选择邻域外的解作为父本,避免了产生重复解,增加了种群多样性.选择好父本后,需要对父本进行重组操作产生新解.MOEA/D 采用模拟二进制交叉(simulatedbinarycrossover,SBX)和多项式变异(polynomialmutation,PM)作为重组算子产生新解.由于不同算子搜索行为不同,对算法的影响也不同.已有不少算子被提出应用于 MOEA/D 框架中.Li 等人44提出使用差分算子(differentialevolution,DE)作为杂交算子来处理 PS 复杂的 MOP.Huang 等人47进一步研究了各种 DE 策略对 MOEA/D 性能影响,这些 DE 策略包括 DE/best/1、DE/rand/1、DE/best/2、DE/rand/2 和 DE/rand-best/1.实验结果表明各种 DE 策略关键不同在于父本的选择,但没有一种 DE 策略适合所有问题.Li 等人48提出基于适配率等级的多臂强盗(fitness-rate-rank-basedmultiarmedbandit,FRRMAB)策略来自适应地选择重组算子.为了减轻直接使用适应度改进导致算法鲁棒性弱的问题,FRRMAB 使用适应度改进率(fitnessimprovementrates,FIR)衡量算子在最近搜索过程中的表现,并用一个固定大小的滑动窗口来存储最近使用算子的 FIR 值,每个算子的奖励为当前滑动窗口中该算子所有 FIR 值总和.然后,引入一个衰退机制,为所有算子分配信用值来指导算子选择.将 FRRMAB 方法融入 MOEA/D 的一个改进算法(MOEA/D-DRA49)中,选择 4 种常用的交叉算子作为候选算子(即 DE/rand/1,DE/rand/2,DE/current-to-rand/1 和 DE/current-to-rand/2),测试了算法在UF50测试实例上的性能.实验结果表明,算法在该测试实例上显著提高了 MOEA/D-DE44、MOEA/D-DRA49和ENS-MOEA/D51的性能.NKe 等人52将 MOEA/D 与蚁群算法结合来构造解.提出的算法将一个多目标优化问题分解为个单目标优化子问题,每个单目标优化子问题由一只蚂蚁负责.在搜索过程中,每只蚂蚁利用当前解,邻域信息素矩阵和自身启发式信息矩阵组成的函数来构造一个新解,使得构造的解充分利用全局和局部信息,更可能为子问题的一个较好的解,加速算法收敛.Zhou 等人53提出利用高