Authors: Doerr, Benjamin
Neumann, Frank
Sudholt, Dirk
Witt, Carsten
Title: On the influence of pheromone updates in ACO algorithms
Language (ISO): en
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 have been determined for the example function OneMax. This paper puts forward the runtime analysis of the 1-ANT on example functions. 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.
URI: http://hdl.handle.net/2003/26130
http://dx.doi.org/10.17877/DE290R-8719
Issue Date: 2007-01
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
22307.pdfDNB205.99 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.