Many real-world optimization problems in, e.g., engineering
or biology have the property that not much is known about
the function to be optimized. This excludes the application
of problem-specific algorithms. Simple randomized search
heuristics are then used with surprisingly good results. In
order to understand the working principles behind such
heuristics, they are analyzed on combinatorial optimization
problems whose structure is well-studied. The idea is to
investigate when it is possible to "simulate randomly" clever
optimization techniques and when this random search fails.
The main purpose is to develop methods for the analysis of
general randomized search heuristics. The maximum matching
problem is well suited for this approach since long augmenting
paths do not allow local improvements and since our results on
randomized local search and simple evolutionary algorithms
can be compared with published results on the Metropolis
algorithm and simulated annealing.