Stopping criteria for evolutionary multi-objective optimization

The use of multi-objective evolutionary algorithms for solving black-box problems with multiple conflicting objectives has become an important research area. However, when no gradient information is available, the examination of formal convergence or optimality criteria is often impossible. Thus, sophisticated heuristic online stopping criteria (OSC) have recently become subject of intensive research.

Tutorials and slides

Convergence Detection and Stopping Criteria for Evolutionary Multi-Objective Optimization

by Luis Martí and Nayat Sanchez-Pi

Tutorial presented at the 2015 IEEE Congress on Evolutionary Computation (doi: 10.13140/RG.2.1.4308.5926).

EMO Stopping Criteria Detecting Stagnation in Multi–Objective Optimization

by Luis Martí

Mini course at the 5ª Escola Luso-Brasileira de Computação Evolutiva.

Laboratório Nacional de Computação Científica,

Petrópolis, Brazil; Feb. 18–21, 2014.

Software

We integrate the known approaches within the taxonomy and discuss them by extracting their building blocks. The formal structure of the taxonomy is used as basis for the implementation of a comprehensive MATLAB toolbox.

  • Wagner, T., Martí, L. (2010) Taxonomy-based Matlab framework for online stopping criteria.

A Python implementation of the current state of the art stop criteria. Can be used along DEAP and inspyred.

Reading list

This reading list contains papers that have to do with stopping criteria for evolutionary multi-objective optimization. Feel free to contribute to the list via the Mendeley group.

2015

Kalyanmoy Deb, Mohamed Abouhawwash, Joydeep Dutta (2015) An Optimality Theory Based Proximity Measure for Evolutionary Multi-Objective and Many-Objective Optimization, Evolutionary Multi-Criterion Optimization 2015 2, p. 18-33, url, doi:10.1007/978-3-319-15892-1_2

Debora Gil, David Roche, Agnés Borràs, Jesús Giraldo (2015) Terminating evolutionary algorithms at their steady state, Computational Optimization and Applications 61(2), p. 489-515, url, doi:10.1007/s10589-014-9722-4

2012

David Hadka, Patrick Reed (2012) Diagnostic Assessment of Search Controls and Failure Modes in Many-Objective Evolutionary Optimization, Evolutionary Computation 20(3), p. 423-452, pubmed, doi:10.1162/EVCO_a_00053

2011

Bun Theang Ong, Masao Fukushima (2011) Genetic algorithm with automatic termination and search space rotation, Memetic Computing 3(2), p. 111-127, doi:10.1007/s12293-011-0057-8

María C. Maciel, Sandra a. Santos, Graciela N. Sottosanto (2011) On Second-Order Optimality Conditions for Vector Optimization, Journal of Optimization Theory and Applications 149(2), p. 332-351, doi:10.1007/s10957-010-9793-z

Tobias Wagner, Heike Trautmann, L. Martí (2011) A Taxonomy of Online Stopping Criteria for Multi-Objective Evolutionary Algorithms, Evolutionary Multi-Criterion Optimization, p. 16–30, Springer, pdf, doi:10.1007/978-3-642-19893-9_2

Rupesh Tulshyan, Kalyanmoy Deb, Sunith Bandaru (2011) KKT proximity measure for testing convergence in smooth multi-objective optimization, Proceedings of the 13th annual conference companion on Genetic and evolutionary computation - GECCO '11(2), p. 93, New York, New York, USA: ACM Press, url, doi:10.1145/2001858.2001912

Salem F. Adra, Peter J. Fleming (2011) Diversity Management in Evolutionary Many-Objective Optimization, IEEE Transactions on Evolutionary Computation 15(2), p. 183-195, IEEE, url, doi:10.1109/TEVC.2010.2058117

2010

Luis Martí, Jesús García, Antonio Berlanga, José M. Molina (2010) A progress indicator for detecting success and failure in evolutionary multi-objective optimization, 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010, doi:10.1109/CEC.2010.5586352

José L. Guerrero, Luis Martí, Antonio Berlanga, Jesús García, José M. Molina (2010) Introducing a robust and efficient stopping criterion for MOEAs, 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010, doi:10.1109/CEC.2010.5586265

Francisco V. Fernandez, J. Esteban-Muller, Elisenda Roca, Rafael Castro-Lopez (2010) Stopping criteria in evolutionary algorithms for multi-objective performance optimization of integrated inductors, IEEE Congress on Evolutionary Computation, p. 1-8, Ieee, url, doi:10.1109/CEC.2010.5586196

José Luis Guerrero, Luis Martí, Antonio Berlanga, Jesús Garcia, José Manuel Molina (2010) Introducing a robust and efficient stopping criterion for MOEAs, IEEE Congress on Evolutionary Computation 33(5), p. 1-8, IEEE, url, doi:10.1109/CEC.2010.5586265

Tushar Goel, Nielen Stander (2010) A non-dominance-based online stopping criterion for multi-objective evolutionary algorithms, International Journal for Numerical Methods in Engineering 84(6), p. 661-684, url, doi:10.1002/nme.2909

Olaf Mersmann, Heike Trautmann, Boris Naujoks, Claus Weihs (2010) Benchmarking evolutionary multiobjective optimization algorithms, IEEE Congress on Evolutionary Computation, p. 1-8, IEEE, url, doi:10.1109/CEC.2010.5586241

2009

José Luis Guerrero, Jesús García, Luis Martí, José Manuel Molina, Antonio Berlanga (2009) A Stopping Criterion Based on Kalman Estimation Techniques with Several Progress Indicators, roceedings of the 11th Annual conference on Genetic and evolutionary computation Pages, p. 587-594, doi:10.1145/1569901.1569983

Luis Martì, Jesùs Garcìa, Antonio Berlanga, M. Molina Josè (2009) An approach to stopping criteria for multi-objective optimization evolutionary algorithms: The MGBM criterion, 2009 IEEE Congress on Evolutionary Computation, CEC 2009, p. 1263-1270, doi:10.1109/CEC.2009.4983090

H. Trautmann, T. Wagner, B. Naujoks, M. Preuss, J. Mehnen (2009) Statistical Methods for Convergence Detection of Multi-Objective Evolutionary Algorithms, Evolutionary Computation 17(4), p. 493-509, IEEE, url, doi:10.1162/evco.2009.17.4.17403

N. J. Huang, J. Li, S. Y. Wu (2009) Optimality Conditions for Vector Optimization Problems, Journal of Optimization Theory and Applications 142(2), p. 323-342, url, doi:10.1007/s10957-009-9514-7

L.T. Bui, S. Wesolkowski, Axel Bender, H.A. Abbass, M. Barlow (2009) A dominance-based stability measure for multi-objective evolutionary algorithms, 2009 IEEE Congress on Evolutionary Computation, p. 749-756, IEEE, url, doi:10.1109/CEC.2009.4983020

Tobias Wagner, Heike Trautmann, Boris Naujoks (2009) OCD: Online Convergence Detection for Evolutionary Multi-Objective Algorithms Based on Statistical Testing, Evolutionary Multi-Criterion Optimization, p. 198-215, url, doi:10.1007/978-3-642-01020-0_19

Anne Auger, Johannes Bader, Dimo Brockhoff, Eckart Zitzler (2009) Articulating user preferences in many-objective problems by sampling the weighted hypervolume, Proceedings of the 11th Annual conference on Genetic and evolutionary computation - GECCO '09, p. 555, New York, New York, USA: ACM Press, url, doi:10.1145/1569901.1569979

Salem F. Adra, Tony J. Dodd, Ian A. Griffin, Peter J. Fleming (2009) Convergence Acceleration Operator for Multiobjective Optimization, IEEE Transactions on Evolutionary Computation 13(4), p. 825-847, url, doi:10.1109/TEVC.2008.2011743

Boris Naujoks, Heike Trautmann (2009) Online convergence detection for multiobjective aerodynamic applications, 2009 IEEE Congress on Evolutionary Computation, p. 332-339, IEEE, url, doi:10.1109/CEC.2009.4982966

2008

Heike Trautmann, Uwe Ligges, Jörn Mehnen, Mike Preuss (2008) A Convergence Criterion for Multiobjective Evolutionary Algorithms Based on Systematic Statistical Testing, Parallel Problem Solving from Nature – PPSN X, G. Rudolph (ed.), p. 825-836, url, doi:10.1007/978-3-540-87700-4_82

2007

Luis Martí, Jesús García, Antonio Berlanga, José Manuel Molina (2007) A cumulative evidential stopping criterion for multiobjective optimization evolutionary algorithms, Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation - GECCO '07, p. 2835, url, doi:10.1145/1274000.1274053

Luis Martí, Jesús García, Antonio Berlanga, José Manuel Molina (2007) A cumulative evidential stopping criterion for multiobjective optimization evolutionary algorithms, Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation - GECCO '07, p. 2835, url, doi:10.1145/1274000.1274053

M. Hachimi, B. Aghezzaf (2007) New results on second-order optimality conditions in vector optimization problems, Journal of Optimization Theory and Applications 135(1), p. 117-133, doi:10.1007/s10957-007-9242-9

Thomas Bartz-Beielstein, Mike Preuss (2007) Experimental research in evolutionary computation, Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation - GECCO '07, p. 3001, New York, New York, USA: ACM Press, url, doi:10.1145/1274000.1274102

Salem Fawaz Adra, Ian Griffin, Peter J. Fleming (2007) An informed convergence accelerator for evolutionary multiobjective optimiser, Proceedings of the 9th annual conference on Genetic and evolutionary computation - GECCO '07 44(0), p. 734, New York, New York, USA: ACM Press, url, doi:10.1145/1276958.1277110

A.R. Hedar, B.T. Ong, Masao Fukushima (2007) Genetic algorithms with automatic accelerated termination, p. 1-19, url

Karin Zielinski, Rainer Laur (2007) Stopping criteria for a constrained single-objective particle swarm optimization algorithm, Informatica 31(1), p. 51-59, Citeseer, pdf

2006

Thomas Bartz-Beielstein (2006) Comparison, Experimental Research in Evolutionary Computation, p. 105-143, Berlin/Heidelberg: Springer-Verlag, url, doi:10.1007/3-540-32027-X

2004

Martín Safe, Jessica Carballido, Ignacio Ponzoni, Nélida Brignole (2004) On Stopping Criteria for Genetic Algorithms, Advances in Artificial Intelligence – SBIA 2004, p. 405-413, url, doi:10.1007/978-3-540-28645-5_41

Olga Rudenko, Marc Schoenauer (2004) A steady performance stopping criterion for pareto-based evolutionary algorithms, Proc. 6th Intl Conf. on Multi Objective Programming and Goal Programming, ps

2003

G.M. Lee, M.H. Kim (2003) On second order necessary optimality conditions for vector optimization problems, J. Korean Math. Soc 40(2), p. 287–305, pdf

L. M. Graña Drummond, A. N. Iusem, B. F. Svaiter (2003) On First Order Optimality Conditions for Vector Optimization, Acta Mathematicae Applicatae Sinica, English Series 19(3), p. 371-386, Institute of Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society, co-published with Springer-Verlag GmbH, url, doi:10.1007/s10255-003-0112-4

2002

Eckart Zitzler, Marco Laumanns, Lothar Thiele, Carlos M. Fonseca, V.G. da Fonseca (2002) Why quality assessment of multiobjective optimizers is difficult, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), p. 666–674, Citeseer, pdf

2001

Jin Wu, Shapour Azarm (2001) Metrics for Quality Assessment of a Multiobjective Design Optimization Solution Set, Journal of Mechanical Design 123(1), p. 18, url, doi:10.1115/1.1329875

B.J. Jain, H. Pohlheim, J. Wegener (2001) On termination criteria of evolutionary algorithms, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), L. Spector (ed.), p. 768, Morgan Kaufmann Publishers, pdf

Marco Laumanns, Günter Rudolph, H.P. Schwefel (2001) Mutation control and convergence in evolutionary multi-objective optimization, Proceedings of the 7th International Mendel Conference on soft Computing (MENDEL 2001), p. 24–29, Citeseer, url, doi:10.1.1.29.2059

2000

Haldun Aytug, Gary J. Koehler (2000) New stopping criterion for genetic algorithms, European Journal of Operational Research 126(3), p. 662-674, url, doi:10.1016/S0377-2217(99)00321-5

Günter Rudolph, Alexandru Agapie (2000) Convergence properties of some multi-objective evolutionary algorithms, Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512) 2, p. 1010-1016, IEEE, url, doi:10.1109/CEC.2000.870756

1999

Thomas Hanne (1999) On the convergence of multiobjective evolutionary algorithms, European Journal of Operational Research 117(3), p. 553-564, url, doi:10.1016/S0377-2217(98)00262-8

1998

Michael Pilegaard Hansen, Andrzej Jaszkiewicz (1998) Evaluating the Quality of Approximations to the Non-Dominated Set, url

Günter Rudolph (1998) On a multi-objective evolutionary algorithm and its convergence to the Pareto set, 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360)(1), p. 511-516, IEEE, url, doi:10.1109/ICEC.1998.700081