基于自适应e截断策略的约束多目标优化算法

毕晓君　张　磊（哈尔滨工程大学信息与通信工程学院哈尔滨150001）



基于自适应e截断策略的约束多目标优化算法

毕晓君张磊*
（哈尔滨工程大学信息与通信工程学院哈尔滨150001）

为提高约束多目标优化问题所求解集的分布性和收敛性，该文提出基于自适应ε截断策略的约束多目标优化算法。首先，自适应ε截断选择策略能够保留Pareto最优解和约束违反度及目标函数值均较优的不可行解，不仅提高了种群多样性，而且能够较好地兼顾多样性和收敛性；其次，为增强算法的局部开发能力，在变异操作和交叉操作之后进行指数变异；最后，改进的拥挤密度估计方式只选择一部分Pareto最优解和距离较近的个体参与计算，不仅更加准确地反映解集的分布性，而且降低了计算量。通过在标准测试问题（CTP系列）上与其他4种优秀算法的对比结果可以得出，该算法所求解集的分布性和收敛性均得到一定提高，而且相较于对比算法在求解性能上具备一定的优势。

约束多目标优化；约束处理技术；ε截断；分布性；收敛性

1　引言

约束多目标优化问题（Constrained Multiob jective Optim ization Problems，CMOPs）是科学研究和工程实践中最常见的问题之一，涉及到航空航天、网络通信、机械设计、作业调度和决策科学等诸多领域［14］-。然而随着目标个数的增加和约束条件的复杂，现有约束多目标优化算法已不能完全满足应用的需求，算法的性能急需进一步提高。因此，约束多目标优化算法的研究具有重要的理论价值和实际意义。

文献［5］在更新可行解集时随机删除欧氏距离最小的两个个体中的一个，但会遗失边界解，从而影响多样性。同时在更新不可行解集时优先选择约束违反度小的个体，但这样的个体可能目标函数值较差，从而影响种群收敛速度；文献［6］对可行解和不可行解分别构造不同的适应度函数，使得少量不可行解得到保留，从而扩大探索范围。但由于缺少多样性维持策略，所求解集的分布性欠佳；文献［7］优先选择位于稀疏区域的Pareto可行解进入下一代可行解集以及目标函数较优并且位于稀疏区域的不可行解进入下一代不可行解集，从而兼顾多样性和收敛性，但算法收敛速度较慢；文献［8］将目标函数、多样性度量准则和约束违反度聚合成一个适应度函数，从而协调了精英选择、多样性和可行性之间的关系，但算法收敛精度不高；文献［9］提出以可行解极小化目标函数值和不可行解极小化约束违反度为目标，并利用差分进化算法优良的多样性能力进化种群，但可行解集与不可行解集的信息交流不够，种群多样性还需提高。文献［10］将分解算法和随机排序法以及Deb准则结合，但由于存在多个子问题对应同一个体的情况，严重影响了种群的多样性。

综上，约束多目标优化算法的核心在于如何兼顾多样性和收敛性，具体涉及到目标函数与约束条件的平衡，可行解与不可行解的比较，全局探索和局部开发的协调等方面。但目前大多数优秀算法在多样性和收敛性上很难达到充分的平衡。为此，本文提出基于自适应ε截断策略的约束多目标优化算法。首先，提出的自适应ε截断操作能够有效协调可行解和不可行解，从而加强对搜索空间的探索范围，并且在保证多样性的同时又能兼顾收敛性；其次，在交叉和变异操作之后引入指数变异，进一步提高局部搜索能力，从而在一定程度上权衡全局探索和局部开发；最后，改进的拥挤密度估计方式能够更加准确地评估种群的分布性，不仅提高进化效率而且更好地维持种群多样性。

2　基于自适应e截断的约束多目标优化算法

实验研究表明，影响约束多目标优化算法性能的关键在于多样性和收敛性的协调关系。因此本文算法不仅针对约束处理技术进行改进，而且还对进化操作以及多样性维持方式进行改进，提出自适应ε截断策略，引入指数变异，改进拥挤密度估计方法，从而获得算法整体求解性能的改善。

2.1自适应e截断策略

目前应用效果最好的约束处理技术为双种群存储［7］和ε约束［11］。双种群存储对可行解和不可行解分别存储，能够利用少量不可行解来提高种群多样性。但由于在更新不可行解集时只是优先考虑约束违反度，使得种群中存在目标函数值较差的不可行解，进而影响收敛速度。ε约束最先用于解决约束单目标优化问题，在一定程度上协调了可行解和不可行解的关系，扩大了探索范围。但其一对一的替换机制又会影响多样性，因为被替换个体位于稀疏区域时，将会遗失部分搜索区域，所以ε约束在多样性和收敛性上更加偏重后者。为此，在两者基础上提出ε截断策略，充分协调多样性和收敛性。

定义1ε截集：种群中所有满足（）Gε≤X的个体X构成的集合称为ε截集，记为ε≤P。

定义2ε截断操作：将种群划分为以约束违反度ε为界限的两个种群（ε≤P和ε>P）的操作，称为ε截断操作。

ε设置如式（1）所示。

性质2当ε=0时，ε截断策略与双种群存储性质相同，双种群存储是ε截断的一个特例。

（1）ε截断策略与双种群存储的比较：相同点：两者均让部分不可行解参与进化，从而提高种群多样性；两者都能避免可行解与不可行解的直接比较，事实上可行解与优秀不可行解很难定量比较。不同点：双种群存储是ε截断策略在ε=0时的特例；两者更新种群的机理不同，ε截断策略会在进化种群中会保留少量优秀不可行解，而双种群存储通过单独的不可行解集储存不可行解，需要额外的存储开支；ε截断策略在进化前期时，ε值相对较大，种群中的不可行解能够扩大对搜索空间的探索范围，增强多样性，同时保留的Pareto最优解又能保证收敛性。在进化后期ε相对较小并随着进化迭代次数的增加逐渐趋于零，种群中会全部由可行解构成，此时更加注重的是种群的收敛性，所以ε截断具有自适应性。

（2）ε截断策略与ε约束的比较：相同点：两者均能有效协调可行解和不可行解的关系，从而加强种群的多样性。不同点：ε截断能够方便融合其他操作，如小生境和拥挤密度估计等，从而更好改善种群的分布性；ε约束是新生个体与旧个体一对一的比较，是基于单个个体的操作，虽然能够加快收敛速度，但会影响种群的多样性，而ε截断是基于集合的操作并结合拥挤密度估计，所以能更好维护多样性。

综上，ε截断策略通过自适应调整有效平衡了可行解与不可行解的关系，在进化前期保留Pareto最优解和一部分优秀不可行解，从而较好地兼顾了多样性和收敛性，而在进化后期更加注重对可行域的开发能力，促使种群向Pareto前沿收敛。

2.2进化操作

本文采用文献［12］的变异算子和交叉算子，分别如式（2）和式（3）所示。

研究表明，上述的变异算子和交叉算子对于维护种群的多样性效果显著。而为了加强局部搜索能力，本文以概率mp进行指数变异［13］，如式（4）所示。

其中，η为指数因子，rand（）·为［0，1］随机数，jl和ju分别为决策空间j维的下界和上界。

2.3基于e截断策略的精英选择

经过2.2节的进化操作，会产生包含N个体的新生种群，进而将父代种群和新生种群合并，然后利用ε截断操作，将合并种群一分为二成

接着从合并种群中选择N个体作为下一代种群，共分3种情况。情况1则从中选择N个体作为下一代种群；情况2：将ε≤P作为下一代种群；情况3:则从个体，并与合并作为下一代种群。

对于情况1，为了有效平衡多样性和收敛性，应该选择在目标空间上Pareto等级较高和拥挤密度较大的个体。首先利用快速非支配排序法［14］将分层为中选择使得其总个体数量sN大于或等于N，如果sN N=，将然后选择合适的前若干等级层作为下一代种群，如果sN N>，计算sF中所有个体的拥挤密度。接着选择sF中拥挤密度最大的体，将其与合并作为下一代种群。值得注意的是，本文将sF中所有边界解的拥挤密度定义为无穷大，以确保它们进入下一代，从而能够加大对搜索空间的探索广度。

拥挤密度计算方式［14］如式（6）所示。

其中，N为种群规模，，ijd表示个体iX到jX在目标空间上的欧氏距离。

由于式（6）考虑了其中一个个体到种群其他所有个体的距离，一方面计算量很大，另一方面处于Pareto等级较差等级，相对距离较远的个体会对所要计算拥挤密度的个体会产生一定影响，从而不能准确反映种群的多样性分布。为此，提出改进的拥挤密度公式，如式（7）所示。

式（7）中参与计算个体数量远小于N，从而减少了计算量，并提高算法效率。同时，式（7）右边第1项表示选择距离较近的1T个体，从而避免距离较远个体影响，而第2项表示选择Pareto等级较优的2T个体，从而消除Pareto等级较差个体影响。所以改进的拥挤密度不仅能够降低计算量，而且在计算个体的拥挤密度时能够去除较远个体和Pareto等级较差个体的影响，从而能够准确反映个体的分布情况，并提高种群多样性。

对于情况3，由于ε≤P中的个体数量较少，说明可行域相对较小，造成进化过程中搜索到的可行解较少，此时算法更应该偏重搜索可行解，故选择约束违反度最小的个体，这样能够在一定程度上促使种群向可行域靠近。

2.4算法流程

为便于理解，给出本文算法的具体步骤。

步骤1初始化参数。包括最大进化代数maxG，种群规模N，缩放因子F，交叉因子CR，指数因子η，变异因子mp.；

步骤2在决策空间里随机生成产生N个体，构成初始种群；

步骤3执行2.2节中进化操作，生成新生种群；

步骤4合并父代种群和新生种群，并计算合并种群所有个体的约束违反度和目标函数值；

步骤6执行2.3节中基于ε截断的精英选择操作，选择N个体作为下一代种群；

步骤7判断是否达到maxG，是则将种群中的Pareto最优解作为结果输出，否则，转到步骤3。

3　实验及分析

为验证本文算法在约束多目标优化问题上的求解性能，将其与目前性能优异的文献［5］算法、文献［6］算法、BB-MOPSO［7］，NSGA-2约束多目标优化算法［15］（以下简称NSGA-2）在通用标准测试函数CTP2-CTP7［6］上进行对比实验，并采用GD［5］和SP［5］这两种通用的评价指标测试算法的性能。其中，GD用于评价解集的收敛性，SP用于评价解集的分布性。实验硬件环境为Intel Pentium，CPU:G 620，4 GB内存、主频2.6 GHz的计算机，程序采用MATLAB R2010编写。

由于CTP3和CTP4的真实Pareto最优解为多个离散点，CTP5的真实Pareto最优解为一段连续区域和多个离散点，再利用SP来度量分布性就不合适了。于是，将上述6个测试函数分为2组：CTP2，CTP6和CTP7记为第1组，CTP3，CTP4和CTP5记为第2组。第1组测试函数用SP来度量分布性以及用GD来度量收敛性，第2组测试函数用离散点个数来度量分布性以及用GD来度量收敛性。

3.1改进的拥挤密度估计的有效性验证

为验证改进拥挤密度估计的有效性，在本文算法基础上，将原始拥挤密度估计方式（式（6））和改进拥挤密度估计方式（式（7））进行对比实验，分别记为改进前和改进后。参数取值为N=100，Gmax= 3000，F=0.5，CR=0.9，η=20，pm=1/n。独立运行次数为10次，实验结果如表1～表3所示。

表1　第1组测试函数上改进前后的SP值

表2　第2组测试函数上改进前后的离散点个数

表3　 2组测试函数上改进前后的GD值

从表1可以看出，改进后的SP均值均优于改进前。特别在测试函数CTP5上，改进后的分布性有明显的改善，表明改进的拥挤密度估计方法在种群多样性维持上具有更好的性能；从表2可以看出，改进前后的离散点个数均取得较好的效果；从表3可以看出，在所有测试函数上，改进后的GD均值均优于改进前，特别在测试函数CTP2和CTP7上有明显的提高，说明改进的拥挤密度估计方法对加强收敛性也有帮助。同时，改进后的标准差普遍较小，说明算法稳定性也得到增强。因此，改进的拥挤密度估计方法对提高多样性起着重要作用，而多样性的提高又能有效避免陷入局部搜索，为最终收敛到整个真实Pareto前沿提供保障。

3.2对比实验及结果分析

为验证本文算法的先进性，将其与优秀的NSGA-2，文献［5］算法，BB-MOPSO和文献［7］算法进行对比实验，独立运行为30次。为保证公平性，所有算法参数取值为种群规模N=100，最大迭代次数除此，本文算法其他参数取值对比实验结果如表4～表6所示。

从表4可以看出，在测试函数CTP2和CTP6上，本文算法的SP均值优于其他4种算法，所求解集的分布性最优，说明在进化过程中较好地维持了种群多样性。在测试函数CTP7上，NSGA-2的SP均值在5种算法中最优，略优于排名第2的本文算法。从表5可以看出，在测试函数CTP3上，文献［5］算法、BB-MOPSO以及本文算法的离散点个数均值都为14，说明在30次独立运行中都一致找到了所有的离散点。但文献［5］算法的离散点个数均值只有9.90，表明由于多样性维持不足导致遗失一部分Pareto解。在测试函数CTP4和CTP5上，本文算法均取得最优的结果，并且明显优于其他4种算法，说明本文算法在进化中探索能力更强。综上，本文算法在种群多样性维护上具有明显优势，使得所求的解集分布性较好。

表4　 5种算法在第1组测试函数上的SP值

表5　 5种算法在第2组测试函数上的离散点个数

从表6可以看出，在测试函数CTP3，CTP4和CTP7上，本文算法获得了最优的GD均值，表明所求得的解集更加逼近真实Pareto前沿。文献［7］算法在测试函数CTP2和CTP6上，取得最优的GD均值，而在这两个测试函数上，本文算法略劣于文献［7］算法。在测试函数CTP5上，NSGA-2的GD均值最好，本文算法排名第2。但是NSGA-2的离散点个数均值和GD标准差都较差，说明NSGA-2的多样性维持能力还需加强。以上实验结果表明，本文算法在多样性和收敛性上均具有一定的优势。最后，本文算法的SP标准差和GD标准差在2组测试函数几乎均为最优，表明本文算法的稳定性更好。

4　结束语

针对现有约束多目标优化算法在求解复杂约束多目标优化问题时解集分布性较差和收敛精度不高等问题，本文提出基于自适应ε截断的约束多目标优化算法。首先，在双种群存储和ε约束的基础上，提出ε截断策略。通过自适应调整种群中的优秀不可行解的比例，有效协调可行解与不可行解的关系，从而兼顾多样性和收敛性。其次，在变异和交叉操作后再次进行指数变异以增强对新生个体周围区域的开发，进一步增强局部开发能力。最后，提出的拥挤密度估计方式通过选择部分Pareto个体和距离较近的个体参与计算，能够在改善解集的分布性的

表6　 5种算法在二组测试函数上的GD值

同时降低计算量。通过在CTP2-CTP7测试函数上进行测试，并与NSGA-2，文献［5］算法，BB-MOPSO和文献［7］算法进行对比实验。实验结果表明，本文算法所求解集的多样性和收敛性均有较大的提高。下一步工作将针对约束高维目标优化算法及其在决策管理和工程优化中的应用进行展开，以获得更高的社会价值和经济价值。

［1］W EI H.Design exp loration of th ree-dim ensional transverse jet in a supersonic crossflow based on data m ining and mu lti-ob jective design optim ization app roaches［J］. International Journal of Hydrogen Energy，2014，39（8）: 3914-3925.doi:10.1016/j.ijhydene.2013.12.129.

［2］ABDELKHALEK O，KRICHEN S，and GUITOUNI A.A genetic algorithm based decision support system for the mu lti-ob jective node p lacement problem in next w ireless generation network［J］.Applied Soft Com puting，2015，33（8）: 278-291.doi:10.1016/j.asoc.2015.03.034.

［3］PARENTE M，CORTEZ P，and CORREIA A G.An evolutionary multi-ob jective optim ization system for earthworks［J］.Expert System swith Applications，2015，42（19）: 6674-6685.

［4］GRASSO R，COCOCCIONI M，MOURRE B，et al.A decision support system for optimal dep loyment of sonobuoy networks based on sea current forecasts and multi-ob jective evolutionary op tim ization［J］.Expert Systems with Applications，2013，40（10）:3886-3899.doi:10.1016/j.eswa. 2012.12.080.

［5］孟红云，张小华，刘三阳.用于约束多目标优化问题的双种群差分进化算法［J］.计算机学报，2008，31（2）:229-235. MENG Hongyun，ZHANG Xiaohua，and LIU Sanyang.A differential evolution based on double population for constrained multi-ob jective optim ization prob lem s［J］. Chinese Journal ofComputers，2008，31（2）:229-235.

［6］WOLDESENBET Y G，YEN G G，and TESSEMA B G. Constraint handling in multi-ob jective evolutionary optim ization［J］.IEEE Transactions on Evo lutionary Computation，2009，13（3）:514-525.doi:10.1109/TEVC. 2008.2009032.

［7］张勇，巩敦卫，任永强，等.用于约束优化的简洁多目标微粒群优化算法.电子学报，2011，39（6）:1437-1440.

ZHANG Yong，GONG Dunwei，REN Yongqiang，et al. Barebones mu lti-ob jective particle swarm optim izer for constrained optimization prob lem s［J］.Acta Electronica Sinica，2011，39（6）:1437-1440.

［8］LONG Q.A constraint handling technique for constrained multi-ob jective genetic algorithm［J］.Swarm and Evolutionary Computation，2014，15（4）:66-79.doi:10.1016/j. swevo.2013.12.002.

［9］GAO W F，YEN G G，and LIU S Y.A dual-population differential evolution w ith coevolution for constrained optim ization［J］.IEEE Transactions on Cybernetics，2015，45（5）:1094-1107.doi:10.1109/TCYB.2014.2345478.

［10］JAN M A and KHANUM R A.A study of two penalty-parameterless constraint handling techniques in theframework of MOEA/D［J］.Applied Soft Computing，2013，13（1）:128-148.doi:10.1016/j.asoc.2012.07.027.

［11］毕晓君，王珏，李博，等.基于动态迁移的ε约束生物地理学优化算法［J］.计算机研究与发展，2014，3（3）:580-589.

BI Xiaojun，WANG Jue，LIBo，et al.Anεconstrained biogeography-based optim ization w ith dynam ic m igration［J］Journal ofComputer Research and Development，2014，3（3）: 580-589.

［12］邹德旋，高立群，段纳.用修正的差分进化算法确定光电模型参数［J］.电子与信息学报，2014，36（10）:2521-2525.doi: 10.3724/SP.J.1146.2013.01858.

ZOU Dexuan，GAO Liqun，and DUAN Na.Determ ining the parametersof photovoltaicmodulesby amodified differential evolution algorithm［J］.Journal of Electron ics&Inform ation Technology，2014，36（10）:2521-2525.doi:10.3724/SP.J. 1146.2013.01858.

［13］TAN YY，JIAO YC，LI H，et al.Amodification to MOEA/D-DE for multi-ob jective optim ization problem s w ith com plicated Pareto sets［J］.Information Sciences，2012，213（23）:14-38.

［14］DEB Kand JAIN H.An evolutionary many-ob jective optim ization algorithm using reference-point-based nondom inated sorting approach，part I:solving problem s w ith box constraints［J］.IEEE Transactions on Evolutionary Computation，2014，18（4）:577-601.doi:10.1109/TEVC. 2013.2281535.

［15］DEB K，PRATAP A，AGARW AL S，et al.A fast and elitist multi-ob jective genetic algorithm:NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）: 182-197.

毕晓君：女，1964年生，教授，博士生导师，主要研究方向为智能信号处理、数字图像处理、人工智能、机器学习等.

张磊：男，1987年生，博士生，研究方向为智能信号处理、约束多目标优化.

Constrained Multi-objective Optim ization Algorithm with Adap tivee Truncation Strategy

BIXiaojun ZHANG Lei
（College of Information and Communications Engineering，Harbin Engineering University，Harbin 150001，China）

To im prove distribution and convergence of the obtained solution set in constrained multi-ob jective op tim ization p rob lem s，this paper presents a constrained multi-ob jective op tim ization algorithm based on adaptive εtruncation strategy.Firstly，th rough the proposedεtruncation strategy，the Pareto optim al solutions and the in feasib le solutions with low constraint violation and good ob jective function values are retained to im prove diversity.Besides，both diversity and convergence are coordinated.Second ly，the exponential variation is added for further enhancing the local exploitation ability after mutation and crossover operation.Finally，the im proved crowding density estimation chooses a part of the Pareto optimal individuals and the near individuals to take part in the calcu lation，thus it not on ly assesses the distribution of the solution setmore accurately，bu t also reduces the com putational quantity.The com parative experim ent resu lts w ith another four excellent constrained multiob jective algorithm s on the standard constrained multi-ob jective op tim ization p rob lem s（CTP series）show that diversity and convergence of the proposed algorithm are imp roved，and it has certain advantages com pared with these algorithm s.

Constrained mu lti-ob jectiveoptim ization；Constraint hand ling technique；εtruncation；Distribution；Convergence

The National Natural Science Foundation of China（61175126）

TP18

A

1009-5896（2016）08-2047-07

10.11999/JEIT 151237

2015-11-05；改回日期：2016-03-17；网络出版：2016-05-05

张磊zl12306124@163.com

国家自然科学基金资助项目（61175126）