Computer Science ›› 2023, Vol. 50 ›› Issue (7): 194-206.doi: 10.11896/jsjkx.220600186

• Artificial Intelligence • Previous Articles     Next Articles

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).

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

CLC Number: 

  • 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.
[1] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[2] LI Li, LI Guang-peng, CHANG Liang, GU Tian-long. Survey of Constrained Evolutionary Algorithms and Their Applications [J]. Computer Science, 2021, 48(4): 1-13.
[3] ZHOU Sheng-yi, ZENG Hong-wei. Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution [J]. Computer Science, 2021, 48(12): 107-116.
[4] ZHAO Yang, NI Zhi-wei, ZHU Xu-hui, LIU Hao, RAN Jia-min. Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform [J]. Computer Science, 2021, 48(11A): 30-38.
[5] ZHU Han-qing, MA Wu-bin, ZHOU Hao-hao, WU Ya-hui, HUANG Hong-bin. Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms [J]. Computer Science, 2021, 48(10): 343-350.
[6] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[7] CHEN Meng-hui, CAO Qian-feng and LAN Yan-qi. Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem [J]. Computer Science, 2020, 47(6A): 108-113.
[8] YANG Hao, CHEN HONG-mei. Mixed-sampling Method for Imbalanced Data Based on Quantum Evolutionary Algorithm [J]. Computer Science, 2020, 47(11): 88-94.
[9] XIE Teng-yu,ZHOU Xiao-gen,HU Jun,ZHANG Gui-jun. Contact Map-based Residue-pair Distances Restrained Protein Structure Prediction Algorithm [J]. Computer Science, 2020, 47(1): 59-65.
[10] GENG Huan-tong, HAN Wei-min, ZHOU Shan-sheng, DING Yang-yang. MOEA/D Algorithm Based on New Neighborhood Updating Strategy [J]. Computer Science, 2019, 46(5): 191-197.
[11] JIN Ting, TAN Wen-an, SUN Yong, ZHAO Yao. Social Team Formation Method Based on Fuzzy Multi-objective Evolution [J]. Computer Science, 2019, 46(2): 315-320.
[12] LIU Xin-ping, GU Chun-hua, LUO Fei, DING Wei-chao. Improved NSGA-II Algorithm Based on Loser Group and Hybrid Coding Strategy [J]. Computer Science, 2019, 46(10): 222-228.
[13] LAI Wen-xing, DENG Zhong-min. Improved NSGA2 Algorithm Based on Dominant Strength [J]. Computer Science, 2018, 45(6): 187-192.
[14] CHEN Jin-yin, XIONG Hui, ZHENG Hai-bin. Parameters Optimization for SVM Based on Particle Swarm Algorithm [J]. Computer Science, 2018, 45(6): 197-203.
[15] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem [J]. Computer Science, 2018, 45(4): 76-82.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!