A simple ant colony optimizer for stochastic shortest path problems

DOI10.1007/s00453-011-9606-2zbMath1267.68219OpenAlexW2050441104MaRDI QIDQ1945168

Christian Thyssen, Dirk Sudholt

Publication date: 3 April 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9606-2

zbMATH Keywords

stochastic optimizationcombinatorial optimizationant colony optimizationshortest path problemsrunning time analysis

Mathematics Subject Classification ID

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

Related Items

Towards a runtime comparison of natural and artificial evolution, Robustness of populations in stochastic environments, PH-graphs for analyzing shortest path problems with correlated traveling times, Analysis of noisy evolutionary optimization when sampling fails, Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial, Analyzing randomized search heuristics via stochastic domination, Exponential upper bounds for the runtime of randomized search heuristics, Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise, Runtime analysis of ant colony optimization on dynamic shortest path problems, Running time analysis of the (1+1)-EA for robust linear optimization, Runtime analysis of a binary particle swarm optimizer, Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Running time analysis of ant colony optimization for shortest path problems
• Crossover can provably be useful in evolutionary computation
• Runtime analysis of the 1-ANT ant colony optimizer
• Shortest paths without a map
• A faster algorithm for the single source shortest path problem with few distinct positive lengths
• Ant colony optimization and the minimum spanning tree problem
• Runtime analysis of a simple ant colony optimization algorithm
• Runtime analysis of ant colony optimization with best-so-far reinforcement
• Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
• On the analysis of the \((1+1)\) evolutionary algorithm
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• More effective crossover operators for the all-pairs shortest path problem
• A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs
• Arriving on time
• Ant colony optimization theory: a survey
• Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks
• Fast Routing in Road Networks with Transit Nodes
• More algorithms for all-pairs shortest paths in weighted graphs
• Ant Colony Optimization Algorithms for Shortest Path Problems
• An Analysis of Stochastic Shortest Path Problems
• 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
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Concentration of Measure for the Analysis of Randomized Algorithms