Simple Max-Min Ant Systems and the Optimization 
of Linear Pseudo-Boolean Functions

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

With this paper, we contribute to the understanding of ant
colony optimization (ACO) algorithms by formally analyz-
ing their runtime behavior. We study simple MAX-MIN ant
systems on the class of linear pseudo-Boolean functions de-
fined 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^3logn)/rho) on the running time for two ACO variants
on all linear functions, where rho 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.