TY - GEN
T1 - Ants easily solve stochastic shortest path problems
AU - Doerr, Benjamin
AU - Hota, Ashish
AU - Kötzing, Timo
PY - 2012/8/13
Y1 - 2012/8/13
N2 - 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.
AB - 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.
KW - running time analysis
KW - stochastic shortest path
KW - theory
U2 - 10.1145/2330163.2330167
DO - 10.1145/2330163.2330167
M3 - Conference contribution
AN - SCOPUS:84864671670
SN - 9781450311779
T3 - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
SP - 17
EP - 24
BT - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
T2 - 14th International Conference on Genetic and Evolutionary Computation, GECCO'12
Y2 - 7 July 2012 through 11 July 2012
ER -