面向约束超多目标优化的双阶段搜索策略研究

doi:10.3778/j.issn.1002-8331.2207-0167

摘要/Abstract

摘要： 解决约束超多目标优化问题的关键在于约束处理和均衡收敛性与多样性，搜索空间中的约束阻碍种群寻找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距离

Abstract: In dealing with constrained many-objective optimization problems, a key issue of evolutionary algorithms is constraint handling and the tradeoffs between convergence anddiversity. However, the constraints in the search space hinder the population from finding the Pareto front, which tends to make the population fall into a local optimum, while the discrete 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 objective function and the population is not constrained to approach the Pareto front direction rapidly. Secondly, the constraint violation degree is treated as a new objective function to solve the original constraint problem by objective transformation. A combined operator consisting of the simulated binary crossover operator and the DE/current-to-pbest/1 operator is used in the search process to generate individuals with excellent convergence and diversity. To verify the strategy effectiveness, AGE-MOEA combined with TSCO（TSCOEA） is compared with four state-of-the-art constrained many-objective evolutionary algorithms on the C_DTLZ, DC_DTLZ, and MW test suites. Experiments show that TSCOEA obtains better population convergence and diversity on most problems.

Key words: constrained many-objective optimization, evolutionary algorithm, two-stage search, combined operator, Minkowski distance

耿焕同, 周征礼, 沈俊烨, 宋飞飞. 面向约束超多目标优化的双阶段搜索策略研究[J]. 计算机工程与应用, 2023, 59(7): 80-91.

GENG Huantong, ZHOU Zhengli, SHEN Junye, SONG Feifei. Research onTwo-Stage Search Strategy for Constrained Many-Objective Optimization[J]. Computer Engineering and Applications, 2023, 59(7): 80-91.

参考文献

[1] 李智勇，黄滔，陈少淼，等.约束优化进化算法综述[J].软件学报，2017，28（6）：1529-1546.
LI Z Y，HUANG T，CHEN S M，et al.Overview of constrained optimization evolutionary algorithms[J].Journal of Software，2017，28（6）：1529-1546.
[2] MALA-JETMAROVA H，SULTANOVA N，SAVIC D.Lost in optimisation of water distribution systems? a literature review of system design[J].Environmental Modelling & Software，2018，93：209-254.
[3] 易灵芝，林佳豪，刘建康，等.改进自适应MOEA/D算法的楼宇负荷优化调度[J].计算机工程与应用，2022，58（2）：295-302.
YI L Z，LIN J H，LIU J K，et al.Improved adaptive MOEA/D algorithm for building load optimization scheduling[J].Computer Engineering and Applications，2022，58（2）：295-302.
[4] JAIN H，DEB K.An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach，part II：handling constraints and extending to an adaptive approach[J].IEEE Transactions on Evolutionary Computation，2013，18（4）：602-622.
[5] DEB K，JAIN H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach，part I：solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation，2014，18（4）：577-601.
[6] PANICHELLA A.An adaptive evolutionary algorithm based on non-Euclidean geometry for many-objective optimization[C]//Proceedings of the Genetic and Evolutionary Computation Conference，2019：595-603.
[7] 谢承旺，余伟伟，郭华，等.DAV-MOEA：一种采用动态角度向量支配关系的高维多目标进化算法[J].计算机学报，2022，45（2）：317-333.
XIE C W，YU W W，GUO H，et al.DAV-MOEA：a many-objective evolutionary algorithm adopting dynamic angle vector based dominance relation[J].Chinese Journal of Computers，2022，45（2）：317-313.
[8] ZHANG Q，LI H.MOEA/D：a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.
[9] CHENG R，JIN Y，OLHOFER M，et al.A reference vector guided evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2016，20（5）：773-791.
[10] 耿焕同，戴中斌，王天雷，等.基于参考点选择策略的改进型NSGA-III算法[J].模式识别与人工智能，2020，33（3）：191-201.
GENG H T，DAI Z B，WANG T L，et al.Improved NSGA-III algorithm based on reference point selection strategy[J].Pattern Recognition and Artificial Intelligence，2020，3（3）：191-201.
[11] BADER J，ZITZLER E.HypE：an algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation，2011，19（1）：45-76.
[12] TIAN Y，CHENG R，ZHANG X，et al.An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility[J].IEEE Transactions on Evolutionary Computation，2017，22（4）：609-622.
[13] DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.
[14] TAKAHAMA T，SAKAI S.Efficient constrained optimization by the ε constrained adaptive differential evolution[C]//Proceedings of IEEE Congress on Evolutionary Computation，2010：1-8.
[15] JIAO R，ZENG S，LI C，et al.Handling constrained many-objective optimization problems via problem transformation[J].IEEE Transactions on Cybernetics，2020，51（10）：4834-4847.
[16] JIAO R，ZENG S，LI C，et al.Two-type weight adjustments in MOEA/D for highly constrained many-objective optimization[J].Information Sciences，2021，578：592-614.
[17] LI K，CHEN R，FU G，et al.Two-archive evolutionary algorithm for constrained multiobjective optimization[J].IEEE Transactions on Evolutionary Computation，2018，23（2）：303-315.
[18] XIANG Y，YANG X，HUANG H，et al.Balancing constraints and objectives by considering problem types in constrained multiobjective optimization[J].IEEE Transactions on Cybernetics，2023，53（1）：88-101.
[19] DEB K，AGRAWAL R B.Simulated binary crossover for continuous search space[J].Complex Systems，1995，9（2）：115-148.
[20] DEB K，GOYAL M.A combined genetic adaptive search（GeneAS） for engineering design[J].Computer Science and Informatics，1996，26：30-45.
[21] DAS S，SUGANTHAN P N.Differential evolution：a survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation，2010，15（1）：4-31.
[22] ISHIBUCHI H，SETOGUCHI Y，MASUDA H，et al.Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes[J].IEEE Transactions on Evolutionary Computation，2016，21（2）：169-190.
[23] THOMPSON A C，THOMPSON A C.Minkowski geometry[M].Cambridge：Cambridge University Press，1996.
[24] ALEFELD G.On the convergence of Halley’s method[J].The American Mathematical Monthly，1981，88（7）：530-536.
[25] TIAN Y，CHENG R，ZHANG X，et al.PlatEMO：a Matlab platform for evolutionary multi-objective optimization[educational forum][J].IEEE Computational Intelligence Magazine，2017，12（4）：73-87.
[26] MA Z，WANG Y.Evolutionary constrained multiobjective optimization：test suite construction and performance comparisons[J].IEEE Transactions on Evolutionary Computation，2019，23（6）：972-986.
[27] BOSMAN P A N，THIERENS D.The balance between proximity and diversity in multiobjective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation，2003，7（2）：174-188.
[28] WANG W，LI K，TAO X，et al.An improved MOEA/D algorithm with an adaptive evolutionary strategy[J].Information Sciences，2020，539：1-15.
[29] WANG H，JIN Y，YAO X.Diversity assessment in many-objective optimization[J].IEEE Transactions on Cybernetics，2016，47（6）：1510-1522.
[30] TIAN Y，CHENG R，ZHANG X，et al.Diversity assessment of multi-objective evolutionary algorithms：Performance metric and benchmark problems[research frontier][J].IEEE Computational Intelligence Magazine，2019，14（3）：61-74.