---
_id: '54548'
author:
- first_name: Raphael Patrick
full_name: Prager, Raphael Patrick
last_name: Prager
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
citation:
ama: Prager RP, Trautmann H. Exploratory Landscape Analysis for Mixed-Variable Problems.
IEEE Transactions on Evolutionary Computation. Published online 2024:1-1.
doi:10.1109/TEVC.2024.3399560
apa: Prager, R. P., & Trautmann, H. (2024). Exploratory Landscape Analysis for
Mixed-Variable Problems. IEEE Transactions on Evolutionary Computation,
1–1. https://doi.org/10.1109/TEVC.2024.3399560
bibtex: '@article{Prager_Trautmann_2024, title={Exploratory Landscape Analysis for
Mixed-Variable Problems}, DOI={10.1109/TEVC.2024.3399560},
journal={IEEE Transactions on Evolutionary Computation}, author={Prager, Raphael
Patrick and Trautmann, Heike}, year={2024}, pages={1–1} }'
chicago: Prager, Raphael Patrick, and Heike Trautmann. “Exploratory Landscape Analysis
for Mixed-Variable Problems.” IEEE Transactions on Evolutionary Computation,
2024, 1–1. https://doi.org/10.1109/TEVC.2024.3399560.
ieee: 'R. P. Prager and H. Trautmann, “Exploratory Landscape Analysis for Mixed-Variable
Problems,” IEEE Transactions on Evolutionary Computation, pp. 1–1, 2024,
doi: 10.1109/TEVC.2024.3399560.'
mla: Prager, Raphael Patrick, and Heike Trautmann. “Exploratory Landscape Analysis
for Mixed-Variable Problems.” IEEE Transactions on Evolutionary Computation,
2024, pp. 1–1, doi:10.1109/TEVC.2024.3399560.
short: R.P. Prager, H. Trautmann, IEEE Transactions on Evolutionary Computation
(2024) 1–1.
date_created: 2024-06-03T06:16:33Z
date_updated: 2024-06-03T06:17:13Z
department:
- _id: '819'
doi: 10.1109/TEVC.2024.3399560
keyword:
- Optimization
- Evolutionary computation
- Benchmark testing
- Hyperparameter optimization
- Portfolios
- Extraterrestrial measurements
- Dispersion
- Exploratory landscape analysis
- mixed-variable problem
- mixed search spaces
- automated algorithm selection
language:
- iso: eng
page: 1-1
publication: IEEE Transactions on Evolutionary Computation
status: public
title: Exploratory Landscape Analysis for Mixed-Variable Problems
type: journal_article
user_id: '15504'
year: '2024'
...
---
_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: '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: '48875'
abstract:
- lang: eng
text: A multiobjective perspective onto common performance measures such as the
PAR10 score or the expected runtime of single-objective stochastic solvers is
presented by directly investigating the tradeoff between the fraction of failed
runs and the average runtime. Multi-objective indicators operating in the bi-objective
space allow for an overall performance comparison on a set of instances paving
the way for instance-based automated algorithm selection techniques.
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. Multi-Objective Performance Measurement: Alternatives
to PAR10 and Expected Running Time. In: Battiti R, Brunato M, Kotsireas I, Pardalos
PM, eds. Learning and Intelligent Optimization. Lecture Notes in Computer
Science. Springer International Publishing; 2019:215–219. doi:10.1007/978-3-030-05348-2_19'
apa: 'Bossek, J., & Trautmann, H. (2019). Multi-Objective Performance Measurement:
Alternatives to PAR10 and Expected Running Time. In R. Battiti, M. Brunato, I.
Kotsireas, & P. M. Pardalos (Eds.), Learning and Intelligent Optimization
(pp. 215–219). Springer International Publishing. https://doi.org/10.1007/978-3-030-05348-2_19'
bibtex: '@inproceedings{Bossek_Trautmann_2019, place={Cham}, series={Lecture Notes
in Computer Science}, title={Multi-Objective Performance Measurement: Alternatives
to PAR10 and Expected Running Time}, DOI={10.1007/978-3-030-05348-2_19},
booktitle={Learning and Intelligent Optimization}, publisher={Springer International
Publishing}, author={Bossek, Jakob and Trautmann, Heike}, editor={Battiti, Roberto
and Brunato, Mauro and Kotsireas, Ilias and Pardalos, Panos M.}, year={2019},
pages={215–219}, collection={Lecture Notes in Computer Science} }'
chicago: 'Bossek, Jakob, and Heike Trautmann. “Multi-Objective Performance Measurement:
Alternatives to PAR10 and Expected Running Time.” In Learning and Intelligent
Optimization, edited by Roberto Battiti, Mauro Brunato, Ilias Kotsireas, and
Panos M. Pardalos, 215–219. Lecture Notes in Computer Science. Cham: Springer
International Publishing, 2019. https://doi.org/10.1007/978-3-030-05348-2_19.'
ieee: 'J. Bossek and H. Trautmann, “Multi-Objective Performance Measurement: Alternatives
to PAR10 and Expected Running Time,” in Learning and Intelligent Optimization,
2019, pp. 215–219, doi: 10.1007/978-3-030-05348-2_19.'
mla: 'Bossek, Jakob, and Heike Trautmann. “Multi-Objective Performance Measurement:
Alternatives to PAR10 and Expected Running Time.” Learning and Intelligent
Optimization, edited by Roberto Battiti et al., Springer International Publishing,
2019, pp. 215–219, doi:10.1007/978-3-030-05348-2_19.'
short: 'J. Bossek, H. Trautmann, in: R. Battiti, M. Brunato, I. Kotsireas, P.M.
Pardalos (Eds.), Learning and Intelligent Optimization, Springer International
Publishing, Cham, 2019, pp. 215–219.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:32Z
department:
- _id: '819'
doi: 10.1007/978-3-030-05348-2_19
editor:
- first_name: Roberto
full_name: Battiti, Roberto
last_name: Battiti
- first_name: Mauro
full_name: Brunato, Mauro
last_name: Brunato
- first_name: Ilias
full_name: Kotsireas, Ilias
last_name: Kotsireas
- first_name: Panos M.
full_name: Pardalos, Panos M.
last_name: Pardalos
extern: '1'
keyword:
- Algorithm selection
- Performance measurement
language:
- iso: eng
page: 215–219
place: Cham
publication: Learning and Intelligent Optimization
publication_identifier:
isbn:
- 978-3-030-05348-2
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: 'Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected
Running Time'
type: conference
user_id: '102979'
year: '2019'
...
---
_id: '48885'
abstract:
- lang: eng
text: Performance comparisons of optimization algorithms are heavily influenced
by the underlying indicator(s). In this paper we investigate commonly used performance
indicators for single-objective stochastic solvers, such as the Penalized Average
Runtime (e.g., PAR10) or the Expected Running Time (ERT), based on exemplary benchmark
performances of state-of-the-art inexact TSP solvers. Thereby, we introduce a
methodology for analyzing the effects of (usually heuristically set) indicator
parametrizations - such as the penalty factor and the method used for aggregating
across multiple runs - w.r.t. the robustness of the considered optimization algorithms.
author:
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- 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: 'Kerschke P, Bossek J, Trautmann H. Parameterization of State-of-the-Art Performance
Indicators: A Robustness Study Based on Inexact TSP Solvers. In: Proceedings
of the Genetic and Evolutionary Computation Conference Companion. GECCO’18.
Association for Computing Machinery; 2018:1737–1744. doi:10.1145/3205651.3208233'
apa: 'Kerschke, P., Bossek, J., & Trautmann, H. (2018). Parameterization of
State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP
Solvers. Proceedings of the Genetic and Evolutionary Computation Conference
Companion, 1737–1744. https://doi.org/10.1145/3205651.3208233'
bibtex: '@inproceedings{Kerschke_Bossek_Trautmann_2018, place={New York, NY, USA},
series={GECCO’18}, title={Parameterization of State-of-the-Art Performance Indicators:
A Robustness Study Based on Inexact TSP Solvers}, DOI={10.1145/3205651.3208233},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference
Companion}, publisher={Association for Computing Machinery}, author={Kerschke,
Pascal and Bossek, Jakob and Trautmann, Heike}, year={2018}, pages={1737–1744},
collection={GECCO’18} }'
chicago: 'Kerschke, Pascal, Jakob Bossek, and Heike Trautmann. “Parameterization
of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact
TSP Solvers.” In Proceedings of the Genetic and Evolutionary Computation Conference
Companion, 1737–1744. GECCO’18. New York, NY, USA: Association for Computing
Machinery, 2018. https://doi.org/10.1145/3205651.3208233.'
ieee: 'P. Kerschke, J. Bossek, and H. Trautmann, “Parameterization of State-of-the-Art
Performance Indicators: A Robustness Study Based on Inexact TSP Solvers,” in Proceedings
of the Genetic and Evolutionary Computation Conference Companion, 2018, pp.
1737–1744, doi: 10.1145/3205651.3208233.'
mla: 'Kerschke, Pascal, et al. “Parameterization of State-of-the-Art Performance
Indicators: A Robustness Study Based on Inexact TSP Solvers.” Proceedings of
the Genetic and Evolutionary Computation Conference Companion, Association
for Computing Machinery, 2018, pp. 1737–1744, doi:10.1145/3205651.3208233.'
short: 'P. Kerschke, J. Bossek, H. Trautmann, in: Proceedings of the Genetic and
Evolutionary Computation Conference Companion, Association for Computing Machinery,
New York, NY, USA, 2018, pp. 1737–1744.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:48:38Z
department:
- _id: '819'
doi: 10.1145/3205651.3208233
extern: '1'
keyword:
- algorithm selection
- optimization
- performance measures
- transportation
- travelling salesperson problem
language:
- iso: eng
page: 1737–1744
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference Companion
publication_identifier:
isbn:
- 978-1-4503-5764-7
publisher: Association for Computing Machinery
series_title: GECCO’18
status: public
title: 'Parameterization of State-of-the-Art Performance Indicators: A Robustness
Study Based on Inexact TSP Solvers'
type: conference
user_id: '102979'
year: '2018'
...
---
_id: '48884'
abstract:
- lang: eng
text: The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard
problems. Over the years, many different solution approaches and solvers have
been developed. For the first time, we directly compare five state-of-the-art
inexact solvers\textemdash namely, LKH, EAX, restart variants of those, and MAOS\textemdash
on a large set of well-known benchmark instances and demonstrate complementary
performance, in that different instances may be solved most effectively by different
algorithms. We leverage this complementarity to build an algorithm selector, which
selects the best TSP solver on a per-instance basis and thus achieves significantly
improved performance compared to the single best solver, representing an advance
in the state of the art in solving the Euclidean TSP. Our in-depth analysis of
the selectors provides insight into what drives this performance improvement.
author:
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Lars
full_name: Kotthoff, Lars
last_name: Kotthoff
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Holger H.
full_name: Hoos, Holger H.
last_name: Hoos
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: Kerschke P, Kotthoff L, Bossek J, Hoos HH, Trautmann H. Leveraging TSP Solver
Complementarity through Machine Learning. Evolutionary Computation. 2018;26(4):597–620.
doi:10.1162/evco_a_00215
apa: Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H. H., & Trautmann, H. (2018).
Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary
Computation, 26(4), 597–620. https://doi.org/10.1162/evco_a_00215
bibtex: '@article{Kerschke_Kotthoff_Bossek_Hoos_Trautmann_2018, title={Leveraging
TSP Solver Complementarity through Machine Learning}, volume={26}, DOI={10.1162/evco_a_00215},
number={4}, journal={Evolutionary Computation}, author={Kerschke, Pascal and Kotthoff,
Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike}, year={2018},
pages={597–620} }'
chicago: 'Kerschke, Pascal, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike
Trautmann. “Leveraging TSP Solver Complementarity through Machine Learning.” Evolutionary
Computation 26, no. 4 (2018): 597–620. https://doi.org/10.1162/evco_a_00215.'
ieee: 'P. Kerschke, L. Kotthoff, J. Bossek, H. H. Hoos, and H. Trautmann, “Leveraging
TSP Solver Complementarity through Machine Learning,” Evolutionary Computation,
vol. 26, no. 4, pp. 597–620, 2018, doi: 10.1162/evco_a_00215.'
mla: Kerschke, Pascal, et al. “Leveraging TSP Solver Complementarity through Machine
Learning.” Evolutionary Computation, vol. 26, no. 4, 2018, pp. 597–620,
doi:10.1162/evco_a_00215.
short: P. Kerschke, L. Kotthoff, J. Bossek, H.H. Hoos, H. Trautmann, Evolutionary
Computation 26 (2018) 597–620.
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:51:26Z
department:
- _id: '819'
doi: 10.1162/evco_a_00215
intvolume: ' 26'
issue: '4'
keyword:
- automated algorithm selection
- machine learning.
- performance modeling
- Travelling Salesperson Problem
language:
- iso: eng
page: 597–620
publication: Evolutionary Computation
publication_identifier:
issn:
- 1063-6560
status: public
title: Leveraging TSP Solver Complementarity through Machine Learning
type: journal_article
user_id: '102979'
volume: 26
year: '2018'
...
---
_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: '46396'
abstract:
- lang: eng
text: The steady supply of new optimization methods makes the algorithm selection
problem (ASP) an increasingly pressing and challenging task, specially for real-world
black-box optimization problems. The introduced approach considers the ASP as
a cost-sensitive classification task which is based on Exploratory Landscape Analysis.
Low-level features gathered by systematic sampling of the function on the feasible
set are used to predict a well-performing algorithm out of a given portfolio.
Example-specific label costs are defined by the expected runtime of each candidate
algorithm. We use one-sided support vector regression to solve this learning problem.
The approach is illustrated by means of the optimization problems and algorithms
of the BBOB’09/10 workshop.
author:
- 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
- first_name: Mike
full_name: Preuß, Mike
last_name: Preuß
citation:
ama: 'Bischl B, Mersmann O, Trautmann H, Preuß M. Algorithm Selection Based on Exploratory
Landscape Analysis and Cost-Sensitive Learning. In: Proceedings of the 14th
Annual Conference on Genetic and Evolutionary Computation. GECCO ’12. Association
for Computing Machinery; 2012:313–320. doi:10.1145/2330163.2330209'
apa: Bischl, B., Mersmann, O., Trautmann, H., & Preuß, M. (2012). Algorithm
Selection Based on Exploratory Landscape Analysis and Cost-Sensitive Learning.
Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation,
313–320. https://doi.org/10.1145/2330163.2330209
bibtex: '@inproceedings{Bischl_Mersmann_Trautmann_Preuß_2012, place={New York, NY,
USA}, series={GECCO ’12}, title={Algorithm Selection Based on Exploratory Landscape
Analysis and Cost-Sensitive Learning}, DOI={10.1145/2330163.2330209},
booktitle={Proceedings of the 14th Annual Conference on Genetic and Evolutionary
Computation}, publisher={Association for Computing Machinery}, author={Bischl,
Bernd and Mersmann, Olaf and Trautmann, Heike and Preuß, Mike}, year={2012}, pages={313–320},
collection={GECCO ’12} }'
chicago: 'Bischl, Bernd, Olaf Mersmann, Heike Trautmann, and Mike Preuß. “Algorithm
Selection Based on Exploratory Landscape Analysis and Cost-Sensitive Learning.”
In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation,
313–320. GECCO ’12. New York, NY, USA: Association for Computing Machinery, 2012.
https://doi.org/10.1145/2330163.2330209.'
ieee: 'B. Bischl, O. Mersmann, H. Trautmann, and M. Preuß, “Algorithm Selection
Based on Exploratory Landscape Analysis and Cost-Sensitive Learning,” in Proceedings
of the 14th Annual Conference on Genetic and Evolutionary Computation, 2012,
pp. 313–320, doi: 10.1145/2330163.2330209.'
mla: Bischl, Bernd, et al. “Algorithm Selection Based on Exploratory Landscape Analysis
and Cost-Sensitive Learning.” Proceedings of the 14th Annual Conference on
Genetic and Evolutionary Computation, Association for Computing Machinery,
2012, pp. 313–320, doi:10.1145/2330163.2330209.
short: 'B. Bischl, O. Mersmann, H. Trautmann, M. Preuß, in: Proceedings of the 14th
Annual Conference on Genetic and Evolutionary Computation, Association for Computing
Machinery, New York, NY, USA, 2012, pp. 313–320.'
date_created: 2023-08-04T15:51:56Z
date_updated: 2023-10-16T13:48:48Z
department:
- _id: '34'
- _id: '819'
doi: 10.1145/2330163.2330209
keyword:
- machine learning
- exploratory landscape analysis
- fitness landscape
- benchmarking
- evolutionary optimization
- bbob test set
- algorithm selection
language:
- iso: eng
page: 313–320
place: New York, NY, USA
publication: Proceedings of the 14th Annual Conference on Genetic and Evolutionary
Computation
publication_identifier:
isbn:
- '9781450311779'
publisher: Association for Computing Machinery
series_title: GECCO ’12
status: public
title: Algorithm Selection Based on Exploratory Landscape Analysis and Cost-Sensitive
Learning
type: conference
user_id: '15504'
year: '2012'
...