面向高维多目标优化的双阶段双种群进化算法

doi:10.3778/j.issn.1002-8331.2307-0381

摘要/Abstract

摘要： 随着目标维度的上升，高维多目标优化问题的帕累托前沿越来越复杂，传统的基于分解的高维多目标进化算法难以挑选出多样性和收敛性良好的种群。针对以上问题提出了一种面向高维多目标优化的双阶段双种群进化算法。该算法将进化过程划分为两个阶段，在第一阶段判断帕累托前沿的形状是否规则，而在第二阶段则根据帕累前沿的形状选择是否对权重向量进行调整，以保证种群在规则及不规则帕累托前沿上都能获得良好的多样性。为了对权重向量进行调整且不影响算法的收敛性，该算法使用了两个种群进行进化，一个主种群正常进化，另一个辅种群作为权重向量。为了在不规则的帕累托前沿上获得一组适应种群分布的权重向量，引入了自然界中能量平衡的概念收集了多样性良好的辅种群作为权重向量。将提出的算法与其他算法在3-10目标的测试问题上进行比较。实验结果表明，提出的算法在大多数测试问题上性能优于比较的算法。

关键词: 高维多目标优化, 进化算法, 双阶段, 双种群, 权重向量, 能量平衡

Abstract: As the number of objectives increases, the Pareto front of many-objective optimization problem becomes increasingly complex. Traditional decomposition-based many-objective evolutionary algorithms struggle to select populations with both good diversity and convergence characteristics. To address this issue, a novel dual-stage dual-population evolutionary algorithm for many-objective optimization is proposed. In this algorithm, the evolutionary process is divided into two stages. In the first stage, it determines whether the shape of the Pareto front is regular. In the second stage, it adjusts the weight vectors based on the shape of the Pareto front, ensuring that the population can achieve good diversity on both regular and irregular Pareto fronts. To perform weight vector adjustments without affecting the convergence of the algorithm, two populations are used for evolution：one main population evolves normally, and the other auxiliary population serves as the weight vectors. Finally, to obtain a set of weight vectors that adapt well to populations distributed on irregular Pareto fronts, the concept of energy balance in nature is introduced to collect a well-diverse auxiliary population as weight vectors. The proposed algorithm is compared with other algorithms on test problems with 3-10 objectives. Experimental results demonstrate that the proposed algorithm outperforms the compared algorithms on the majority of the test problems.

Key words: many-objective optimization, evolutionary algorithm, dual-stage, dual-population, weight vector, energy balance

曹嘉乐, 杨磊, 田井林, 李华德, 李康顺. 面向高维多目标优化的双阶段双种群进化算法[J]. 计算机工程与应用, 2024, 60(9): 159-171.

CAO Jiale, YANG Lei, TIAN Jinglin, LI Huade, LI Kangshun. Dual-Stage Dual-Population Evolutionary Algorithm for Many-Objective Optimization[J]. Computer Engineering and Applications, 2024, 60(9): 159-171.

参考文献

[1] 易灵芝, 林佳豪, 刘建康, 等. 改进自适应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.
[2] 顾清华, 骆家乐, 李学现. 基于小生境的多目标进化算法[J]. 计算机工程与应用, 2023, 59(1): 126-139.
GU Q H, LUO J L, LI X X. Evolutionary algorithm based on niche for multi-objective optimization[J]. Computer Engineering and Applications, 2023, 59(1): 126-139.
[3] 安宇欣, 王转. 配送中心多区并行拣货系统投产顺序优化研究[J]. 计算机工程与应用, 2023, 59(7): 328-336.
AN Y X, WANG Z. Research on optimization of production sequence of multi-district parallel picking system in distribution center[J]. Computer Engineering and Applications, 2023, 59(7): 328-336.
[4] SHEN J, WANG P, WANG X. A controlled strengthened dominance relation for evolutionary many-objective optimization[J]. IEEE Transactions on Cybernetics, 2020, 52(5): 3645-3657.
[5] ZHU S, XU L, GOODMAN E D, et al. A new many-objective evolutionary algorithm based on generalized Pareto dominance[J]. IEEE Transactions on Cybernetics, 2021, 52(8): 7776-7790.
[6] ZHOU Y, LI S, PEDRYCZ W, et al. ACDB-EA: adaptive convergence-diversity balanced evolutionary algorithm for many-objective optimization[J]. Swarm and Evolutionary Computation, 2022, 75: 101145.
[7] CHEN G, LI J. A diversity ranking based evolutionary algorithm for multi-objective and many-objective optimization[J]. Swarm and Evolutionary Computation, 2019, 48: 274-287.
[8] BADER J, ZITZLER E. HypE: an algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45-76.
[9] SUN Y, YEN G G, YI Z. IGD indicator-based evolutionary algorithm for many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 173-187.
[10] ZITZLER E, THIELE L. Multiobjective optimization using evolutionary algorithms—a comparative case study[C]//International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 1998: 292-301.
[11] COELLO COELLO C A, REYES SIERRA M. A study of the parallelization of a convolutionary multi-objective evolutionary algorithm[C]//Proceedings of the Third Mexican International Conference on Artificial Intelligence, Mexico City, Mexico, April 26-30, 2004. Berlin, Heidelberg: Springer, 2004: 688-697.
[12] LIU Q, ZOU J, YANG S, et al. A multiobjective evolutionary algorithm based on decision variable classification for many-objective optimization[J]. Swarm and Evolutionary Computation, 2022, 73: 101108.
[13] LI J, WANG P, DONG H, et al. A two-stage surrogate-assisted evolutionary algorithm (TS-SAEA) for expensive multi/many-objective optimization[J]. Swarm and Evolutionary Computation, 2022, 73: 101107.
[14] WANG H, JIAO L, YAO X. Two_Arch2: an improved two-archive algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(4): 524-541.
[15] ZHANG Q, LI H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
[16] 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.
[17] SAXENA D K, DEB K. Non-linear dimensionality reduction procedures for certain large-dimensional multi-objective optimization problems: employing correntropy and a novel maximum variance unfolding[C]//International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg: Springer, 2007: 772-787.
[18] LIU S, LIN Q, WONG K C, et al. A self-guided reference vector strategy for many-objective optimization[J]. IEEE Transactions on Cybernetics, 2020, 52(2): 1164-1178.
[19] ZHAO C, ZHOU Y, HAO Y. Decomposition-based evolutionary algorithm with dual adjustments for many-objective optimization problems[J]. Swarm and Evolutionary Computation, 2022, 75: 101168.
[20] ZHANG C, TAN K C, LEE L H, et al. Adjust weight vectors in MOEA/D for bi-objective optimization problems with discontinuous Pareto fronts[J]. Soft Computing, 2018, 22: 3997-4012.
[21] LIU Y, GONG D, SUN J, et al. A many-objective evolutionary algorithm using a one-by-one selection strategy[J]. IEEE Transactions on Cybernetics, 2017, 47(9): 2689-2702.
[22] HARDIN D P, SAFF E B. Minimal Riesz energy point configurations for rectifiable d-dimensional manifolds[J]. Advances in Mathematics, 2005, 193(1): 174-204.
[23] AGGARWAL C C, HINNEBURG A, KEIM D A. On the surprising behavior of distance metrics in high dimensional space[C]//Proceedings of the 8th International Conference on Database Theory, London, UK, January 4-6, 2001. Berlin, Heidelberg: Springer, 2001: 420-434.
[24] DEB K, THIELE L, LAUMANNS M, et al. Scalable test problems for evolutionary multiobjective optimization[M]//Evolutionary multiobjective optimization: theoretical advances and applications. London: Springer, 2005: 105-145.
[25] HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506.
[26] CHENG R, LI M, TIAN Y, et al. A benchmark test suite for evolutionary many-objective optimization[J]. Complex & Intelligent Systems, 2017, 3: 67-81.
[27] 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.
[28] ZHANG X, TIAN Y, JIN Y. A knee point-driven evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(6): 761-776.
[29] XIANG Y, ZHOU Y, LI M, et al. A vector angle-based evolutionary algorithm for unconstrained many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 21(1): 131-152.
[30] DEB K, SINDHYA K, OKABE T. Self-adaptive simulated binary crossover for real-parameter optimization[C]//Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, 2007: 1187-1194.
[31] DEB K, GOYAL M. A combined genetic adaptive search (GeneAS) for engineering design[J]. Computer Science and Informatics, 1996, 26: 30-45.
[32] DERRAC J, GARCíA S, MOLINA D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18.
[33] MAO Z, LIU M. A local search-based many-objective five-element cycle optimization algorithm[J]. Swarm and Evolutionary Computation, 2022, 68: 101009.
[34] LIAO X, LI Q, YANG X, et al. Multiobjective optimization for crash safety design of vehicles using stepwise regression model[J]. Structural and Multidisciplinary Optimization, 2008, 35: 561-569.