×

zbMATH — the first resource for mathematics

Convergence speed in multi-objective metaheuristics: efficiency criteria and empirical study. (English) Zbl 1202.65081
Summary: Solving optimization problems using a reduced number of objective function evaluations is an open issue in the design of multi-objective optimization metaheuristics. The usual approach to analyze the behavior of such techniques is to choose a benchmark of known problems, to perform a predetermined number of function evaluations, and then, apply a set of performance indicators in order to assess the quality of the solutions obtained. However, this sort of methodology does not provide any insights of the efficiency of each algorithm. Here, efficiency is defined as the effort required by a multi-objective metaheuristic to obtain a set of non-dominated solutions that is satisfactory to the user, according to some pre-defined criterion. Indeed, the type of solutions of interest to the user may vary depending on the specific characteristics of the problem being solved. In this paper, the convergence speed of seven state-of-the-art multi-objective metaheuristics is analyzed, according to three pre-defined efficiency criteria. Our empirical study shows that SMPSO (based on a particle swarm optimizer) is found to be the best overall algorithm on the test problems adopted when considering the three efficiency criteria.

MSC:
65K10 Numerical optimization and variational techniques
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Glover, Handbook of Metaheuristics (2003) · Zbl 1058.90002 · doi:10.1007/b101874
[2] Blum, Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Computing Surveys 35 (3) pp 268– (2003)
[3] Alba, Parallel Metaheuristics: A New Class of Algorithms (2005)
[4] Goel, Response surface approximation of Pareto optimal front in multi-objective optimization, Computer Methods in Applied Mechanics and Engineering 196 pp 879– (2007) · Zbl 1120.76358
[5] Lian, Multiobjective optimization using coupled response surface model and evolutionary algorithm, AIAA Journal 43 (6) pp 1316– (2005)
[6] Coello, Genetic Algorithms and Evolutionary Computation, in: Evolutionary Algorithms for Solving Multi-objective Problems (2002) · Zbl 1130.90002 · doi:10.1007/978-1-4757-5184-0
[7] Deb, Multi-objective Optimization Using Evolutionary Algorithms (2001) · Zbl 0970.90091
[8] Zitzler, Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation 3 (4) pp 257– (1999)
[9] Knowles J Thiele L Zitzler E A tutorial on the performance assessment of stochastic multiobjective optimizers 2006
[10] Coello, Lecture Notes in Computer Science, in: Evolutionary Multi-criterion Optimization. First International Conference, EMO 2001 (2001)
[11] Pulido, Lecture Notes in Computer Science, in: Evolutionary Multi-Criterion Optimization. First International Conference, EMO 2003 (2003)
[12] Santana-Quintero, Lecture Notes in Computer Science, in: Parallel Problem Solving from Nature (PPSN IX) pp 483– (2006)
[13] Hernández-Díaz, Genetic and Evolutionary Computation Conference (GECCO’2006) pp 675– (2006)
[14] Toscano-Pulido, Lecture Notes in Computer Science, in: Evolutionary Multi-criterion Optimization (EMO 2007) pp 272– (2007)
[15] Eskandari, Lecture Notes in Computer Science, in: Evolutionary Multi-criterion Optimization. Fourth International Conference, EMO 2007 pp 141– (2007) · Zbl 1107.82324
[16] Knowles, ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems, IEEE Transactions on Evolutionary Computation 10 (1) pp 50– (2006)
[17] Sindhya, Parallel Problem Solving for Nature pp 815– (2008)
[18] Nebro, Parallel Problem Solving for Nature pp 763– (2008)
[19] Wolpert, No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1 (1) pp 67– (1997)
[20] Deb, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6 (2) pp 182– (2002)
[21] Zitzler E Laumanns M Thiele L SPEA2: improving the strength Pareto evolutionary algorithm 2002 95 100
[22] Knowles, Proceedings of the 1999 Congress on Evolutionary Computation pp 9– (1999)
[23] Kukkonen S Lampinen J GDE3: the third evolution step of generalized differential evolution 443 450
[24] Nebro A Durillo J García-Nieto J Coello CC Luna F Alba E SMPSO: a new PSO-based metaheuristic for multi-objective optimization 66 73
[25] Nebro, AbYSS: adapting scatter search to multiobjective optimization, IEEE Transactions on Evolutionary Computation 12 (4) pp 439– (2008)
[26] Nebro A Durillo J Luna F Dorronsoro B Alba E A cellular genetic algorithm for multiobjective optimization 25 36 · Zbl 1176.90552
[27] Zitzler, Comparison of multiobjective evolutionary algorithms: empirical results, IEEE Transactions on Evolutionary Computation 8 (2) pp 173– (2000) · Zbl 05412936 · doi:10.1162/106365600568202
[28] Deb, Evolutionary Multiobjective Optimization. Theoretical Advances and Applications pp 105– (2005) · Zbl 1078.90567
[29] Huband, A review of multiobjective test problems and a scalable test problem toolkit, IEEE Transactions on Evolutionary Computation 10 (5) pp 477– (2006)
[30] Li, Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II, IEEE Transactions on Evolutionary Computation 12 (2) pp 284– (2008)
[31] Zhang Q Zhou A Zhao S Suganthan P Liu W Tiwari S Multiobjective optimization test instances for the CEC 2009 special session and competition 2008
[32] Durillo J Nebro A Luna F Dorronsoro B Alba E jMetal: a Java framework for developing multi-objective optimization metaheuristics 2006
[33] Zitzler E Laumanns M Thiele L SPEA2: improving the strength Pareto evolutionary algorithm 2001
[34] Lampinen J DE’s selection rule for multiobjective optimization 2001
[35] Nebro, Lecture Notes in Computer Science, in: Evolutionary Multi-criterion Optimization. Fourth International Conference, EMO 2007 pp 126– (2007)
[36] Demšar, Statistical comparisons of classifiers over multiple data sets, Journal of Machine Learning Research 7 pp 1– (2006)
[37] Everson M Fieldsend J Singh S Full elite sets for multi-objective optimization 343 354
[38] Fieldsend, Using unconstrained elite archives for multiobjective optimization, IEEE Transactions on Evolutionary Computation 7 (3) pp 305– (2003)
[39] Knowles J Corne D Bounded Pareto archiving: theory and practice Metaheuristics for Multiobjective Optimisation Lecture Notes in Economics and Mathematical Systems Springer Berlin 39 64 · Zbl 1140.90489
[40] Goel, Response surface approximation of Pareto optimal front in multi-objective optimization, Computer Methods in Applied Mechanics and Engineering 196 pp 879– (2007) · Zbl 1120.76358
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.