Fitness Probability Distribution of Bit-Flip Mutation
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.
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)
Stichwörter der Autor:innen
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}
}
EUVIMED