Workshop Theory of Randomized Search Heuristics

(colocated with ICALP 2007)


Theory of Randomized Search Heuristics in Combinatorial Optimization

by Carsten Witt

The rigorousmathematical analysis of randomized search heuristics (RSHs) with respect to their expected runtime is a growing research area where many results have been obtained in recent years. This class of heuristics contains well-known approaches such as Randomized Local Search (RLS), the Metropolis Algorithm (MA), Simulated Annealing (SA), and Evolutionary Algorithms (EAs) as well as more recent approaches such as Ant Colony Optimization (ACO). Such heuris- tics are often applied to problems whose structure is not known or if there are not enough resources such as time, money, or knowledge to obtain good specific algorithms. It is widely acknowledged that a solid mathematical foundation for such heuristics is needed.
Most designers of RSHs, however, rather focused on mimicking processes in nature (such as evolution) rather than making the heuristics amenable to a mathematical analysis. This is different to the classical design of (randomized) algorithms which are developed with their theoretical analysis of runtime (and proof of correctness) in mind. Despite these obstacles, research from the last about 15 years has shown how to apply the methods for the probabilistic analysis of randomized algorithms to RSHs. Mostly, the expected runtime of RSHs on selected problems is analzyed. Thereby, we understand why and when RSHs are efficient optimizers and, conversely, when they cannot be efficient.
This talk will give an overview on the analysis of RSHs for solving com- binatorial optimization problems. Starting from the first toy examples such as the OneMax function, we approach more realistic problems and arrive at analysis of the runtime and approximation quality of RSHs even for NP-hard problems. Our studies treat not only simple RLS algorithms and SA but also more complex population-based EAs and even ACO algorithms. We will present exemplary analyses to underline that many models and methods from the prob- abilistic analysis of algorithms (e. g., concentration inequalities such as Markov, Chebyscheff, Chernoff-Hoeffding bounds, the principle of deferred decision, de- lay sequence methods, martingale theory, random walks and rapidly mixing markov chains) and modifications thereof return in our studies. To apply these methods, however, a deep understanding of the stochastic process behind the considered RSH is required which is often the hardest task in the analysis.

Back to mainpage