Escaping local optima with diversity mechanisms and crossover

Duc Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, Andrew M. Sutton

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

26 Citations (Scopus)


Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jumpk. All previous results in this context only hold for unrealistically low crossover probability pc = O(k/n), while we give analyses for the setting of constant pc < 1 in all but one case. Our bounds show a dependence on the problem size n, the jump length k, the population size μ, and the crossover probability pc. For the typical case of constant k > 2 and constant pc, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ: • O (nk-1) J for duplicate elimination/minimisation, • O (n2 log n) for maximising the convex hull, • O(n log n) for det. crowding (assuming pc = k/n), • O(n log n) for maximising the Hamming distance, • O(n log n) for fitness sharing, • O(n log n) for the single-receiver island model. This proves a sizeable advantage of all variants of the (μ+1) GA compared to the (1+1) EA, which requires Θ(n). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.

Original languageEnglish
Title of host publicationGECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Electronic)9781450342063
Publication statusPublished - 20 Jul 2016
Event2016 Genetic and Evolutionary Computation Conference, GECCO 2016 - Denver, United States
Duration: 20 Jul 201624 Jul 2016


Conference2016 Genetic and Evolutionary Computation Conference, GECCO 2016
Country/TerritoryUnited States


  • Crossover
  • Diversity
  • Genetic algorithms
  • Recombination
  • Run time analysis
  • Theory

ASJC Scopus subject areas

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Software


Dive into the research topics of 'Escaping local optima with diversity mechanisms and crossover'. Together they form a unique fingerprint.

Cite this