On the Potential of Normalized TSP Features for Automated Algorithm Selection

J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, in: for Computing Machinery Association (Ed.), Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI), Association for Computing Machinery, Dornbirn, Austria, 2021, pp. 1–15.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
Heins, Jonathan; Bossek, JakobLibreCat ; Pohl, Janina; Seiler, MoritzLibreCat; Trautmann, HeikeLibreCat ; Kerschke, Pascal
Editor
Computing Machinery Association, for
Abstract
Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithm selection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph (NNG) transformation of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. Eventually, a proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features.
Publishing Year
Proceedings Title
Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI)
Page
1–15
LibreCat-ID

Cite this

Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. On the Potential of Normalized TSP Features for Automated Algorithm Selection. In: Computing Machinery Association for, ed. Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI). Association for Computing Machinery; 2021:1–15. doi:10.1145/3450218.3477308
Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., & Kerschke, P. (2021). On the Potential of Normalized TSP Features for Automated Algorithm Selection. In for Computing Machinery Association (Ed.), Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI) (pp. 1–15). Association for Computing Machinery. https://doi.org/10.1145/3450218.3477308
@inproceedings{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2021, place={Dornbirn, Austria}, title={On the Potential of Normalized TSP Features for Automated Algorithm Selection}, DOI={10.1145/3450218.3477308}, booktitle={Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI)}, publisher={Association for Computing Machinery}, author={Heins, Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal}, editor={Computing Machinery Association, for}, year={2021}, pages={1–15} }
Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann, and Pascal Kerschke. “On the Potential of Normalized TSP Features for Automated Algorithm Selection.” In Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI), edited by for Computing Machinery Association, 1–15. Dornbirn, Austria: Association for Computing Machinery, 2021. https://doi.org/10.1145/3450218.3477308.
J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “On the Potential of Normalized TSP Features for Automated Algorithm Selection,” in Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of genetic Algorithms (FOGA XVI), 2021, pp. 1–15, doi: 10.1145/3450218.3477308.
Heins, Jonathan, et al. “On the Potential of Normalized TSP Features for Automated Algorithm Selection.” Proceedings of the 16$^th$ ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVI), edited by for Computing Machinery Association, Association for Computing Machinery, 2021, pp. 1–15, doi:10.1145/3450218.3477308.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar