---
_id: '48869'
abstract:
- lang: eng
text: Evolutionary algorithms have been shown to obtain good solutions for complex
optimization problems in static and dynamic environments. It is important to understand
the behaviour of evolutionary algorithms for complex optimization problems that
also involve dynamic and/or stochastic components in a systematic way in order
to further increase their applicability to real-world problems. We investigate
the node weighted traveling salesperson problem (W-TSP), which provides an abstraction
of a wide range of weighted TSP problems, in dynamic settings. In the dynamic
setting of the problem, items that have to be collected as part of a TSP tour
change over time. We first present a dynamic setup for the dynamic W-TSP parameterized
by different types of changes that are applied to the set of items to be collected
when traversing the tour. Our first experimental investigations study the impact
of such changes on resulting optimized tours in order to provide structural insights
of optimization solutions. Afterwards, we investigate simple mutation-based evolutionary
algorithms and study the impact of the mutation operators and the use of populations
with dealing with the dynamic changes to the node weights of the problem.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. On the Impact of Basic Mutation Operators
and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling
Salesperson Problem. In: Proceedings of the Genetic and Evolutionary Computation
Conference. GECCO’23. Association for Computing Machinery; 2023:248–256. doi:10.1145/3583131.3590384'
apa: Bossek, J., Neumann, A., & Neumann, F. (2023). On the Impact of Basic Mutation
Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted
Traveling Salesperson Problem. Proceedings of the Genetic and Evolutionary
Computation Conference, 248–256. https://doi.org/10.1145/3583131.3590384
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2023, place={New York, NY, USA},
series={GECCO’23}, title={On the Impact of Basic Mutation Operators and Populations
within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson
Problem}, DOI={10.1145/3583131.3590384},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Aneta and Neumann, Frank}, year={2023}, pages={248–256}, collection={GECCO’23}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “On the Impact of Basic
Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic
Weighted Traveling Salesperson Problem.” In Proceedings of the Genetic and
Evolutionary Computation Conference, 248–256. GECCO’23. New York, NY, USA:
Association for Computing Machinery, 2023. https://doi.org/10.1145/3583131.3590384.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “On the Impact of Basic Mutation Operators
and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling
Salesperson Problem,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2023, pp. 248–256, doi: 10.1145/3583131.3590384.'
mla: Bossek, Jakob, et al. “On the Impact of Basic Mutation Operators and Populations
within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson
Problem.” Proceedings of the Genetic and Evolutionary Computation Conference,
Association for Computing Machinery, 2023, pp. 248–256, doi:10.1145/3583131.3590384.
short: 'J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2023, pp. 248–256.'
date_created: 2023-11-14T15:58:56Z
date_updated: 2023-12-13T10:46:27Z
department:
- _id: '819'
doi: 10.1145/3583131.3590384
extern: '1'
keyword:
- dynamic optimization
- evolutionary algorithms
- re-optimization
- weighted traveling salesperson problem
language:
- iso: eng
page: 248–256
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- '9798400701191'
publisher: Association for Computing Machinery
series_title: GECCO’23
status: public
title: On the Impact of Basic Mutation Operators and Populations within Evolutionary
Algorithms for the Dynamic Weighted Traveling Salesperson Problem
type: conference
user_id: '102979'
year: '2023'
...
---
_id: '46310'
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) nearest neighbor relationships
of the input instance. To this end we theoretically derive minimum and maximum
values for properties of MSTs and k-nearest neighbor graphs (NNG) 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. 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
id: '105520'
last_name: Seiler
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
citation:
ama: Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. A study on the
effects of normalized TSP features for automated algorithm selection. Theoretical
Computer Science. 2023;940:123-145. doi:https://doi.org/10.1016/j.tcs.2022.10.019
apa: Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., & Kerschke,
P. (2023). A study on the effects of normalized TSP features for automated algorithm
selection. Theoretical Computer Science, 940, 123–145. https://doi.org/10.1016/j.tcs.2022.10.019
bibtex: '@article{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2023, title={A study
on the effects of normalized TSP features for automated algorithm selection},
volume={940}, DOI={https://doi.org/10.1016/j.tcs.2022.10.019},
journal={Theoretical Computer Science}, author={Heins, Jonathan and Bossek, Jakob
and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal},
year={2023}, pages={123–145} }'
chicago: 'Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann,
and Pascal Kerschke. “A Study on the Effects of Normalized TSP Features for Automated
Algorithm Selection.” Theoretical Computer Science 940 (2023): 123–45.
https://doi.org/10.1016/j.tcs.2022.10.019.'
ieee: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “A
study on the effects of normalized TSP features for automated algorithm selection,”
Theoretical Computer Science, vol. 940, pp. 123–145, 2023, doi: https://doi.org/10.1016/j.tcs.2022.10.019.'
mla: Heins, Jonathan, et al. “A Study on the Effects of Normalized TSP Features
for Automated Algorithm Selection.” Theoretical Computer Science, vol.
940, 2023, pp. 123–45, doi:https://doi.org/10.1016/j.tcs.2022.10.019.
short: J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, Theoretical
Computer Science 940 (2023) 123–145.
date_created: 2023-08-04T07:18:38Z
date_updated: 2024-06-10T11:57:21Z
department:
- _id: '34'
- _id: '819'
doi: https://doi.org/10.1016/j.tcs.2022.10.019
intvolume: ' 940'
keyword:
- Feature normalization
- Algorithm selection
- Traveling salesperson problem
language:
- iso: eng
page: 123-145
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
status: public
title: A study on the effects of normalized TSP features for automated algorithm selection
type: journal_article
user_id: '15504'
volume: 940
year: '2023'
...
---
_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: '48893'
abstract:
- lang: eng
text: Computing diverse sets of high-quality solutions has gained increasing attention
among the evolutionary computation community in recent years. It allows practitioners
to choose from a set of high-quality alternatives. In this paper, we employ a
population diversity measure, called the high-order entropy measure, in an evolutionary
algorithm to compute a diverse set of high-quality solutions for the Traveling
Salesperson Problem. In contrast to previous studies, our approach allows diversifying
segments of tours containing several edges based on the entropy measure. We examine
the resulting evolutionary diversity optimisation approach precisely in terms
of the final set of solutions and theoretical properties. Experimental results
show significant improvements compared to a recently proposed edge-based diversity
optimisation approach when working with a large population of solutions or long
segments.
author:
- first_name: Adel
full_name: Nikfarjam, Adel
last_name: Nikfarjam
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Entropy-Based Evolutionary Diversity
Optimisation for the Traveling Salesperson Problem. In: Proceedings of the
Genetic and Evolutionary Computation Conference. GECCO’21. Association for
Computing Machinery; 2021:600–608. doi:10.1145/3449639.3459384'
apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Entropy-Based
Evolutionary Diversity Optimisation for the Traveling Salesperson Problem. Proceedings
of the Genetic and Evolutionary Computation Conference, 600–608. https://doi.org/10.1145/3449639.3459384
bibtex: '@inproceedings{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York,
NY, USA}, series={GECCO’21}, title={Entropy-Based Evolutionary Diversity Optimisation
for the Traveling Salesperson Problem}, DOI={10.1145/3449639.3459384},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Nikfarjam, Adel and Bossek,
Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={600–608}, collection={GECCO’21}
}'
chicago: 'Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Entropy-Based
Evolutionary Diversity Optimisation for the Traveling Salesperson Problem.” In
Proceedings of the Genetic and Evolutionary Computation Conference, 600–608.
GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459384.'
ieee: 'A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Entropy-Based Evolutionary
Diversity Optimisation for the Traveling Salesperson Problem,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2021, pp. 600–608,
doi: 10.1145/3449639.3459384.'
mla: Nikfarjam, Adel, et al. “Entropy-Based Evolutionary Diversity Optimisation
for the Traveling Salesperson Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2021, pp. 600–608,
doi:10.1145/3449639.3459384.
short: 'A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the
Genetic and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2021, pp. 600–608.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:50:06Z
department:
- _id: '819'
doi: 10.1145/3449639.3459384
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimisation
- high-order entropy
- traveling salesperson problem
language:
- iso: eng
page: 600–608
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson
Problem
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48892'
abstract:
- lang: eng
text: 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 problem, but a diverse set of high quality solutions from which a decision
maker can choose one for implementation. Currently, there are only a few approaches
for computing a diverse solution set for the TSP. Furthermore, almost all of them
assume that the optimal solution is known. In this paper, we introduce evolutionary
diversity optimisation (EDO) approaches for the TSP that find a diverse set of
tours when the optimal tour is known or unknown. We show how to adopt EAX to not
only find a high-quality solution but also to maximise the diversity of the population.
The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse
high-quality tours when the optimal solution for the TSP is known or unknown.
A comparison to existing approaches shows that they are clearly outperformed by
EAX-EDO.
author:
- first_name: Adel
full_name: Nikfarjam, Adel
last_name: Nikfarjam
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Computing Diverse Sets of High
Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation. In: Proceedings
of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms. Association
for Computing Machinery; 2021:1–11.'
apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Computing
Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation.
In Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms (pp. 1–11). Association for Computing Machinery.
bibtex: '@inbook{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York, NY, USA},
title={Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary
Diversity Optimisation}, booktitle={Proceedings of the 16th ACM}/SIGEVO Conference
on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery},
author={Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank},
year={2021}, pages={1–11} }'
chicago: 'Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Computing
Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation.”
In Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms, 1–11. New York, NY, USA: Association for Computing Machinery,
2021.'
ieee: 'A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Computing Diverse Sets
of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation,” in
Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms,
New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–11.'
mla: Nikfarjam, Adel, et al. “Computing Diverse Sets of High Quality TSP Tours by
EAX-Based Evolutionary Diversity Optimisation.” Proceedings of the 16th ACM}/SIGEVO
Conference on Foundations of Genetic Algorithms, Association for Computing
Machinery, 2021, pp. 1–11.
short: 'A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the
16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms, Association
for Computing Machinery, New York, NY, USA, 2021, pp. 1–11.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:59Z
department:
- _id: '819'
extern: '1'
keyword:
- edge assembly crossover (EAX)
- evolutionary algorithms
- evolutionary diversity optimisation (EDO)
- traveling salesperson problem (TSP)
language:
- iso: eng
page: 1–11
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: Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary
Diversity Optimisation
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '48897'
abstract:
- lang: eng
text: '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 where the solvers show strongly different performance profiles. These instances
serve as a basis for an exploratory study on the identification of well-discriminating
problem characteristics (features). Our results in a nutshell: we show that even
though (1) promising features exist, (2) these are in line with previous results
from the literature, and (3) models trained with these features are more accurate
than models adopting sophisticated feature selection methods, the advantage is
not close to the virtual best solver in terms of penalized average runtime and
so is the performance gain over the single best solver. However, we show that
a feature-free deep neural network based approach solely based on visual representation
of the instances already matches classical AS model results and thus shows huge
potential for future studies.'
author:
- first_name: Moritz
full_name: Seiler, Moritz
last_name: Seiler
- first_name: Janina
full_name: Pohl, Janina
last_name: Pohl
- 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: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Seiler M, Pohl J, Bossek J, Kerschke P, Trautmann H. 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-Verlag;
2020:48–64. doi:10.1007/978-3-030-58112-1_4'
apa: Seiler, M., Pohl, J., Bossek, J., Kerschke, P., & Trautmann, H. (2020).
Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection
on the Traveling Salesperson Problem. Parallel Problem Solving from {Nature}
(PPSN XVI), 48–64. https://doi.org/10.1007/978-3-030-58112-1_4
bibtex: '@inproceedings{Seiler_Pohl_Bossek_Kerschke_Trautmann_2020, place={Berlin,
Heidelberg}, title={Deep Learning as a Competitive Feature-Free Approach for Automated
Algorithm Selection on the Traveling Salesperson Problem}, DOI={10.1007/978-3-030-58112-1_4},
booktitle={Parallel Problem Solving from {Nature} (PPSN XVI)}, publisher={Springer-Verlag},
author={Seiler, Moritz and Pohl, Janina and Bossek, Jakob and Kerschke, Pascal
and Trautmann, Heike}, year={2020}, pages={48–64} }'
chicago: 'Seiler, Moritz, Janina Pohl, Jakob Bossek, Pascal Kerschke, and Heike
Trautmann. “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), 48–64. Berlin, Heidelberg: Springer-Verlag,
2020. https://doi.org/10.1007/978-3-030-58112-1_4.'
ieee: 'M. Seiler, J. Pohl, J. Bossek, P. Kerschke, and H. Trautmann, “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), 2020, pp. 48–64, doi: 10.1007/978-3-030-58112-1_4.'
mla: Seiler, Moritz, et al. “Deep Learning as a Competitive Feature-Free Approach
for Automated Algorithm Selection on the Traveling Salesperson Problem.” Parallel
Problem Solving from {Nature} (PPSN XVI), Springer-Verlag, 2020, pp. 48–64,
doi:10.1007/978-3-030-58112-1_4.
short: 'M. Seiler, J. Pohl, J. Bossek, P. Kerschke, H. Trautmann, in: Parallel Problem
Solving from {Nature} (PPSN XVI), Springer-Verlag, Berlin, Heidelberg, 2020, pp.
48–64.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:45Z
department:
- _id: '819'
doi: 10.1007/978-3-030-58112-1_4
extern: '1'
keyword:
- Automated algorithm selection
- Deep learning
- Feature-based approaches
- Traveling Salesperson Problem
language:
- iso: eng
page: 48–64
place: Berlin, Heidelberg
publication: Parallel Problem Solving from {Nature} (PPSN XVI)
publication_identifier:
isbn:
- 978-3-030-58111-4
publisher: Springer-Verlag
status: public
title: Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm
Selection on the Traveling Salesperson Problem
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48848'
abstract:
- lang: eng
text: We build upon a recently proposed multi-objective view onto performance measurement
of single-objective stochastic solvers. The trade-off between the fraction of
failed runs and the mean runtime of successful runs \textendash both to be minimized
\textendash is directly analyzed based on a study on algorithm selection of inexact
state-of-the-art solvers for the famous Traveling Salesperson Problem (TSP). Moreover,
we adopt the hypervolume indicator (HV) commonly used in multi-objective optimization
for simultaneously assessing both conflicting objectives and investigate relations
to commonly used performance indicators, both theoretically and empirically. Next
to Penalized Average Runtime (PAR) and Penalized Quantile Runtime (PQR), the HV
measure is used as a core concept within the construction of per-instance algorithm
selection models offering interesting insights into complementary behavior of
inexact TSP solvers. \textbullet The multi-objective perspective is naturally
generalizable to multiple objectives. \textbullet Proof of relationship between
HV and the PAR in the considered bi-objective space. \textbullet New insights
into complementary behavior of stochastic optimization algorithms.
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: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: Bossek J, Kerschke P, Trautmann H. A Multi-Objective Perspective on Performance
Assessment and Automated Selection of Single-Objective Optimization Algorithms.
Applied Soft Computing. 2020;88(C). doi:10.1016/j.asoc.2019.105901
apa: Bossek, J., Kerschke, P., & Trautmann, H. (2020). A Multi-Objective Perspective
on Performance Assessment and Automated Selection of Single-Objective Optimization
Algorithms. Applied Soft Computing, 88(C). https://doi.org/10.1016/j.asoc.2019.105901
bibtex: '@article{Bossek_Kerschke_Trautmann_2020, title={A Multi-Objective Perspective
on Performance Assessment and Automated Selection of Single-Objective Optimization
Algorithms}, volume={88}, DOI={10.1016/j.asoc.2019.105901},
number={C}, journal={Applied Soft Computing}, author={Bossek, Jakob and Kerschke,
Pascal and Trautmann, Heike}, year={2020} }'
chicago: Bossek, Jakob, Pascal Kerschke, and Heike Trautmann. “A Multi-Objective
Perspective on Performance Assessment and Automated Selection of Single-Objective
Optimization Algorithms.” Applied Soft Computing 88, no. C (2020). https://doi.org/10.1016/j.asoc.2019.105901.
ieee: 'J. Bossek, P. Kerschke, and H. Trautmann, “A Multi-Objective Perspective
on Performance Assessment and Automated Selection of Single-Objective Optimization
Algorithms,” Applied Soft Computing, vol. 88, no. C, 2020, doi: 10.1016/j.asoc.2019.105901.'
mla: Bossek, Jakob, et al. “A Multi-Objective Perspective on Performance Assessment
and Automated Selection of Single-Objective Optimization Algorithms.” Applied
Soft Computing, vol. 88, no. C, 2020, doi:10.1016/j.asoc.2019.105901.
short: J. Bossek, P. Kerschke, H. Trautmann, Applied Soft Computing 88 (2020).
date_created: 2023-11-14T15:58:53Z
date_updated: 2023-12-13T10:52:17Z
department:
- _id: '819'
doi: 10.1016/j.asoc.2019.105901
intvolume: ' 88'
issue: C
keyword:
- Algorithm selection
- Combinatorial optimization
- Multi-objective optimization
- Performance measurement
- Traveling Salesperson Problem
language:
- iso: eng
publication: Applied Soft Computing
publication_identifier:
issn:
- 1568-4946
status: public
title: A Multi-Objective Perspective on Performance Assessment and Automated Selection
of Single-Objective Optimization Algorithms
type: journal_article
user_id: '102979'
volume: 88
year: '2020'
...
---
_id: '46334'
abstract:
- lang: eng
text: We build upon a recently proposed multi-objective view onto performance measurement
of single-objective stochastic solvers. The trade-off between the fraction of
failed runs and the mean runtime of successful runs – both to be minimized – is
directly analyzed based on a study on algorithm selection of inexact state-of-the-art
solvers for the famous Traveling Salesperson Problem (TSP). Moreover, we adopt
the hypervolume indicator (HV) commonly used in multi-objective optimization for
simultaneously assessing both conflicting objectives and investigate relations
to commonly used performance indicators, both theoretically and empirically. Next
to Penalized Average Runtime (PAR) and Penalized Quantile Runtime (PQR), the HV
measure is used as a core concept within the construction of per-instance algorithm
selection models offering interesting insights into complementary behavior of
inexact TSP solvers.
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: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
citation:
ama: Bossek J, Kerschke P, Trautmann H. A multi-objective perspective on performance
assessment and automated selection of single-objective optimization algorithms.
Applied Soft Computing. 2020;88:105901. doi:https://doi.org/10.1016/j.asoc.2019.105901
apa: Bossek, J., Kerschke, P., & Trautmann, H. (2020). A multi-objective perspective
on performance assessment and automated selection of single-objective optimization
algorithms. Applied Soft Computing, 88, 105901. https://doi.org/10.1016/j.asoc.2019.105901
bibtex: '@article{Bossek_Kerschke_Trautmann_2020, title={A multi-objective perspective
on performance assessment and automated selection of single-objective optimization
algorithms}, volume={88}, DOI={https://doi.org/10.1016/j.asoc.2019.105901},
journal={Applied Soft Computing}, author={Bossek, Jakob and Kerschke, Pascal and
Trautmann, Heike}, year={2020}, pages={105901} }'
chicago: 'Bossek, Jakob, Pascal Kerschke, and Heike Trautmann. “A Multi-Objective
Perspective on Performance Assessment and Automated Selection of Single-Objective
Optimization Algorithms.” Applied Soft Computing 88 (2020): 105901. https://doi.org/10.1016/j.asoc.2019.105901.'
ieee: 'J. Bossek, P. Kerschke, and H. Trautmann, “A multi-objective perspective
on performance assessment and automated selection of single-objective optimization
algorithms,” Applied Soft Computing, vol. 88, p. 105901, 2020, doi: https://doi.org/10.1016/j.asoc.2019.105901.'
mla: Bossek, Jakob, et al. “A Multi-Objective Perspective on Performance Assessment
and Automated Selection of Single-Objective Optimization Algorithms.” Applied
Soft Computing, vol. 88, 2020, p. 105901, doi:https://doi.org/10.1016/j.asoc.2019.105901.
short: J. Bossek, P. Kerschke, H. Trautmann, Applied Soft Computing 88 (2020) 105901.
date_created: 2023-08-04T07:42:26Z
date_updated: 2024-06-10T12:00:46Z
department:
- _id: '34'
- _id: '819'
doi: https://doi.org/10.1016/j.asoc.2019.105901
intvolume: ' 88'
keyword:
- Algorithm selection
- Multi-objective optimization
- Performance measurement
- Combinatorial optimization
- Traveling Salesperson Problem
language:
- iso: eng
page: '105901'
publication: Applied Soft Computing
publication_identifier:
issn:
- 1568-4946
status: public
title: A multi-objective perspective on performance assessment and automated selection
of single-objective optimization algorithms
type: journal_article
user_id: '15504'
volume: 88
year: '2020'
...
---
_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'
...
---
_id: '46388'
abstract:
- lang: eng
text: Understanding the behaviour of well-known algorithms for classical NP-hard
optimisation problems is still a difficult task. With this paper, we contribute
to this research direction and carry out a feature based comparison of local search
and the well-known Christofides approximation algorithm for the Traveling Salesperson
Problem. We use an evolutionary algorithm approach to construct easy and hard
instances for the Christofides algorithm, where we measure hardness in terms of
approximation ratio. Our results point out important features and lead to hard
and easy instances for this famous algorithm. Furthermore, our cross-comparison
gives new insights on the complementary benefits of the different approaches.
author:
- first_name: Samadhi
full_name: Nallaperuma, Samadhi
last_name: Nallaperuma
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
- first_name: Bernd
full_name: Bischl, Bernd
last_name: Bischl
- first_name: Olaf
full_name: Mersmann, Olaf
last_name: Mersmann
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
citation:
ama: 'Nallaperuma S, Wagner M, Neumann F, Bischl B, Mersmann O, Trautmann H. A Feature-Based
Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson
Problem. In: Proceedings of the Twelfth Workshop on Foundations of Genetic
Algorithms XII. FOGA XII ’13. Association for Computing Machinery; 2013:147–160.
doi:10.1145/2460239.2460253'
apa: Nallaperuma, S., Wagner, M., Neumann, F., Bischl, B., Mersmann, O., & Trautmann,
H. (2013). A Feature-Based Comparison of Local Search and the Christofides Algorithm
for the Travelling Salesperson Problem. Proceedings of the Twelfth Workshop
on Foundations of Genetic Algorithms XII, 147–160. https://doi.org/10.1145/2460239.2460253
bibtex: '@inproceedings{Nallaperuma_Wagner_Neumann_Bischl_Mersmann_Trautmann_2013,
place={New York, NY, USA}, series={FOGA XII ’13}, title={A Feature-Based Comparison
of Local Search and the Christofides Algorithm for the Travelling Salesperson
Problem}, DOI={10.1145/2460239.2460253},
booktitle={Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms
XII}, publisher={Association for Computing Machinery}, author={Nallaperuma, Samadhi
and Wagner, Markus and Neumann, Frank and Bischl, Bernd and Mersmann, Olaf and
Trautmann, Heike}, year={2013}, pages={147–160}, collection={FOGA XII ’13} }'
chicago: 'Nallaperuma, Samadhi, Markus Wagner, Frank Neumann, Bernd Bischl, Olaf
Mersmann, and Heike Trautmann. “A Feature-Based Comparison of Local Search and
the Christofides Algorithm for the Travelling Salesperson Problem.” In Proceedings
of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 147–160.
FOGA XII ’13. New York, NY, USA: Association for Computing Machinery, 2013. https://doi.org/10.1145/2460239.2460253.'
ieee: 'S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, and H. Trautmann,
“A Feature-Based Comparison of Local Search and the Christofides Algorithm for
the Travelling Salesperson Problem,” in Proceedings of the Twelfth Workshop
on Foundations of Genetic Algorithms XII, 2013, pp. 147–160, doi: 10.1145/2460239.2460253.'
mla: Nallaperuma, Samadhi, et al. “A Feature-Based Comparison of Local Search and
the Christofides Algorithm for the Travelling Salesperson Problem.” Proceedings
of the Twelfth Workshop on Foundations of Genetic Algorithms XII, Association
for Computing Machinery, 2013, pp. 147–160, doi:10.1145/2460239.2460253.
short: 'S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, H. Trautmann,
in: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII,
Association for Computing Machinery, New York, NY, USA, 2013, pp. 147–160.'
date_created: 2023-08-04T15:42:03Z
date_updated: 2023-10-16T13:45:53Z
department:
- _id: '34'
- _id: '819'
doi: 10.1145/2460239.2460253
keyword:
- approximation algorithms
- local search
- traveling salesperson problem
- feature selection
- prediction
- classification
language:
- iso: eng
page: 147–160
place: New York, NY, USA
publication: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms
XII
publication_identifier:
isbn:
- '9781450319904'
publisher: Association for Computing Machinery
series_title: FOGA XII ’13
status: public
title: A Feature-Based Comparison of Local Search and the Christofides Algorithm for
the Travelling Salesperson Problem
type: conference
user_id: '15504'
year: '2013'
...