### 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 μ , 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 |
---|---|

Journal | Algorithmica |

Volume | 75 |

Issue number | 3 |

Pages (from-to) | 554-576 |

ISSN | 0178-4617 |

DOIs | |

Publication status | Published - 2015 |

### Keywords

- Ant colony optimization
- Dynamic problems
- Evolutionary algorithms
- Populations
- Runtime analysis
- Polynomial approximation
- Population statistics
- Dynamic fitness function
- Dynamic problem
- Finite alphabet
- Fitness functions
- Polynomial-time
- Population sizes
- Run-time analysis

## Cite this

Lissovoi, A., & Witt, C. (2015). MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions.

*Algorithmica*,*75*(3), 554-576. https://doi.org/10.1007/s00453-015-9975-z