Escaping large deceptive basins of attraction with heavy-tailed mutation operators

Tobias Friedrich, Francesco Quinzan, Markus Wagner

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

43 Citations (Scopus)

Abstract

In many evolutionary algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results in a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.

Original languageEnglish
Title of host publicationProceedings of the 2018 Genetic and Evolutionary Computation Conference
EditorsKeiki Takadama
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages293-300
Number of pages8
ISBN (Electronic)9781450356183
DOIs
Publication statusPublished - 2018
Externally publishedYes
EventThe Genetic and Evolutionary Computation Conference 2018 - Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018
Conference number: 20th
http://gecco-2018.sigevo.org/index.html/tiki-index.php
https://dl.acm.org/doi/proceedings/10.1145/3205455 (Proceedings)

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2018
Abbreviated titleGECCO 2018
Country/TerritoryJapan
CityKyoto
Period15/07/1819/07/18
Internet address

Keywords

  • Combinatorial optimization
  • Heavy-tailed mutation
  • Single-objective optimization

Cite this