第41卷 第2期吉林大学学报(信息科学版)Vol.41 No.22023年3月Journal of Jilin University (Information Science Edition)Mar.2023文章编号:1671⁃5896(2023)02⁃0321⁃08基于协同进化的多目标约束进化算法收稿日期:2022⁃03⁃17基金项目:吉林省科技厅基金资助项目(20200201276JC);吉林省教育厅基金资助项目(20200822KJ)作者简介:刘仁云(1968 ),女,辽宁大连人,长春师范大学教授,博士,主要从事最优化理论及应用研究,(Tel)86⁃131****0345(E⁃mail)liurenyun@㊂刘仁云1a ,张 旭1a ,姚亦飞1b ,于繁华2(1.长春师范大学a.数学学院;b.计算机科学与技术学院,长春130032;2.北华大学计算机科学与技术学院,吉林吉林132013)摘要:针对约束多目标优化算法(COA:Constrained Optimization Algorithms)中存在的难以有效兼顾收敛性和多样性的问题,提出了采用协同进化策略的多目标优化算法(CoMaC)㊂首先,将一个COA 转化为一个带动态约束处理的多目标进化算法㊂然后采用差分进化(DE:Differential Evolution)生成第1种群,并将其中的已知可行解选入第2种群,并与第1种群协同进化㊂第1种群通过保持原约束条件的全局搜索加快收敛㊂第2种群通过局部搜索进化,保持并获得更多可行解㊂最后采用标准约束多目标测试函数进行实验,以测试所提出算法的性能㊂实验结果表明,与使用惩罚函数处理约束问题(PF:Penalty Function)和使用动态处理约束边界方法(DCMaOP:Dynamic Constrained Many Objective optimization Problem)相比,所提算法在反向世代距离(IGD:Inverted Generational Distance)和超体积(HV:Hypervolume)两个指标上均取得了良好的结果,说明所提算法可以有效地兼顾收敛性和多样性㊂关键词:多目标进化算法;动态约束处理;协同进化;全局搜索中图分类号:TP391文献标志码:AMulti⁃Objective Constrained Evolutionary Algorithm Based on CoevolutionLIU Renyun 1a ,ZHANG Xu 1a ,YAO Yifei 1b ,YU Fanhua 2(1a.College of Mathematics;1b.College of Computer Science and Technology,Changchun Normal University,Changchun 130032,China;2.College of Computer Science and Technology,Beihua University,Jilin 132013,China)Abstract :A CoMaCOA(Co⁃evolution Multi⁃Objective Constrained)optimization algorithm is proposed to deal with the problem that it cannot be combined convergence and diversity effectively in multi⁃objective COA (Constrained Optimization Algorithms ).First,a COA is transformed into the multi⁃objective evolutionaryalgorithm with dynamic constraint processing.Then,DE (Differential Evolution)is used to generate the first population.The second population is generated by the known feasible solution in the first population and coevolved with the first.The first population accelerates convergence by global search that does not deal with constraints.The second population evolves through local search to maintain and obtain more feasible solutions.Finally,the standard constrained multi⁃objective test function is used for experiments in order to test the performance of the proposed algorithm.The experiment result shows that the proposed algorithm achieves goodresults on both IGD (Inverted Generational Distance)and HV (Hypervolume),comparing with PF (Penalty Function)method and dynamic boundary processing to constrain problem DCMaOP(Dynamic Constrained Many Objective optimization Problem).It shows that the algorithm is both effective in convergence and diversity.Key words :multi⁃objective evolutionary algorithm;dynamic constraint processing;co⁃evolution;global search223吉林大学学报(信息科学版)第41卷0 引 言在科学和工程应用领域中,存在着具有各种制约条件的多目标优化问题,这类问题称为约束多目标优化(CMOP:Constrained Multi⁃objective Optimization Problem)㊂此类问题曾经通过增加约束处理技术解决,使无约束多目标优化问题转变为CMOP[1⁃3]㊂但随着解决实际问题要求的不断提高,类似的方案渐渐不再适用㊂于是,一些新的约束多目标优化算法被提出㊂例如,基于惩罚函数处理优化问题的方法,即构造惩罚适应度函数fitness(x),用惩罚函数值p(x)与目标函数值f(x)的和衡量个体的违约程度[4]; Fan等[5]提出了一种动态处理约束边界的方案,在收敛速度方面效果良好㊂近年来,针对出现越来越多的大规模㊁高维㊁动态优化等问题,协同进化算法发挥了积极作用[6⁃8]㊂Li等[9]采用了该算法思想:一个种群面向收敛性存档,另一个种群面向多样性存档;前者对目标和约束同时优化,后者仅对目标优化;二者在协同进化环境中合作㊂Wang等[10]同样采用协同进化的算法思想,建立了针对每个目标的种群进化机制:先将CMOP分解为有约束的单目标问题,进一步构建收集子种群的非劣解集,再进行协同进化以获得更好的结果㊂上述针对约束多目标问题的算法取得了一定的效果,但也存在一些缺陷,主要表现为:无法在提高收敛速度的同时,摆脱高度依赖搜索阶段参数选择的限制[4⁃5];在收敛性和多样性等性能上,低维优化问题远不如高维CMOP的平衡性能好[9]㊂为此,张磊等[11]提出了一种不处理约束条件的全局搜索和局部搜索的协同进化策略,所采用的差分(DE:Differential Evolution)机制和约束处理技术可以兼顾多样性和收敛性㊂受此启发,笔者提出了一种动态约束边界与基于协同进化相融合的约束多目标优化算法,实验结果表明,该算法在获得良好收敛性能的同时又能很好地兼顾多样性㊂1 相关研究1.1 CMOP及其相关定义一般地,CMOP如下min F(x)=(f(x),f2(x), ,f n(x)),(1)s.t. g i(x)≤0, i=1,2, ,r,g j(x)=0, i=1,2, ,s,x=(x1,x2, ,x D)T∈Ω,其中Ω为决策空间,R n为目标空间;F:Ω→R n为目标函数(n是目标的数量),x为D维决策变量;有r个不等式约束g i(x)≤0,s个等式约束g j(x)=0㊂等式约束可转化为不等式约束,如下:g j(x)=hj(x)-δ≤0, j=1,2, ,s,(2)其中δ为等式约束容忍阈值,设为0.0001㊂G(x)为g i(x)和g j(x)的约束违背函数,如下:G(x)=∑i=1r max(0,g i(x))+∑j=1s max(0,hj)(x)-δ㊂(3) 定义1(可行解) 决策变量x=(x1,x2, ,x D)满足G(x)=0时,x为可行解,否则x为不可行解㊂一个可行解集S F包含一个约束优化问题的所有可行解S F={x x是可行解,x∈Ω}㊂定义2(Pareto支配) 在多目标优化中,两个解的比较主要依赖于Pareto支配关系㊂给定两个向量a=(a1,a2, ,a p),b=(b1,b2, ,b p),当且仅当每个指标a i≤b i,且至少有一个指标a j<b j时,称a Pareto优于(支配)b㊂对两个解x1和x2,如果目标向量f(x1)Pareto优于(支配)f(x2),则x1Pareto优于(支配)x2(记为x1≺x2)[12]㊂定义3(Pareto最优解) 如果没有Pareto优于(支配)x*的其他解决方案,则x*就是Pareto最优(非支配)解㊂通常,非支配的概念为多目标优化问题提供一组解决方案,这个集合称为Pareto集(非支配集)㊂相应的目标向量集称为Pareto 前沿(PF)[13]㊂1.2 将CMOP 转换为CMaOP近年来,在许多研究中,多目标优化技术的优势被用于处理约束㊂通常约束条件是作为一个整体加在一起,将约束优化问题(COA:Constrained Optimization Algorithms)转化为双目标问题㊂由于这些约束具有不同的特性,例如,一些约束很容易满足,而另一些则不容易满足㊂但作为一个约束总和的缺陷是容易丢失信息㊂因此,笔者采取的方法是将每个约束转化为一个目标,由CMOP 转换的约束多目标优化(CMaOP:Constrained Many Objective optimization Problem)说明如下:min y =(f (x ),φ1(x ),φ2(x ), ,φm (x )),s.t. g =g (x )=(g 1(x ),g 2(x ), ,g m (x ))≤0,(4)其中φi (x )(i =1,2, ,m )为g i (x )的约束违背函数,定义为 φi (x )=max{g i (x ),0}, i =1,2, ,m ㊂(5)1.3 CMaOP 转换为DCMaOP求解CMaOPs 的多目标进化算法(MaOEAs:Many Objective Evolutionary Algorithms)将面临与求解COA 相同的约束处理困难㊂MOEAs 能很好地解决无约束的MOP (Multi⁃objective OptimizationProblem)[14⁃16]㊂如果要使约束边界非常宽松,就像没有约束一样,一个MaOEA 只要种群总是可行的,即可直接应用,并具有高效的搜索能力㊂笔者采用Zeng 等[17]提出的动态约束处理方法解决上述问题㊂该方法改变约束边界,使大多数个体可行㊂首先,将方程(4)中的CMaOP 的原边界扩大到e (0),使其足够大,保证初始种群P (0)中的所有个体都可行,则有e (0)=(e (0)1,e (0)2, ,e (0)m ),e (0)i=max x ∈p (0){g i (x )}, i =1,2, ,m ㊂(6) 随着种群的演化,变宽的边界e(0)逐渐减小㊂这种减少是足够小的,所以总是有一个几乎可行的种群㊂最终,边界能收缩到原始边界0㊂这个过程构造一个动态处理约束边界的多目标优化方法DCMaOP (Dynamic Constrained ManyObjective optimization Problem),它是一系列CMaOPs 问题,其公式如下:min y =(f (x ),φ1(x ),φ2(x ), ,φm (x )),s.t. g (x )≤e (0){,(7)min y =(f (x ),φ1(x ),φ2(x ), ,φm (x )),s.t. g (x )≤e (1){,(8) min y =(f (x ),φ1(x ),φ2(x ), ,φm (x )),s.t. g (x )≤e(S )=0{,(9)其中e (0)≥e (1)≥ ≥e (S )=0,e (τ)(τ=0,1,2, ,S )为弹性约束边界,τ为环境状态㊂各环境状态的边界e (τ)为e (τ)=(e (τ)1,e (τ)2, ,e (τ)m ),(10)e (τ)i=A i e -(τ/B i )2-ε, i =1,2, ,m ,其中ε为控制弹性边界收敛速度的正参数,它无限接近于零,A i 和B i 为常数,可用e τ(τ=0,1,2, ,S )计算㊂在初始状态τ=0时,弹性边界方程为e (0)i=max x ∈p (0){g i (x )}=A i -ε, i =1,2, ,m ㊂(11)当最终状态τ=S 时,弹性边界由e (S )i=0=A i e -(S /B i )2-ε, i =1,2, ,m (12)恢复为0㊂根据式(11)和式(12),A i 和B i 可由323第2期刘仁云,等:基于协同进化的多目标约束进化算法A i =max x ∈p (0){g i (x )}+ε, i =1,2, ,m ,(13)B i =Sln max x ∈p (0){g i (x )}+εæèçöø÷ε, i =1,2, ,m(14)计算㊂2 算法描述下面给出这种协同进化策略CoMaC 的主要框架(算法1)㊂首先,第1种群由算法随机生成的初始种群构成,然后将其中的可行解选出构成第2种群;其次,采用对第1种群与第2种群之间的协同进化策略进行迭代,进化到满足条件为止㊂这时,约束边界将随着演化过程而缩小,直到整个种群是e⁃可行的㊂如果种群中的某些个体在某一状态下是e⁃不可行的,算法将无限迭代进化以达到e⁃可行种群,MaxG 为最大迭代数㊂2.1 第1种群与第2种群的协同进化策略图1描述了两种群协同进化策略㊂首先,由随机生成的第1种群负责全局搜索,暂不考虑约束处理策略(CHM:Constraint Handling Method),而采用无CHM 的多目标进化算法实现全局搜索;由于不考虑约束是否满足,在全局搜索时比基于CHM 的约束搜索方法的种群收敛速度更快;同时,对第2种群采取局部搜索机制,只选择收敛性好的可行解保留在第2种群中㊂这种CHM 有助于算法快速地寻找更多的可行解,促进了可行解的收敛;其次,利用局部搜索和全局搜索生成的可行个体对第2种群进行更新;最后,通过局部搜索和全局搜索生成的个体进行环境选择,生成新的第1种群成员㊂当第2种群中的个体数量大于种群规模N p 时,需要维持第2种群㊂算法2总结了第2种群的更新和维护机制㊂首先,保留第2种群中的非优势个体,将剩余个体从中移除㊂如果种群规模仍然大于N p ,则移除拥挤距离较低的个体,以获得更好的分布㊂在算法初始运行时,第2种群的可行解的后代会加速第1种群的收敛㊂随着算法的运行,第1种群的可行后代也会提高第2种群的收敛速度㊂因此,第1种群的全局搜索和第2种群的局部搜索是互补的㊂显然,这种协同进化策略解决了传统CMOEAs 收敛不足的问题㊂算法1 CoMac㊂输入:Generationnumber T max ,population size N p ,environment states S ,the current feasible solutions㊂输出:The second population A ㊂图1 第1种群和第2种群共同进化示意图Fig.1 Co⁃evolution schematic diagram of the first and the second populations1)/*Initialization */2)Add the current feasible solutions to A ;3)The initial main population pop 0=initialize();4)Add the feasible solutions of pop0to A ;G =1;5)Set e =e (0),τ=0,g =0㊂6)/*Main loop*/7)while (G <T max and τ<S )8)If all individuals in the current population are e⁃feasible, then change elastic constraint boundary e =e (τ+1),τ=τ+1㊂9)Childpop G =Evolve(pop G -1)by SBX and polynomial mutation;10)Add the feasible solutions of childpop G to A ;11)Offspring A =Evolve (A )by DE and polynomial mutation;12)Add the feasible solutions of Offspring A to A ;13)Update the second population A according to algorithm 2;14)Get the pop G from pop G -1,childpop G and Offspring A by environmental selection;15)G =G +1;g =g +1;423吉林大学学报(信息科学版)第41卷16)end算法2 Update mechanism of the second population㊂输入:The second population A ㊂输出:The updated second population A ㊂1)if the population size of A is more than N p ,then 2)Delete the dominated solutions of A ;3)if the population size of A is large to N p ,then4)CrowdDis =CrowdingDistance(A );5)Sort CrowdDis in descending order and select the top N p individuals as A ;6)end 7)end2.2 算法框架笔者提出的CoMac 将第1种群和第2种群之间的协同进化策略整合到DE 框架中㊂选择DE 作为多目标优化框架的原因是其鲁棒性高,易于实现㊂CoMac 方法示意图见图1㊂算法1中,步骤1)~5)为启动CoMac㊂在初始化时,加入已知的稳态可行解,即初始种群pop0随机生成,然后求出第1群每个独立解的目标值,根据目标函数对种群进行评价㊂通过方程(2)评估一个解的整体约束违背情况,识别出pop0的可行解并加入到第2种群A 中;步骤7)~步骤16)是CoMac 的主循环㊂步骤8),约束边界将随着演化过程而缩小,但它不会改变,直到整个pop 是e⁃可行的㊂如果种群中的某些个体在某一状态下是e⁃不可行的,算法将无限迭代进化以达到e⁃可行种群㊂步骤9),使用SBX 和多项式变异算子产生子个体,与DE 相同㊂生成的N p 个子个体构成了子群体Childpop G ㊂将Childpop G 的可行解保存到A 中㊂步骤11),使用DE 算子和多项式变异算子对第2种群进行局部搜索,并将结果保存为Offspring A ㊂将Offspring A 的可行解保存到A 中㊂步骤13),根据算法1保持第2种群㊂步骤14),individ⁃与DE 的环境选择方法相同,从第2种群的主种群㊁子种群和后代的结合中,逐步筛选出N p 个新的主种群㊂最终CoMac 的输出是最后的第2种群㊂笔者提出了一种基于协同进化的约束多目标进化算法CoMac,用于解决COAs,使已知的可行解在第2种群中保持,并与其一起进化第1种群㊂第1种群是通过不处理约束条件的全局搜索加快收敛速度,第2种群通过局部搜索进行进化,以获得更多可行的解决方案,保持了可行解的多样性㊂3 实验与分析为验证笔者算法的性能,选择Belegundu㊁Binh(2)等测试问题集进行测试及分析㊂选择近几年新提出的惩罚函数(PF:Penalty Function)处理约束问题和DCMaOP 方案作为对比㊂3.1 评价指标反转世代距离(IGD:Inverted Generational Distance)是既可评价算法收敛性又可评价多样性的指标;超体积指标(HV:Hypervolume)可同时评价解集的收敛性与分布性㊂本实验中IGD 为Pareto 前沿近似解集与真实前沿之间最小距离的平均值;HV 为目标空间区域中由非支配解集覆盖的部分㊂设P *为均匀采样在真实Pareto 前沿上的解集,Pareto 前沿近似解集为P R ,如下:I IGD (P R ,P *)=1P *∑x ∈P *dist(x ,P R ),(15)H HV (S )=vol(∪x ∈P R[f 1(x ),r *1]×[f 2(x ),r *2]× ×[f m (x ),r *m ]),(16)其中dist(x ,P )为P *中的个体x 到P R 上最近点的距离;vol(㊃)为Lebesgue 测度;P *为集合P *中的基数;r *=[r *1,r *2, ,r *m ]为目标空间分布的参考点,是Pareto 前沿极值点的1.1倍㊂考察IGD 和HV 的值,如果算法的收敛性和多样性越好,则IGD 值应该越小,或HV 值越大,这时P R 与Pareto 前沿面越近似㊂523第2期刘仁云,等:基于协同进化的多目标约束进化算法3.2 实验参数设置设种群N =450,两个子种群N 1=300,N 2=150,当函数评估次数达到1000时,算法终止;算法对所有测试问题集独立运行20次,结果取平均值[18]㊂3.3 实验结果分析将笔者算法与小生境Pareto 遗传算法(NPGA:Niche Pareto Genetic Algorithms)和DCMaoP 算法进行比较,对测试集Belegundu 和Binh(2),在IGD 和HV 指标上均能取得较好结果,如表1所示(IGD 和HV为最优结果)㊂表1 IGD ,HV 和可行比的均值比较分布情况,如图2所示㊂前期搜索可行解所建立的第1种群P 1(图2浅色粒子)在目标空间分布比较均匀,保持了协同进化初期良好的多样性;中期,第2种群P 2(图2深色粒子,b 图左下方)引导P 1跳出不可行域实现进化,再对P 1改变约束边界继续维持种群多样性,克服了收敛到局部Pareto 前沿的缺陷;后期,P 2的多样性策略产生效果,P 1中的个体逐渐聚集于Pareto 前沿的端点(c 图弧形线),完成引导种群演化过程㊂可见,基于改变约束边界与多目标协同进化相结合的方法在维持种群多样性㊁收敛性方面都具有良好结果㊂图2 Belegundu 的协同进化过程Fig.2 Coevolution of Belegundu综上所述,第1阶段的种群搜索和进化方式保证了高质量的可行解,可产生多个子种群,保持了种群多样性;第2阶段两种群以基于改变约束边界的方式实现协同演化,通过交叉变异机制实现各任务的协同,在兼顾收敛性和多样性的同时,实现了改变约束边界与协同进化两种优化方式的良好结合㊂在不连续Pareto 前沿的测试集Belegundu 上,笔者算法取得了良好的结果㊂笔者在测试问题Belegundu 和Binh(2)上测试了4种子种群规模(N 1,N 2)的效果:分别为(300,50)㊁623吉林大学学报(信息科学版)第41卷(300,100)㊁(300,150)㊁(300,200),以便考察种群数量对算法性能的影响㊂算法独立运行51次,评价标准为IGD 平均值,函数评价次数为3000,如表2所示㊂可见,在进化阶段,子种群数量具有相对较低的敏感性㊂表2 N 2取不同值时的IGD 均值对比Tab.2 Comparison of IGD mean values of N 2with different values实例(300,50)(300,100)(300,150)(300,200)Belegundu0.00120.00110.00060.0011Binh(2)0.12040.10940.10880.10884 结 语笔者提出了一种基于协同进化的多目标约束优化算法,通过改变约束边界与结合稳态演化方法提高了前期搜索速度和有效性,并采用两个种群协同进化策略找到最优可行解,算法有效地兼顾了进化过程中的收敛性和多样性,并通过测试集和实例比较验证了算法的可行性㊂参考文献:[1]HUSSEIN R,DEB K.A Generative Kriging Surrogate Model for Constrained and Unconstrained Multi⁃Objective Optimization [C]∥Proceedings of the Genetic and Evolutionary Computation Conference 2016.[S.l.]:IEEE,2016:573⁃580.[2]NING W,GUO B,YAN Y,et al.Constrained Multi⁃Objective Optimization Using Constrained Non⁃Dominated Sorting Combined with an Improved Hybrid Multi⁃Objective Evolutionary Algorithm [J].Engineering Optimization,2017,49(10):1645⁃1664.[3]LONG Q.A Constraint Handling Technique for Constrained Multi⁃Objective Genetic Algorithm [J].Swarm and Evolutionary Computation,2014,15:66⁃79.[4]LIU Z,WANG Y.Handling Constrained Multiobjective Optimization Problems with Constraints in Both the Decision and Objective Spaces [J].IEEE Transactions on Evolutionary Computation,2019,23(5):870⁃884.[5]FAN Z,LI W,CAI X,et al.Push and Pull Search for Solving Constrained Multi⁃Objective Optimization Problems [J].Swarm and Evolutionary Computation,2019,44:665⁃679.[6]YAZDANI D,OMIDVAR M N,BRANKE J,et al.Scaling up Dynamic Optimization Problems:A Divide⁃and⁃Conquer Approach [J].IEEE Transactions on Evolutionary Computation,2019,24(1):1⁃15.[7]WANG H,JIAO L,YAO X.Two_Arch2:An Improved Two⁃Aarchive Algorithm for Many Objective Optimization [J].IEEE Transactions on Evolutionary Computation,2015,19(4):524⁃541.[8]GOH C K,TAN K C.A Competitive Cooperative Coevolutionary Paradigm for Dynamic Multiobjective Optimization [J].IEEE Transactions on Evolutionary Computation,2009,13(1):103⁃127.[9]LI K,CHEN R,FU G,et al.Two⁃Archive Evolutionary Algorithm for Constrained Multiobjective Optimization [J].IEEE Transactions on Evolutionary Computation,2019,23(2):303⁃315.[10]WANG J,LIANG G,ZHANG J.Cooperative Differential Evolution Framework for Constrained Multiobjective Optimization [J].IEEE Transactions on Cybernetics,2019,49(6):2060⁃2072.[11]张磊,毕晓君,王艳娇.基于重新匹配策略的ε约束多目标分解优化算法[J].电子学报,2018,46(5):1032⁃1040.ZHANG L,BI X J,WANG Y J.The εConstrained Multi⁃Objective Decomposition Optimization Algorithm Based on Re⁃Matching Strategy [J].Acta Electronica Sinica,2018,46(5):1032⁃1040.[12]NEDJAH N,MOURELLE L D.Evolutionary Multi⁃Objective Optimisation:A Survey [J].International Journal of Bio⁃Inspired Computation,2015,7(1):1⁃25.[13]QIAN F,XU B,QI R,et al.Self⁃Adaptive Differential Evolution Algorithm with Alpha⁃Constrained⁃Domination Principle for Constrained Multi⁃Objective Optimization [J].Soft Comput,2012,16(8):1353⁃1372.[14]ZHANG Q F,LI H.MOEA /D:A Multiobjective Evolutionary Based on Decomposition [J].IEEE Trans Evolut Comput,2007,11(6):712⁃731.[15]WANG R,PURSHOUSE R C,FLEMIN G P J.Preference⁃Inspired Coevolutionary Algorithms for Many⁃Objective Optimization723第2期刘仁云,等:基于协同进化的多目标约束进化算法823吉林大学学报(信息科学版)第41卷[J].IEEE Trans Evolut Comput,2013,17(4):474⁃494.[16]JARA E C.Multi⁃Objective Optimization by Using Evolutionary Algorithms:The P⁃Optimality Criteria[J].IEEE Trans Evolut Comput,2014,18:167⁃179.[17]ZENG S Y,CHEN S,ZHAO J,et al.Dynamic Constrained Multi⁃Objective Model for Solving Constrained Optimization Problem[C]∥IEEE Congress on Evolutionary Computation.CEC2011.New Orleans:IEEE,2011:2041⁃2046. [18]CAI X,MEI Z,FAN Z,et al.A Constrained Decomposition Approach with Grids for Evolutionary Multiobjective Optimization [J].IEEE Transactions on Evolutionary Computation,2018,22(4):564⁃577.(责任编辑:刘东亮)。
