Mutation rates of the (1+1)-EA on Pseudo-Boolean functions of bounded epistasis

Andrew M. Sutton, L. Darrell Whitley, Adele E. Howe

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)-EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of 1/n is provably optimal. On functions where epistasis is bounded by a constant k, we show that for sufficiently high fitness, the commonly used mutation rate of 1/n is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degree-k polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum k-satisfiability problems and NK-landscapes show that this expectation-maximized mutation rate can cause significant gains early in search.

Original languageEnglish (US)
Title of host publicationGenetic and Evolutionary Computation Conference, GECCO'11
Pages973-980
Number of pages8
DOIs
StatePublished - Aug 24 2011
Event13th Annual Genetic and Evolutionary Computation Conference, GECCO'11 - Dublin, Ireland
Duration: Jul 12 2011Jul 16 2011

Publication series

NameGenetic and Evolutionary Computation Conference, GECCO'11

Other

Other13th Annual Genetic and Evolutionary Computation Conference, GECCO'11
CountryIreland
CityDublin
Period7/12/117/16/11

Keywords

  • Evolutionary algorithms
  • Walsh analysis

Fingerprint Dive into the research topics of 'Mutation rates of the (1+1)-EA on Pseudo-Boolean functions of bounded epistasis'. Together they form a unique fingerprint.

Cite this