Running time analysis of ant colony optimization for shortest path problems

DOI10.1016/j.jda.2011.06.002zbMath1250.68238OpenAlexW2143945515MaRDI 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 optimizationheuristic searchant colony optimizationshortest path problemsrunning time analysis

Mathematics Subject Classification ID

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

Related Items (8)

MMAS versus population-based EA on a family of dynamic fitness functions ⋮ Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems ⋮ 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 ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ Memetic algorithms outperform evolutionary algorithms in multimodal optimisation ⋮ Runtime analysis of ant colony optimization on dynamic 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

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

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