---
_id: '48861'
abstract:
- lang: eng
text: Generating instances of different properties is key to algorithm selection
methods that differentiate between the performance of different solvers for a
given combinatorial optimization problem. A wide range of methods using evolutionary
computation techniques has been introduced in recent years. With this paper, we
contribute to this area of research by providing a new approach based on quality
diversity (QD) that is able to explore the whole feature space. QD algorithms
allow to create solutions of high quality within a given feature space by splitting
it up into boxes and improving solution quality within each box. We use our QD
approach for the generation of TSP instances to visualize and analyze the variety
of instances differentiating various TSP solvers and compare it to instances generated
by established approaches from the literature.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann F. Exploring the Feature Space of TSP Instances Using Quality
Diversity. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’22. Association for Computing Machinery; 2022:186–194. doi:10.1145/3512290.3528851'
apa: Bossek, J., & Neumann, F. (2022). Exploring the Feature Space of TSP Instances
Using Quality Diversity. Proceedings of the Genetic and Evolutionary Computation
Conference, 186–194. https://doi.org/10.1145/3512290.3528851
bibtex: '@inproceedings{Bossek_Neumann_2022, place={New York, NY, USA}, series={GECCO
’22}, title={Exploring the Feature Space of TSP Instances Using Quality Diversity},
DOI={10.1145/3512290.3528851},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank}, year={2022}, pages={186–194}, collection={GECCO ’22} }'
chicago: 'Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP
Instances Using Quality Diversity.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 186–194. GECCO ’22. New York, NY, USA: Association
for Computing Machinery, 2022. https://doi.org/10.1145/3512290.3528851.'
ieee: 'J. Bossek and F. Neumann, “Exploring the Feature Space of TSP Instances Using
Quality Diversity,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2022, pp. 186–194, doi: 10.1145/3512290.3528851.'
mla: Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP Instances
Using Quality Diversity.” Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, 2022, pp. 186–194, doi:10.1145/3512290.3528851.
short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2022, pp.
186–194.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:56Z
department:
- _id: '819'
doi: 10.1145/3512290.3528851
extern: '1'
keyword:
- instance features
- instance generation
- quality diversity
- TSP
language:
- iso: eng
page: 186–194
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-9237-2
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’22
status: public
title: Exploring the Feature Space of TSP Instances Using Quality Diversity
type: conference
user_id: '102979'
year: '2022'
...
---
_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: Proceedings
of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association
for Computing Machinery; 2021:1–15.'
apa: 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 Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms (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 Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, 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
Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,
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.” Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, 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'
...
---
_id: '48842'
abstract:
- lang: eng
text: '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.'
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: '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: Proceedings
of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. FOGA
’19. Association for Computing Machinery; 2019:58–71. doi:10.1145/3299904.3340307'
apa: 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. Proceedings of the 15th ACM/SIGEVO Conference on Foundations of
Genetic Algorithms, 58–71. https://doi.org/10.1145/3299904.3340307
bibtex: '@inproceedings{Bossek_Kerschke_Neumann_Wagner_Neumann_Trautmann_2019, place={New
York, NY, USA}, series={FOGA ’19}, title={Evolving Diverse TSP Instances by Means
of Novel and Creative Mutation Operators}, DOI={10.1145/3299904.3340307},
booktitle={Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms}, publisher={Association for Computing Machinery}, author={Bossek,
Jakob and Kerschke, Pascal and Neumann, Aneta and Wagner, Markus and Neumann,
Frank and Trautmann, Heike}, year={2019}, pages={58–71}, collection={FOGA ’19}
}'
chicago: '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 15th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, 58–71. FOGA ’19. New York, NY, USA: Association for
Computing Machinery, 2019. https://doi.org/10.1145/3299904.3340307.'
ieee: '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 15th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms, 2019, pp. 58–71, doi: 10.1145/3299904.3340307.'
mla: Bossek, Jakob, et al. “Evolving Diverse TSP Instances by Means of Novel and
Creative Mutation Operators.” Proceedings of the 15th ACM/SIGEVO Conference
on Foundations of Genetic Algorithms, Association for Computing Machinery,
2019, pp. 58–71, doi:10.1145/3299904.3340307.
short: 'J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, H. Trautmann,
in: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,
Association for Computing Machinery, New York, NY, USA, 2019, pp. 58–71.'
date_created: 2023-11-14T15:58:52Z
date_updated: 2023-12-13T10:42:57Z
department:
- _id: '819'
doi: 10.1145/3299904.3340307
extern: '1'
keyword:
- benchmarking
- instance features
- optimization
- problem generation
- traveling salesperson problem
language:
- iso: eng
page: 58–71
place: New York, NY, USA
publication: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-1-4503-6254-2
publication_status: published
publisher: Association for Computing Machinery
series_title: FOGA ’19
status: public
title: Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators
type: conference
user_id: '102979'
year: '2019'
...