Computational Complexity of Bio-inspired Computation in Combinatorial Optimization

algorithms or ant colony optimization have been shown to be very
successful when dealing with real-world applications or problems from
combinatorial optimization. In recent years, a lot of progress has
been made in understanding the runtime behavior of these heuristics
from a theoretical point of view.

In this tutorial, I would like to give an
overview how to analyze randomized search heuristics with respect to
the number of solutions they need to produce until a good one has been
found. I start by considering the optimization of artificial
pseudo-boolean functions and point out some general methods. After
that, I consider some well-known combinatorial optimization problems
such as minimum spanning trees, Eulerian cycles, and the set covering problem and show how the runtime behavior of different
randomized search heuristics can be analyzed for these problems.