Benjamin Doerr
ABSTRACT
The first rigorous theoretical analysis (Horoba, Sudholt (GECCO 2010)) of an ant colony optimizer for the stochastic shortest path problem suggests that ant system experience significant difficulties when the input data is prone to noise. In this work, we propose a slightly different ant optimizer to deal with noise.
We prove that under mild conditions, it finds the paths with shortest expected length efficiently, despite the fact that we do not have convergence in the classic sense. To prove our results, we introduce a stronger drift theorem that can also deal with the situation that the progress is faster when one is closer to the goal.
- 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:88--92, 2008. Google Scholar
Digital Library
- P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal of Computing, 32:48--77, 2003. Google ScholarDigital Library
- L. Bianchi, M. Dorigo, L. M. Gambardella, and W. J. Gutjahr. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing, 8:239--287, 2009. Google ScholarDigital Library
- N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. Google ScholarDigital Library
- B. Doerr, M. Fouz, and C. Witt. Sharp bounds by probability-generating functions and variable drift. In Genetic and Evolutionary Computation Conference (GECCO'11), pages 2083--2090. ACM, 2011. Google ScholarDigital Library
- B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. In Genetic and Evolutionary Computation Conference (GECCO'10), pages 1449--1456. ACM, 2010. Google ScholarDigital Library
- B. Doerr, F. Neumann, D. Sudholt, and C. Witt. On the runtime analysis of the 1-ANT ACO algorithm. In Genetic and Evolutionary Computation Conference (GECCO'07), pages 33--40. ACM, 2007. Google ScholarDigital Library
- M. Dorigo. Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, 1992.Google Scholar
- M. Dorigo and T. Stützle. Ant colony optimization. MIT Press, 2004. Google ScholarDigital Library
- M. Gardner. Nontransitive dice and other probability paradoxes. Scientific American, 223:110--114, 1970.Google ScholarCross Ref
- W. J. Gutjahr. A graph-based ant system and its convergence. Future Generation Comper Systems, 16:873--888, 2000. Google ScholarDigital Library
- W. J. Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution. Information Processessing Letters, 82:145--153, 2002.Google ScholarCross Ref
- W. J. Gutjahr. A converging ACO algorithm for stochastic combinatorial optimization. In Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'03), pages 10--25, 2003.Google ScholarCross Ref
- W. J. Gutjahr. S-ACO: An ant-based approach to combinatorial optimization under uncertainty. In ANTS, pages 238--249. Springer, 2004.Google ScholarCross Ref
- W. J. Gutjahr. Mathematical runtime analysis of aco algorithms: survey on an emerging issue. Swarm Intelligence, 1:59--79, 2007.Google ScholarCross Ref
- W. J. Gutjahr. First steps to the runtime complexity analysis of ant colony optimization. Computers and Operations Research, 35:2711--2727, 2008. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- A. György, T. Linder, G. Lugosi, and G. Ottucsák. The on-line shortest path problem under partial monitoring. Journal of Machine Learning Research, 8:2369--2403, 2007. Google ScholarDigital Library
- J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127:57--85, 2001. Google ScholarDigital Library
- J. He and X. Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3:21--35, 2004. Google ScholarDigital Library
- C. Horoba and D. Sudholt. Running time analysis of ACO systems for shortest path problems. In Engineering Stochastic Local Search Algorithms (SLS'09), pages 76--91. Springer, 2009. Google ScholarDigital Library
- C. Horoba and D. Sudholt. Ant colony optimization for stochastic shortest path problems. In Genetic and Evolutionary Computation Conference (GECCO'10), pages 1465--1472. ACM, 2010. Google ScholarDigital Library
- D. Johannsen. Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universität des Saarlandes, 2010. Available online at http://scidok.sulb.uni-saarland.de/volltexte/2011/3529/pdf/Dissertation_3166_Joha_Dani_2010.pdf.Google Scholar
- T. Kötzing, F. Neumann, D. Sudholt, and M. Wagner. Simple max-min ant systems and the optimization of linear pseudo-boolean functions. In Foundations of Genetic Algorithms (FOGA'11), pages 209--218. ACM, 2011. Google ScholarDigital Library
- T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4--22, 1985.Google ScholarDigital Library
- H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527--535, 1952.Google ScholarCross Ref
- T. Stützle and H. H. Hoos. MAX-MIN ant system. Future Generation Computer Systems, 16:889--914, 2000. Google ScholarDigital Library
Index Terms
- Ants easily solve stochastic shortest path problems
Recommendations
Ant colony optimization for stochastic shortest path problems
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computationWe consider Ant Colony Optimization (ACO) for stochastic shortest path problems where edge weights are subject to noise that reflects delays and uncertainty. The question is whether the ants can find or approximate shortest paths in the presence of ...
Optimizing expected path lengths with ant colony optimization using fitness proportional update
FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XIIWe study the behavior of a Max-Min Ant System (MMAS) on the stochastic single-destination shortest path (SDSP) problem. Two previous papers already analyzed this setting for two slightly different MMAS algorithms, where the pheromone update fitness-...
A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems
Ant Colony Optimization (ACO) is a popular optimization paradigm inspired by the capabilities of natural ant colonies of finding shortest paths between their nest and a food source. This has led to many successful applications for various combinatorial ...
Comments