2026-07-21T15:07:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:592 2024-03-06T11:06:43Z ddc:004 open_access

Runtime Analysis of a Simple Ant Colony Optimization Algorithm Neumann, Frank Witt, Carsten Randomized Search Heuristics Ant Colony Optimization Runtime Analysis Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in a finite amount of time. We present the first runtime analysis of a simple ACO algorithm that transfers many rigorous results with respect to the expected runtime of a simple evolutionary algorithm to our algorithm. In addition, we examine the choice of the evaporation factor, which is a crucial parameter in such an algorithm, in greater detail and analyze its effect with respect to the runtime. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frank Neumann and Carsten Witt 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06061.8 urn:nbn:de:0030-drops-5928 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.8 eng https://creativecommons.org/licenses/by/4.0/legalcode