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

Kergaßner M, Keszöcze O, Wanka R (2024)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2024

Event location: Melbourne

Abstract

So far, only few 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 new Markov chain-based approach to calculate the expected optimization time, i. e., the expected number of iterations until the algorithm terminates. This
approach allows to derive exact formulæ for the expected optimization time for the problems Sorting and LeadingOnes. It turns out that the ratio of the two pheromone values significantly governs the runtime be-
havior of BACO. To the best of our knowledge, for the first time, we can present tight bounds for Sorting (Θ(n³)) with a specifically chosen objective function and prove the missing lower bound Ω(n²) for LeadingOnes which, thus, is tightly bounded by Θ(n²). We show that despite we have a drastically simplified ant algorithm with respect to the influence of the pheromones on the solving process, known bounds on the expected optimization time for the problems OneMax (O(n log n)) and LeadingOnes (O(n²)) can be re-produced as a by-product of our approach. Experiments validate our theoretical findings.

Authors with CRIS profile

Matthias Kergaßner Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung) Oliver Keszöcze Juniorprofessur für Informatik Rolf Wanka Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)

How to cite

APA:

Kergaßner, M., Keszöcze, O., & Wanka, R. (2024). Markov Chain-based Optimization Time Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). Melbourne, AU.

MLA:

Kergaßner, Matthias, Oliver Keszöcze, and Rolf Wanka. "Markov Chain-based Optimization Time Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes." Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Melbourne 2024.

BibTeX: Download