Simple max-min ant systems and the optimization of linear pseudo-Boolean functions

Timo Kötzing; Frank Neumann; Dirk Sudholt; Markus Wagner

doi:10.1145/1967654.1967673

Simple max-min ant systems and the optimization of linear pseudo-Boolean functions

Timo Kötzing, Frank Neumann, Dirk Sudholt, Markus Wagner

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

27 Citations (Scopus)

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((n³ 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.

Original language	English
Title of host publication	FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI
Publisher	Association for Computing Machinery (ACM)
Pages	209-218
Number of pages	10
ISBN (Print)	9781450306331
DOIs	https://doi.org/10.1145/1967654.1967673
Publication status	Published - 2011
Externally published	Yes
Event	Foundations of Genetic Algorithms Workshop 2011 - Schwarzenberg, Austria Duration: 5 Jan 2011 → 9 Jan 2011 Conference number: 11th https://dl.acm.org/doi/proceedings/10.1145/1967654 (Proceedings)

Workshop

Workshop	Foundations of Genetic Algorithms Workshop 2011
Abbreviated title	FOGA XI
Country/Territory	Austria
City	Schwarzenberg
Period	5/01/11 → 9/01/11
Internet address	https://dl.acm.org/doi/proceedings/10.1145/1967654 (Proceedings)

Keywords

Ant colony optimization
MMAS
Pseudo-Boolean optimization
Runtime analysis
Theory

Access to Document

10.1145/1967654.1967673

Cite this

@inproceedings{cc257afae1964bf7a759792c85e9f726,

title = "Simple max-min ant systems and the optimization of linear pseudo-Boolean functions",

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, Pseudo-Boolean optimization, Runtime analysis, Theory",

author = "Timo K{\"o}tzing and Frank Neumann and Dirk Sudholt and Markus Wagner",

year = "2011",

doi = "10.1145/1967654.1967673",

language = "English",

isbn = "9781450306331",

pages = "209--218",

booktitle = "FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

note = "Foundations of Genetic Algorithms Workshop 2011, FOGA XI ; Conference date: 05-01-2011 Through 09-01-2011",

url = "https://dl.acm.org/doi/proceedings/10.1145/1967654",

}

Kötzing, T, Neumann, F, Sudholt, D & Wagner, M 2011, Simple max-min ant systems and the optimization of linear pseudo-Boolean functions. in FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI. Association for Computing Machinery (ACM), pp. 209-218, Foundations of Genetic Algorithms Workshop 2011, Schwarzenberg, Austria, 5/01/11. https://doi.org/10.1145/1967654.1967673

Simple max-min ant systems and the optimization of linear pseudo-Boolean functions. / Kötzing, Timo; Neumann, Frank; Sudholt, Dirk et al.
FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI. Association for Computing Machinery (ACM), 2011. p. 209-218.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Simple max-min ant systems and the optimization of linear pseudo-Boolean functions

AU - Kötzing, Timo

AU - Neumann, Frank

AU - Sudholt, Dirk

AU - Wagner, Markus

N1 - Conference code: 11th

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Ant colony optimization

KW - MMAS

KW - Pseudo-Boolean optimization

KW - Runtime analysis

KW - Theory

UR - https://www.scopus.com/pages/publications/79956015422

U2 - 10.1145/1967654.1967673

DO - 10.1145/1967654.1967673

M3 - Conference Paper

AN - SCOPUS:79956015422

SN - 9781450306331

SP - 209

EP - 218

BT - FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI

PB - Association for Computing Machinery (ACM)

T2 - Foundations of Genetic Algorithms Workshop 2011

Y2 - 5 January 2011 through 9 January 2011

ER -

Simple max-min ant systems and the optimization of linear pseudo-Boolean functions

Abstract

Workshop

Keywords

Access to Document

Other files and links

Cite this