How Crossover Helps in Pseudo-Boolean Optimization

T Kötzing, Dirk Sudholt, M Theile

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

57 Citations (Scopus)


Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions OneMax and Jump.

First, we assess the potential speedup by crossover when combined with a fitness-invariant bit shuffling operator that simulates a lineage of independent evolution on a function of unitation. Theoretical and empirical results show drastic speedups for both functions.

Second, we consider a simple GA without shuffling and investigate the interplay of mutation and crossover on Jump. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. We complement our theoretical findings by Monte Carlo simulations on the population diversity.
Original languageEnglish
Title of host publicationGECCO '11 Proceedings of the 13th annual conference on Genetic and evolutionary computation
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Print)978-1-4503-0557-0
Publication statusPublished - 16 Jul 2011
EventAnnual Conference on Genetic and Evolutionary Computation (GECCO '11), 13th - New York, United States
Duration: 16 Jul 2011 → …


ConferenceAnnual Conference on Genetic and Evolutionary Computation (GECCO '11), 13th
Country/TerritoryUnited States
CityNew York
Period16/07/11 → …


Dive into the research topics of 'How Crossover Helps in Pseudo-Boolean Optimization'. Together they form a unique fingerprint.

Cite this