EUVIMEDEUVIMED entdecken
Crossref

Fitness Probability Distribution of Bit-Flip Mutation

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

Evolutionary Computation · 2015-06 · 23 (2) · 217-248

DOI: 10.1162/evco_a_00130 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2015-06. Verfasst von Francisco Chicano und 3 weiteren Autor:innen. Beteiligte Einrichtung: Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Spain chicano@lcc.uma.es. Hauptthemen laut MEDLINE: Algorithms, Mathematics, Models, Theoretical. Die Arbeit wurde bisher 48-mal zitiert (Crossref) und nennt 26 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsMathematicsModels, TheoreticalBiological EvolutionComputer SimulationModels, StatisticalMutation

Stichwörter der Autor:innen

Bit-flip mutationcombinatorial optimizationevolutionary algorithmslandscape theoryrandomized algorithms

Autor:innen und Institutionen

  • Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Spain chicano@lcc.uma.es.
  • Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität Jena, Germany andrew.sutton@uni-jena.de.
  • Department of Computer Science Colorado State University, USA whitley@cs.colostate.edu.
  • Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Spain eat@lcc.uma.es.

Zitieren

APA

Chicano, F., Sutton, A. M., Whitley, L. D., & Alba, E. (2015). Fitness Probability Distribution of Bit-Flip Mutation. Evolutionary Computation, 23(2), 217-248. https://doi.org/10.1162/evco_a_00130

Vancouver

Chicano F, Sutton AM, Whitley LD, Alba E. Fitness Probability Distribution of Bit-Flip Mutation. Evolutionary Computation. 2015;23(2):217-248. doi:10.1162/evco_a_00130

BibTeX
@article{Chicano2015,
  author = {Chicano, Francisco and Sutton, Andrew M and Whitley, L Darrell and Alba, Enrique},
  title = {Fitness Probability Distribution of Bit-Flip Mutation},
  journal = {Evolutionary Computation},
  year = {2015},
  volume = {23},
  number = {2},
  pages = {217--248},
  doi = {10.1162/evco_a_00130}
}
Kostenlos starten →