---
_id: '48862'
abstract:
- lang: eng
  text: 'Most runtime analyses of randomised search heuristics focus on the expected
    number of function evaluations to find a unique global optimum. We ask a fundamental
    question: if additional search points are declared optimal, or declared as desirable
    target points, do these additional optima speed up evolutionary algorithms? More
    formally, we analyse the expected hitting time of a target set OPT {$\cup$} S
    where S is a set of non-optimal search points and OPT is the set of optima and
    compare it to the expected hitting time of OPT. We show that the answer to our
    question depends on the number and placement of search points in S. For all black-box
    algorithms and all fitness functions we show that, if additional optima are placed
    randomly, even an exponential number of optima has a negligible effect on the
    expected optimisation time. Considering Hamming balls around all global optima
    gives an easier target for some algorithms and functions and can shift the phase
    transition with respect to offspring population sizes in the (1,{$\lambda$}) EA
    on One-Max. Finally, on functions where search trajectories typically join in
    a single search point, turning one search point into an optimum drastically reduces
    the expected optimisation time.'
author:
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Dirk
  full_name: Sudholt, Dirk
  last_name: Sudholt
citation:
  ama: 'Bossek J, Sudholt D. Do Additional Optima Speed up Evolutionary Algorithms?
    In: <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
    Algorithms</i>. Association for Computing Machinery; 2021:1–11.'
  apa: Bossek, J., &#38; Sudholt, D. (2021). Do Additional Optima Speed up Evolutionary
    Algorithms? In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i> (pp. 1–11). Association for Computing Machinery.
  bibtex: '@inbook{Bossek_Sudholt_2021, place={New York, NY, USA}, title={Do Additional
    Optima Speed up Evolutionary Algorithms?}, booktitle={Proceedings of the 16th
    ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association
    for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2021},
    pages={1–11} }'
  chicago: 'Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary
    Algorithms?” In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i>, 1–11. New York, NY, USA: Association for Computing
    Machinery, 2021.'
  ieee: 'J. Bossek and D. Sudholt, “Do Additional Optima Speed up Evolutionary Algorithms?,”
    in <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
    Algorithms</i>, New York, NY, USA: Association for Computing Machinery, 2021,
    pp. 1–11.'
  mla: Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary
    Algorithms?” <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of
    Genetic Algorithms</i>, Association for Computing Machinery, 2021, pp. 1–11.
  short: 'J. Bossek, D. Sudholt, 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:58:55Z
date_updated: 2023-12-13T10:45:31Z
department:
- _id: '819'
extern: '1'
keyword:
- evolutionary algorithms
- pseudo-boolean functions
- runtime analysis
- theory
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
publication_status: published
publisher: Association for Computing Machinery
status: public
title: Do Additional Optima Speed up Evolutionary Algorithms?
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_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: <i>Proceedings
    of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>. Association
    for Computing Machinery; 2021:1–15.'
  apa: Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., &#38; Kerschke,
    P. (2021). On the Potential of Normalized TSP Features for Automated Algorithm
    Selection. In <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i> (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 <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i>, 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
    <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>,
    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.” <i>Proceedings of the 16th ACM/SIGEVO Conference on Foundations
    of Genetic Algorithms</i>, 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: <i>Proceedings
    of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms</i>. Association
    for Computing Machinery; 2021:1–11.'
  apa: Nikfarjam, A., Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Computing
    Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation.
    In <i>Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
    Algorithms</i> (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 <i>Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
    Algorithms</i>, 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
    <i>Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms</i>,
    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.” <i>Proceedings of the 16th ACM}/SIGEVO
    Conference on Foundations of Genetic Algorithms</i>, 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'
...