Running time analysis of ant colony optimization for shortest path problems

DOI10.1016/j.jda.2011.06.002zbMath1250.68238MaRDI QIDQ414437

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

combinatorial optimization; heuristic search; ant colony optimization; shortest path problems; running time analysis

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90C27: Combinatorial optimization

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax, MMAS versus population-based EA on a family of dynamic fitness functions, Runtime analysis of ant colony optimization on dynamic shortest path problems, 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, Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems

Uses Software

• AntNet

Cites Work

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