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

Andrei Lissovoi; Carsten Witt

doi:10.1145/2576768.2598301

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

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14))
Publisher	Association for Computing Machinery
Publication date	2014
Pages	1399-1406
ISBN (Electronic)	978-1-4503-2662-9
DOIs	https://doi.org/10.1145/2576768.2598301
Publication status	Published - 2014
Event	2014 Genetic and Evolutionary Computation Conference - Vancouver, Canada Duration: 12 Jul 2014 → 16 Jul 2014 http://www.sigevo.org/gecco-2014/index.html

Conference

Conference	2014 Genetic and Evolutionary Computation Conference
Country	Canada
City	Vancouver
Period	12/07/2014 → 16/07/2014
Internet address	http://www.sigevo.org/gecco-2014/index.html

Keywords

Evolutionary Algorithms
Ant Colony Optimization
Dynamic Problems
Populations
Runtime Analysis

Access to Document

10.1145/2576768.2598301

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

@inproceedings{b93077b10e7c4542bdcaf702b6592fdf,

title = "MMAS vs. Population-based EA on a family of dynamic fitness functions",

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{\"o}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.",

keywords = "Evolutionary Algorithms, Ant Colony Optimization, Dynamic Problems, Populations, Runtime Analysis",

author = "Andrei Lissovoi and Carsten Witt",

year = "2014",

doi = "10.1145/2576768.2598301",

language = "English",

pages = "1399--1406",

booktitle = "Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14))",

publisher = "Association for Computing Machinery",

address = "United States",

note = "2014 Genetic and Evolutionary Computation Conference, GECCO 2014 ; Conference date: 12-07-2014 Through 16-07-2014",

url = "http://www.sigevo.org/gecco-2014/index.html",

}

TY - GEN

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

AU - Lissovoi, Andrei

AU - Witt, Carsten

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Evolutionary Algorithms

KW - Ant Colony Optimization

KW - Dynamic Problems

KW - Populations

KW - Runtime Analysis

U2 - 10.1145/2576768.2598301

DO - 10.1145/2576768.2598301

M3 - Article in proceedings

SP - 1399

EP - 1406

BT - Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14))

PB - Association for Computing Machinery

T2 - 2014 Genetic and Evolutionary Computation Conference

Y2 - 12 July 2014 through 16 July 2014

ER -