约束多目标优化问题(CMOPs)是指多个目标之间互相冲突且同时有多个等式和不等式约束的一类问题，广泛存在于科学研究和工程实践中[1]．由于约束多目标优化问题不仅要考虑解的收敛性和多样性，而且要考虑解的可行性，因此使得问题的解空间由于约束条件限制而变得复杂且难以搜索，为求解该类问题带来很大的困难，是当前科学研究和工程实践中亟须解决的难题．进化算法(EA)具有强大的解空间搜索能力，且通过一次运行就可以获取一组最优解的特性[2]，因此被广泛用于求解各类复杂非线性问题．已有的求解约束多目标优化问题的方法主要由多目标进化算法(MOEAs)和各种约束处理规则构成的．根据算法的运行机制可将其分为三类：a．基于支配关系的约束多目标优化算法[3]；b．基于分解的约束多目标优化算法[4]；c．基于指标的约束多目标优化算法[5]．在已有的约束多目标优化算法中，大多数算法的求解都侧重于可行解优先的选择机制，在优先保留可行解的基础上再平衡解的收敛性和多样性．由于约束条件的限制，问题的解空间通常被分割成多个离散的可行域，因此这种可行解优先的机制容易丢失分布性好的不可行解，导致种群的多样性丢失，使算法陷入到部分可行域中，最终获取的解难以收敛和分布到约束帕累托前沿上．近年来提出的多种约束多目标算法[6-8]在求解过程中考虑了部分不可行解的信息，但这些算法往往依赖于各种设定的参数值，而且个别算法的逻辑复杂，求解效率较低．针对上述问题，本研究提出一种基于分层环境选择策略的约束多目标优化算法．该算法首先采用两个不同的进化操作算子SBX和DE分别产生子代种群；然后通过第一层环境选择策略选取分布性较好的个体，确保种群的收敛性和多样性得到提升；再通过第二层环境选择策略对整个联合种群进行选择；最后将提出的CMOEA-HES算法与5个最新的约束多目标优化算法在MW和DOC两组测试集上进行测试，通过IGD指标可知CMOEA-HES在求解约束多目标优化问题上相比其他算法更有优势．1 问题描述1.1　约束多目标优化问题(CMOPs)在通常情况下，一个最小化约束多目标优化问题的数学模型可表示为min F(x)=(f1(x),f2(x),…,fm(x))；s.t. gk(x)≤0    (k=1,2,…,p)；(1)hl(x)=0    (l=1,2,…,q)；x=(x1,x2,…,xn)∈Ω，式中：F(x)为m个目标函数；gk(x)为第k个不等式约束；hl(x)为第l个等式约束；p和q分别为不等式约束和等式约束的个数；x为一个n维决策变量；Ω为决策空间．对于两个解xu和xv，若xu的每个目标函数值都不大于且至少有一个目标小于xv的目标函数值，则称xu帕累托支配xv，可表示为xu≺xv；若解xu不受解空间中其他解的帕累托支配，则称xu为帕累托非支配解．解空间中所有帕累托非支配解构成的集合称为帕累托最优解集，在目标空间中称为帕累托前沿．在约束优化中，采用约束违反度(CV)来判断一个解是否违反约束或违反约束的程度，解x的约束违反度计算公式为CV(x)=∑k=1pmax(0,gk(x))+∑l=1qmax(0,|hl(x)|-δ),式中δ为一个很小的正数，通常设置为1×10-6，主要用于将等式约束转化为不等式约束．1.2　约束处理机制(CHT)多目标优化算法中的约束处理机制基本都是从约束单目标算法中引入，常用的约束处理机制有罚函数法[9]、约束支配法[10]、多目标法[11]和混合方法[12]．在这些处理机制中，约束支配法因简单实用且无需额外的参数而得到了广泛应用，可以嵌入到任意一种算法中．具体的描述如下．假设存在xu和xv，如果xu约束支配xv(记为xu≺cxv)，那么须满足以下条件：a．xu是可行解，同时xv是不可行解；b．xu和xv都是不可行解，同时CV(xu)CV(xv)；c．xu和xv都是可行解，且xu≺xv．2 算法设计本研究提出的CMOEA-HES为了有效平衡种群的可行性、收敛性和多样性，采用分层的环境选择策略：第一层环境选择策略侧重于种群的多样性和收敛性；第二层选择策略加入了解的可行性选择机制，在多样性和收敛性的基础上保证解的可行性．两层不同的环境选择策略可有效改进种群中个体可行性、收敛性和多样性之间的平衡．2.1　算法流程CMOEA-HES算法的计算流程如下．步骤1 初始化种群Pt，设置种群大小为N，最大迭代次数为Gmax，进化代数为t．步骤2 通过进化算子SBX和DE分别产生子代种群off_sbx和off_de．步骤3 合并种群off_sbx和off_de为off_union，采用第一层环境选择策略从off_union中选取个数为N的个体组成种群Ptoff_union．步骤4 合并种群，Pt=Pt⋃Ptoff_union采用第二层环境选择策略从合并后的种群Pt中选取N个个体作为下一代进化的种群Pt+1．步骤5 当迭代次数达到Gmax时，输出最终结果Pt+1，否则返回步骤2．2.2　进化算子进化算子在多目标算法中起到非常重要的作用，是推动算法不断迭代演化的重要组成部分．不同的进化算子在求解问题中有不同的性能，为了提高算法的搜索能力，通常将多种进化算子结合起来，使其发挥各自的优势．在已有的进化算子中，SBX和DE因其良好的搜索性能得到了广泛的应用，其中SBX偏向于局部搜索，而DE侧重于全局搜索．因此，为保证算法在求解过程中的种群多样性，本研究采用结合SBX和DE的方式来产生子代种群．a．在SBX中，假定xi1和xi2为第i代种群中两个个体，β为多项式概率分布，η为分布因子，rand为[0，1]之间的随机数．新的子代个体ci1和ci2的具体计算过程为：ci1=0.5[(1+β)xi1+(1-β)xi2]；ci2=0.5[(1-β)xi1+(1+β)xi2]；β=(2rand)1/(1+η)    (rand≤0.5),(0.5-2rand)1/(1+η)    (其他).b．DE采用“DE/rand/1/bin”，假定xi1，xi2，xi3为第i代种群中的三个不同个体，F为控制参数，yi为新生成的子代个体，具体计算式为yi=xi1+F(xi2-xi3)．2.3　适应度函数CMOEA-HES算法中的适应度函数Fitness来源于SPEA2算法[13]，在SPEA2基础上加入约束处理规则．SPEA2中Fitness的具体计算式为Fitness(x)=R(x)+D(x)；R(x)=∑y∈S(x)|Ry|；(2)D(x)=1/(dist(x,x')+2)，式中：Ry包含了被y支配的解；S(x)包含了支配x的解；D(x)为距离解x到其第k(k=2n)个邻近个体之间的距离；dist(x,x')为x和x'之间的欧式距离．可以看出：Fitness(x)的值越小，表示解x的质量越高．本研究采用的适应度函数Fitness与SPEA2的区别在于：R(x)的值在SPEA2中是直接通过解个体之间目标函数值来确定支配关系的，而在CMOEA-HES中，解个体之间的支配关系由目标函数值和约束违反度两个因素决定，具体如下．假设种群中两个解x和y，若CV(x)CV(y)，则x≺y；若CV(x)CV(y)，则y≺x；若CV(x)=CV(y)，则根据x和y各自对应的目标函数值来判断支配关系．2.4　分层环境选择策略a．第一层环境选择策略的计算步骤如下．步骤1 根据Deb的约束非支配排序对2.1节算法中的联合种群off_union进行排序，生成F1,F2,⋯,Fl层．步骤2 判断F1⋃F2⋃⋯⋃Fl-1的规模是否大于种群个数N．若F1⋃F2⋃⋯⋃Fl-1规模小于，则将Fl层的个体也合并进来，循环操作直到规模大于N，然后进入步骤3中的截断函数；若F1⋃F2⋃⋯⋃Fl-1规模大于N，则算法直接进入步骤3中的截断函数．步骤3 截断函数．计算种群中每个个体之间的欧式距离，将距离最小的个体按照位置索引依次删除一个，重复操作直到种群大小为N．步骤4 将规模为N的种群作为下一代的种群．b．第二层环境选择策略的计算步骤如下．步骤1 计算种群中每个个体的适应度值，并将种群中适应度小于1的个体保存到临时Archive中．步骤2 计算Archive中的个体数．若Archive中的个体数小于N，则根据适应度值从小到大依次加入到Archive中，直到个体数等于N；若Archive中的个体数大于N，则通过截断函数将超出的个体移除直到大小为N，截断函数与第一层环境选择策略中的截断函数一样．步骤3 将Archive中的个体作为下一代种群．2.5　算法复杂度分析CMOEA-HES算法主要包括种群初始化、子代个体生成、第一层选择和第二层选择这四部分．假设N为解的个数，m为目标的个数，t为迭代次数，O(mN2)为初始化的计算复杂度；子代生成主要通过SBX和DE来产生，可以在线性时间内完成，复杂度都为O(tmN)；在第一层环境选择中，复杂度为O(tmN2)；第二层环境选择的复杂度也为O(tmN2)．因此，CMOEA-HES算法的复杂度约为O(tmN2)．3 实验设置及结果分析选取5个最新的约束多目标优化算法与提出的CMOEA-HES进行对比实验，并对结果进行分析．3.1　对比算法和测试函数本研究选取的对比算法有PPS[7]，ToP[14]，CTAEA[6]，CMOEA_MS[8]和MOEADDAE[15]．测试函数采用MW[16]和DOC[14]两组测试集共23个问题进行测试，其中：MW是从实际问题中抽象归纳出来，包含14个不同类型的约束多目标优化问题(不连续、线性、离散、非凸等特性)；DOC问题既包含目标空间中的约束，又包含了决策空间的约束，是一类比较复杂的约束多目标优化问题．3.2　性能指标本研究采用反向世代距离(IGD)[17]来评价算法的性能，该指标能同时衡量解集的收敛性和多样性．假设P*为一组从真实帕累托前沿面采样获得的解，P为算法获取的一组解，IGD的定义为IGD(P*,P)=∑x∈P*dis(x,P)/|P*|，式中dis(x,P)为问题的真实解x到P中最近个体的欧式距离．本实验从真实帕累托前沿上采样了1×104个均匀分布的解．可以看出：IGD的值越小，算法的性能越好；IGD的值越大，算法的性能越差．3.3　参数设置为客观公正评价算法性能，实验中的种群个数统一设置为100，每个算法的评价次数统一设置为1×105．DE中的F=0.5，SBX中η=20．DE和SBX都采用多项式变异，变异概率pm=1/D，其中D为决策变量的维度，其他参数都依据各自算法在原文献中的设置进行．实验在配置为Intel Xeon(R) CPU 2.6 GHz的处理器和8 GiB内存的服务器上运行，且全部算法都在PlatEMO[18]上进行测试．为了统计实验结果，每个算法分别独立运行30次，记录的实验结果为IGD的均值．实验采用Wilcoxon符号秩检验来比较算法之间的性能差异，显著水平为5%．3.4　实验结果分析3.4.1　MW问题的实验结果分析所有对比算法在MW问题上获取的IGD均值如表1所示，表中：“+”，“-”和“=”分别表示对比算法显著优于、显著劣于和无显著差异于CMOEA-HES；NaN表示算法在当前问题上无法取得可行解．从表1中可以看出：CMOEA-HES算法的性能明显优于其他对比算法，能够获得更好的结果．10.13245/j.hust.230521.T001表1在MW问题上运行30次的IGD均值统计结果问题目标数PPSCTAEAToPMOEADDAECMOEA_MSCMOEA-HESMW123.30×10-3 -2.01×10-3 -NaN1.87×10-3 -2.21×10-3 -1.63×10-3MW221.47×10-1 -1.48×10-2 +1.32×10-1 -7.61×10-2 -2.16×10-2 =2.31×10-2MW326.11×10-3 -5.10×10-3 =5.25×10-1 -5.45×10-3 -5.34×10-3 -5.07×10-3MW435.79×10-2 -4.67×10-2 -4.53×10-1 -4.68×10-2 -4.20×10-2 =4.21×10-2MW524.53×10-1 -1.40×10-2 -NaN6.63×10-3 -2.07×10-2 -4.66×10-4MW625.81×10-1 -9.00×10-3 +6.25×10-1 -3.10×10-1 -5.84×10-2 =2.91×10-2MW725.54×10-3 -6.96×10-3 -8.51×10-2 -4.63×10-3 =1.51×10-2 -4.63×10-3MW831.41×10-1 -5.38×10-2 -6.74×10-1 -1.05×10-1 -4.83×10-2 =4.84×10-2MW929.89×10-2 -8.52×10-3 +6.05×10-1 -3.64×10-2 -1.86×10-1 =1.11×10-2MW1023.80×10-1 =1.86×10-2 +4.37×10-1 =2.85×10-1 =3.51×10-2 +3.14×10-1MW1127.40×10-3 -1.46×10-2 -6.22×10-1 -6.91×10-3 -2.91×10-2 =6.19×10-3MW1226.56×10-2 -7.93×10-3 -8.04×10-1 -5.79×10-2 -5.30×10-3 -4.76×10-3MW1325.19×10-1 -3.66×10-2 +5.49×10-1 -2.54×10-1 -9.81×10-2 =1.14×10-1MW1431.39×10-1 -1.12×10-1 -2.62×10-1 -1.13×10-1 =1.29×10-1 -1.00×10-1由于MW这类问题的搜索空间包含多个离散可行域，因此对算法在维护种群的多样性方面提出了更高的要求．CTAEA在求解过程中利用两个档案集提升种群的多样性，MOEADDAE和CMOEA_ES利用了不可行解的信息来增加种群的多样性，因此它们在MW问题上都得到了较好的结果．PPS侧重于让种群跨过较大的不可行区域，但在多样性方面的提升不足．ToP在多个离散的可行域空间中容易陷入局部可行区域中，因此无法较好收敛到帕累托前沿．为了验证算法的稳定性，图1显示了各对比算法在MW1问题上的盒图．可以看出：相比其他算法，CMOEA-HES在求解问题中具有更好的稳定性．10.13245/j.hust.230521.F001图1对比算法在MW1问题上的盒图3.4.2　DOC问题的实验结果分析DOC问题是一组既包含目标空间的约束，又有决策变量约束的测试集．表2显示了对比算法在DOC问题上获取的IGD均值．通过Wilcoxon秩和检验可以得出：CMOEA-HES在DOC问题上相比其他对比算法有更加显著的效果．在DOC2和DOC4-DOC9等问题上都要优于其他算法．ToP在DOC1问题上获得了最好的解，主要原因是DOC1问题的帕累托前沿面是非凸且连续的，而ToP在第二阶段优化中能够使解较好分布到帕累托前沿上，因此在DOC1问题上获得了最优的解．10.13245/j.hust.230521.T002表2在DOC问题上运行30次的IGD均值统计结果问题目标数PPSCTAEAToPMOEADDAECMOEA_MSCMOEA-HESDOC129.57×10-2 -5.31×102 -6.50×10-3 +2.61×10-1 -6.04×100 -5.84×10-2DOC225.30×10-1 -NaNNaNNaNNaN3.13×10-1DOC322.66×102 =NaN5.82×102 =NaN6.48×102 -4.02×102DOC423.63×10-1 -3.84×102 -3.86×10-1 -8.32×10-1 -1.10×100 -4.89×10-2DOC526.05×101 -NaN2.39×102 -NaN8.22×101 -2.63×101DOC625.31×10-1 -3.48×101 -1.38×101 -1.97×100 -3.19×100 -7.75×10-2DOC726.96×10-1 -NaNNaN3.82×100 -4.71×100 =7.27×10-2DOC831.08×102 -5.11×102 -1.75×102 -1.46×102 -1.67×102 -7.85×10-1DOC933.38×10-1 -NaN3.86×10-1 -2.28×10-1 -1.10×10-1 =6.57×10-2各对比算法在DOC8问题上的盒图如图2所示，可以看出：相比其他对比算法，CMOEA-HES的性能更加稳定．10.13245/j.hust.230521.F002图2对比算法在DOC8问题上的盒图3.4.3　多进化算子的有效性分析为验证多进化算子的有效性，实验构造了两个算法变体，即CMOEA-HES-DE和CMOEA-HES-SBX，其中：CMOEA-HES-DE表示算法只采用DE产生子代；CMOEA-HES-SBX表示算法只采用SBX产生子代．将它们与CMOEA-HES在MW和DOC问题上进行实验对比，表3显示了三种算法在这些问题上获得的Friedman检验实验结果．可以看出：在95%的置信区间下，同时采用DE和SBX算子能够更好提升算法的性能，获得更好的结果．10.13245/j.hust.230521.T003表3Friedman检验试验结果算法平均等级CMOEA-HES-SBX2.43CMOEA-HES-DE1.83CMOEA-HES1.744 结语为求解约束多目标优化问题，本研究提出一种基于分层环境选择策略CMOEA-HES．首先采用SBX和DE产生子代种群，然后通过第一层环境选择策略选择收敛性和多样性较好的个体，在第二层环境选择策略中通过构造的Fitness指标选择更优个体组成下一代种群．将CMOEA-HES与其他5种算法在MW和DOC两组问题上进行了对比实验，结果表明所提算法在这两组问题上都能够获得较好的结果．CMOEA-HES在2～3个目标的约束问题上能够较好进行求解，但当问题的目标数超过3个时，问题将变得更加复杂，因此如何求解约束超多目标问题是下一步研究的主要内容．