---
_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'
...