Journal
INFORMATION PROCESSING LETTERS
Volume 105, Issue 3, Pages 88-92Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2007.08.013
Keywords
analysis of algorithms; graph algorithms; ant colony optimization; shortest paths
Categories
Ask authors/readers for more resources
In this paper, we prove polynomial running time bounds for an Ant Colony Optimization (ACO) algorithm for the single-destination shortest path problem on directed acyclic graphs. More specifically, we show that the expected number of iterations required for an ACO-based algorithm with n ants is O(1/rho n(2) log n) for graphs with n nodes and nt edges, where rho is an evaporation rate. This result can be modified to show that an ACO-based algorithm for One-Max with multiple ants converges in expected O(1/rho n(2) log n) iterations, where n is the number of variables. This result stands in sharp contrast with that of Neumann and Witt, where a single-ant algorithm is shown to require an exponential running time if rho = O(n(-1-epsilon)) epsilon > 0. (C) 2007 Elsevier B.V. All fights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available