Runtime analysis of ant colony optimization on dynamic shortest path problems

Andrei Lissovoi; Carsten Witt

doi:10.1145/2463372.2463567

Runtime analysis of ant colony optimization on dynamic shortest path problems

Andrei Lissovoi
, Carsten Witt

Department of Applied Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

A simple ACO algorithm called λ-MMAS for dynamic variants of the single-destination shortest paths problem is studied by rigorous runtime analyses. Building upon previous results for the special case of 1-MMAS, it is studied to what extent an enlarged colony using $\lambda$ ants per vertex helps in tracking an oscillating optimum. It is shown that easy cases of oscillations can be tracked by a constant number of ants. However, the paper also identifies more involved oscillations that with overwhelming probability cannot be tracked with any polynomial-size colony. Finally, parameters of dynamic shortest-path problems which make the optimum difficult to track are discussed. Experiments illustrate theoretical findings and conjectures.

Original language	English
Title of host publication	Proceeding of the fifteenth annual conference on Genetic and evolutionary computation
Publisher	Association for Computing Machinery
Publication date	2013
Pages	1605-1612
ISBN (Print)	978-1-4503-1963-8
DOIs	https://doi.org/10.1145/2463372.2463567
Publication status	Published - 2013
Event	2013 Genetic and Evolutionary Computation Conference - Amsterdam, Netherlands Duration: 6 Jul 2013 → 10 Jul 2013 http://www.sigevo.org/gecco-2013/

Conference

Conference	2013 Genetic and Evolutionary Computation Conference
Country/Territory	Netherlands
City	Amsterdam
Period	06/07/2013 → 10/07/2013
Internet address	http://www.sigevo.org/gecco-2013/

Keywords

Ant Colony Optimization
Shortest Paths
Dynamic Problems
Runtime Analysis

Access to Document

10.1145/2463372.2463567

OpenUrl availability

Full text

Cite this

@inproceedings{6668b8d0bd4044f5b78898c61e94d0fe,

title = "Runtime analysis of ant colony optimization on dynamic shortest path problems",

abstract = "A simple ACO algorithm called λ-MMAS for dynamic variants of the single-destination shortest paths problem is studied by rigorous runtime analyses. Building upon previous results for the special case of 1-MMAS, it is studied to what extent an enlarged colony using \$\textbackslash{}lambda\$ ants per vertex helps in tracking an oscillating optimum. It is shown that easy cases of oscillations can be tracked by a constant number of ants. However, the paper also identifies more involved oscillations that with overwhelming probability cannot be tracked with any polynomial-size colony. Finally, parameters of dynamic shortest-path problems which make the optimum difficult to track are discussed. Experiments illustrate theoretical findings and conjectures.",

keywords = "Ant Colony Optimization, Shortest Paths, Dynamic Problems, Runtime Analysis",

author = "Andrei Lissovoi and Carsten Witt",

year = "2013",

doi = "10.1145/2463372.2463567",

language = "English",

isbn = "978-1-4503-1963-8",

pages = "1605--1612 ",

booktitle = "Proceeding of the fifteenth annual conference on Genetic and evolutionary computation",

publisher = "Association for Computing Machinery",

address = "United States",

note = "2013 Genetic and Evolutionary Computation Conference, GECCO 2013 ; Conference date: 06-07-2013 Through 10-07-2013",

url = "http://www.sigevo.org/gecco-2013/",

}

Lissovoi, A & Witt, C 2013, Runtime analysis of ant colony optimization on dynamic shortest path problems. in Proceeding of the fifteenth annual conference on Genetic and evolutionary computation. Association for Computing Machinery, pp. 1605-1612 , 2013 Genetic and Evolutionary Computation Conference, Amsterdam, Netherlands, 06/07/2013. https://doi.org/10.1145/2463372.2463567

Runtime analysis of ant colony optimization on dynamic shortest path problems. / Lissovoi, Andrei; Witt, Carsten.
Proceeding of the fifteenth annual conference on Genetic and evolutionary computation. Association for Computing Machinery, 2013. p. 1605-1612 .

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Runtime analysis of ant colony optimization on dynamic shortest path problems

AU - Lissovoi, Andrei

AU - Witt, Carsten

PY - 2013

Y1 - 2013

N2 - A simple ACO algorithm called λ-MMAS for dynamic variants of the single-destination shortest paths problem is studied by rigorous runtime analyses. Building upon previous results for the special case of 1-MMAS, it is studied to what extent an enlarged colony using $\lambda$ ants per vertex helps in tracking an oscillating optimum. It is shown that easy cases of oscillations can be tracked by a constant number of ants. However, the paper also identifies more involved oscillations that with overwhelming probability cannot be tracked with any polynomial-size colony. Finally, parameters of dynamic shortest-path problems which make the optimum difficult to track are discussed. Experiments illustrate theoretical findings and conjectures.

AB - A simple ACO algorithm called λ-MMAS for dynamic variants of the single-destination shortest paths problem is studied by rigorous runtime analyses. Building upon previous results for the special case of 1-MMAS, it is studied to what extent an enlarged colony using $\lambda$ ants per vertex helps in tracking an oscillating optimum. It is shown that easy cases of oscillations can be tracked by a constant number of ants. However, the paper also identifies more involved oscillations that with overwhelming probability cannot be tracked with any polynomial-size colony. Finally, parameters of dynamic shortest-path problems which make the optimum difficult to track are discussed. Experiments illustrate theoretical findings and conjectures.

KW - Ant Colony Optimization

KW - Shortest Paths

KW - Dynamic Problems

KW - Runtime Analysis

U2 - 10.1145/2463372.2463567

DO - 10.1145/2463372.2463567

M3 - Article in proceedings

SN - 978-1-4503-1963-8

SP - 1605

EP - 1612

BT - Proceeding of the fifteenth annual conference on Genetic and evolutionary computation

PB - Association for Computing Machinery

T2 - 2013 Genetic and Evolutionary Computation Conference

Y2 - 6 July 2013 through 10 July 2013

ER -

Runtime analysis of ant colony optimization on dynamic shortest path problems

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this