Markov Chain-based Optimization Time and Variance Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes

Rössler M, Keszöcze O, Wanka R (2026)

Publication Language: English

Publication Type: Journal article, Original article

Publication year: 2026

Journal

ACM Transactions on Evolutionary Learning and Optimization Association for Computing Machinery (ACM)

Abstract

Only few mathematically proven bounds on the runtime behavior of Ant Colony Optimization (ACO) have been reported. To alleviate this situation, we investigate the ACO variant we call Bivalent ACO (BACO) that uses exactly two pheromone values. We provide and successfully apply a Markov chain-based approach to calculate the expected optimization time, i. e., the expected number of iterations until an adjustable quality κ of the solution is reached and the algorithm terminates. This approach allows to derive exact formulas for the expected optimization time and its variance for the problems Sorting and LeadingOnes. It turns out that the ratio of the two pheromone values significantly governs the runtime behavior of BACO. We present tight bounds Θ(κ ⋅ n²) for Sorting with a specifically chosen objective function and Θ(κ ⋅ n) for LeadingOnes. We
show that, despite having a drastically simplified ant algorithm with respect to the influence of the pheromones on the solving process, the known bound on the expected optimization time for the problem LeadingOnes (O(n²)) can be re-produced. Experiments validate our theoretical findings.

Authors with CRIS profile

Matthias Rössler Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung) Rolf Wanka Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)

Involved external institutions

Technische Universität Clausthal / Clausthal University of Technology

Germany (DE)

How to cite

APA:

Rössler, M., Keszöcze, O., & Wanka, R. (2026). Markov Chain-based Optimization Time and Variance Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes. ACM Transactions on Evolutionary Learning and Optimization. https://doi.org/10.1145/3795136

MLA:

Rössler, Matthias, Oliver Keszöcze, and Rolf Wanka. "Markov Chain-based Optimization Time and Variance Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes." ACM Transactions on Evolutionary Learning and Optimization (2026).

BibTeX: Download