research-article

On the potential of normalized TSP features for automated algorithm selection

Authors:

Jonathan Heins,

Heike Trautmann,

Pascal KerschkeAuthors Info & Claims

FOGA '21: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Article No.: 7, Pages 1 - 15

https://doi.org/10.1145/3450218.3477308

Published: 06 September 2021 Publication History

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.

References

[1]

David L. Applegate, Robert E. Bixby, Vasek Chvátal, and William J. Cook. 2006. The Traveling Salesman Problem. Princeton University Press.

[2]

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.

Digital Library

[3]

Jakob Bossek. 2017. salesperson: Computation of Instance Features and R Interface to the State-of-the-Art Exact and Inexact Solvers for the Traveling Salesperson Problem. https://github.com/jakobbossek/salesperson R package version 1.0.0.

[4]

Jakob Bossek, Katrin Casel, Pascal Kerschke, and Frank Neumann. 2020. The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. In Proceedings of the 22nd Annual Conference on Genetic and Evolutionary Computation (Cancún, Mexico) (GECCO '20). ACM, 1286 -- 1294.

Digital Library

[5]

Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. 2019. Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Potsdam, Germany) (FOGA '19). Association for Computing Machinery, 58--71.

Digital Library

[6]

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) (Ischia, Italy). Springer, 48 -- 59.

[7]

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) (Genova, Italy). Springer, 3 -- 12.

Digital Library

[8]

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 (Madrid, Spain) (GECCO '15). Association for Computing Machinery, 377--384.

Digital Library

[9]

Keld Helsgaun. 2009. General k-Opt Submoves for the Lin-Kernighan TSP Heuristic. Mathematical Programming Computation 1 (10 2009), 119--163.

[10]

G. E. Hinton and R. R. Salakhutdinov. 2006. Reducing the Dimensionality of Data with Neural Networks. Science 313, 5786 (2006), 504--507.

[11]

Frank Hutter, Lin Xu, Holger Hoos, and Kevin Leyton-Brown. 2014. Algorithm Runtime Prediction: The State of the Art. Artificial Intelligence 206 (11 2014), 79 -- 111.

Digital Library

[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 Companion (Kyoto, Japan) (GECCO '18). ACM, 1737 -- 1744.

Digital Library

[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.

Digital Library

[14]

Pascal Kerschke, Lars Kotthoff, Jakob Bossek, Holger Hoos, and Heike Trautmann. 2018. Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation 26, 4 (2018), 597 -- 620.

Digital Library

[15]

Lars Kotthoff. 2014. Algorithm Selection for Combinatorial Search Problems: A Survey. AI Magazine 35, 3 (2014), 48 -- 60.

[16]

Lars Kotthoff, Pascal Kerschke, Holger Hoos, and Heike Trautmann. 2015. Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection. In Learning and Intelligent Optimization. Springer International Publishing, 202--217.

[17]

Shen Lin and Brian W. Kernighan. 1973. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research 21, 2 (04 1973), 498--516.

Digital Library

[18]

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, 2 (2013), 151--182.

Digital Library

[19]

Yuichi Nagata and Shigenobu Kobayashi. 1997. Edge Assembly Crossover: A High-power Genetic Algorithm for the Traveling Salesman Problem. In Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA 1997). Morgan-Kaufmann, San Francisco, CA, 450--457.

[20]

Yuichi Nagata and Shigenobu Kobayashi. 2013. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing 25 (05 2013), 346--363.

Digital Library

[21]

Samadhi Nallaperuma, Markus Wagner, Frank Neumann, Bernd Bischl, Olaf Mersmann, and Heike Trautmann. 2013. A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem. In Proceedings of the 12th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Adelaide, Australia) (FOGA '13). ACM, 147 -- 160.

Digital Library

[22]

Josef Pihera and Nysret Musliu. 2014. Application of Machine Learning to Algorithm Selection for TSP. In Proceedings of the 2014 IEEE 26th International Conference on Tools with Artificial Intelligence (ICTAI '14). IEEE Computer Society, USA, 47 -- 54.

Digital Library

[23]

R Core Team. 2020. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. https://www.R-project.org/

[24]

Gerhard Reinelt. 1991. TSPLIB-A Traveling Salesman Problem Library. ORSA Journal on Computing 3, 4 (1991), 376--384.

[25]

John R. Rice. 1976. The Algorithm Selection Problem. In Department of Computer Science Technical Report. Advances in Computers, Vol. 15. Elsevier, 65 -- 118.

[26]

Gabriel Robins and Jeffrey S. Salowe. 1994. On the Maximum Degree of Minimum Spanning Trees. In Proceedings of the Tenth Annual Symposium on Computational Geometry (Stony Brook, New York, USA) (SCG '94). Association for Computing Machinery, New York, NY, USA, 250--258.

Digital Library

[27]

Alireza Sarveniazi. 2014. An Actual Survey of Dimensionality Reduction. American Journal of Computational Mathematics 4 (2014), 55--72.

[28]

Moritz Seiler, Janina Pohl, Jakob Bossek, Pascal Kerschke, and Heike Trautmann. 2020. Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem. In Parallel Problem Solving from Nature - PPSN XVI. Springer International Publishing, Cham, 48--64.

[29]

Kate Smith-Miles, Jano Ilja van Hemert, and Xin Yu Lim. 2010. Understanding TSP Difficulty by Learning from Evolved Instances. In Proceedings of the 4th International Conference on Learning and Intelligent Optimization (LION) (Venice, Italy), Vol. 6073. Springer, 266 -- 280.

[30]

Jarkko Venna and Samuel Kaski. 2005. Local multidimensional scaling with controlled tradeoff between trustworthiness and continuity. In In Proceedings of 5th Workshop on Self-Organizing Maps (Paris, France). 695 -- 702.

Cited By

Heins JSchäpermeier LKerschke PWhitley D(2024)Dancing to the State of the Art?Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_7(100-115)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_7
Vinzent Seiler MRook JHeins JLudger Preuß OBossek JTrautmann H(2023)Using Reinforcement Learning for Per-Instance Algorithm Configuration on the TSP2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10372008(361-368)Online publication date: 5-Dec-2023
https://doi.org/10.1109/SSCI52147.2023.10372008
Heins JBossek JPohl JSeiler MTrautmann HKerschke P(2023)A study on the effects of normalized TSP features for automated algorithm selectionTheoretical Computer Science10.1016/j.tcs.2022.10.019940:PB(123-145)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.019

Index Terms

On the potential of normalized TSP features for automated algorithm selection
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by regression
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Computing diverse sets of high quality TSP tours by EAX-based evolutionary diversity optimisation
FOGA '21: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Evolutionary algorithms based on edge assembly crossover (EAX) constitute some of the best performing incomplete solvers for the well-known traveling salesperson problem (TSP). Often, it is desirable to compute not just a single solution for a given ...
A study on the effects of normalized TSP features for automated algorithm selection
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-...
Highlights
- Study on the effects of feature normalization in algorithm selection for the TSP.
Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem
Parallel Problem Solving from Nature – PPSN XVI
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 nodes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '21: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

September 2021

130 pages

ISBN:9781450383523

DOI:10.1145/3450218

General Chair:
Steffen Finck
Vorarlberg University of Applied Sciences
,
Program Chairs:
Michael Hellwig
Vorarlberg University of Applied Sciences
,
Pietro S. Oliveto
University of Sheffield

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 September 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '21

Sponsor:

SIGEVO

FOGA '21: Foundations of Genetic Algorithms XVI

September 6 - 8, 2021

Virtual Event, Austria

Acceptance Rates

FOGA '21 Paper Acceptance Rate 10 of 21 submissions, 48%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
166
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Heins JSchäpermeier LKerschke PWhitley D(2024)Dancing to the State of the Art?Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_7(100-115)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_7
Vinzent Seiler MRook JHeins JLudger Preuß OBossek JTrautmann H(2023)Using Reinforcement Learning for Per-Instance Algorithm Configuration on the TSP2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10372008(361-368)Online publication date: 5-Dec-2023
https://doi.org/10.1109/SSCI52147.2023.10372008
Heins JBossek JPohl JSeiler MTrautmann HKerschke P(2023)A study on the effects of normalized TSP features for automated algorithm selectionTheoretical Computer Science10.1016/j.tcs.2022.10.019940:PB(123-145)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.019

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents