The talk starts with giving a motivation for developing and investigating ACO variants where the time until the optimal solution is reached can be explicitly bounded, even if the bound is not polynomial. Such variants would be very desirable as algorithmic components applied for the solution of medium-sized instances of multicriteria stochastic CO problems. Runtime complexity analysis of ACO has only started recently, and very few results are available at the moment. However, two analytical techniques applied in existing investigations seem to have to potential to be generalizable to a larger class of problems. The talk outlines the key ideas of these techniques and illustrates them by results on the OneMax function.
Ant Colony Optimization, multiobjective optimization, stochastic optimization, combinatorial optimization, analysis of algorithms