Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem

M. Seiler, J. Pohl, J. Bossek, P. Kerschke, H. Trautmann, in: T. Bäck, M. Preuss, A. Deutz, H. Wang, C. Doerr, M. Emmerich, H. Trautmann (Eds.), Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI), Leiden, The Netherlands, 2020, pp. 48–64.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
Editor
Bäck, Thomas; Preuss, Mike; Deutz, André; Wang, Hao; Doerr, Carola; Emmerich, Michael; Trautmann, Heike
Abstract
In this work we focus on the well-known Euclidean Traveling Salesperson Problem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in the context of per-instance algorithm selection (AS). We evolve instances with 1000 nodes where the solvers show strongly different performance profiles. These instances serve as a basis for an exploratory study on the identification of well-discriminating problem characteristics (features). Our results in a nutshell: we show that even though (1) promising features exist, (2) these are in line with previous results from the literature, and (3) models trained with these features are more accurate than models adopting sophisticated feature selection methods, the advantage is not close to the virtual best solver in terms of penalized average runtime and so is the performance gain over the single best solver. However, we show that a feature-free deep neural network based approach solely based on visual representation of the instances already matches classical AS model results and thus shows huge potential for future studies.
Publishing Year
Proceedings Title
Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI)
Page
48–64
LibreCat-ID

Cite this

Seiler M, Pohl J, Bossek J, Kerschke P, Trautmann H. Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem. In: Bäck T, Preuss M, Deutz A, et al., eds. Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI). ; 2020:48–64. doi:10.1007/978-3-030-58112-1_4
Seiler, M., Pohl, J., Bossek, J., Kerschke, P., & Trautmann, H. (2020). Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem. In T. Bäck, M. Preuss, A. Deutz, H. Wang, C. Doerr, M. Emmerich, & H. Trautmann (Eds.), Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI) (pp. 48–64). https://doi.org/10.1007/978-3-030-58112-1_4
@inproceedings{Seiler_Pohl_Bossek_Kerschke_Trautmann_2020, place={Leiden, The Netherlands}, title={Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem}, DOI={10.1007/978-3-030-58112-1_4}, booktitle={Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI)}, author={Seiler, Moritz and Pohl, Janina and Bossek, Jakob and Kerschke, Pascal and Trautmann, Heike}, editor={Bäck, Thomas and Preuss, Mike and Deutz, André and Wang, Hao and Doerr, Carola and Emmerich, Michael and Trautmann, Heike}, year={2020}, pages={48–64} }
Seiler, Moritz, Janina Pohl, Jakob Bossek, Pascal Kerschke, and Heike Trautmann. “Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem.” In Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI), edited by Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, and Heike Trautmann, 48–64. Leiden, The Netherlands, 2020. https://doi.org/10.1007/978-3-030-58112-1_4.
M. Seiler, J. Pohl, J. Bossek, P. Kerschke, and H. Trautmann, “Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem,” in Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI), 2020, pp. 48–64, doi: 10.1007/978-3-030-58112-1_4.
Seiler, Moritz, et al. “Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem.” Proceedings of the 16$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XVI), edited by Thomas Bäck et al., 2020, pp. 48–64, doi:10.1007/978-3-030-58112-1_4.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar