---
_id: '48876'
abstract:
- lang: eng
text: In recent years, Evolutionary Algorithms (EAs) have frequently been adopted
to evolve instances for optimization problems that pose difficulties for one algorithm
while being rather easy for a competitor and vice versa. Typically, this is achieved
by either minimizing or maximizing the performance difference or ratio which serves
as the fitness function. Repeating this process is useful to gain insights into
strengths/weaknesses of certain algorithms or to build a set of instances with
strong performance differences as a foundation for automatic per-instance algorithm
selection or configuration. We contribute to this branch of research by proposing
fitness-functions to evolve instances that show large performance differences
for more than just two algorithms simultaneously. As a proof-of-principle, we
evolve instances of the multi-component Traveling Thief Problem (TTP) for three
incomplete TTP-solvers. Our results point out that our strategies are promising,
but unsurprisingly their success strongly relies on the algorithms’ performance
complementarity.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
citation:
ama: 'Bossek J, Wagner M. Generating Instances with Performance Differences for
More than Just Two Algorithms. In: Proceedings of the Genetic and Evolutionary
Computation Conference Companion. GECCO’21. Association for Computing Machinery;
2021:1423–1432. doi:10.1145/3449726.3463165'
apa: Bossek, J., & Wagner, M. (2021). Generating Instances with Performance
Differences for More than Just Two Algorithms. Proceedings of the Genetic and
Evolutionary Computation Conference Companion, 1423–1432. https://doi.org/10.1145/3449726.3463165
bibtex: '@inproceedings{Bossek_Wagner_2021, place={New York, NY, USA}, series={GECCO’21},
title={Generating Instances with Performance Differences for More than Just Two
Algorithms}, DOI={10.1145/3449726.3463165},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference
Companion}, publisher={Association for Computing Machinery}, author={Bossek, Jakob
and Wagner, Markus}, year={2021}, pages={1423–1432}, collection={GECCO’21} }'
chicago: 'Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance
Differences for More than Just Two Algorithms.” In Proceedings of the Genetic
and Evolutionary Computation Conference Companion, 1423–1432. GECCO’21. New
York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449726.3463165.'
ieee: 'J. Bossek and M. Wagner, “Generating Instances with Performance Differences
for More than Just Two Algorithms,” in Proceedings of the Genetic and Evolutionary
Computation Conference Companion, 2021, pp. 1423–1432, doi: 10.1145/3449726.3463165.'
mla: Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences
for More than Just Two Algorithms.” Proceedings of the Genetic and Evolutionary
Computation Conference Companion, Association for Computing Machinery, 2021,
pp. 1423–1432, doi:10.1145/3449726.3463165.
short: 'J. Bossek, M. Wagner, in: Proceedings of the Genetic and Evolutionary Computation
Conference Companion, Association for Computing Machinery, New York, NY, USA,
2021, pp. 1423–1432.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:41Z
department:
- _id: '819'
doi: 10.1145/3449726.3463165
extern: '1'
keyword:
- evolutionary algorithms
- evolving instances
- fitness function
- instance hardness
- traveling thief problem (TTP)
language:
- iso: eng
page: 1423–1432
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference Companion
publication_identifier:
isbn:
- 978-1-4503-8351-6
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Generating Instances with Performance Differences for More than Just Two Algorithms
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48873'
abstract:
- lang: eng
text: Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP)
heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful
in generating satisfactory or even optimal solutions. However, the reasons for
their success are not yet fully understood. Recent approaches take an analytical
viewpoint and try to identify instance features, which make an instance hard or
easy to solve. We contribute to this area by generating instance sets for couples
of TSP algorithms A and B by maximizing/minimizing their performance difference
in order to generate instances which are easier to solve for one solver and much
harder to solve for the other. This instance set offers the potential to identify
key features which allow to distinguish between the problem hardness classes of
both algorithms.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Trautmann H. Evolving Instances for Maximizing Performance Differences
of State-of-the-Art Inexact TSP Solvers. In: Festa P, Sellmann M, Vanschoren J,
eds. Learning and Intelligent Optimization. Lecture Notes in Computer Science.
Springer International Publishing; 2016:48–59. doi:10.1007/978-3-319-50349-3_4'
apa: Bossek, J., & Trautmann, H. (2016). Evolving Instances for Maximizing Performance
Differences of State-of-the-Art Inexact TSP Solvers. In P. Festa, M. Sellmann,
& J. Vanschoren (Eds.), Learning and Intelligent Optimization (pp.
48–59). Springer International Publishing. https://doi.org/10.1007/978-3-319-50349-3_4
bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Cham}, series={Lecture Notes
in Computer Science}, title={Evolving Instances for Maximizing Performance Differences
of State-of-the-Art Inexact TSP Solvers}, DOI={10.1007/978-3-319-50349-3_4},
booktitle={Learning and Intelligent Optimization}, publisher={Springer International
Publishing}, author={Bossek, Jakob and Trautmann, Heike}, editor={Festa, Paola
and Sellmann, Meinolf and Vanschoren, Joaquin}, year={2016}, pages={48–59}, collection={Lecture
Notes in Computer Science} }'
chicago: 'Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing
Performance Differences of State-of-the-Art Inexact TSP Solvers.” In Learning
and Intelligent Optimization, edited by Paola Festa, Meinolf Sellmann, and
Joaquin Vanschoren, 48–59. Lecture Notes in Computer Science. Cham: Springer International
Publishing, 2016. https://doi.org/10.1007/978-3-319-50349-3_4.'
ieee: 'J. Bossek and H. Trautmann, “Evolving Instances for Maximizing Performance
Differences of State-of-the-Art Inexact TSP Solvers,” in Learning and Intelligent
Optimization, 2016, pp. 48–59, doi: 10.1007/978-3-319-50349-3_4.'
mla: Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance
Differences of State-of-the-Art Inexact TSP Solvers.” Learning and Intelligent
Optimization, edited by Paola Festa et al., Springer International Publishing,
2016, pp. 48–59, doi:10.1007/978-3-319-50349-3_4.
short: 'J. Bossek, H. Trautmann, in: P. Festa, M. Sellmann, J. Vanschoren (Eds.),
Learning and Intelligent Optimization, Springer International Publishing, Cham,
2016, pp. 48–59.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:05Z
department:
- _id: '819'
doi: 10.1007/978-3-319-50349-3_4
editor:
- first_name: Paola
full_name: Festa, Paola
last_name: Festa
- first_name: Meinolf
full_name: Sellmann, Meinolf
last_name: Sellmann
- first_name: Joaquin
full_name: Vanschoren, Joaquin
last_name: Vanschoren
extern: '1'
keyword:
- Algorithm selection
- Feature selection
- Instance hardness
- TSP
language:
- iso: eng
page: 48–59
place: Cham
publication: Learning and Intelligent Optimization
publication_identifier:
isbn:
- 978-3-319-50349-3
publication_status: published
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: Evolving Instances for Maximizing Performance Differences of State-of-the-Art
Inexact TSP Solvers
type: conference
user_id: '102979'
year: '2016'
...
---
_id: '48874'
abstract:
- lang: eng
text: State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem
TSP are known to mostly yield high-quality solutions in reasonable computation
times. With the purpose of understanding different levels of instance difficulties,
instances for the current State of the Art heuristic TSP solvers LKH+restart and
EAX+restart are presented which are evolved using a sophisticated evolutionary
algorithm. More specifically, the performance differences of the respective solvers
are maximized resulting in instances which are easier to solve for one solver
and much more difficult for the other. Focusing on both optimization directions,
instance features are identified which characterize both types of instances and
increase the understanding of solver performance differences.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Trautmann H. Understanding Characteristics of Evolved Instances
for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
In: Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037.
AI*IA 2016. Springer-Verlag; 2016:3–12. doi:10.1007/978-3-319-49130-1_1'
apa: Bossek, J., & Trautmann, H. (2016). Understanding Characteristics of Evolved
Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
Proceedings of the XV International Conference of the Italian Association for
Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037,
3–12. https://doi.org/10.1007/978-3-319-49130-1_1
bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Berlin, Heidelberg}, series={AI*IA
2016}, title={Understanding Characteristics of Evolved Instances for State-of-the-Art
Inexact TSP Solvers with Maximum Performance Difference}, DOI={10.1007/978-3-319-49130-1_1},
booktitle={Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037},
publisher={Springer-Verlag}, author={Bossek, Jakob and Trautmann, Heike}, year={2016},
pages={3–12}, collection={AI*IA 2016} }'
chicago: 'Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of
Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance
Difference.” In Proceedings of the XV International Conference of the Italian
Association for Artificial Intelligence on Advances in Artificial Intelligence
- Volume 10037, 3–12. AI*IA 2016. Berlin, Heidelberg: Springer-Verlag, 2016.
https://doi.org/10.1007/978-3-319-49130-1_1.'
ieee: 'J. Bossek and H. Trautmann, “Understanding Characteristics of Evolved Instances
for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference,”
in Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037,
2016, pp. 3–12, doi: 10.1007/978-3-319-49130-1_1.'
mla: Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved
Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.”
Proceedings of the XV International Conference of the Italian Association for
Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037,
Springer-Verlag, 2016, pp. 3–12, doi:10.1007/978-3-319-49130-1_1.
short: 'J. Bossek, H. Trautmann, in: Proceedings of the XV International Conference
of the Italian Association for Artificial Intelligence on Advances in Artificial
Intelligence - Volume 10037, Springer-Verlag, Berlin, Heidelberg, 2016, pp. 3–12.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:11Z
doi: 10.1007/978-3-319-49130-1_1
extern: '1'
keyword:
- Combinatorial optimization
- Instance hardness
- Metaheuristics
- Transportation
- TSP
language:
- iso: eng
page: 3–12
place: Berlin, Heidelberg
publication: Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037
publication_identifier:
isbn:
- 978-3-319-49129-5
publication_status: published
publisher: Springer-Verlag
series_title: AI*IA 2016
status: public
title: Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact
TSP Solvers with Maximum Performance Difference
type: conference
user_id: '102979'
year: '2016'
...