Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/66754
Citations | ||
Scopus | Web of ScienceĀ® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | On the Runtime Analysis of the 1-ANT ACO Algorithm |
Author: | Doerr, B. Neumann, F. Sudholt, D. Witt, C. |
Citation: | GECCO 2007 : Genetic and Evolutionary Computation Conference, July 7-11, 2007 University College London, London, UK / Dirk Thierens, et al. (eds.), pp. 33-40 |
Publisher: | ACM New York |
Publisher Place: | New York |
Issue Date: | 2007 |
ISBN: | 1595936971 9781595936974 |
Conference Name: | Genetic and Evolutionary Computation Conference (9th : 2007 : London, England) |
Editor: | Lipson, H. |
Statement of Responsibility: | Benjamin Doerr, Frank Neumann, Dirk Sudholt, Carsten Witt |
Abstract: | The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. These results, however, apply particularly to classical search heuristics such as Evolutionary Algorithms (EAs) and Simulated Annealing. First runtime analyses of modern search heuristics have been conducted only recently w.r.t a simple Ant Colony Optimization (ACO) algorithm called 1-ANT. In particular, the influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w.r.t the runtime behavior have been determined for the example function OneMax.This paper puts forward the rigorous runtime analysis of the 1-ANT on example functions, namely on the functions LeadingOnes and BinVal. With respect to EAs, such analyses have been essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice can be very crucial to allow efficient runtimes. Moreover, the analyses provide insight into the working principles of ACO algorithms and, in terms of their robustness, describe essential differences to other randomized search heuristics. |
Keywords: | Ant colony optimization runtime analysis |
Rights: | Copyright 2007 ACM |
DOI: | 10.1145/1276958.1276964 |
Description (link): | http://www.sigevo.org/gecco-2007/index.html |
Published version: | http://dx.doi.org/10.1145/1276958.1276964 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.