MMAS vs. Population-based EA on a family of dynamic fitness functions

Andrei Lissovoi, Carsten Witt

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

Abstract

We study the behavior of a population-based EA and the Max-Min Ant System (MMAS) on a family of deterministically-changing fitness functions, where, in order to find the global optimum, the algorithms have to find specific local optima within each of a series of phases. In particular, we prove that a (2+1) EA with genotype diversity is able to find the global optimum of the Maze function, previously considered by Kötzing and Molter (PPSN 2012, 113--122), in polynomial time. This is then generalized to a hierarchy result stating that for every μ, a (μ+1) EA with genotype diversity is able to track a Maze function extended over a finite alphabet of μ symbols, whereas population size μ-1 is not sufficient. Furthermore, we show that MMAS does not require additional modifications to track the optimum of the finite-alphabet Maze functions, and, using a novel drift statement to simplify the analysis, reduce the required phase length of the Maze function.
Original languageEnglish
Title of host publicationProceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14))
PublisherAssociation for Computing Machinery
Publication date2014
Pages1399-1406
ISBN (Electronic)978-1-4503-2662-9
DOIs
Publication statusPublished - 2014
Event2014 Genetic and Evolutionary Computation Conference - Vancouver, Canada
Duration: 12 Jul 201416 Jul 2014
http://www.sigevo.org/gecco-2014/index.html

Conference

Conference2014 Genetic and Evolutionary Computation Conference
CountryCanada
CityVancouver
Period12/07/201416/07/2014
Internet address

Keywords

  • Evolutionary Algorithms
  • Ant Colony Optimization
  • Dynamic Problems
  • Populations
  • Runtime Analysis

Fingerprint Dive into the research topics of 'MMAS vs. Population-based EA on a family of dynamic fitness functions'. Together they form a unique fingerprint.

Cite this