---
_id: '48881'
abstract:
- lang: eng
  text: '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.'
author:
- first_name: Jonathan
  full_name: Heins, Jonathan
  last_name: Heins
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Janina
  full_name: Pohl, Janina
  last_name: Pohl
- first_name: Moritz
  full_name: Seiler, Moritz
  last_name: Seiler
- first_name: Heike
  full_name: Trautmann, Heike
  last_name: Trautmann
- first_name: Pascal
  full_name: Kerschke, Pascal
  last_name: Kerschke
citation:
  ama: 'Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. On the Potential
    of Normalized TSP Features for Automated Algorithm Selection. In: <i>Proceedings
    of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>. Association
    for Computing Machinery; 2021:1–15.'
  apa: Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., &#38; Kerschke,
    P. (2021). On the Potential of Normalized TSP Features for Automated Algorithm
    Selection. In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i> (pp. 1–15). Association for Computing Machinery.
  bibtex: '@inbook{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2021, place={New York,
    NY, USA}, title={On the Potential of Normalized TSP Features for Automated Algorithm
    Selection}, booktitle={Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Heins,
    Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann,
    Heike and Kerschke, Pascal}, year={2021}, pages={1–15} }'
  chicago: '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 <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i>, 1–15. New York, NY, USA: Association for Computing
    Machinery, 2021.'
  ieee: '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
    <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>,
    New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–15.'
  mla: Heins, Jonathan, et al. “On the Potential of Normalized TSP Features for Automated
    Algorithm Selection.” <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i>, Association for Computing Machinery, 2021, pp. 1–15.
  short: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, in:
    Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,
    Association for Computing Machinery, New York, NY, USA, 2021, pp. 1–15.'
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:47:23Z
department:
- _id: '819'
extern: '1'
keyword:
- automated algorithm selection
- graph theory
- instance features
- normalization
- traveling salesperson problem (TSP)
language:
- iso: eng
page: 1–15
place: New York, NY, USA
publication: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
  Algorithms
publication_identifier:
  isbn:
  - 978-1-4503-8352-3
publisher: Association for Computing Machinery
status: public
title: On the Potential of Normalized TSP Features for Automated Algorithm Selection
type: book_chapter
user_id: '102979'
year: '2021'
...