Analysis of an Asymmetric Mutation Operator

Thomas Jansen, Dirk Sudholt

Research output: Contribution to journalArticlepeer-review

Abstract

Evolutionary algorithms are general randomized search heuristics and typically perform all unbiased random search that is guided only by the fitness of the search points encountered. However, in applications there is often problem-specific knowledge that suggests some additional bias. The use of appropriately biased variation opera tors may speed up the search considerably. Problems defined over bit strings of finite length often have the property that good solutions have only very few 1-bits or very few 0-bits. A mutation operator tailored toward such situations is studied under different perspectives and in a rigorous way discussing its assets and drawbacks. We consider the runtime of evolutionary algorithms using biased mutations oil illustrative example functions as well as oil function classes. A comparison with unbiased operators shows on which functions biased mutations lead to a speedup, on which functions biased Mutations increase the runtime, and in which settings there is almost no difference in performance. The main focus is on theoretical runtime analysis yielding asymptotic results. These findings are accompanied by the results of empirical investigations that deliver additional insights.

Original languageEnglish
Pages (from-to)1-26
Number of pages26
JournalEvolutionary Computation
Volume18
Issue number1
DOIs
Publication statusPublished - 2010

Keywords

  • runtime analysis
  • Evolutionary algorithms
  • mutation
  • unimodal problems
  • EVOLUTIONARY ALGORITHMS

Fingerprint

Dive into the research topics of 'Analysis of an Asymmetric Mutation Operator'. Together they form a unique fingerprint.

Cite this