Escaping local optima with diversity mechanisms and crossover

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

Authors

  • 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

Abstract

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.

Details

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

Conference

Conference2016 Genetic and Evolutionary Computation Conference, GECCO 2016
CountryUnited States
CityDenver
Period20/07/1624/07/16

Keywords

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