Using markov-chain mixing time estimates for the analysis of ant colony optimization

ABSTRACT

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 MMAS ant systems on shortest path problems.

References

1. D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. Monograph in preparation, http://stat-www.berkeley.edu/users/aldous/RWG/book.html, 2010.
2. N. Attiratanasunthron and J. Fakcharoenphol. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs. Information Processing Letters, 105 (3): 88--92, 2008.
3. B. Doerr and D. Johannsen. Refined runtime analysis of a basic ant colony optimization algorithm. In Proceedings of the Congress of Evolutionary Computation (CEC '07), pages 501--507. IEEE Press, 2007.
4. B. Doerr, M. Gnewuch, N. Hebbinghaus, and F. Neumann. A rigorous view on neutrality. In Proceedings of the Congress of Evolutionary Computation (CEC '07), pages 2591--2597. IEEE Press, 2007.
5. B. Doerr, F. Neumann, D. Sudholt, and C. Witt. On the runtime analysis of the 1-ANT ACO algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '07), pages 33--40. ACM, 2007.
6. M. Dorigo and C. Blum. Ant colony optimization theory: A survey. Theoretical Computer Science, 344: 243--278, 2005.
7. M. Dorigo and T. Stützle. Ant Colony Optimization. MIT Press, 2004.
8. S. Droste, T. Jansen, and I. Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems, 39 (4): 525--544, 2006.
9. J. Garnier, L. Kallel, and M. Schoenauer. Rigorous hitting times for binary mutations. Evolutionary Computation, 7 (2): 173--203, 1999.
10. W. J. Gutjahr. First steps to the runtime complexity analysis of ant colony optimization. Computers and Operations Research, 35 (9): 2711--2727, 2008.
11. W. J. Gutjahr and G. Sebastiani. Runtime analysis of ant colony optimization with best-so-far reinforcement. Methodology and Computing in Applied Probability, 10: 409--433, 2008.
12. B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14: 502--525, 1982.
13. E. Happ, D. Johannsen, C. Klein, and F. Neumann. Rigorous analyses of fitness-proportional selection for optimizing linear functions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '08), pages 953--960. ACM, 2008.
14. T. P. Hayes, J. C. Vera, and E. Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. In STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 450--458. ACM, 2007.
15. C. Horoba and D. Sudholt. Running time analysis of ACO systems for shortest path problems. In Proceedings of Engineering Stochastic Local Search Algorithms (SLS '09), volume 5752 of LNCS, pages 76--91. Springer, 2009.
16. C. Horoba and D. Sudholt. Ant colony optimization for stochastic shortest path problems. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '10), pages 1465--1472, 2010.
17. M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems, pages 482--520. PWS Publishing, 1996.
18. M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51 (4): 671--697, 2004.
19. J. Jägersküpper and T. Storch. When the plus strategy outperforms the comma strategy - and when not. In Proceedings of the 2007 IEEE Symposium on Foundations of Computational Intelligence (FOCI '07), pages 25--32. IEEE, 2007.
20. T. Kötzing, P. K. Lehre, P. S. Oliveto, and F. Neumann. Ant colony optimization and the minimum cut problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '10), pages 1393--1400. ACM, 2010.
21. T. Kötzing, F. Neumann, H. Röglin, and C. Witt. Theoretical properties of two ACO approaches for the traveling salesman problem. In Seventh International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS '10), volume 6234 of LNCS, pages 324--335. Springer, 2010.
22. J. Lässig and D. Sudholt. The benefit of migration in parallel evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '10), pages 1105--1112, 2010.
23. P. K. Lehre and X. Yao. On the impact of the mutation-selection balance on the runtime of evolutionary algorithms. In FOGA '09: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, pages 47--58. ACM, 2009.
24. D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008.
25. J. Liu. Monte Carlo Strategies in Scientific Computing. Springer, 2002.
26. L. Lovász and S. Vempala. Simulated annealing in convex bodies and an O*(n⁴) volume algorithm. Journal of Computer and System Sciences, 72 (2): 392--417, 2006.
27. B. Mitavskiy, J. E. Rowe, A. H. Wright, and L. M. Schmitt. Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm. Genetic Programming and Evolvable Machines, 9 (2): 109--123, 2008.
28. M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.
29. F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 378 (1): 32--40, 2007.
30. F. Neumann and C. Witt. Runtime analysis of a simple ant colony optimization algorithm. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC '06), volume 4288 of LNCS, pages 618--627. Springer, 2006.
31. F. Neumann and C. Witt. Ant Colony Optimization and the minimum spanning tree problem. In Proceedings of Learning and Intelligent Optimization (LION '07), volume 5313 of LNCS, pages 153--166. Springer, 2008.
32. F. Neumann and C. Witt. Runtime analysis of a simple ant colony optimization algorithm. Algorithmica, 54 (2): 243--255, 2009.
33. F. Neumann, D. Sudholt, and C. Witt. Comparing variants of MMAS ACO algorithms on pseudo-Boolean functions. In Proceedings of Engineering Stochastic Local Search Algorithms (SLS '07), volume 4638 of LNCS, pages 61--75. Springer, 2007.
34. F. Neumann, D. Sudholt, and C. Witt. Rigorous analyses for the combination of ant colony optimization and local search. In Proceedings of the Sixth International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS '08), volume 5217 of LNCS, pages 132--143. Springer, 2008.
35. F. Neumann, P. S. Oliveto, and C. Witt. Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 835--842. ACM, 2009.
36. F. Neumann, D. Sudholt, and C. Witt. Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intelligence, 3 (1): 35--68, 2009.
37. F. Neumann, D. Sudholt, and C. Witt. A few ants are enough: ACO with iteration-best update. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '10), pages 63--70. ACM, 2010.
38. S. Sanyal, R. S., and S. Biswas. Necessary and sufficient conditions for success of the metropolis algorithm for optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '10), pages 1417--1424. ACM, 2010.
39. C. Witt. Rigorous runtime analysis of swarm intelligence algorithms - an overview. In Swarm Intelligence for Multi-objective Problems in Data Mining, volume 242/2009 of Studies in Computational Intelligence, pages 157--177. Springer, 2009.
40. Y. Zhou. Runtime analysis of an ant colony optimization algorithm for TSP instances. IEEE Transactions on Evolutionary Computation, 13 (5): 1083--1092, 2009.

Index Terms

• Theory of computation

  • Design and analysis of algorithms