@MASTERSTHESIS\{IMM2012-06426,
    author       = "A. Lissovoi",
    title        = "Analysis of Ant Colony Optimization for Dynamic Shortest Path Problems",
    year         = "2012",
    school       = "Technical University of Denmark, {DTU} Informatics, {E-}mail: reception@imm.dtu.dk",
    address      = "Asmussens Alle, Building 305, {DK-}2800 Kgs. Lyngby, Denmark",
    type         = "",
    note         = "{DTU} supervisor: associate professor Carsten Witt, cawi@imm.dtu.dk, {DTU} Informatics",
    url          = "http://www.imm.dtu.dk/English.aspx",
    abstract     = "Combinatorial optimisation problems have traditionally been solved by specialized algorithms. Such problems also occur abundantly in nature, where they are solved without requiring excessive amounts of computing power or explicit algorithm design. Nature-inspired algorithms are based on behavior observed in nature, and are able to solve a wide variety of combinatorial optimisation problems without requiring much adaptation to a particular problem. Ant Colony Optimisation (ACO) is a metaheuristic encompassing a family of nature-inspired algorithms that are based on the foraging behavior of ants – using simulated pheromone trails to influence construction of random solutions to a problem, and updating the pheromone values to favor constructing good solutions over time.
This thesis considers how variants of the Max-Min Ant System algorithm, based on the {ACO} metaheuristic, are able to solve dynamic shortest path problems. Known results bounding its expected run time on static shortest path problems are presented and applied to rediscovering the shortest paths after a one-time change is made to the graph, showing O(n3 ) and \&\#937;(n3 ) upper and lower bounds (where n is the number of vertices in the graph) on the expected number of iterations to rediscover the shortest paths after specific one-time changes to the weight function.
It is then shown that the \&\#955;-{MMAS} algorithm, which constructs \&\#955; solutions in a single iteration in expectation requires fewer iterations to find the shortest paths, and, if parallel computation resources are available, also requires less running time. This approach is shown to reduce the expected number of iterations to O(n) while only requiring a polynomial number of ants (with respect to n) to be started at each vertex. Using additional ants is also shown to allow iteration-best pheromone reinforcement, where the colony reinforces the best paths constructed in the current iteration only. Patterns of periodic changes to the graph are then considered, and it is shown that when the changes to the shortest paths specified by the weight functions are relatively minor (adding or removing few arcs), \&\#955;-{MMAS} is able to keep track of the shortest paths reliably when log2 n ants are started at each vertex as long as the pheromone evaporation rate is not too high. When the changes to the shortest paths are more significant, it is shown that log2 n ants are no longer sufficient.
The considered algorithms are implemented in C. This implementation is used to perform experiments to supplement the analytical results with more detailed empirical data for small problem sizes."
}