基于目标相似性驱动与双端变量引导搜索的大规模多目标进化算法

doi:10.11896/jsjkx.250200091

摘要/Abstract

摘要： 大规模多目标优化问题涉及成百上千维的决策变量,致使探索空间过于庞大,这给进化算法在有限资源内快速得到理想解集合带来了巨大挑战。为此,提出一种基于目标相似性驱动与双端变量引导搜索的大规模多目标进化算法(LMOEA/OS-DES)。LMOEA/OS-DES包含3种策略:第一种是基于目标相似性驱动的多种群共同进化策略,以快速得到反映Pareto最优解分布特点的解;第二种策略根据精英解在决策空间上的分布特点,设计多种决策变量分组方案,以适应不同目标向量方向最优解的分布差异,再结合分组方案,增强探索性的双端变量引导搜索采取较之前策略更大的探索强度,生成与先前精英解分布特点相近的新解,以加速优化收敛性与多样性;在最后一种策略中,借助竞争群优化在优解周围探索,以优化多样性。将LMOEA/OS-DES与其他8个具有竞争力的算法,在100至5 000维的LSMOP及UF问题上进行对比实验。结果表明,LMOEA/OS-DES具有显著优势。

关键词: 进化算法, 大规模多目标优化, 多种群优化, 问题转换, 竞争群优化

Abstract: Large-scale multi-objective optimization problems (LSMOPs) involve a large number of decision variables,resulting in expansive search spaces that make them challenging for traditional evolutionary algorithms to find good solutions efficiently within limited resources.To address this,a large-scale multi-objective evolutionary algorithm based on objective similarity and dual-end variable guided search (LMOEA/OS-DES) is proposed.LMOEA/OS-DES includes three strategies.The first strategy is the co-evolution of multiple swarms driven by objective similarity in order to quickly obtain solutions that reflects the distribution characteristics of Pareto optimal solution set.The second strategy is to design various variable grouping schemes based on the distribution characteristics of elite solutions in the decision space,so as to adapt to the differences between the distribution of optimal solutions for different objective vector directions.Combined with the grouping schemes,the dual-end variable guided search generates new solutions with distribution characteristics similar to the previous elite solutions,which enables it to adopt larger variations than the previous strategy,explore more regions faster,and accelerate the optimization of convergence and diversity.In the final strategy,it uses the competitive swarm optimization to explore the regions around elite solutions,so as to rapidly optimize diversity.Comparative experiments with eight other competitive algorithms on LSMOP and UF with dimensions ranging from 100 to 5 000 demonstrate that LMOEA/OS-DES has strong advantages.

Key words: Evolutionary algorithm, Large-scale multi-objective optimization, Multi-swarm optimization, Problem transformation, Competitive swarm optimization

中图分类号:

TP301

杨昌好, 秦进, 王豪. 基于目标相似性驱动与双端变量引导搜索的大规模多目标进化算法[J]. 计算机科学, 2026, 53(3): 351-365. https://doi.org/10.11896/jsjkx.250200091

YANG Changhao, QIN Jin, WANG Hao. Large-scale Multi-objective Evolutionary Algorithm Based on Objective Similarity and Dual-EndVariable Guided Search[J]. Computer Science, 2026, 53(3): 351-365. https://doi.org/10.11896/jsjkx.250200091

参考文献

[1]JIN Y C,OKABE T,SENDHOFF B.Neural network regularization and ensembling using multi-objective evolutionary algorithms[C]//Proceedings of the 2004 Congress on Evolutionary Computation.2004:1-8.
[2]LI H,ZHANG Q F,DENG J D,et al.A preference-based multiobjective evolutionary approach for sparse optimization[J].IEEE Transactions on Neural Networks and Learning Systems,2018,29(5):1716-1731.
[3]TOSCANO-PULIDO G,RAZAVI H,NEJADHASHEMI A P,et al.Large-scale multiobjective optimization for watershed planning and assessment[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2024,54(6):3471-3483.
[4]WANG H F,CHEN L,HAO X X,et al.Learning-guided cross-sampling for large-scale evolutionary multi-objective optimization[J].Swarm and Evolutionary Computation,2024,91:101763.
[5]MIGUEL A L,COELLO C A C.Use of cooperative coevolution for solving large scale multiobjective optimization problems[C]//2013 IEEE Congress on Evolutionary Computation.2013:2758-2765.
[6]MA X L,LIU F,QI Y T,et al.A multiobjective evolutionary algorithm based on decision variable analyses for multiobjective optimization problems with large-scale variables[J].IEEE Transactions on Evolutionary Computation,2016,20(2):275-298.
[7]CAO B,ZHAO J W,GU Y.Applying graph-based differentialgrouping for multiobjective large-scale optimization[J].Swarm and Evolutionary Computation,2020,53:100626.
[8]LIU J,LIU R C,ZHANG X L.Recursive grouping and dynamic resource allocation method for large-scale multi-objective optimization problem[J].Applied Soft Computing,2022,130:109651.
[9]ZHANG X Y,TIAN Y,CHENG R,et al.A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2018,22(1):97-112.
[10]XU Y,XU C,ZHANG H,et al,A multi-population multi-objective evolutionary algorithm based on the contribution of decision variables to objectives for large-scale multi/many-objective optimization[J].IEEE Transactions on Cybernetics,2023,53(11):6998-70007.
[11]MA L B,HUANG M,YANG S X,et al.An adaptive localized decision variable analysis approach to large-scale multiobjective and many-objective optimization[J].IEEE Transactions on Cybernetics,2022,52(7):6684-6696.
[12]HE C,CHENG R,LI L H,et al.Large-scale multiobjective opti-mization via reformulated decision variable analysis[J].IEEE Transactions on Evolutionary Computation,2024,28(1):47-61.
[13]ZILLE H,ISHIBUCHI H,MOSTAGHIM S,et al.A framework for large-scale multiobjective optimization based on problem transformation[J].IEEE Transactions on Evolutionary Computation,2018,22(2):260-275.
[14]LIU S B,LIN Q Z,WONG K C,et al.Evolutionary large-scale multiobjective optimization:benchmarks and algorithms[J].IEEE Transactions on Evolutionary Computation,2023,27(3):401-415.
[15]HE C,LI L H,TIAN Y,et al.Accelerating large-scale multi-objective optimization via problem reformulation[J].IEEE Transactions on Evolutionary Computation,2019,23(6):949-961.
[16]JIANG S W,ZHANG J,ONG Y S,et al.A simple and fast hy-pervolume indicator-based multiobjective evolutionary algorithm[J].IEEE Transactions on Cybernetics,2015,45(10):2202-2213.
[17]QIN S F,SUN C L,JIN Y C,et al.Large-scale evolutionarymultiobjective optimization assisted by directed sampling[J].IEEE Transactions on Evolutionary Computation,2021,25(4):724-738.
[18]TIAN Y,ZHENG X T,ZHANG X Y,et al.Efficient large-scale multiobjective optimization based on a competitive swarm optimizer[J].IEEE Transactions on Cybernetics,2019,50(8):3696-3708.
[19]SUN Y,JIANG D J.An improved problem transformation algorithm for large-scale multi-objective optimization[J].Swarm and Evolutionary Computation,2024,89:101622.
[20]LI B D,ZHANG Y,YANG P,et al.A two-population algorithm for large-scale multi-objective optimization based on fitness-aware operator and adaptive environmental selection[J].IEEE Transactions on Evolutionary Computation,2025,29(3):631-645.
[21]LI D Y,WANG L,LI L,et al.A large-scale multiobjective particle swarm optimizer with enhanced balance of convergence and diversity[J].IEEE Transactions on Cybernetics,2024,54(3):1596-1607.
[22]YANG X,ZOU J,YANG S X,et al.A fuzzy decision variables framework for large-scale multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2023,27(3):445-459.
[23]HE C,CHENG R,YAZDANI D.Adaptive offspring generation for evolutionary large-scale multiobjective optimization[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2022,52(2):786-798.
[24]TIAN Y,LI X P,MA H P,et al.Deep reinforcement learning based adaptive operator selection for evolutionary multi-objective optimization[J].IEEE Transactions on Emerging Topics in Computational Intelligence,2022,7(4):1051-1064.
[25]DENG Q,KANG Q,ZHANG L,et al.Objective space-basedpopulation generation to accelerate evolutionary algorithms for large-scale many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2023,27(2):326-340.
[26]WANG S T,ZHENG J H,ZOU Y J,et al.A population hierarchical-based evolutionary algorithm for large-scale many-objective optimization[J].Swarm and Evolutionary Computation,2024,91:101752.
[27]LIU S B,LI J,LIN Q Z,et al.Learning to accelerate evolutio-nary search for large-scale multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2023,27(1):67-81.
[28]FARIAS L R C,ARAÚJO A F R.IM-MOEA/D:An inversemodeling multi-objective evolutionary algorithm based on decomposition[C]//2021 IEEE International Conference on Systems,Man,and Cybernetics (SMC).2021:462-467.
[29]CHEN H K,CHENG R,WEN J M,et al.Solving large-scale many-objective optimization problems by covariance matrix adaptation evolution strategy with scalable small subpopulations[J].Information Sciences,2020,509:457-469.
[30]WANG S,ZHOU A M,ZHANG G X,et al.Learning regularity for evolutionary multiobjective search:a generative model-based approach[J].IEEE Computational Intelligence Magazine,2023,18(4):29-42.
[31]LIU S B,LI J,LIN Q Z,et al.Evolutionary large-scale multi-objective optimization via autoencoder-based problem transformation[J].IEEE Transactions on Emerging Topics in Computational Intelligence,2024,8(4):2709-2722.
[32]WANG Z J,ZHAN Z H,KWONG S,et al.Adaptive granularity learning distributed particle swarm optimization for large-scale optimization[J].IEEE Transactions on Cybernetics,2021,51(3):1175-1188.
[33]WANG X J,WANG F,QI H,et al.A multi-swarm optimizerwith a reinforcement learning mechanism for large-scale optimization[J].Swarm and Evolutionary Computation,2024,86:101486.
[34]VAN AELST S,WANG X G,ZAMAR R H,et al.Lineargrouping using orthogonal regression[J].Computational Statistics and Data Analysis,2006,50(5):1287-1312.
[35]OMIDVAR M N,LI X D,YANG Z Y,et al.Cooperative co-evolution for large scale optimization through more frequent random grouping[C]//IEEE Congress on Evolutionary Computation.2010:1-8.
[36]CHEN W X,WEISE T,YANG Z Y,et al.Large-scale global optimization using cooperative coevolution with variable interaction learning[M]//Parallel Problem Solving from Nature,PPSN XI.Berlin:Springer,2010:300-309.
[37]OMIDVAR M N,LI X D,MEI Y,et al.Cooperative co-Evolution with differential grouping for large scale optimization[J].IEEE Transactions on Evolutionary Computation,2014,18(3):378-393.
[38]LIU R C,LIU J,LI Y F,et al.A random dynamic grouping based weight optimization framework for large-scale multi-objective optimization problems[J].Swarm and Evolutionary Computation,2020,55:100684.
[39]FIELDSEND J E,EVERSON R M,SINGH S.Using uncon-strained elite archives for multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2003,7(3):305-323.
[40]CHENG R,JIN Y C,OLHOFER M.A reference vector guided evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2016,20(5):773-791.
[41]MING F,GONG W Y,WANG L.A two-stage evolutionary algorithm with balanced convergence and diversity for many-objective optimization[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems.2022,52(10):6222-6234.
[42]LI K W,ZHANG T,WANG R.Deep reinforcement learning for multiobjective optimization[J].IEEE Transactions on Cyberne-tics,2021,51(6):3103-3114.
[43]ZHANG Q F,LI H.MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[44]LI M Q,YANG S X,LIU X H.Shift-based density estimation for Pareto-based algorithms in many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2014,18(3):348-365.
[45]CHENG R,JIN Y C,OLHOFER M,et al.Test Problems for Large-Scale Multiobjective and Many-Objective Optimization[J].IEEE Transactions on Cybernetics,2017,47(12):4108-4121.
[46]ZHANG Q F,ZHOU A M,ZHAO S,et al.Multiobjective optimization Test Instances for the CEC 2009 Special Session and Competition[EB/OL].https://www.alroomi.org/multimedia/CEC_Database/CEC2009/MultiObjectiveEA/CEC2009_MultiObjectiveEA_TechnicalReport.pdf.
[47]TIAN Y,CHENG R,ZHANG X Y.PlatEMO:A MATLABPlatform for Evolutionary Multi-Objective Optimization [Educational Forum][J].IEEE Computational Intelligence Magazine,2017,12(4):73-87.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed