2010/07/27 by Timo Kötzing, Frank Neumann, Kötzing, Timo +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #F.2 #FOS: Computer and information sciences #Formal Methods in Verification #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Protein Degradation and Inhibitors #cs.NE
paper · pdf · doi:10.48550/arxiv.1007.4707
19 pages, 2 figures
arxiv created 2010/07/27 · openalex publication_date 2010/07/27 · arxiv updated 2010/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
With this paper, we contribute to the understanding of ant colony optimization (ACO) algorithms by formally analyzing their runtime behavior. We study simple MAX-MIN ant systems on the class of linear pseudo-Boolean functions defined on binary strings of length 'n'. Our investigations point out how the progress according to function values is stored in pheromone. We provide a general upper bound of O((n3 log n)/ ρ) for two ACO variants on all linear functions, where (ρ) determines the pheromone update strength. Furthermore, we show improved bounds for two well-known linear pseudo-Boolean functions called OneMax and BinVal and give additional insights using an experimental study.