基于组合排序的约束多目标优化算法

收稿日期:2018-11-10摇摇摇摇摇摇修回日期:2019-03-13摇摇摇摇摇摇网络出版时间:2019-06-26基金项目:中国航空科技基金(20175552042)作者简介:李振宇(1993-),男,硕士,CCF会员(88897G),研究方向为智能计算与机器学习。网络出版地址:基于组合排序的约束多目标优化算法李振宇,胡摇涵(南京航空航天大学计算机科学与技术学院,江苏南京211100)摘摇要:约束的多目标优化问题(CMOPs)常见于工程应用和现实生活中,这类问题往往包括多个冲突的目标以及一组约束条件。与无约束的多目标优化问题相比,此类问题包含了一些复杂的特征,解决起来也要困难得多。对此,文中提出了一种基于组合排序的约束处理方法。该方法与一个最新提出的基于约束分解的算法框架相结合来解决约束的多目标优化问题。基于网格的约束分解的进化算法(CDG-MOEA)是新提出的解决多目标优化的算法,在解决无约束多目标优化问题上具有多样性和鲁棒性等良好的特性。基于此框架,提出了基于组合排序的约束处理方法,旨在算法的每次进化中,选择出种群中多样性比较好且可行的那些解。为了验证算法的有效性,将提出的约束多目标优化算法(CDG-CS)与现有算法在多个约束的优化问题上进行实验分析,结果表明,该算法在约束的多目标优化问题上有着不错的效果。关键词:约束优化;多目标优化算法;基于网格的约束分解;约束处理中图分类号:TP301.6摇摇摇摇摇摇文献标识码:A摇摇摇摇摇摇文章编号:1673-629X(2019)11-0032-05doi:10.3969/j.issn.1673-629X.2019.11.007ResearchonConstrainedMulti-objectiveOptimizationAlgorithmBasedonCombinedRankLIZhen-yu,HUHan(SchoolofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing211100,China)Abstract:Constrainedmulti-objectiveoptimizationproblems(CMOPS)arecommoninengineeringapplicationsandreallife,whichofteninvolvemultipleconflictingobjectivesaswellasanumberofconstraints.Comparedwithunconstrainedmany-objectiveoptimizationproblems,CMOPscontainsomecomplicatedfeaturesandaremuchmoredifficulttosolve.Therefore,weproposeaconstraint-handlingmechanismbasedonacombinedsorting,andcombinesitwithanewlyproposedoptimizationalgorithmframeworkbasedonconstraineddecompositiontosolveCMOPs.AconstraineddecompositionMOEAwithgrid(CDG-MOEA)isnewlyproposedtoperformgreatintermsofdiversityandrobustness.Basedonthisframework,weproposetheconstraint-handlingmechanismbasedoncombinedsorting,whichaimstoselectsolutionsthatarefeasibleandhavebetterdiversity.Toverifytheeffectivenessofthealgorithm,theproposedconstrainedmulti-objectiveoptimizationalgorithm(CDG-CS)willcomparewithotheralgorithmsonsomeconstrainedop鄄timizationproblems.TheexperimentdemonstratesthatCDG-CScansolveCMOPsverywell.Keywords:constrainedoptimization;multi-objectiveoptimization;constraineddecompositionwithgrids;constrainthandling0摇引摇言现实世界中很多优化问题都是约束的多目标优化问题(CMOPs),这些问题往往包括多个冲突的目标以及一组约束条件。在多目标优化问题中[1],在一个目标上的改善可能会导致另一个或者其余几个目标上性能的降低,此时算法关注的是收敛性与多样性的平衡。当引入一组约束条件后,算法求解出可行解又成了新的挑战,此时算法关注的是收敛性,多样性与可行性的平衡。约束的多目标进化算法[2](CMOEA)在求解此类问题时旨在找到一组满足约束条件的最优解集。文中提出一种约束的多目标进化算法(CDG-CS)。该算法采用基于网格的约束分解(CDG)框架[3]。在选择解的阶段,设计了一个组合排序的约束处理策略,该策略与约束分解的框架相结合,可以保持CDG拥有较好的多样性及对特殊PF形状具有鲁棒性的优点,又能够求解出一组符合约束条件的可行解集。第29卷摇第11期2019年11月摇摇摇摇摇摇摇摇摇摇计算机技术与发展COMPUTERTECHNOLOGYANDDEVELOPMENT摇摇摇摇摇摇摇摇摇摇Vol.29摇No.11Nov.摇20191摇概摇述1.1摇约束多目标优化问题的定义一个约束多目标优化问题(CMOP)定义如下:minimizeF(x)=(f1(x),…,fm(x))Tsubjecttogi(x)臆0,i=1,2,…,phj(x)=0,j=1,2,…,qx沂赘其中,赘是决策空间,x沂赘是决策变量。F:赘寅Rm是由m个实值目标函数组成的目标空间。此外,p是不等式约束的数量,q是等式约束的数量。通常情况下,等式约束都会转化为不等式约束的形式,如下:hj(x)-着臆0,j=1,2,…,q其中,着是一个允许的正容差值。基于以上陈述,约束违反值渍(x)可以根据约束条件定义如下:渍(x)=移imax(0,gi(x))+移jmax(0,hj(x)-着)1.2摇多目标优化中的一些定义定义1(可行解):解x为可行解当且仅当渍(x)臆0,否则解x为不可行解。定义2(Pareto支配):对于解u,v沂Rm,u支配v(u刍v)当且仅当对于所有的i沂{1,2,…,m}都有ujvj,且至少存在一个j沂{1,2,…,m}有ujvj。定义3(Pareto最优):解x*沂赘是Pareto最优解当且仅当F(x*)在整个目标集中是非支配的,F(x*)也被称为Pareto最优目标向量。定义4(idealpoint理想点):理想点z*可表示为向量z*={z*1,z*2,…,z*m}T,其中z*j=minx沂赘fj(x),j沂{1,2,…,m}。定义5(nadirpoint极值点):极值点znad可表示为向量znad=(znad1,znad2,…,znadm)T,其中znadj=maxx沂PSfj(x),j沂{1,2,…,m}。1.3摇约束优化的背景对于解决约束的单目标优化问题,近年来有很多约束处理技术[4-7](CHTs)。但是专门处理多目标优化问题的约束处理技术很少。根据一篇关于约束处理技术的调查[8],早期的约束处理技术可以分为这几种:惩罚函数法、特殊算子法、分离目标与约束法等。在基于数学规划的方法中,惩罚函数法[9-10]首先在进化计算中提出,具有以下公式:椎(x寅)=f(x寅)+g(x寅)其中,椎(x寅)是更新后的目标值;g(x寅)是惩罚函数值。通过增加一个附加的惩罚函数值,不可行解的目标值在计算之后会变差。然而,在算法迭代的不同阶段,难以给出惩罚函数合适的值。分离目标与约束法也较为常见,它是将约束转化为一个新的目标后使用多目标优化算法来解决约束的优化问题。近年来,约束的多目标优化[11]也受到了很多的关注。其中约束支配原则[12](CDP)是一个在约束的多目标优化中广泛使用的约束处理技术。在约束支配原则中,解xi要优于解xj当且仅当在以下条件满足时才成立:(1)解xi和解xj都是可行的且解xi支配解xj;(2)解xi与解xj都是不可行解,但是解xi比解xj拥有更小的约束违反值;(3)解xi是可行解而解xj是不可行解。随机数排序法[13](SR)引入了一个概率因子pf。当两个解都不可行时,此概率因子用来控制两个体是根据目标值还是约束违反值来比较。当pf=1时,随机数排序法就会等价于约束支配法。Jan和Khanum[9]将这两种约束处理技术与MOEA/D整合在一起,提出了两种约束的多目标进化算法(MOEA/D-CDP,MOEA/D-SR)。除此之外,在沂-约束处理方法中[14],将约束违反值小于一个动态变化的阈值沂的解视作可行解,沂的值由一个较大的值逐渐减小为0。相似地,这个方法可以应用到多目标的情形中。M.Asafuddoula和T.Ra[14]提出了一种新的约束多目标进化算法(C-MOEA/D)。该算法在MOEA/D框架下使用了一个自适应的约束违反阈值。1.4摇多目标进化算法多目标进化算法可以按照它们的选解方式分为不同的种类。常见的有基于支配的[12],基于指标的[15]以及基于分解的多目标进化算法[16]。MOEA/D是一个典型的基于分解的多目标进化算法,将一个多目标优化问题分解为一组单目标优化问题并以协作的方式来优化它们[16]。为了更好地保持种群的多样性,提出了一个基于网格的约束分解(CDG)框架[3]。在CDG中,一个目标函数被选择去优化当且仅当其他所有的目标通过设置上界和下界转换为约束。所有边界的等高线形成了一个网格系统,可以用于选择种群并保持更好的种群多样性。此外,CDG对于处理不同PF的形状也具有鲁棒性,例如在非常凸的PFs或者不同尺度的目标上。实验结果显示CDG在常规PFs同样表现良好。2摇算摇法2.1摇基于网格的约束分解(1)网格系统的设置。与基于一组均匀分布的权重向量的分解方法不同,CDG-MOEA中使用的约束分解方法基于一个网格系统。首先,每个目标在理想点和极值点之间被划分为K(K是一个参数)个间隔。此时,每个间隔的宽·33·摇第11期摇摇摇摇摇摇摇摇摇摇摇摇李振宇等:基于组合排序的约束多目标优化算法度可以表示为:dj=(znadj-z*j+2伊滓)/K因此,解x在第j个目标上的坐标gj(x)计算如下:gj(x)=腋(fj(x)-z*j+滓)/dj骎其中,腋·骎是向上取整函数;fj(x)是第j个目标函数;滓是一个很小的正数,用来确保gj大于0且小于等于K。定义6(网格间距):对于解u,v沂Rm,u,v之间的网格间距GD(u,v)可以定义为:GD(u,v)=maxj=1,2,…,m(gj(u)-gj(v))定义7(网格邻居):一个解x在网格间距T之内的网格邻居可以定义为:GN(x,T)={x*|GD(x,x*)臆T,x,x*沂Rm}(2)有关约束分解的定义。约束分解可以基于上述网格系统进行介绍,其中第l个目标上的第k个子问题定义为:minimizefl(x)subjecttogj(x)=kj,j=1,2,…,m,j屹1kj沂{1,2,…,K}x沂赘其中,K是决定网格数目的参数。每个目标向量上被均匀地划分为K个间隔,这样原始的多目标优化问题就被划分为m伊Km-1个子问题。因此,在第l个目标上第k个子问题中包含的一个解集Sl(k)可