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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1145/2576768.2598301 | GECCO |
Keywords | Field | DocType |
dynamic problems,runtime analysis,ant colony optimization,evolutionary algorithms,general,populations | Ant colony optimization algorithms,Population,Mathematical optimization,Evolutionary algorithm,Local optimum,Global optimum,Population size,Artificial intelligence,Time complexity,Dynamic problem,Machine learning,Mathematics | Conference |
Citations | PageRank | References |
9 | 0.49 | 15 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrei Lissovoi | 1 | 67 | 7.69 |
Carsten Witt | 2 | 394 | 24.26 |