Abstract of Paper

Towards a Theory of Randomized Search Heuristics
by Ingo Wegener

Abstract:

There is a well-developed theory about the algorithmic complexity of
optimization problems.
Complexity theory provides negative results which typically are based on
assumptions like NP$\neq$P or NP$\neq$RP.
Positive results are obtained by the design and analysis of clever
algorithms.
These algorithms are well-tuned for their specific domain.
Practitioners, however, prefer simple algorithms which are easy to
implement and which can be used without many changes for different types
of problems.
They report surprisingly good results when applying randomized search
heuristics like randomized local search, tabu search, simulated
annealing, and evolutionary algorithms.
Here a framework for a theory of randomized search heuristics is
presented.
It is discussed how randomized search heuristics can be delimited from
other types of algorithms.
This leads to the theory of black-box optimization.
Lower bounds in this scenario can be proved without any
complexity-theoretical assumption.
Moreover, methods how to analyze randomized search heuristics, in
particular, randomized local search and evolutionary algorithms are
presented.