Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A survey on handling computationally expensive multiobjective optimization problems with evolutionary algorithms

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

Evolutionary algorithms are widely used for solving multiobjective optimization problems but are often criticized because of a large number of function evaluations needed. Approximations, especially function approximations, also referred to as surrogates or metamodels are commonly used in the literature to reduce the computation time. This paper presents a survey of 45 different recent algorithms proposed in the literature between 2008 and 2016 to handle computationally expensive multiobjective optimization problems. Several algorithms are discussed based on what kind of an approximation such as problem, function or fitness approximation they use. Most emphasis is given to function approximation-based algorithms. We also compare these algorithms based on different criteria such as metamodeling technique and evolutionary algorithm used, type and dimensions of the problem solved, handling constraints, training time and the type of evolution control. Furthermore, we identify and discuss some promising elements and major issues among algorithms in the literature related to using an approximation and numerical settings used. In addition, we discuss selecting an algorithm to solve a given computationally expensive multiobjective optimization problem based on the dimensions in both objective and decision spaces and the computation budget available.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Aarts E, Lenstra JK (eds) (2003) Local search in combinatorial optimization. Princeton University Press, Princeton

    MATH  Google Scholar 

  • Ackley D (1987) A connectionist machine for genetic hillclimbing. Kluwer Academic Publishers, Boston

    Google Scholar 

  • Akhtar T, Shoemaker CA (2015) Multi objective optimization of computationally expensive multi-modal functions with RBF surrogates and multi-rule selection. J Glob Optim 64:17–32

    MathSciNet  MATH  Google Scholar 

  • Alexandrov NM, Dennis JE Jr, Lewis RM, Torczon V (1998) A trust-region framework for managing the use of approximation models in optimization. Struct Optim 15:16–23

    Google Scholar 

  • Arias-Montano A, Coello CAC, Mezura-Montes E (2010) MODE-LD+SS: A novel differential evolution algorithm incorporating local dominance and scalar selection mechanisms for multi-objective optimization. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1–8

  • Arias-Montano A, Coello CAC, Mezura-Montes E (2012) Multi-objective airfoil shape optimization using a multiple-surrogate approach. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1–8

  • Aytug H, Sayin S (2009) Using support vector machines to learn the efficient set in multiple objective discrete optimization. Eur J Oper Res 193:510–519

    MATH  Google Scholar 

  • Azzouz N, Bechikh S, Said LB (2014) Steady state IBEA assisted by MLP neural networks for expensive multi-objective optimization problems. In: Proceedings of the genetic and evolutionary computation conference, ACM, pp 581–588

  • Bäck T (1996) Evolutionary algorithms in theory and practice. Oxford University Press, New York

    MATH  Google Scholar 

  • Bandaru S, Ng AHC, Deb K (2014) On the performance of classification algorithms for learning Pareto-dominance relations. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1139–1146

  • Bandyopadhyay S, Saha S, Maulik U, Deb K (2008) A simulated annealing-based multiobjective optimization algorithm: AMOSA. IEEE Trans Evol Comput 12:269–283

    Google Scholar 

  • Bezdek JC (1981) Pattern recognition with fuzzy objective function algorithms. Springer, US

  • Branke J, Schmidt C (2005) Faster convergence by means of fitness estimation. Soft Comput 9:13–20

    Google Scholar 

  • Chen J-H, Goldberg DE, Ho S-Y, Sastry K (2002) Fitness inheritance in multiobjective optimization. In: Langdon WB et al (eds) Proceedings of the genetic and evolutionary computation conference. Morgan Kaufmann, Burlington

    Google Scholar 

  • Chen G, Han X, Liu G, Jiang C, Zhao Z (2012) An efficient multi-objective optimization method for black-box functions using sequential approximate technique. Appl Soft Comput 12:14–27

    Google Scholar 

  • Chen T, Tang K, Chen G, Yao X (2012) A large population size can be unhelpful in evolutionary algorithms. Theor Comput Sci 436:54–70

    MathSciNet  MATH  Google Scholar 

  • Cheng R, Jin Y, Olhofer M, Sendhoff B (2016) A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 20:773–791

    Google Scholar 

  • Chugh T, Jin Y, Miettinen K, Hakanen J, Sindhya K (2016a) A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization. IEEE Trans Evol Comput. https://doi.org/10.1109/TEVC.2016.2622301

  • Chugh T, Sindhya K, Miettinen K, Hakanen J, Jin Y (2016b) On constraint handling in surrogate assisted evolutionary many-objective optimization. In: Handl J et al (eds) Proceedings of the 14th parallel problem solving from nature-PPSN, vol XIV. Springer, Berlin, pp 214–224

    Google Scholar 

  • Coello CAC, Lamont GB (eds) (2004) Applications of multi-objective evolutionary algorithms. World Scientific, Singapore

  • Coello CAC, Pulido GT (2001) A micro multi-objective genetic algorithm for multi-objective optimizations. In: Zitzler E, Thiele L, Deb K, Coello CAC, Corne D (eds) Proceedings of the evolutionary multi-criterion optimization. Springer, Berlin, pp 126–140

    Google Scholar 

  • Coello CAC, Lamont GB, Veldhuizen DAV (2007) Evolutionary algorithms for solving multi-objective problems, 2nd edn. Springer, New York

    MATH  Google Scholar 

  • Corne DW, Jerram NR, Knowles JD, Oates MJ (2001) PESA-II: region-based selection in evolutionary multiobjective optimization. In: Proceedings of the genetic and evolutionary computation conference, pp 283–290, Morgan Kaufmann

  • Couckuyt I, Deschrijver D, Dhaene T (2014) Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization. J Glob Optim 60:575–594

    MathSciNet  MATH  Google Scholar 

  • Currin C, Mitchell M, Morris M, Ylvisaker D (1998) A Bayesian approach to the design and analysis of computer experiments, technical report. Oak Ridge National Laboratory, Oak Ridge

    Google Scholar 

  • Custodio AL, Madeira JFA, Vaz AIF, Vicente LN (2011) Direct multisearch for multiobjective optimization. SIAM J Optim 21:1109–1140

    MathSciNet  MATH  Google Scholar 

  • Datta R, Regis RG (2016) A surrogate-assisted evolution strategy for constrained multi-objective optimization. Expert Syst Appl 57:270–284

    Google Scholar 

  • Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Chichester

    MATH  Google Scholar 

  • Deb K, Nain P (2007) An evolutionary multi-objective adaptive meta-modelling procedure using artificial neural networks. In: Yan S, Ong Y-S, Jin Y (eds) Proceedings of the evolutionary compitation in dynamic and uncertain environments. Springer, Berlin, pp 297–322

    Google Scholar 

  • Deb K, Prarap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197

    Google Scholar 

  • Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multiobjective optimization. Springer, London, pp 105–145

    MATH  Google Scholar 

  • Deb K, Miettinen K, Chaudhuri S (2010) Toward an estimation of nadir objective vector using a hybrid of evolutionary and local search approaches. IEEE Trans Evol Comput 6:821–841

    Google Scholar 

  • Dennis JE, Torczon V (1995) Managing approximation models in optimization. In: Alexandrov NM, Hussaini N (eds) Proceedings of the multidisciplinary design optimization: state-of-the-art, pp 330–347

  • Ducheyne E, Baets BD, Wulf RD (2003) Is fitness inheritance useful for real-world applications? In: Fonseca CM, Fleming PJ, Zitzler E, Thiele L, Deb K (eds) Proceedings of the evolutionary multi-criterion optimization. Springer, Berlin, pp 31–42

    Google Scholar 

  • Durillo J, Nebro A, Alba E (2010) The jmetal framework for multi-objective optimization: design and architecture. In Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1–8

  • Emmerich M, Giotis A, Özdemir M, Bäck T, Giannakoglou K (2002) Metamodel-assisted evolution strategies. In: Merelo-Guervós JJ et al (eds) Proceedings of the parallel problem solving from nature-PPSN VII. Springer, Berlin, pp 361–370

    Google Scholar 

  • Emmerich M, Beume N, Naujoks B (2005) An EMO algorithm using the hypervolume measure as selection criterion. In: Coello CAC, Aguirre AH, Zitzler E (eds) Proceedings of the evolutionary multi-criterion optimization. Springer, Berlin, pp 62–76

    Google Scholar 

  • Emmerich M, Giannakoglou K, Naujoks B (2006) Single- and multiobjective evolutionary optimization assisted by Gaussian random field metamodels. IEEE Trans Evol Comput 10:421–439

    Google Scholar 

  • Emmerich M, Deutz AH, Klinkenberg JW (2011) Hypervolume-based expected improvement: monotonicity properties and exact computation. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 2147–2154

  • Fonseca CM, Fleming PJ (1995) An overview of evolutionary algorithms in multiobjective optimization. Evol Comput 3(1):1–16

    Google Scholar 

  • Forrester A, Keane A (2009) Recent advances in surrogate-based optimization. Progr Aerospace Sci 45:50–79

    Google Scholar 

  • Gano SE, Renaud JE, Martin JD, Simpson TW (2006) Update strategies for Kriging models used in variable fidelity optimization. Struct Multidiscip Optim 32:287–298

    Google Scholar 

  • Giannakoglou KC, Kampolis IC (2010) Multilevel optimization algorithms based on metamodel-and fitness inheritance-asisted evolutionary algorithms. In: Tenne Y, Goh C-K (eds) Computational intelligence in expensive optimization problems. Springer, Berlin, pp 61–84

    Google Scholar 

  • Gorissen D, Couckuyt I, Demeester P, Dhaene T, Crombecq K (2010) A surrogate modelling and adaptive sampling toolbox for computer based design. J Mach Learn Res 11:2051–2055

    Google Scholar 

  • Gräning L, Jin Y, Sendhoff B (2007) Individual-based management of meta-models for evolutionary optimization with application to three-dimensional blade optimization. In: Yang S, Ong Y-S, Jin Y (eds) Evolutionary computation in dynamic and uncertain environments. Springer, Berlin, pp 225–250

    Google Scholar 

  • Hansen MP, Jaskiewicz A (1998) Evaluating the quality of approximation to the non-dominated set. Technical report, Technical University of Denmark

  • Hansen N, Ostermeier A (2001) Completely derandomized self-adaptation in evolution strategies. Evol Comput 9:159–195

    Google Scholar 

  • Herrera M, Guglielmetti A, Xiao M, Coelho RF (2014) Metamodel-assisted optimization based on multiple kernel regression for mixed variables. Struct Multidiscip Optim 49:979–991

    Google Scholar 

  • Horn D, Wagner T, Biermann D, Weihs C, Bischl B (2015) Model-based multi-objective optimization: taxonomy, multi-point proposal, toolbox and benchmark. In: Gasper-Cunha A, Antunes CH, Coello CC (eds) Evolutionary multi-criterion optimization. Springer, Berlin, pp 64–78

    Google Scholar 

  • Huang GB, Zhu QY, Siew CK (2004) Extreme learning machine: a new learning scheme of feedforward neural networks. In: Proceedings of the international joint conference on neural networks, IEEE, pp 985–990

  • Huband S, Barone L, While L, Hingston P (2005) A scalable multi-objective test problem toolkit. In: Coello CAC, Aguirre AH, Zitzler E (eds) Evolutionary multi-criterion optimization. Springer, Berlin, pp 280–295

    Google Scholar 

  • Husain A, Kim K-Y (2010) Enhanced multi-objective optimization of a microchannel heat sink through evolutionary algorithm coupled with multiple surrogate models. Appl Thermal Eng 30:1683–1691

    Google Scholar 

  • Igel C, Hansen N, Roth S (2007) Covariance matrix adaptation for multi-objective optimization. Evol Comput 15:1–28

    Google Scholar 

  • Ishibuchi H, Hitotsuyanagi Y, Tsukamoto N, Nojima Y (2008) Use of heuristic local search for single-objective optimization in multiobjective memetic algorithms. In: Rudolph G, Jansen T, Lucas S, Poloni C, Beume N (eds) Proceedings of the parallel problem solving from nature-PPSN X. Springer, Berlin, pp 743–752

    Google Scholar 

  • Ishibuchi H, Hitotsuyanagi Y, Wakamatsu Y, Nojima Y (2010) How to choose solutions for local search in multiobjective combinatorial memetic algorithms. In: Schaefer R, Cotta C, Kolodziej J, Rudolph G (eds) Parallel problem solving from nature-PPSN XI. Springer, Berlin, pp 516–525

    Google Scholar 

  • Jain H, Deb K (2014) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part II: handling constraints and extending to an adaptive approach. IEEE Trans Evol Comput 18:602–622

    Google Scholar 

  • Jain AK, Dubes RC (1998) Algorithms for clustering data. Prentice-Hall, Upper Saddle River

    MATH  Google Scholar 

  • Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31:264–323

    Google Scholar 

  • Jang B-S, Ko D-E, Suh Y-S, Yang Y-S (2009) Adaptive approximation in multi-objective optimization for full stochastic fatigue design problem. Marine Struct 22:610–632

    Google Scholar 

  • Jeong S, Obayashi S (2005) Efficient global optimization (EGO) for multi-objective problem and data mining. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 2138–2145

  • Jin Y (2005) A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput 9:3–12

    Google Scholar 

  • Jin Y (2011) Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm Evol Comput 1:61–70

    Google Scholar 

  • Jin Y, Sendhoff B (2004) Reducing fitness evaluations using clustering techniques and neural network ensembles. In: Deb K (ed) Proceedings of the genetic and evolutionary computation conference. Springer, Berlin, pp 688–699

    Google Scholar 

  • Jin Y, Olhofer M, Sendhoff B (2002) A framework for evolutionary optimization with approximate fitness functions. IEEE Trans Evol Comput 6:481–494

    Google Scholar 

  • Jin Y, Olhofer M, Sendhoff B (2000) On evolutionary optimization with approximate fitness functions. In: Proceedings of the genetic and evolutionary computation conference, pp 786–793. Morgan Kaufmann

  • Johnson ME, Moore LM, Ylvisaker D (1990) Minimax and maximin distance designs. J Stat Plan Inference 26:131–148

    MathSciNet  Google Scholar 

  • Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. J Glob Optim 13:455–492

    MathSciNet  MATH  Google Scholar 

  • Kampolis IC, Giannakoglou KC (2008) A multilevel approach to single and multiobjective aerodynamic optimization. Comput Methods Appl Mech Eng 197:2963–2975

    MATH  Google Scholar 

  • Keane AJ (2006) Statistical improvement criteria for use in multiobjective design optimization. AIAA J 44:879–891

    Google Scholar 

  • Kim H-S, Cho S-B (2001) An efficient genetic algorithm with less fitness evaluation by clustering. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 887–894

  • Knowles J (2006) ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans Evol Comput 10:50–66

    Google Scholar 

  • Knowles J (2009) Closed-loop evolutionary multiobjective optimization. IEEE Comput Intell Mag 4:77–91

    Google Scholar 

  • Knowles J, Nakayama H (2008) Meta-modeling in multiobjective optimization. In: Branke J, Deb K, Miettinen K, Slowinski R (eds) Multiobjective optimization: interactive and evolutionary approaches. Springer, Berlin, pp 245–284

    Google Scholar 

  • Kourakos G, Mantoglou A (2009) Pumping optimization of coastal aquifers based on evolutionary algorithms and surrogate modular neural network models. Adv Water Resour 32:507–521

    Google Scholar 

  • Kourakos G, Mantoglou A (2013) Development of a multi-objective optimization algorithm using surrogate models for coastal aquifer management. J Hydrol 479:13–23

    Google Scholar 

  • Kursawe Frank (1991) A variant of evolution strategies for vector optimization. In: Proceedings of the 1st workshop on parallel problem solving from nature-PPSN I, pp 193–197. Springer

  • Lattarulo V, Seshadri P, Parks GT (2013) Optimization of a supersonic airfoil using the multi-objective alliance algorithm. In: Proceedings of the genetic and evolutionary computation conference, ACM, pp 1333–1340

  • Lee DS, Gonzalez LF, Periaux J, Srinivas K (2008) Robust design optimisation using multi-objective evolutionary algorithms. Comput Fluids 37:565–583

    MATH  Google Scholar 

  • Lee S, Almon PV, Fink W, Petropoulos AE, Terrile RJ (2005) Comparison of multi-objective genetic algorithms in optimizing q-law low-thrust orbit transfers. In: Proceedings of the genetic and evolutionary computation conference, ACM, pp 25–29

  • Li H, Zhang Q (2009) Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans Evol Comput 12:284–302

    Google Scholar 

  • Li M, Li G, Azarm S (2008) A kriging metamodel assisted multi-objective genetic algorithm for design optimization. J Mech Des 130:1–10

    Google Scholar 

  • Li G, Li M, Azarm S, Hashimi SA, Ameri TA, Qasas NA (2009) Improving multi-objective genetic algorithm with adaptive design of experiments and online metamodeling. Struct Multidiscip Optim 37:447–461

    Google Scholar 

  • Lim D, Jin Y (2010) Generalizing surrogate-assisted evolutionary computation. IEEE Trans Evol Comput 14:329–354

    Google Scholar 

  • Liu Y, Collette M (2014) Improving surrogate-assisted variable fidelity multi-objective optimization using a clustering algorithm. Appl Soft Comput 24:482–493

    Google Scholar 

  • Liu GP, Han X, Jiang C (2008) A novel multi-objective optimization method based on an approximation model management technique. Comput Methods Appl Mech Eng 197:2719–2731

    MATH  Google Scholar 

  • Loshchilov I, Schoenauer M, Sebag M (2010) Dominance-based Pareto-surrogate for multi-objective optimization. In: Deb K, Bhattacharya A, Chakroborty N, Das S, Dutta J, Gupta SK, Jain A, Aggarwal V, Branke J, Louis SJ, Tan KC (eds) Proceedings of the simulated evolution and learning. Springer, Berlin, pp 230–239

    Google Scholar 

  • Loshchilov I, Schoenauer M, Sebag M (2009) A mono surrogate for multiobjective optimization. In: Proceedings of the genetic and evolutionary computation conference, ACM, pp 471–478

  • Luo C, Shimoyama K, Obayashi S (2014) Kriging model based many-objective optimization with efficient calculation of expected hypervolume improvement. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1187–1194

  • Martinez SZ, Coello CAC (2013) MOEA/D assisted by RBF networks for expensive multi-objective optimization problems. In: Blum C (ed) Proceedings of the genetic and evolutionary computation conference. ACM, New York, pp 1405–1412

    Google Scholar 

  • Mckay MD, Beckman RJ, Conover WJ (2000) A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 42:55–61

    MATH  Google Scholar 

  • Mengistu T, Ghaly W (2008) Aerodynamic optimization of turbomachinery blades using evolutionary methods and ANN-based surrogate models. Optim Eng 9:239–255

    MathSciNet  MATH  Google Scholar 

  • Miettinen K (1999) Nonlinear multiobjective optimization. Kluwer, Boston

    MATH  Google Scholar 

  • Mitra K, Majumder S (2011) Successive approximate model based multi-objective optimization for an industrial straight grate iron ore induration process using evolutionary algorithm. Chem Eng Sci 66:3471–3481

    Google Scholar 

  • Mlakar M, Petelin D, Tusar T, Filipic B (2015) GP-DEMO: differential evolution with multiobjective optimization based on gaussian process models. Eur J Oper Res 243:347–361

    MathSciNet  MATH  Google Scholar 

  • Mogilicharla A, Chugh T, Majumder S, Mitra K (2014) Multi-objective optimization of bulk vinyl acetate polymerization with branching. Mater Manuf Process 29:210–217

    Google Scholar 

  • Nain PKS, Deb K (2005) A multi-objective optimization procedure with successive approximate models. Technical Report 2005002, KanGAL, Indian Institute of Technology Kanpur, India

  • Nakayama H, Inoue K, Yoshimori Y (2006) Approximate optimization using computational intelligence and its application to reinforcement of cable-stayed bridges. In: Proceedings of the integrated intelligent systems for engineering design, pp 289–304. IOS press

  • Osyczka A, Kundu S (1995) A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm. Structural optimization 10(2):94–99

    Google Scholar 

  • Oyama A, Okabe Y, Shimoyama K, Fujii K (2009) Aerodynamic multiobjective design exploration of a flapping airfoil using a Navier–stokes solver. J Aerosp Comput Inf Commun 6:256–270

    Google Scholar 

  • Palar PS, Tsuchiya T, Parks G (2015) Comparison of scalarization functions within a local surrogate assisted multi-objective memetic algorithm framework for expensive problems. In: IEEE congress on evolutionary computation (CEC), pp 862–869

  • Palar PS, Tsuchiya T, Parks GT (2016) A comparative study of local search within a surrogate-assisted multi-objective memetic algorithm framework for expensive problems. Appl Soft Comput 43:1–19

    Google Scholar 

  • Pavelski LM, Delgado MR, Almeida CP, Goncalves RA, Venske SM (2014) ELMOEA/D-DE: extreme learning surrogate models in multi-objective optimization based on decomposition and differential evolution. In: Proceedings of the Brazilian conference on intelligent systems, IEEE, pp 318–323

  • Pavelski LM, Delgado MR, Almeida CP, Gonaslves RA, Venske SM (2016) Extreme learning surrogate models in multi-objective optimization based on decomposition. Neurocomputing 180:55–67

    Google Scholar 

  • Pilát M, Neruda R (2011a) ASM-MOMA: multiobjective memetic algorithm with aggregate surrogate model. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1202–1208

  • Pilát M, Neruda R (2011b) Improving many-objective optimizers with aggregate meta-models. In Proceedings of the 11th international conference on hybrid intelligent systems, IEEE, pp 555–560

  • Pilát M, Neruda R (2014) Hypervolume-based local search in multi-objective evolutionary optimization. In: Proceedings of the genetic and evolutionary computation conference, ACM, pp 637–644

  • Poloni C, Giurgevich A, Onesti L, Pediroda V (2000) Hybridization of a multi-objective genetic algorithm, a neural network and a classical optimizer for a complex design problem in fluid dynamics. Comput Methods Appl Mech Eng 186(2):403–420

    MATH  Google Scholar 

  • Ponweiser W, Wagner T, Biermann D, Vincze M (2008) Multiobjective optimization on a limited budget of evaluations using model-assisted S-metric selection. In: Proceedings of the parallel problem solving from nature-PPSN X, pp 784–794, Springer

  • Ponweiser W, Wagner T, Vincze M (2008) Clustered multiple generalized expected improvement: a novel infill sampling criterion for surrogate models. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 3515–3522

  • Qasem SN, Shamsuddin SM, Hashim SMM, Darus M, Shammari EA (2013) Memetic multiobjective particle swarm optimization-based radial basis function network for classification problems. Inf Sci 239:165–190

    MathSciNet  Google Scholar 

  • Quagliarella D, Vicini A (1998) Genetic algorithms and evolutionary strategies in engineering and computer science, chapter coupling genetic algorithms and gradient based optimization techniques. Wiley, Chichester, pp 289–309

    Google Scholar 

  • Ray T, Singh HK, Isaacs A, Smith W (2009) Infeasibility driven evolutionary algorithm for constrained optimization. In: Mezura-Montes E (ed) Constraint-handling in evolutionary optimization. Springer, Berlin, pp 145–165

    Google Scholar 

  • Regis RG (2016) Multi-objective constrained black-box optimization using radial basis function surrogates. J Comput Sci 16:140–155

    MathSciNet  Google Scholar 

  • Reyes-Sierra M, Coello CAC (2005) A study of fitness inheritance and approximation techniques for multi-objective particle swarm optimization. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 65–72

  • Robic T, Filipic B (2005) DEMO: differential evolution for multiobjective optimization. In: Proceedings of evolutionary multi-criterion optimization, pp 520–533. Springer

  • Roy PC, Deb K (2016) High dimensional model representation for solving expensive multi-objective optimization problems. Technical Report COIN Report Number 2016012, Michigan State University

  • Sacks J, Welch WJ, Mitchell TJ, Wynn HP (1989) Design and analysis of computer experiments. Stat Sci 4:409–423

    MathSciNet  MATH  Google Scholar 

  • Santana-Quintero LV, Montano AA, Coello CAC (2010) A review of techniques for handling expensive functions in evolutionary multi-objective optimization. In: Tenne Y, Goh C-K (eds) Computational intelligence in expensive optimization problems. Springer, Berlin, pp 29–59

    Google Scholar 

  • Sasena MJ, Papalambros P, Goovaerts P (2002) Exploration of metamodeling sampling criteria for constrained global optimization. Eng Optim 34:263–278

    Google Scholar 

  • Sastry K, Goldberg DE, Pelikan M (2001) Don’t evaluate, inherit. In: Proceedings of the genetic and evolutionary computation conference, pp 551–558. Morgan Kaufmann

  • Schaffer JD (1985) Some experiments in machine learning using vector evaluated genetic algorithms. Ph.D. thesis, Vanderbilt University, Nashville

  • Seah C-W, Ong Y-S, Tsang IW, Jiang S (2012) Pareto rank learning in multi-objective evolutionary algorithms. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1–8

  • Shimoyama K, Sato K, Jeong S, Obayashi S (2013) Updating kriging surrogate models based on the hypervolume indicator in multi-objective optimization. J Mech Des 135:1–7

    Google Scholar 

  • Sindhya K, Deb K, Miettinen K (2011) Improving convergence of evolutionary multi-objective optimization with local search: a concurrent-hybrid algorithm. Nat Comput 10:1407–1430

    MathSciNet  MATH  Google Scholar 

  • Sindhya K, Miettinen K, Deb K (2013) A hybrid framework for evolutionary multi-objective optimization. IEEE Trans Evol Comput 17:495–511

    MATH  Google Scholar 

  • Singh HK, Ray T, Smith W (2010) Surrogate assisted simulated annealing (SASA) for constrained multi-objective optimization. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1–8

  • Singh P, Couckuyt I, Ferranti F, Dhaene T (2014) A constrained multi-objective surrogate-based optimization algorithm. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 3080–3087

  • Smith RE, Dike BA, Stegmann SA (1995) Fitness inheritance in genetic algorithms. In: Proceedings of the ACM symposium on applied computing, ACM, pp 345–350

  • Sobol IM (2001) Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Math Comput Simul 55:271–280

    MathSciNet  MATH  Google Scholar 

  • Syberfeldt A, Grimm H, Ng A, John RI (2008) A parallel surrogate-assisted multi-objective evolutionary algorithm for computationally expensive optimization problems. In: Proceedings of the IEEE world congress on computational intelligence, IEEE, pp 3177–3184

  • Tenne Y, Armfield SW (2008) Metamodel accuracy assessment in evolutionary optimization. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1505–1512

  • Toscano G, Deb K (2016) Study of the approximation of the fitness landscape and the ranking process of scalarizing functions for many-objective problems. Technical Report COIN Report Number 2016018, Michigan State University

  • Turco A (2011) Metahybrid: Combining metamodels and gradient-based techniques in a hybrid multi-objective genetic algorithm. In: Coello CAC (ed) Proceedings of the learning and intelligent optimization. Springer, Berlin, pp 293–307

    Google Scholar 

  • Ulmer H, Streichert F, Zell A (2003) Evolution strategies assisted by Gaussian processes with improved preselection criterion. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 692–699

  • van Veldhuizen DA, Lamont GB (1999) Multiobjective evolutionary algorithm test suites. In: Proceedings of the 1999 ACM symposium on applied computing, ACM, pp 351–357

  • Veldhuizen DAV, Lamont GB (1998) Evolutionary computation and convergence to a Pareto front. In: Proceedings of the genetic programming, pp 221–228. Morgan Kaufmann

  • Veldhuizen DAV (1999) Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. Ph.D. thesis, Graduate School of Engineering of the Air Force Institute of Technology Air University, Dayton

  • Vrgut JA, Robinson BA (2007) Improved evolutionary optimization from genetically adaptive multimethod search. Proc Natl Acad Sci USA 104:708–711

    Google Scholar 

  • Wagner T, Emmerich M, Deutz A, Ponweiser W (2010) On expected-improvement criteria for model-based multi-objective optimization. In: Schaefer R, Cotta C, Kolodziej J, Rudolph G (eds) Proceedings of the parallel problem solving from nature-PPSN XI. Springer, Berlin, pp 718–727

    Google Scholar 

  • Wang GG (2003) Adaptive response surface method using inherited latin hypercube design points. J Mech Des 125:210–220

    Google Scholar 

  • Wang H, Jin Y, Jansen JO (2016) Data-driven surrogate-assisted multi-objective evolutionary optimization of a trauma system. IEEE Trans Evol Comput 20:939–952

    Google Scholar 

  • Wilson B, Cappelleri D, Simpson TW, Frecker M (2001) Efficient pareto frontier exploration using surrogate approximations. Optim Eng 2(1):31–50

    MathSciNet  MATH  Google Scholar 

  • Yang BS, Yeun Y-S, Ruy W-S (2002) Managing approximation models in multiobjective optimization. Struct Multidiscip Optim 24:141–156

    Google Scholar 

  • Yuan R, Guangchen B (2009) Comparison of neural network and kriging method for creating simulation-optimization metamodels. In: Yang B, Zhu W, Dai Y, Yang LT,  Ma J (eds) Proceedings of the 8th IEEE international symposium on dependable, autonomic and secure computing, IEEE, pp 815–821

  • Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11:712–731

    Google Scholar 

  • Zhang Q, Liu W, Tsang E, Virginas B (2010) Expensive multiobjective optimization by MOEA/D with gaussian process model. IEEE Trans Evol Comput 14:456–474

    Google Scholar 

  • Zhang Q, Liu W, Li H (2009) The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 203–208

  • Zhang Q, Zhau A, Zhao S, Suganthan PN, Liu W,  Tiwari S (2009) Multiobjective optimization test instances for the CEC 2009 special session and competition. Technical Report CES-487, University of Essex/Nanyang Technological University, Essex, UK/Singapore

  • Zheng Y, Julstrom BA, Cheng W (1997) Design of vector quantization codebooks using a genetic algorithm. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 525–529

  • Zhu J, Wang Y-J, Collette M (2013) A multi-objective variable-fidelity optimization method for genetic algorithms. Eng Optim 46:521–542

    MathSciNet  Google Scholar 

  • Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.D. thesis, Swiss Federal Institute of Technology Zurich

  • Zitzler E, Kunzli S (2004) Indicator-based selection in multiobjective search. In: Yao X et al (eds) Proceedings of the parallel problem solving from nature-PPSN VIII. Springer, Berlin, pp 832–842

    Google Scholar 

  • Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms-a comparative case study. In: Eiben AE (ed) Proceedings of the parallel problem solving from nature-PPSN V. Springer, Berlin, pp 292–301

    Google Scholar 

  • Zitzler E, Deb K, Thiele L (2000) Comparison of multiobjective evolutionary algorithms: empirical results. Evol Comput 8:173–195

    Google Scholar 

  • Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou KC (ed) Proceedings of the evolutionary methods for design, optimisation and control with application to industrial problems (EUROGEN 2001). CIMNE, Barcelona, pp 95–100

    Google Scholar 

  • Zitzler E, Thiele L, Laumanns M, Fonseca C, Fonseca V (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 8:117–132

    Google Scholar 

Download references

Acknowledgements

The research of Tinkle Chugh was funded by the COMAS Doctoral Program (at the University of Jyväskylä) and FiDiPro Project DeCoMo (funded by Tekes, the Finnish Funding Agency for Innovation), and the research of Dr. Karthik Sindhya was funded by SIMPRO project funded by Tekes as well as DeCoMo.

Author information

Authors and Affiliations

  1. University of Jyvaskyla, Faculty of Information Technology, P.O. Box 35, Agora, 40014, University of Jyvaskyla, Finland

    Tinkle Chugh, Karthik Sindhya, Jussi Hakanen & Kaisa Miettinen

Authors
  1. Tinkle Chugh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Karthik Sindhya
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jussi Hakanen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kaisa Miettinen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tinkle Chugh.

Ethics declarations

Conflict of interest

Authors declare that there is no conflict of interest.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Communicated by V. Loia.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chugh, T., Sindhya, K., Hakanen, J. et al. A survey on handling computationally expensive multiobjective optimization problems with evolutionary algorithms. Soft Comput 23, 3137–3166 (2019). https://doi.org/10.1007/s00500-017-2965-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-017-2965-0

Keywords

Search

Navigation