Update Strength in EDAs and ACO: How to Avoid Genetic Drift

Dirk Sudholt, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We provide a rigorous runtime analysis concerning the update strength, a vital parameter in probabilistic model-building GAs such as the step size 1/K in the compact Genetic Algorithm (cGA) and the evaporation factor ρ in ACO. While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to genetic drift and poor performance. We demonstrate this trade-off for the cGA and a simple MMAS ACO algorithm on the OneMax function. More precisely, we obtain lower bounds on the expected runtime of Ω(K√n + nlogn) and Ω(√n/ρ + nlogn), respectively, showing that the update strength should be limited to 1/K, ρ = O(1/(√n log n)). In fact, choosing 1/K, ρ ∼ 1/(√n log n) both algorithms efficiently optimize OneMax in expected time O (n log n). Our analyses provide new insights into the stochastic behavior of probabilistic model-building GAs and propose new guidelines for setting the update strength in global optimization.
Original languageEnglish
Title of host publicationProceedings of the Genetic and Evolutionary Computation Conference (GECCO '16)
PublisherAssociation for Computing Machinery
Publication date2016
Pages61-68
ISBN (Print)978-1-4503-4206-3
DOIs
Publication statusPublished - 2016
Event2016 Genetic and Evolutionary Computation Conference - Denver, United States
Duration: 20 Jul 201624 Jul 2016
http://gecco-2016.sigevo.org/index.html/HomePage#&panel1-1

Conference

Conference2016 Genetic and Evolutionary Computation Conference
CountryUnited States
CityDenver
Period20/07/201624/07/2016
Internet address

Keywords

  • Ant Colony Optimization
  • Estimation-of-Distribution Algorithms
  • Iteration-Best Update
  • Genetic Drift
  • Runtime Analysis
  • Theory

Fingerprint Dive into the research topics of 'Update Strength in EDAs and ACO: How to Avoid Genetic Drift'. Together they form a unique fingerprint.

Cite this