Evolutionary algorithms and multi-objectivization for the travelling salesman problem

ABSTRACT

This paper studies the multi-objectivization of single-objective optimization problems (SOOP) using evolutionary multi-objective algorithms (EMOAs). In contrast to the single-objective case, diversity can be introduced by the multi-objective view of the algorithm and the dynamic use of objectives. Using the travelling salesman problem as an example we illustrate that two basic approaches, a) the addition of new objectives to the existing problem and b) the decomposition of the primary objective into sub-objectives, can improve performance compared to a single-objective genetic algorithm when objectives are used dynamically. Based on decomposition we propose the concept "Multi-Objectivization via Segmentation" (MOS), at which the original problem is reassembled. Experiments reveal that this new strategy clearly outperforms both the traditional genetic algorithm (GA) and the algorithms based on existing multiobjective approaches even without changing objectives.

REFERENCES

• 1: Dimo Brockhoff , Tobias Friedrich , Nils Hebbinghaus , Christian Klein , Frank Neumann , Eckart Zitzler, Do additional objectives make a problem harder?, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277114]
• 2: C. A. Coello Coello and G. Lamont. Applications of Multi-Objective Evolutionary Algorithms. World Scientific Publishing, Singapore, 2004.
• 3: David L. Applegate , Robert E. Bixby , Vasek Chvatal , William J. Cook, The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics), Princeton University Press, Princeton, NJ, 2007
• 4: David S. Johnson and Lyle A. Mcgeoch. The traveling salesman problem: A case study in local optimization. In Local Search in Combinatorial Optimization. Wiley and Sons. Chapter 8, E. Aarts and J.K. Lenstra (Eds.).
• 5: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 6: K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6:182--197, 2002.
• 7: W. S. Gosset. The probable error of a mean. Biometrika, 6(1):1--25, March 1908. Originally published under the pseudonym "Student".
• 8: Julia Handl , Simon C. Lovell , Joshua Knowles, Investigations into the Effect of Multiobjectivization in Protein Structure Prediction, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_70]
• 9: Julia Handl , Simon C. Lovell , Joshua Knowles, Multiobjectivization by Decomposition of Scalar Cost Functions, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_4]
• 10: Jensen, M. T. Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation. Journal of Mathematical Modelling and Algorithms 3(4), pages 323--347, 2004.
• 11: Joshua D. Knowles , Richard A. Watson , David Corne, Reducing Local Optima in Single-Objective Problems by Multi-objectivization, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.269-283, March 07-09, 2001
• 12: S. Watanabe, K. Sakakibara. Multiobjective approaches in single objective optimization environment. In The 2005 IEEE Congress on Evolutionary Computation, volume 2, pages 1714--1721, 2005.
• 13: T. Starkweather, S. Mcdaniel, C. Whitley, K. Mathias, D. Whitley, and M. E. Dept. A comparison of genetic sequencing operators. In Genetic Algorithms, pages 69--76. Morgan Kaufmann, 1991.
• 14: Z. Yan, L. Zhang, L. Kang, and G. Lin. A new moea for multi-objective tsp and its convergence property analysis. In EMO, pages 342--354, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms, Performance

Keywords:
genetic algorithms, multi-objective optimization, multi-objectivization, travelling salesman problem