Running time analysis of ant colony optimization for shortest path problems (Q414437)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Running time analysis of ant colony optimization for shortest path problems
scientific article

    Statements

    Running time analysis of ant colony optimization for shortest path problems (English)
    0 references
    0 references
    0 references
    11 May 2012
    0 references
    Ant colony optimization denotes a class of randomized search heuristics that are inspired by the ability of natural ants to find shortest paths. They simulate the path finding of ants algorithmically to find good solutions to different optimization problems. While finding shortest paths is the original motivation for ant colony optimization, its applications are usually in difficult optimization problems (see [\textit{M.\ Dorigo} and \textit{T. Stützle}, Ant Colony Optimization. Cambridge, MA: MIT Press (2004; Zbl 1092.90066)] for an introduction and overview). The theoretical analysis is concerned with particularly simple ant colony optimizers and simple problems. An important step was the analysis for the single source shortest paths problem [\textit{N.\ Attiratanasunthron} and \textit{J.\ Fakcharoenphol}, Inf. Process. Lett. 105, No. 3, 88--92 (2008; Zbl 1184.68659)]. The article under review continues this line of research and contains improved bounds, transfers the analysis to the all pairs shortest paths problem, and contains a comparison with evolutionary algorithms. The article is clearly structured and provides useful explanations. The proofs are complete and accessible, the example graphs used for lower bounds help to also build up a useful intuitive understanding.
    0 references
    0 references
    ant colony optimization
    0 references
    heuristic search
    0 references
    combinatorial optimization
    0 references
    running time analysis
    0 references
    shortest path problems
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers