面向约束超多目标优化的双阶段搜索策略研究_耿焕同.pdf

Computer Engineering and Applications计算机工程与应用2023，59（7）约束多目标优化问题（constrained multi-objectiveoptimization problem，CMOP）1广泛存在于现实世界中，如供水系统管道优化2、楼宇负荷优化调度3等。不失一般性，以最小化为例，一个CMOP可以定义为：面向约束超多目标优化的双阶段搜索策略研究耿焕同，周征礼，沈俊烨，宋飞飞南京信息工程大学 计算机学院 软件学院 网络空间安全学院，南京 210044摘要：解决约束超多目标优化问题的关键在于约束处理和均衡收敛性与多样性，搜索空间中的约束阻碍种群寻找Pareto前沿面，容易使种群陷入局部最优，而离散的可行域则使种群的多样性较差。提出组合算子型双阶段搜索策略（two-stagesearch strategy with combined operator，TSCO）。TSCO分两阶段处理约束：一阶段算法仅优化目标函数，种群不受约束制约快速向Pareto前沿面方向接近；二阶段通过目标转换将约束违反度视作一个新目标函数以解决原始约束问题。在搜索过程中使用模拟二进制交叉算子和DE/current-to-pbest/1算子构成的组合算子生成收敛性和多样性优秀的个体。为验证策略有效性，结合 TSCO 策略的 AGE-MOEA（TSCOEA）在 C_DTLZ、DC_DTLZ和MW测试集上同4种性能优异的约束超多目标进化算法进行对比。实验表明，在大多数问题上，TSCOEA获得的种群收敛性和多样性更好。关键词：约束超多目标优化；进化算法；双阶段搜索；组合算子；Minkowski距离文献标志码：A中图分类号：TP18doi：10.3778/j.issn.1002-8331.2207-0167Research onTwo-Stage Search Strategy for Constrained Many-Objective OptimizationGENG Huantong,ZHOU Zhengli,SHEN Junye,SONG FeifeiSchool of Computer Science,Nanjing University of Information Science and Technology,Nanjing 210044,ChinaAbstract：In dealing with constrained many-objective optimization problems,a key issue of evolutionary algorithms isconstraint handling and the tradeoffs between convergence anddiversity.However,the constraints in the search space hin-der the population from finding the Pareto front,which tends to make the population fall into a local optimum,while thediscrete feasible areas make the population less diverse.Therefore,a two-stage search strategywith the combined operator（TSCO）is proposed.TSCO deals with the constraints in two stages.Firstly,the algorithm only optimizes the objectivefunction and the population is not constrained to approach the Pareto front direction rapidly.Secondly,the constraint violationdegree is treated as a new objective function to solve the original constraint problem by objective transformation.A combinedoperator consisting of the simulated binary crossover operator and the DE/current-to-pbest/1 operator is used in the searchprocess to generate individuals with excellent convergence and diversity.To verify the strategy effectiveness,AGE-MOEAcombined with TSCO（TSCOEA）is compared with four state-of-the-art constrained many-objective evolutionary algo-rithms on the C_DTLZ,DC_DTLZ,and MW test suites.Experiments show that TSCOEA obtains better population con-vergence and diversity on most problems.Key words：constrained many-objective optimization;evolutionary algorithm;two-stage search;combined opera-tor;Minkowski distance理论与研发基金项目：国家自然科学基金（51977100）。作者简介：耿焕同（1973），男，博士，教授，CCF会员，研究方向为多目标优化、深度学习，E-mail：；周征礼（1995），男，硕士研究生，研究方向为多目标优化；沈俊烨（1999），男，硕士研究生，研究方向为多目标优化；宋飞飞（1998），男，硕士研究生，研究方向为多目标优化。收稿日期：2022-07-11修回日期：2022-09-26文章编号：1002-8331（2023）07-0080-12802023，59（7）min F()x=()f1()x,f2()x,fM()xs.t.gi()x 0,i=1,2,rhj()x=0,j=1,2,swhere x=()x1,x2,xn=|x lxul=()l1,l2,ln,u=()u1,u2,un（1）其中x是决策空间中的n维的决策变量。F:RM是M个相互冲突的目标函数，RM是目标空间。当M3时，CMOP通常被称为约束超多目标优化问题或约束高维多目标优化问题（constrained many-objectiveoptimization problem，CMaOP）。gi是r个不等式约束，hj是s个等式约束。解x的约束违反度为：G()x=i=1rmax()0,gi()x+j=1smax()0,|hj()x（2）约束违反度为0，解x是可行解，反之为不可行解。如果x的目标函数都不大于并且至少存在一个小于y的目标函数，则称xPareto支配y，简称x支配y。如果不存在解z支配解x，则称x是非支配解。决策空间中所有非支配解构成Pareto解集（Pareto set，PS），PS在目标空间的映射称为Pareto前沿面（Pareto front，PF）。特别地，在CMOP或CMaOP中忽略约束构成的PF称为无约束PF（unconstrained PF，UPF），真实PF称为带约束PF（constrained PF，CPF）。如图 1所示，CMOP或 CMaOP根据 UPF与 CPF的关系一般分为三类4：类型 I 是约束仅在搜索空间中，UPF 与 CPF 完全一致；类型 II是约束使得 UPF 部分可行，即UPF与CPF部分重合；类型III是约束使得UPF完全不可行，CPF是可行区域的边界，即UPF与CPF完全分离。一般求解无约束超多目标优化问题（many-objectiveoptimization problem，MaOP）的超多目标进化算法（many-objective evolutionary algorithm，MaOEA）主要分为三类：（1）基于Pareto支配关系的MaOEA该类算法使用Pareto支配关系衡量解的优劣。如NSGA-III5在临界层依靠参考点选择个体以提高种群多样性。AGE-MOEA6利用第一非支配层估计前沿面形状并用 Minkowski 距离衡量解优劣，能够更好解决MaOP。此外，随着目标数增加，Pareto支配关系难以区分大部分解。因此有研究通过改进支配关系扩大解的支配区域缓解此问题。如DAV-MOEA7使用动态角度向量支配关系增加选择压力。（2）基于分解的MaOEAMOEA/D8是此类算法的代表，该算法使用聚合函数（如加权和方法、切比雪夫方法和边界交叉方法）将多目标优化问题转换成若干单目标优化问题。RVEA9使用新的聚合函数角度惩罚距离区分高维目标空间的解。由于参考向量是固定的，当前沿面形状与参考向量的分布不一致时，种群的多样性会降低。因此，A-NSGA-III4和AR-NSGA-III10等MaOEA根据种群状态动态调整参考向量分布。（3）基于性能指标的MaOEAHypE11以超体积（hyper volume，HV）指标作为环境选择准则，每次从种群中删除一个对HV指标影响最小的个体。AR-MOEA12则采用一种改进的IGD指标并结合自适应参考点来选择优秀个体。约束超多目标进化算法（constrained many-objectiveevolutionary algorithm，CMaOEA）一般由 MaOEA 结合约束处理技术构成。常见的约束处理技术有可行性准则13、epsilon约束准则14等。可行性准则的代表算法主要有C-NSGA-III4和C-MOEA/D4等，该类算法通常是可行性驱动的。epsilon 约束准则的代表算法主要有DCNSGA-III15和MOEA/D-2WA16等，该类算法通常是不可行性驱动的。此外，一些算法使用双归档集实现不可行性驱动。如C-TAEA17使用CA归档集保证种群的收敛性，使用DA归档集探索CA未开发区域。不同类型的CMaOEA各有优劣。一般可行性驱动的CMaOEA无需额外参数，易于实现，能够快速引导种群抵达可行区域。由于倾向于可行解，种群容易陷入局部最优或过早收敛。图1（a）中可行区域远离CPF，种群难以跨越不可行域，收敛到局部可行域中离CPF近的一侧；图1（b）中可行域狭窄，CPF离散，种群容易收敛到部分区域而无法找到完整CPF。不可行性驱动的算法通常需要额外参数，虽然可以利用目标优秀的不可行解，图1三种约束类型Fig.1Three types of constraintsUPFCPF可等域解f2f1（b）类型IIOUPFCPF可等域解f2f1O（a）类型IUPFCPF可等域解f2f1（c）类型IIIO耿焕同，等：面向约束超多目标优化的双阶段搜索策略研究81Computer Engineering and Applications计算机工程与应用2023，59（7）但如果不可行解远离CPF可能会导致性能下降18。图1（c）中CPF与UPF完全分离，UPF上的目标值较好的解无法为种群提供有效信息。基于此，本文提出一种组合算子型双阶段搜索策略（two-stage search strategy with combined operator，TSCO），其特点如下：（1）第一阶段，为了迅速跨越阻碍在CPF前的各种不可行区域，算法仅优化目标函数，种群不受约束制约向UPF方向逼近；第二阶段，算法通过目标转换将约束违反度视作一个