Running time analysis of ant colony optimization for shortest path problems

DOI10.1016/J.JDA.2011.06.002MaRDI QIDQ414437zbMATH OpenOpenAlexFDO

Authors Dirk Sudholt, Christian Thyssen

Publication date 11 May 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2011.06.002

zbMATH Keywords

ant colony optimizationcombinatorial optimizationheuristic searchrunning time analysisshortest path problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Review text

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)].NEWLINENEWLINEThe 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.

Recommendations

• A simple ant colony optimizer for stochastic shortest path problems
• A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs
• Runtime analysis of ant colony optimization on dynamic shortest path problems
• Runtime Analysis of a Simple Ant Colony Optimization Algorithm
• Ant Colony Optimization Algorithms for Shortest Path Problems

Cites work

• A faster algorithm for the single source shortest path problem with few distinct positive lengths
• A GENERALIZED CONVERGENCE RESULT FOR THE GRAPH-BASED ANT SYSTEM METAHEURISTIC
• A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs
• Ant colony optimization theory: a survey
• Ant colony optimization.
• Computing single source shortest paths using single-objective fitness
• Fast Routing in Road Networks with Transit Nodes
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• First steps to the runtime complexity analysis of ant colony optimization
• scientific article; zbMATH DE number 5764853 (Why is no real title available?)
• scientific article; zbMATH DE number 1249654 (Why is no real title available?)
• Introduction to algorithms
• Mathematical Foundations of Computer Science 2003
• More algorithms for all-pairs shortest paths in weighted graphs
• Probability and Computing
• Runtime analysis of a binary particle swarm optimizer
• Runtime analysis of a simple ant colony optimization algorithm
• Runtime Analysis of a Simple Ant Colony Optimization Algorithm
• Runtime analysis of ant colony optimization with best-so-far reinforcement
• Runtime analysis of the 1-ANT ant colony optimizer
• Simple max-min ant systems and the optimization of linear pseudo-Boolean functions
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• The one-dimensional Ising model: mutation versus recombination
• Upper and lower bounds for randomized search heuristics in black-box optimization
• Using Markov-chain mixing time estimates for the analysis of ant colony optimization

Cited in

(17)

• Runtime analysis of a simple ant colony optimization algorithm
• A simple ant colony optimizer for stochastic shortest path problems
• Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks
• Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
• A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs
• Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems
• MMAS versus population-based EA on a family of dynamic fitness functions
• Ant Colony Optimization Algorithms for Shortest Path Problems
• scientific article; zbMATH DE number 2013445 (Why is no real title available?)
• Runtime analysis of ant colony optimization on dynamic shortest path problems
• scientific article; zbMATH DE number 1908584 (Why is no real title available?)
• Using Markov-chain mixing time estimates for the analysis of ant colony optimization
• Optimizing expected path lengths with ant colony optimization using fitness proportional update
• Ant Lion Optimized Lexicographic Model for Shortest Path Identification
• Runtime analysis of discrete particle swarm optimization applied to shortest paths computation
• Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax
• Ant colony optimization and the minimum spanning tree problem

Describes a project that uses

Uses Software

• AntNet

This page was built for publication: Running time analysis of ant colony optimization for shortest path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414437)