Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators
J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, H. Trautmann, in: T. Friedrich, C. Doerr, D. Arnold (Eds.), Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), Potsdam, Germany, 2019, pp. 58–71.
Download
No fulltext has been uploaded.
Conference Paper
| English
Author
Bossek, Jakob;
Kerschke, Pascal;
Neumann, Aneta;
Wagner, Markus;
Neumann, Frank;
Trautmann, HeikeLibreCat 
Editor
Friedrich, Tobias;
Doerr, Carola;
Arnold, Dirk
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.
Publishing Year
Proceedings Title
Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)
Page
58–71
LibreCat-ID
Cite this
Bossek J, Kerschke P, Neumann A, Wagner M, Neumann F, Trautmann H. Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators. In: Friedrich T, Doerr C, Arnold D, eds. Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV). ; 2019:58–71. doi:10.1145/3299904.3340307
Bossek, J., Kerschke, P., Neumann, A., Wagner, M., Neumann, F., & Trautmann, H. (2019). Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators. In T. Friedrich, C. Doerr, & D. Arnold (Eds.), Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV) (pp. 58–71). https://doi.org/10.1145/3299904.3340307
@inproceedings{Bossek_Kerschke_Neumann_Wagner_Neumann_Trautmann_2019, place={Potsdam, Germany}, title={Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators}, DOI={10.1145/3299904.3340307}, booktitle={Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)}, author={Bossek, Jakob and Kerschke, Pascal and Neumann, Aneta and Wagner, Markus and Neumann, Frank and Trautmann, Heike}, editor={Friedrich, Tobias and Doerr, Carola and Arnold, Dirk}, year={2019}, pages={58–71} }
Bossek, Jakob, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. “Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators.” In Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), edited by Tobias Friedrich, Carola Doerr, and Dirk Arnold, 58–71. Potsdam, Germany, 2019. https://doi.org/10.1145/3299904.3340307.
J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, and H. Trautmann, “Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators,” in Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), 2019, pp. 58–71, doi: 10.1145/3299904.3340307.
Bossek, Jakob, et al. “Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators.” Proceedings of the 15$^th$ ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), edited by Tobias Friedrich et al., 2019, pp. 58–71, doi:10.1145/3299904.3340307.
Google Scholar