Comparison between MOEA/D and NSGA-II on the multi-objective travelling salesman problem. (English) Zbl 1160.90679
Goh, Chi-Keong (ed.) et al., Multi-objective memetic algorithms. Berlin: Springer (ISBN 978-3-540-88050-9/hbk; 978-3-540-88051-6/ebook). Studies in Computational Intelligence 171, 309-324 (2009).
Summary: Most multiobjective evolutionary algorithms are based on Pareto dominance for measuring the quality of solutions during their search, among them NSGA-II is well-known. A very few algorithms are based on decomposition and implicitly or explicitly try to optimize aggregations of the objectives. MOEA/D is a very recent such an algorithm. One of the major advantages of MOEA/D is that it is very easy to design local search operator within it using well-developed single-objective optimization algorithms. This chapter compares the performance of MOEA/D and NSGA-II on the multiobjective travelling salesman problem and studies the effect of local search on the performance of MOEA/D.
For the entire collection see [Zbl 1157.68005].
For the entire collection see [Zbl 1157.68005].
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C29 | Multi-objective and goal programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms (2001), Chichester: John Wiley & Sons, Chichester · Zbl 0970.90091 |
| [2] | Coello, C. A.; Veldhuizen, D. A.; Lamont, G. B., Evolutionary Algorithms for Solving Multi-Objective Problems (2002), Norwell: Kluwer, Norwell · Zbl 1130.90002 |
| [3] | Tan, K. C.; Khor, E. F.; Lee, T. H., Multiobjective Evolutionary Algorithms and Applications (2005), New York: Springer, New York · Zbl 1101.68971 |
| [4] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, IEEE Trans. on Evolutionary Computation, 6, 182-197 (2002) · doi:10.1109/4235.996017 |
| [5] | Zhang, Q.; Li, H., MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition, IEEE Trans. on Evolutionary Computation, 11, 712-731 (2007) · doi:10.1109/TEVC.2007.892759 |
| [6] | Johnson, D. S.; McGeoch, L. A.; Aarts, E.; Lenstra, J. K., The traveling salesman problem: a case study, Local Search in Combinatorial Optimization, 215-310 (1997), Chichester: John Wiley & Sons, Chichester · Zbl 0947.90612 |
| [7] | Paquete, L.; Stützle, T.; Fonseca, C. M.; Fleming, P. J.; Zitzler, E.; Deb, K.; Thiele, L., A two-phase local search for the biobjective traveling salesman problem, Evolutionary Multi-Criterion Optimization, 479-493 (2003), Heidelberg: Springer, Heidelberg · Zbl 1036.90561 · doi:10.1007/3-540-36970-8_34 |
| [8] | Yan, Z.; Zhang, L.; Kang, L.; Lin, G.; Fonseca, C. M.; Fleming, P. J.; Zitzler, E.; Deb, K.; Thiele, L., A new MOEA for multi-objective TSP and its convergence property analysis, Evolutionary Multi-Criterion Optimization, 342-354 (2003), Heidelberg: Springer, Heidelberg · Zbl 1036.90557 · doi:10.1007/3-540-36970-8_24 |
| [9] | García-Martínez, C.; Cordón, O.; Herrera, F., A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP, European Journal of Operational Research, 180, 116-148 (2007) · Zbl 1114.90103 · doi:10.1016/j.ejor.2006.03.041 |
| [10] | Miettinen, K., Nonlinear Multiobjective Optimization (1999), Norwell: Kluwer, Norwell · Zbl 0949.90082 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
