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

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 \(\kappa\) 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 \(\Theta(\kappa\cdot n^{2})\) for Sorting with a specifically chosen objective function and \(\Theta(\kappa\cdot 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 ( \(\mathcal{O}(n^{2})\) ) can be re-produced. Experiments validate our theoretical findings.