Using Markov-Chain Mixing Time Estimates for the Analysis of Ant Colony Optimization

摘要

The Markov chain Monte Carlo paradigm has developed powerful and elegant techniques for estimating the time until a Markov chain approaches a stationary distribution. This time is known as mixing time. We introduce the reader into mixing time estimations via coupling arguments and use the mixing of pheromone models for analyzing the expected optimization time of ant colony optimization. We demonstrate the approach for plateaus in pseudo-Boolean optimization and derive upper bounds for the time until a target set is found. We also describe how mixing times can be estimated for MM AS ant systems on shortest, path problems.