Fitness probability distribution of bit-flip mutation

Francisco Chicano, Andrew M. Sutton, L. Darrell Whitley, Enrique Alba

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit.We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.

Original languageEnglish (US)
Pages (from-to)217-248
Number of pages32
JournalEvolutionary Computation
Volume23
Issue number2
DOIs
StatePublished - Jun 17 2015

Bibliographical note

Publisher Copyright:
© 2015 by the Massachusetts Institute of Technology.

Keywords

  • Bit-flip mutation
  • Combinatorial optimization
  • Evolutionary algorithms
  • Landscape theory
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'Fitness probability distribution of bit-flip mutation'. Together they form a unique fingerprint.

Cite this