Back to Search
Start Over
MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions.
- Source :
- Algorithmica; Jul2016, Vol. 75 Issue 3, p554-576, 23p
- Publication Year :
- 2016
-
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 [9], in polynomial time. This is then generalized to a hierarchy result stating that for every $$\mu $$ , a ( $$\mu $$ +1) EA with genotype diversity is able to track a Maze function extended over a finite alphabet of $$\mu $$ symbols, whereas population size $$\mu -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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 75
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 118328691
- Full Text :
- https://doi.org/10.1007/s00453-015-9975-z