Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Simple max-min ant systems and the optimization of linear pseudo-boolean functions
Author: Kötzing, T.
Neumann, F.
Sudholt, D.
Wagner, M.
Citation: Proceeding: FOGA '11: Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms, 2011 / vol.abs/1007.4707, pp.209-218
Publisher: ACM Press
Publisher Place: New York
Issue Date: 2011
ISBN: 9781450306331
Conference Name: ACM SIGEVO Workshop on Foundations of Genetic Algorithms (05 Jan 2011 - 09 Jan 2011 : Schwarzenberg, Austria)
Statement of
Timo Kötzing, Frank Neumann, Dirk Sudholt, Markus Wagner
Abstract: 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 the pheromones. We provide a general upper bound of O((n3 log n)ρ) on the running time 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.
Keywords: Ant colony optimization; MMAS; runtime analysis; pseudo-Boolean optimization; theory
Rights: Copyright 2011 ACM
RMID: 0020110568
DOI: 10.1145/1967654.1967673
Description (link):
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_70712.pdfRestricted Access1.07 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.