---
_id: '48861'
abstract:
- lang: eng
text: Generating instances of different properties is key to algorithm selection
methods that differentiate between the performance of different solvers for a
given combinatorial optimization problem. A wide range of methods using evolutionary
computation techniques has been introduced in recent years. With this paper, we
contribute to this area of research by providing a new approach based on quality
diversity (QD) that is able to explore the whole feature space. QD algorithms
allow to create solutions of high quality within a given feature space by splitting
it up into boxes and improving solution quality within each box. We use our QD
approach for the generation of TSP instances to visualize and analyze the variety
of instances differentiating various TSP solvers and compare it to instances generated
by established approaches from the literature.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann F. Exploring the Feature Space of TSP Instances Using Quality
Diversity. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’22. Association for Computing Machinery; 2022:186–194. doi:10.1145/3512290.3528851'
apa: Bossek, J., & Neumann, F. (2022). Exploring the Feature Space of TSP Instances
Using Quality Diversity. Proceedings of the Genetic and Evolutionary Computation
Conference, 186–194. https://doi.org/10.1145/3512290.3528851
bibtex: '@inproceedings{Bossek_Neumann_2022, place={New York, NY, USA}, series={GECCO
’22}, title={Exploring the Feature Space of TSP Instances Using Quality Diversity},
DOI={10.1145/3512290.3528851},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank}, year={2022}, pages={186–194}, collection={GECCO ’22} }'
chicago: 'Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP
Instances Using Quality Diversity.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 186–194. GECCO ’22. New York, NY, USA: Association
for Computing Machinery, 2022. https://doi.org/10.1145/3512290.3528851.'
ieee: 'J. Bossek and F. Neumann, “Exploring the Feature Space of TSP Instances Using
Quality Diversity,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2022, pp. 186–194, doi: 10.1145/3512290.3528851.'
mla: Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP Instances
Using Quality Diversity.” Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, 2022, pp. 186–194, doi:10.1145/3512290.3528851.
short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2022, pp.
186–194.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:56Z
department:
- _id: '819'
doi: 10.1145/3512290.3528851
extern: '1'
keyword:
- instance features
- instance generation
- quality diversity
- TSP
language:
- iso: eng
page: 186–194
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-9237-2
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’22
status: public
title: Exploring the Feature Space of TSP Instances Using Quality Diversity
type: conference
user_id: '102979'
year: '2022'
...
---
_id: '48881'
abstract:
- lang: eng
text: 'Classic automated algorithm selection (AS) for (combinatorial) optimization
problems heavily relies on so-called instance features, i.e., numerical characteristics
of the problem at hand ideally extracted with computationally low-demanding routines.
For the traveling salesperson problem (TSP) a plethora of features have been suggested.
Most of these features are, if at all, only normalized imprecisely raising the
issue of feature values being strongly affected by the instance size. Such artifacts
may have detrimental effects on algorithm selection models. We propose a normalization
for two feature groups which stood out in multiple AS studies on the TSP: (a)
features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph
(NNG) transformation of the input instance. To this end we theoretically derive
minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs.
We analyze the differences in feature space between normalized versions of these
features and their unnormalized counterparts. Our empirical investigations on
various TSP benchmark sets point out that the feature scaling succeeds in eliminating
the effect of the instance size. Eventually, a proof-of-concept AS-study shows
promising results: models trained with normalized features tend to outperform
those trained with the respective vanilla features.'
author:
- first_name: Jonathan
full_name: Heins, Jonathan
last_name: Heins
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Janina
full_name: Pohl, Janina
last_name: Pohl
- first_name: Moritz
full_name: Seiler, Moritz
last_name: Seiler
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
citation:
ama: 'Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. On the Potential
of Normalized TSP Features for Automated Algorithm Selection. In: Proceedings
of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association
for Computing Machinery; 2021:1–15.'
apa: Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., & Kerschke,
P. (2021). On the Potential of Normalized TSP Features for Automated Algorithm
Selection. In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms (pp. 1–15). Association for Computing Machinery.
bibtex: '@inbook{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2021, place={New York,
NY, USA}, title={On the Potential of Normalized TSP Features for Automated Algorithm
Selection}, booktitle={Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Heins,
Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann,
Heike and Kerschke, Pascal}, year={2021}, pages={1–15} }'
chicago: 'Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann,
and Pascal Kerschke. “On the Potential of Normalized TSP Features for Automated
Algorithm Selection.” In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, 1–15. New York, NY, USA: Association for Computing
Machinery, 2021.'
ieee: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “On
the Potential of Normalized TSP Features for Automated Algorithm Selection,” in
Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,
New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–15.'
mla: Heins, Jonathan, et al. “On the Potential of Normalized TSP Features for Automated
Algorithm Selection.” Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, Association for Computing Machinery, 2021, pp. 1–15.
short: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, in:
Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,
Association for Computing Machinery, New York, NY, USA, 2021, pp. 1–15.'
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:47:23Z
department:
- _id: '819'
extern: '1'
keyword:
- automated algorithm selection
- graph theory
- instance features
- normalization
- traveling salesperson problem (TSP)
language:
- iso: eng
page: 1–15
place: New York, NY, USA
publication: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-1-4503-8352-3
publisher: Association for Computing Machinery
status: public
title: On the Potential of Normalized TSP Features for Automated Algorithm Selection
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '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: '48852'
abstract:
- lang: eng
text: The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial
optimisation problems. However, many real-world problems are composed of several
interacting components. The Traveling Thief Problem (TTP) addresses such interactions
by combining two combinatorial optimisation problems, namely the TSP and the Knapsack
Problem (KP). Recently, a new problem called the node weight dependent Traveling
Salesperson Problem (W-TSP) has been introduced where nodes have weights that
influence the cost of the tour. In this paper, we compare W-TSP and TTP. We investigate
the structure of the optimised tours for W-TSP and TTP and the impact of using
each others fitness function. Our experimental results suggest (1) that the W-TSP
often can be solved better using the TTP fitness function and (2) final W-TSP
and TTP solutions show different distributions when compared with optimal TSP
or weighted greedy solutions.
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. Optimising Tours for the Weighted Traveling
Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of
Solutions. In: Parallel Problem Solving from Nature (PPSN XVI). Springer-Verlag;
2020:346–359. doi:10.1007/978-3-030-58112-1_24'
apa: 'Bossek, J., Neumann, A., & Neumann, F. (2020). Optimising Tours for the
Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural
Comparison of Solutions. Parallel Problem Solving from Nature (PPSN XVI),
346–359. https://doi.org/10.1007/978-3-030-58112-1_24'
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2020, place={Berlin, Heidelberg},
title={Optimising Tours for the Weighted Traveling Salesperson Problem and the
Traveling Thief Problem: A Structural Comparison of Solutions}, DOI={10.1007/978-3-030-58112-1_24},
booktitle={Parallel Problem Solving from Nature (PPSN XVI)}, publisher={Springer-Verlag},
author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={346–359}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Optimising Tours for
the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A
Structural Comparison of Solutions.” In Parallel Problem Solving from Nature
(PPSN XVI), 346–359. Berlin, Heidelberg: Springer-Verlag, 2020. https://doi.org/10.1007/978-3-030-58112-1_24.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Optimising Tours for the Weighted
Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison
of Solutions,” in Parallel Problem Solving from Nature (PPSN XVI), 2020,
pp. 346–359, doi: 10.1007/978-3-030-58112-1_24.'
mla: 'Bossek, Jakob, et al. “Optimising Tours for the Weighted Traveling Salesperson
Problem and the Traveling Thief Problem: A Structural Comparison of Solutions.”
Parallel Problem Solving from Nature (PPSN XVI), Springer-Verlag, 2020,
pp. 346–359, doi:10.1007/978-3-030-58112-1_24.'
short: 'J. Bossek, A. Neumann, F. Neumann, in: Parallel Problem Solving from Nature
(PPSN XVI), Springer-Verlag, Berlin, Heidelberg, 2020, pp. 346–359.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:44:54Z
department:
- _id: '819'
doi: 10.1007/978-3-030-58112-1_24
extern: '1'
keyword:
- Evolutionary algorithms
- Node weight dependent TSP
- Traveling Thief Problem
language:
- iso: eng
page: 346–359
place: Berlin, Heidelberg
publication: Parallel Problem Solving from Nature (PPSN XVI)
publication_identifier:
isbn:
- 978-3-030-58111-4
publication_status: published
publisher: Springer-Verlag
status: public
title: 'Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling
Thief Problem: A Structural Comparison of Solutions'
type: conference
user_id: '102979'
year: '2020'
...
---
_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'
...
---
_id: '48889'
abstract:
- lang: eng
text: Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization
problems. With this paper we contribute to the understanding of the success of
2-opt based local search algorithms for solving the traveling salesperson problem
(TSP). Although 2-opt is widely used in practice, it is hard to understand its
success from a theoretical perspective. We take a statistical approach and examine
the features of TSP instances that make the problem either hard or easy to solve.
As a measure of problem difficulty for 2-opt we use the approximation ratio that
it achieves on a given instance. Our investigations point out important features
that make TSP instances hard or easy to be approximated by 2-opt.
author:
- first_name: Olaf
full_name: Mersmann, Olaf
last_name: Mersmann
- first_name: Bernd
full_name: Bischl, Bernd
last_name: Bischl
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: Mersmann O, Bischl B, Trautmann H, Wagner M, Bossek J, Neumann F. A Novel Feature-Based
Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.
Annals of Mathematics and Artificial Intelligence. 2013;69(2):151–182.
doi:10.1007/s10472-013-9341-2
apa: Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., & Neumann,
F. (2013). A Novel Feature-Based Approach to Characterize Algorithm Performance
for the Traveling Salesperson Problem. Annals of Mathematics and Artificial
Intelligence, 69(2), 151–182. https://doi.org/10.1007/s10472-013-9341-2
bibtex: '@article{Mersmann_Bischl_Trautmann_Wagner_Bossek_Neumann_2013, title={A
Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling
Salesperson Problem}, volume={69}, DOI={10.1007/s10472-013-9341-2},
number={2}, journal={Annals of Mathematics and Artificial Intelligence}, author={Mersmann,
Olaf and Bischl, Bernd and Trautmann, Heike and Wagner, Markus and Bossek, Jakob
and Neumann, Frank}, year={2013}, pages={151–182} }'
chicago: 'Mersmann, Olaf, Bernd Bischl, Heike Trautmann, Markus Wagner, Jakob Bossek,
and Frank Neumann. “A Novel Feature-Based Approach to Characterize Algorithm Performance
for the Traveling Salesperson Problem.” Annals of Mathematics and Artificial
Intelligence 69, no. 2 (2013): 151–182. https://doi.org/10.1007/s10472-013-9341-2.'
ieee: 'O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, and F. Neumann,
“A Novel Feature-Based Approach to Characterize Algorithm Performance for the
Traveling Salesperson Problem,” Annals of Mathematics and Artificial Intelligence,
vol. 69, no. 2, pp. 151–182, 2013, doi: 10.1007/s10472-013-9341-2.'
mla: Mersmann, Olaf, et al. “A Novel Feature-Based Approach to Characterize Algorithm
Performance for the Traveling Salesperson Problem.” Annals of Mathematics and
Artificial Intelligence, vol. 69, no. 2, 2013, pp. 151–182, doi:10.1007/s10472-013-9341-2.
short: O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann, Annals
of Mathematics and Artificial Intelligence 69 (2013) 151–182.
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:50:41Z
department:
- _id: '819'
doi: 10.1007/s10472-013-9341-2
intvolume: ' 69'
issue: '2'
keyword:
- 2-opt
- 90B06
- Classification
- Feature selection
- MARS
- TSP
language:
- iso: eng
page: 151–182
publication: Annals of Mathematics and Artificial Intelligence
publication_identifier:
issn:
- 1012-2443
status: public
title: A Novel Feature-Based Approach to Characterize Algorithm Performance for the
Traveling Salesperson Problem
type: journal_article
user_id: '102979'
volume: 69
year: '2013'
...
---
_id: '48890'
abstract:
- lang: eng
text: With this paper we contribute to the understanding of the success of 2-opt
based local search algorithms for solving the traveling salesman problem TSP.
Although 2-opt is widely used in practice, it is hard to understand its success
from a theoretical perspective. We take a statistical approach and examine the
features of TSP instances that make the problem either hard or easy to solve.
As a measure of problem difficulty for 2-opt we use the approximation ratio that
it achieves on a given instance. Our investigations point out important features
that make TSP instances hard or easy to be approximated by 2-opt.
author:
- first_name: Olaf
full_name: Mersmann, Olaf
last_name: Mersmann
- first_name: Bernd
full_name: Bischl, Bernd
last_name: Bischl
- 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
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Mersmann O, Bischl B, Bossek J, Trautmann H, Wagner M, Neumann F. Local Search
and the Traveling Salesman Problem: A Feature-Based Characterization of Problem
Hardness. In: Revised Selected Papers of the 6th International Conference on
Learning and Intelligent Optimization - Volume 7219. LION 6. Springer-Verlag;
2012:115–129.'
apa: 'Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., & Neumann,
F. (2012). Local Search and the Traveling Salesman Problem: A Feature-Based Characterization
of Problem Hardness. Revised Selected Papers of the 6th International Conference
on Learning and Intelligent Optimization - Volume 7219, 115–129.'
bibtex: '@inproceedings{Mersmann_Bischl_Bossek_Trautmann_Wagner_Neumann_2012, place={Berlin,
Heidelberg}, series={LION 6}, title={Local Search and the Traveling Salesman Problem:
A Feature-Based Characterization of Problem Hardness}, booktitle={Revised Selected
Papers of the 6th International Conference on Learning and Intelligent Optimization
- Volume 7219}, publisher={Springer-Verlag}, author={Mersmann, Olaf and Bischl,
Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank},
year={2012}, pages={115–129}, collection={LION 6} }'
chicago: 'Mersmann, Olaf, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner,
and Frank Neumann. “Local Search and the Traveling Salesman Problem: A Feature-Based
Characterization of Problem Hardness.” In Revised Selected Papers of the 6th
International Conference on Learning and Intelligent Optimization - Volume 7219,
115–129. LION 6. Berlin, Heidelberg: Springer-Verlag, 2012.'
ieee: 'O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, and F. Neumann,
“Local Search and the Traveling Salesman Problem: A Feature-Based Characterization
of Problem Hardness,” in Revised Selected Papers of the 6th International Conference
on Learning and Intelligent Optimization - Volume 7219, 2012, pp. 115–129.'
mla: 'Mersmann, Olaf, et al. “Local Search and the Traveling Salesman Problem: A
Feature-Based Characterization of Problem Hardness.” Revised Selected Papers
of the 6th International Conference on Learning and Intelligent Optimization -
Volume 7219, Springer-Verlag, 2012, pp. 115–129.'
short: 'O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, F. Neumann,
in: Revised Selected Papers of the 6th International Conference on Learning and
Intelligent Optimization - Volume 7219, Springer-Verlag, Berlin, Heidelberg, 2012,
pp. 115–129.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:48:58Z
department:
- _id: '819'
extern: '1'
keyword:
- 2-opt
- Classification
- Feature Selection
- MARS
- TSP
language:
- iso: eng
page: 115–129
place: Berlin, Heidelberg
publication: Revised Selected Papers of the 6th International Conference on Learning
and Intelligent Optimization - Volume 7219
publication_identifier:
isbn:
- 978-3-642-34412-1
publisher: Springer-Verlag
series_title: LION 6
status: public
title: 'Local Search and the Traveling Salesman Problem: A Feature-Based Characterization
of Problem Hardness'
type: conference
user_id: '102979'
year: '2012'
...