Escaping local optima with diversity mechanisms and crossover

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


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

Colleges, School and Institutes

External organisations

  • University of Nottingham
  • Hasso Plattner Institute
  • Sheffield University


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
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
CountryUnited States


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