计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (11): 280-291.doi: 10.11896/jsjkx.230900007

• 人工智能 • 上一篇    下一篇

基于非欧几何权向量产生策略的分解多目标优化算法

孙良旭1, 李林林1, 刘国莉2   

  1. 1 辽宁科技大学计算机与软件工程学院 辽宁 鞍山 114051
    2 沈阳工业大学机械工程学院 沈阳 110300
  • 收稿日期:2023-09-04 修回日期:2024-01-08 出版日期:2024-11-15 发布日期:2024-11-06
  • 通讯作者: 孙良旭(sunliangxumail@163.com)
  • 基金资助:
    国家自然科学基金(61903169,71301066);辽宁省教育厅项目(2020LNQN05);辽宁省振兴人才计划(XLYC2007182)

Decomposition Multi-objective Optimizaiton Algorithm with Weight Vector Generation StrategyBased on Non-Euclidean Geometry

SUN Liangxu1, LI Linlin1, LIU Guoli2   

  1. 1 College of Computer and Software Engineering,University of Science and Technology Liaoning,Anshan,Liaoning 114051,China
    2 College of Mechanical Engineering,Shenyang University of Technology,Shenyang 110300,China
  • Received:2023-09-04 Revised:2024-01-08 Online:2024-11-15 Published:2024-11-06
  • About author:SUN Liangxu,born in 1979,Ph.D,associate professor.His main research intere-sts include multi-objective evolutionary algorithm and production scheduling.
  • Supported by:
    National Natural Science Foundation of China(61903169,71301066),Liaoning Provincial Education Department Project(2020LNQN05) and Liaoning Revitalization Talents Program(XLYC2007182).

PDF (PC)

218

摘要： 随着目标数量的增加,多目标优化问题(Multi Objective Problems,MOPs)的求解越来越困难。基于分解的多目标进化算法表现出更好的性能,但在求解具有复杂Pareto前沿的MOPs时,此类算法易出现种群多样性不足、算法性能下降等问题。为了解决这些问题,提出了一种基于非欧几何权向量产生策略的分解多目标优化算法,通过在非欧几何空间中拟合非支配前沿并进行参数估计,再利用对非支配解目标变量的正态统计采样生成权向量,以此引导种群的进化方向并保持种群的多样性。同时在非欧几何空间中周期性重新确定子问题的邻域,提高分解算法协同进化的效率,进而提高算法的性能。基于MaF基准测试函数的实验结果表明,相比MOEA/D,NSGA-III和AR-MOEA算法,所提算法在求解多目标和众目标优化问题方面具有明显的优势。

关键词: 分解, 多目标, 权向量, 非支配前沿, 非欧几何

Abstract: With the increase of the number of objectives,mult-objective problems(MOPs) are more and more difficult to solve.Decomposition-based multi-objective evolutionary algorithms show better performance.However,when solving MOPs with complex Pareto fronts,decomposition-based algorithms show poor diversity in population and the performance deteriorates.To address these issues,this paper proposes a decomposition multi-objective optimization algorithm with weight vector generation strategy based on non-Euclidean geometry.By fitting the non-dominated frontier in the non-Euclidean geometric space and estimating the parameters,the normal statistical sampling of the target variable of the non-dominated solution is used to generate the weight vector,so as to guide the evolution direction of the population and maintain the diversity of the population.Meanwhile,the neighborhood of sub-problems can be rebuilt periodically,to improve the efficiency of the co-evolution of decomposition algorithm and improve the performance of the algorithm.Experiment results based on the MaF benchmark test problems show that,compared with MOEA/D,NSGA-III and AR-MOEA algorithms,the proposed algorithm has significant performance in solving multi-objective optimization problems.

Key words: Decomposition, Multi objective, Weight vector, Non-dominated front, Non-Euclidean geometry

中图分类号: 

  • TP391
[1] SOFIA A S,GANESHKUMAR P.Multi-Objective Task Sche-duling to Minimize Energy Consumption and Makespan of Cloud Computing Using NSGA-II[J].Journal of Network and Systems Management,2018,26(2):463-485.
[2] BABAJAMALI Z,KHABAZ M,AGHADAVOUDI F,et al.Pareto Multi-Objective Optimization of Tandem Cold Rolling Settings for Reductions and Inter Stand Tensions Using NSGA-II[J].ISA Transactions,2022,130:399-408.
[3] BANSAL J C,SETHI N,ANICHO O,et al.Drone Flocking Op-timization Using NSGA-II and Principal Component Analysis[J].Swarm Intelligence,2022,17:63-87.
[4] DENG W,ZHANG X X,ZHOU Y,et al.An Enhanced FastNon-Dominated Solution Sorting Genetic Algorithm for Multi-objective Problems[J].Information Sciences,2022,585:441-453.
[5] YANG Y K,LIU J C,TAN S B,et al.A Multi-objective Diffe-rential Evolution Algorithm Based on Domination and Constraint-handling Switching[J].Information Sciences,2021,579:796-813.
[6] MA H P,ZHANG Y J,SUN S Y,et al.A Comprehensive Sur-vey on NSGA-II for Multi-objective Optimization and Applications[J].Artificial Intelligence Review,2023,56(12):15217-15270.
[7] GUERREIRO A P,FONSECA C M,PAQUETE L.The Hyper-volume Indicator:Problems and Algorithms[J].ACM Computing Surveys,2021,54(6):1-42.
[8] ZAPOTECAS-MARTÍNEZ S,LÓPEZ-JAIMES A,GARCÍA-NÁJERA A.LIBEA:A Lebesgue Indicator-Based Evolutionary Algorithm for Multi-objective Optimization[J].Swarm & Evolutionary Computation,2019,44:404-419.
[9] ZAPOTECAS-MARTÍNEZ S,GARCÍA-NÁJERA A,MEN-CHACA-MÉNDEZ A.Improved Lebesgue Indicator-based Evo-lutionary Algorithm:Reducing Hypervolume Computations[J].Mathematics,2022,10(1):1-25.
[10] ZHANG Q F,LI H.MOEA/D:A Multi-objective Evolutionary Algorithm based on Decomposition[J].IEEE Transaction on Evolutionary Computing,2007,11(6):712-731.
[11] CHENG R,JIN Y C,OLHOFER M,et al.A Reference Vector Guided Evolutionary Algorithm for Many-objective Optimization[J].IEEE Transaction on Evolutionary Computing,2016,20(5):773-791.
[12] 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 Transaction on Evolutionary Computing,2014,18(4):577-601.
[13] DAS I,DENNIS J E.Normal-Boundary Intersection:A NewMethod for Generating the Pareto Surface in Nonlinear Multi-criteria Optimization Problems[J].SIAM Journal on Optimization 1998,8(3):631-657.
[14] HUA Y C,LIU Q Q,HAO K R.A Survey of Evolutionary Algorithms for Multi-objective Optimization Problems with Irregular Pareto Fronts[J].IEEE/CAA Journal of Automatica Sinica,2021,8(2):303-318.
[15] DONG M G,LIU B,JING C.A Many-objective EvolutionaryAlgorithm Based on Decomposition with Dynamic Resource Allocation for Irregular Optimization[J].Frontiers of Information Technology & Electronic Engineering,2020,21(8):1171-1190.
[16] SRI SRINIVASA RAJU M,MALLIPEDDI R,DAS K N.ATwin-archive Guided Decomposition Based Multi/many-objective Evolutionary Algorithm[J].Swarm and Evolutionary Computation,2022,71:101082.
[17] DAI C,LEI X J,HE X G.A Decomposition-based EvolutionaryAlgorithm with Adaptive Weight Adjustment for Many-objective Problems[J].Soft Computing,2020,24:10597-10609.
[18] ZHAO C L,ZHOU Y R,HAO Y Y.Decomposition-based Evolutionary Algorithm with Dual Adjustments for Many-objective Optimization Problems[J].Swarm and Evolutionary Computation,2022,75(2):101168-101182.
[19] SUN Y H,XIAO K L,WANG S Q,et al.An Evolutionary Many-Objective Algorithm based on Decomposition and Hierarchical Clustering Selection[J].Applied Intelligence,2022,52(8):8464-8509.
[20] LIANG Z P,HOU W J,HUANG X,et al.Two New Reference Vector Adaptation Strategies for Many-Objective Evolutionary Algorithms[J].Information Sciences,2019,483:332-349.
[21] LI G,WANG G G,XIAO R B.A Novel Adaptive Weight Algorithm Based on Decomposition and Two-part Update Strategy for Many-objective Optimization[J].Information Sciences,2022(615):323-347.
[22] FAN R,WEI L X,LI X,et al.Self-Adaptive Weight BectorAdjustment Strategy for Decomposition-based Multi-Objective Differential Evolution Algorithm[J].Soft Computing,2020,24(17):13179-13195.
[23] TIAN Y,ZHANG X Y,CHENG R,et al.Guiding Evolutionary Multio-bjective Optimization with Generic Front Modeling[J].IEEE Transactions on Cybernetics,2020,50(3):1106-1119.
[24] LI L,YEN G G,SAHOO A,et al.On the Estimation of Pareto Front and Dimensional Similarity in Many-objective Evolutio-nary Algorithm[J].Information Sciences,2021,563:375-400.
[25] GUO X F,WANG Y P,GAO X Z.Two-stage Adaptive Weight Vector Design Method for Decomposition Based Many-objective Evolutionary Algorithm[J].International Journal of Ad Hoc and Ubiquitous Computing,2022,39(1/2):58-69.
[26] WU M Y,KWONG S,JIA Y H,et al.Adaptive Weights Gene-ration for Decomposition-based Multi-objective Optimization Using Gaussian Process Regression[C]//Proceedings of the Genetic and Evolutionary Computation Conference(GECCO’17).2017:641-648.
[27] WU M Y,LI K,KWONG S,et al.Learning to Decompose:AParadigm for Decomposition-based Multi-objective Optimization[J].IEEE Transaction on Evolutionary Computing,2019,23(3):376-390.
[28] GE H W,ZHAO M D,SUN L,et al.A Many-Objective Evolutionary Algorithm with Two Interacting Processes:Cascade Clustering and Reference Point Incremental Learning[J].IEEE Transactions on Evolutionary Computation,2019,23(4):572-586.
[29] LIU Y P,ISHIBUCHI H,MASUYAMA N,et al.Adapting Re-ference Vectors and Scalarizing Functions by Growing Neural Gas to Handle Irregular Pareto Fronts[J].IEEE Transaction on Evolutionary Computing,2020,24(3):439-453.
[30] LIU Q Q,JIN Y C,HEIDERICH M,et al.An Adaptive Refe-rence Vector Guided Evolutionary Algorithm Using Growing Neural Gas for Many-objective Optimization of Irregular Pro-blems[J].IEEE Transaction on Cybernetic,2022,52(5):2698-2711.
[31] THOMPSON A C.Minkowski Geometry[M].CambridgeUniversity Press,1996.
[32] PANICHELLA A.An Adaptive Evolutionary Algorithm Based on Non-Euclidean Ggeometry for Many-objective Optimization[C]//Proceedings of the Genetic and Evolutionary Computation Conference(GECCO’19).2019:595-603.
[33] BENALI F,BODÉNÈS D,RUNZ C D,et al.An EnhancedAdaptive Geometry Evolutionary Algorithm Using Stochastic Diversity Mechanism[C]//Proceedings of the Genetic and Evolutionary Computation Conference(GECCO’22).2022:476-483.
[34] TIAN Y,CHENG R,ZHANG X Y,et al.An Indicator BasedMulti-objective Evolutionary Algorithm with Reference Point Adaptation for Better Versatility[J].IEEE Transactions on Evo-lutionary Computation,2018,22(4):609-622.
[35] CHENG R,LI M Q,TIAN Y,et al.A Benchmark Test Suite for Evolutionary Many-objective Optimization[J].Complex & Intelligent Systems,2017,3:67-81.
[36] TIAN Y,CHENG R,ZHANG X Q,et al.PlatEMO:A MATLAB Platform for Evolutionary Multi-Objective Optimization[J].IEEE Computational Intelligence Magazine,2017,12(4):73-87.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发