Evolving diverse TSP instances by means of novel and creative mutation operators

ABSTRACT

Evolutionary algorithms have successfully been applied to evolve problem instances that exhibit a significant difference in performance for a given algorithm or a pair of algorithms inter alia for the Traveling Salesperson Problem (TSP). Creating a large variety of instances is crucial for successful applications in the blooming field of algorithm selection. In this paper, we introduce new and creative mutation operators for evolving instances of the TSP. We show that adopting those operators in an evolutionary algorithm allows for the generation of benchmark sets with highly desirable properties: (1) novelty by clear visual distinction to established benchmark sets in the field, (2) visual and quantitative diversity in the space of TSP problem characteristics, and (3) significant performance differences with respect to the restart versions of heuristic state-of-the-art TSP solvers EAX and LKH. The important aspect of diversity is addressed and achieved solely by the proposed mutation operators and not enforced by explicit diversity preservation.

References

1. Bradley Alexander, James Kortman, and Aneta Neumann. 2017. Evolution of artistic image variants through feature based diversity optimisation. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, July 15--19, 2017, Peter A. N. Bosman (Ed.). ACM, 171--178.
2. David L. Applegate, Robert E. Bixby, Vasek Chvátal, and William J. Cook. 2007. The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, NJ, USA.
3. Bernd Bischl, Pascal Kerschke, Lars Kotthoff, Thomas Marius Lindauer, Yuri Malitsky, Alexandre Fréchette, Holger H. Hoos, Frank Hutter, Kevin Leyton-Brown, Kevin Tierney, and Joaquin Vanschoren. 2016. ASlib: A Benchmark Library for Algorithm Selection. Artificial Intelligence (AIJ) 237 (2016), 41 -- 58.
4. Jakob Bossek and Heike Trautmann. 2016. Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers. In Proceedings of the 10th International Conference on Learning and Intelligent Optimization (LION). Springer, 48 -- 59.
5. Jakob Bossek and Heike Trautmann. 2016. Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. In Advances in Artificial Intelligence (AI*IA). Springer, 3--12.
6. Jakob Bossek and Heike Trautmann. 2019. Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected Running Time. In Proceedings of the 12th International Conference on Learning and Intelligent Optimization (LION) (Lecture Notes in Computer Science), Vol. 11353. Springer International Publishing, Kalamata, Greece, 215--219.
7. Jérémie Dubois-Lacoste, Holger H. Hoos, and Thomas Stützle. 2015. On the Empirical Scaling Behaviour of State-of-the-art Local Search Algorithms for the Euclidean TSP. In Proceedings of the 17th Annual Conference on Genetic and Evolutionary Computation (GECCO). ACM, 377 -- 384.
8. Wanru Gao, Samadhi Nallaperuma, and Frank Neumann. 2016. Feature-Based Diversity Optimization for Problem Instance Classification. In Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN XIV) (Lecture Notes in Computer Science (LNCS)). Springer, 869--879.
9. Dan Gusfield. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York, NY, USA.
10. Keld Helsgaun. 2009. Generalk - opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation 1, 2--3 (2009), 119 -- 163.
11. Frank Hutter, Lin Xu, Holger H. Hoos, and Kevin Leyton-Brown. 2014. Algorithm Runtime Prediction: Methods & Evaluation. Artificial Intelligence (AIJ) 206 (2014), 79 -- 111. http://www.sciencedirect.com/science/article/pii/S0004370213001082
12. Pascal Kerschke, Jakob Bossek, and Heike Trautmann. 2018. Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers. In Proceedings of the 20th Annual Conference on Genetic and Evolutionary Computation (GECCO) Companion. ACM, 1737 -- 1744.
13. Pascal Kerschke, Holger H. Hoos, Frank Neumann, and Heike Trautmann. 2019. Automated Algorithm Selection: Survey and Perspectives. Evolutionary Computation (ECJ) 27, 1 (2019), 3 -- 45.
14. Pascal Kerschke, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike Trautmann. 2018. Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation (ECJ) 26, 4 (2018), 597 -- 620.
15. Lars Kotthoff. 2016. Algorithm Selection for Combinatorial Search Problems: A Survey. Data Mining and Constraint Programming 10101 (2016), 149 -- 190.
16. Lars Kotthoff, Pascal Kerschke, Holger H. Hoos, and Heike Trautmann. 2015. Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection. In Proceedings of the 9th International Conference on Learning and Intelligent Optimization (LION). Springer, 202 -- 217.
17. Paul McMenemy, Nadarajen Veerapen, Jason Adair, and Gabriela Ochoa. 2019. Rigorous Performance Analysis of State-of-the-Art TSP Heuristic Solvers. In Evolutionary Computation in Combinatorial Optimization (Lecture Notes in Computer Science (LNCS)), Arnaud Liefooghe and Luís Paquete (Eds.), Vol. 11452. Springer, 99 -- 114.
18. Stephan Meisel, Christian Grimme, Jakob Bossek, Martin Wölck, Günter Rudolph, and Heike Trautmann. 2015. Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle. In Proceedings of the 17th Genetic and Evolutionary Computation Conference (GECCO). ACM, New York, NY, USA, 425--432.
19. Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory Landscape Analysis. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO). ACM, 829 -- 836.
20. Olaf Mersmann, Bernd Bischl, Heike Trautmann, Markus Wagner, Jakob Bossek, and Frank Neumann. 2013. A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem. Annals of Mathematics and Artificial Intelligence 69 (October 2013), 151 -- 182. Issue 2.
21. Yuichi Nagata and Shigenobu Kobayashi. 2013. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing 25, 2 (2013), 346 -- 363.
22. Aneta Neumann, Wanru Gao, Carola Doerr, Frank Neumann, and Markus Wagner. 2018. Discrepancy-Based Evolutionary Diversity Optimization. In Proceedings of the 20th Annual Conference on Genetic and Evolutionary Computation (GECCO). ACM, 991 -- 998.
23. Aneta Neumann, Wanru Gao, Markus Wagner, and Frank Neumann. 2018. Evolutionary Diversity Optimization Using Multi-Objective Indicators. CoRR abs/1811.06804 (2018), 1 -- 22. arXiv:1811.06804 http://arxiv.org/abs/1811.06804 Conference version appears at GECCO 2019.
24. Aneta Neumann, Christo Pyromallis, and Bradley Alexander. 2018. Evolution of Images with Diversity and Constraints Using a Generative Adversarial Network. In Neural Information Processing - 25th International Conference, ICONIP 2018, Siem Reap, Cambodia, December 13--16, 2018, Proceedings, Part VI (Lecture Notes in Computer Science), Long Cheng, Andrew Chi-Sing Leung, and Seiichi Ozawa (Eds.), Vol. 11306. Springer, 452--465.
25. Harald Niederreiter. 1972. Discrepancy and convex programming. Annali di matematica pura ed applicata. Series 4 93, 1 (1972), 89--97.
26. Josef Pihera and Nysret Musliu. 2014. Application of Machine Learning to Algorithm Selection for TSP. In Proceedings of the IEEE 26th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE, 47--54.
27. John Rischard Rice. 1976. The Algorithm Selection Problem. Advances in Computers 15 (1976), 65 -- 118.
28. Danilo Sanches, L. Darrell Whitley, and Renato Tinós. 2017. Building a Better Heuristic for the Traveling Salesman Problem: Combining Edge Assembly Crossover and Partition Crossover. In Proceedings of the 19th Annual Conference on Genetic and Evolutionary Computation (GECCO). ACM, 329 -- 336.
29. Kate Amanda Smith-Miles. 2009. Cross-Disciplinary Perspectives on Meta-Learning for Algorithm Selection. ACM Computing Surveys (CSUR) 41 (January 2009), 1 -- 25.
30. Kate Amanda Smith-Miles and Jano Ilja van Hemert. 2011. Discovering the Suitability of Optimisation Algorithms by Learning from Evolved Instances. Annals of Mathematics and Artificial Intelligence 61, 2 (2011), 87 -- 104.
31. Renato Tinós, Keld Helsgaun, and L. Darrell Whitley. 2018. Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic. In Proceedings of the 15th International Conference on Parallel Problem Solving from Nature (PPSN XV) (Lecture Notes in Computer Science (LNCS)), Anne Auger, Carlos Manuel Mira da Fonseca, Nuno Lourenço, Penousal Machado, Luis Paquete, and L. Darell Whitley (Eds.), Vol. 11101. Springer, 95 -- 107.
32. Tamara Ulrich and Lothar Thiele. 2011. Maximizing population diversity in single-objective optimization. In Genetic and Evolutionary Computation Conference, GECCO. ACM, 641--648.
33. David Hilton Wolpert and William G. Macready. 1997. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation (TEVC) 1, 1 (1997), 67 -- 82.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Generating random combinatorial structures

    • Random search heuristics