Analysis of different MMAS ACO algorithms on unimodal functions and plateaus
Frank Neumann, Dirk Sudholt, Carsten Witt · Swarm Intelligence · 2008
Recently, the first rigorous runtime analyses of ACO algorithms appeared, covering variants of the MAX–MIN ant system and their runtime on pseudo-Boolean functions. Interestingly, a variant called 1-ANT is very sensitive to the evaporation factor while Gutjahr and Sebastiani proved partly opposite results for their variant MMAS bs . These algorithms differ in their pheromone update mechanisms and, moreover, 1-ANT accepts equally fit solutions in contrast to MMAS bs . By analyzing variants of MMAS bs , we prove that the different behavior of 1-ANT and MMAS bs results from the different pheromone update mechanisms. Building upon results by Gutjahr and Sebastiani, we extend their analyses of MMAS bs to the class of unimodal functions and show improved results for test functions using new and specialized techniques; in particular, we present new lower bounds. Finally, we compare MMAS bs with a variant that also accepts equally fit solutions as this enables the exploration of plateaus. For well-known plateau functions we prove that this drastically reduces the optimization time. Our findings are complemented by experiments that support our asymptotic analyses and yield additional insights.