计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (7): 194-206.doi: 10.11896/jsjkx.220600186

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

基于Kriging模型的改进型NSGA-III解决昂贵优化问题

耿焕同, 宋飞飞, 周征礼, 徐小涵   

  1. 南京信息工程大学计算机学院 南京 210044
  • 收稿日期:2022-06-21 修回日期:2022-11-12 出版日期:2023-07-15 发布日期:2023-07-05
  • 通讯作者: 耿焕同(htgeng@nuist.edu.cn)
  • 基金资助:
    国家自然科学基金(51977100)

Improved NSGA-III Based on Kriging Model for Expensive Many-objective Optimization Problems

GENG Huantong, SONG Feifei, ZHOU Zhengli, XU Xiaohan   

  1. School of Computer Science,Nanjing University of Information Science & Technology,Nanjing 210044,China
  • Received:2022-06-21 Revised:2022-11-12 Online:2023-07-15 Published:2023-07-05
  • About author:GENG Huantong,born in 1973,professor,Ph.D supervisor,is a senior member of China Computer Federation.His main research interests include computational intelligence,multi-objective optimization and meteorological data mi-ning.
  • Supported by:
    National Natural Science Foundation of China(51977100).

PDF (PC)

328

摘要： 在许多实际的优化问题中,为了进行适应度评估,其物理实验或数值仿真代价高昂,这给大多数现有的多目标进化算法(EAs)带来了巨大挑战。因此,文中提出了一种基于克里金模型辅助的改进参考点引导进化的优化算法,用于解决昂贵的超多目标优化问题。具体而言,根据种群的空间分布特征,借助关联点的熵差信息筛选参考点引导进化,以达到探索与开发的平衡。所提出的代理辅助进化算法(SAEA)使用克里金法来逼近每个目标函数,而无需进行原始昂贵的函数评估从而降低了计算成本。模型管理中采用一种纯指标填充采样准则,借助收敛性、多样性指标确定适当采样策略并使用昂贵目标函数对采样解进行真实评估以提升种群收敛与算法优化的效率。对具有3个以上目标的80个DTLZ与WFG基准测试问题进行了对比研究,证明了此算法的有效性和可行性。

关键词: 昂贵耗时问题, 进化算法, 代理辅助多目标优化, Kriging模型, 模型管理

Abstract: In many real world multi-objective optimization problems(MOP),the cost of physical experiments or numerical simulations for fitness evaluation is very expensive,which poses a great challenge to most existing multi-objective evolutionary algorithmEAs).Therefore,this paper proposes an improved reference point guided evolution optimization algorithm assisted by Kriging model to solve expensive many-objective optimization.Specifically,according to the distribution characteristics of the target spatial population,the reference points are selected to guide the evolution of the population to reach the balance of exploration and exploitation.The proposed surrogate-assisted evolution algorithm(SAEA) uses Kriging method to approximate each objective function without the need for the original expensive function evaluation to reduce computational cost.In model management,an infill sampling criterion is adopted to improve population convergence and algorithm optimization efficiency by evaluating convergence and diversity indexes to determine the appropriate sampling strategy for re-evaluation with expensive objective functions.The effectiveness and superiority of the proposed algorithm are proved by the empirical research on the benchmark problems with more than three objectives.

Key words: Expensive and time-consuming problems, Evolutionary algorithm, Surrogate-assisted multi-objective optimization, Kriging model, Model management

中图分类号: 

  • TP183
[1]ISHIBUCHI H,TSUKAMOTO N,NOJIMA Y.Evolutionary manyobjective optimization:A short review[C]//2008 IEEE Congress on Evolutionary Computation(IEEE World Congress on Computational Intelligence).Hong Kong,China,2008:2419-2426.
[2]GUO D,CHAI T,DING J,et al.Small data- driven evolutionary multi-objective optimization of fused magnesium furnaces[C]//2016 IEEE Symposium Series on Computational Intelligence(SSCI).2016:1-8.
[3]YANG S,LI M,LIU X,et al.A grid-based evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2013,17(5):721-736.
[4]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitistmultiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[5]CHENG R,JIN Y,OLHOFER M,et al.A reference vectorguided evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2016,20(5):773-791.
[6]LYGOE R J,CARY M, FLEMING P J.A real-word application of a many-objective optimization complexity reduction process[J].Evolutionary Multi-Criterion Optimization,Berlin:Sprin-ger,2013,7811:641-655.
[7]DEB K,JAIN H.An Evolutionary Many-Objective OptimizationAlgorithm 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.
[8]BADER J, ZITZLER E.HypE:An algorithm for fast hypervo-lume-based many-objective optimization[J].Evolutionary Computation,2011,19(1):45-76.
[9]ZHANG X,TIAN Y, JIN Y.A knee point driven evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(6):761-776.
[10]WANG H,JIAO L, YAO X.Two_arch2:An improved two-archive algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(4):524-541.
[11]JIN Y, SENDHOFF B.A systems approach to evolutionarymultiobjective structural optimization and beyond[J].IEEE Computational Intelligence Magazine,2009,4(3):62-76.
[12]OCHOA-ESTOPIERA L M,ENÍQUEZ-GUTIEEREZA V M,CHEN L,et al.Industrial application of surrogate models to optimize crude oil distillation units[J].Chemical Engineering Transactions,2018,69:289-294.
[13]JIN Y,WANG H,CHUGH T,et al.Data-driven evolutionary optimization:An overview and case studies[J].IEEE Transactions on Evolutionary Computation,2019,23(3):442-458.
[14]SUN Z R,HUANG Y H,CHEN Z Y.Diversity based surrogate-assisted evolutionary algorithm for expensive multi-objective optimization problem[J].Journal of Software,2021,32(12):3814-3828.
[15]ALAN D M,GREGORIO T,HUGO B,et al.A Review of Surrogate Assisted Multiobjective Evolutionary Algorithms[J].Computational Intelligence and Neuroscience,2016,2016-6-12:19.
[16]LIN M M,ZHOU H,WANG L P.Research of Many-objective Evolutionary Algorithm Based on Alpha Dominance[J].Computer Science,2017,44(1):264-270.
[17]JIN Y.Surrogate-assisted evolutionary computation:Recent advances and future challenges[J].Swarm and Evolutionary Computation,2011,1(2):61-70.
[18]WAGNER T,BEUME N,NAUJOKS B.Pareto-,aggregation-,and indicator-based methods in many-objective optimization[J].Evolutionary Multi-Criterion Optimization,2007,4403:742-756.
[19]ZHANG J,ZHOU A,ZHANG G.A classification and Pareto domination based multiobjective evolutionary algorithm[C]//2015 IEEE Congress on Evolutionary Computation(CEC).2015:2883-2890.
[20]SUN Y,YEN G,YI Z.IGD indicator-based evolutionary algorithm for many-objective optimization problems[J].IEEE Transactions on Evolutionary Computation,2019,23(2):173-187.
[21]PONWEISER W,WAGNER T,BIERMANN D,et al.Multiobjective optimization on a limited budget of evaluations using model-assisted s-metric selection[C]//International Conference on Parallel Problem Solving from Nature.2008:784-794.
[22]KNOWLES J.ParEGO:A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation,2006,10(1):50-66.
[23]ZHANG Q,LIU W,TSANG E,et al.Expensive multiobjective optimization by MOEA/D with Gaussian process model[J].IEEE Transactions on Evolutionary Computation,2010,14(3):456-474.
[24]CHUGH T,JIN Y,MIETTINEN K,et al.A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2018,22(1):129-142.
[25]HABIB A,KUMAR S H,CHUGH T,et al.A multiple surrogate assisted decomposition-based evolutionary algorithm for expensive multi/many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2019,23(6):1000-1014.
[26]CHUGH T,SINDHYA K,MIETTINEN K,et al.On constraint handling in surrogate-assisted evolutionary many-objective optimization[C]//International Conference on Parallel Problem Solving from Nature.2016:214-224.
[27]WAGNER T,EMMERICH M,DEUTZ A,et al.On Expected-Improvement Criteria for Model-based Multi-objective Optimization[C]//Proceedings of the 11th International Conference on Parallel Problem Solving From Nature:Part I.Berlin:Springer,2010:718-727.
[28]LIU B,ZHANG Q, GIELEN G.A Gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems[J].IEEE Transactions on Evolutio-nary Computation,2014,18(2):180-192.
[29]COUCKUYT I,DESCHRIJVER D,DHAENE T.Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization[J].Journal of Global Optimization,2014,60(3):575-594.
[30]HERNANDEZ-LOBATO D,HERNANDEZ-LOBATA J, SHAHA.Predictive entropy search for multi-objective Bayesian optimization[C]//Proceedings of the 33rd International Conference on International Conference on Machine Learning.2016:1492-1501.
[31]BELAKARIA S, DESHWAL A.Max-value entropy search for multi-objective Bayesian optimization[C]//Neural Information Processing Systems.2019:1-30.
[32]JIN Y, SENDHOFF B.Reducing fitness evaluations using clustering techniques and neural network ensembles[C]//Genetic and Evolutionary Computation Conference.Seattle,2004:688-699.
[33]EMMERICH M,GIANNAKOGLOU K,NAUJOKS B.Single-and multiobjective evolutionary optimization assisted by Gaussian random field metamodels[J].IEEE Transactions on Evolutionary Computation,2006,10(4):421-439.
[34]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,33(3):191-201.
[35]SONG Z,WANG H,HE C,et al.A Kriging-Assisted Two-Archive Evolutionary Algorithm for Expensive Many-Objective Optimization[J].IEEE Transactions on Evolutionary Computation,2021,25(6):1013-1027.
[36]MCKAY M D,CONOVER R J B J.A comparison of threemethods for selecting values of input variables in the analysis of output from a computer code[J].Technometrics,1979,42(1):55-61.
[37]WANG X L,JIN Y C,SCHMITT S,et al.An adaptive Bayesian approach to surrogate-assisted evolutionary multi-objective optimization[J].Information Sciences,2020,519:317-331.
[38]PAN L,HE C,TIAN Y,et al.A classification based surrogate-assisted evolutionary algorithm for expensive many-objective optimization [J].IEEE Transactions on Evolutionary Computation,2019,23(1):74-88.
[39]GUO D,WANG X,GAO K,et al.Evolutionary Optimization of High-Dimensional Multiobjective and Many-Objective Expensive Problems Assisted by a Dropout Neural Network[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2021,52(4):2084-2097.
[40]GUO D,JIN Y,DING J,et al.Heterogeneous ensemble-based infill criterion for evolutionary multiobjective optimization of expensive problems[J].IEEE Transactions on Cybernetics,2019,49(3):1012-1025.
[41]TIAN Y,CHENG R,ZHANG X,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
本系统由北京玛格泰克科技发展有限公司设计开发