abstract
theoretical analyses of stochastic search algorithms, albeit few, have always existed since
these algorithms became popular. starting in the nineties a systematic approach to analyse
the performance of stochastic search heuristics has been put in place. this quickly increasing
basis of results allows, nowadays, the analysis of sophisticated algorithms such as populationbased evolutionary algorithms, ant colony optimisation and artificial immune systems. results
are available concerning problems from various domains including classical combinatorial and
continuous optimisation, single and multi-objective optimisation, and noisy and dynamic optimisation. this chapter introduces the mathematical techniques that are most commonly
used in the runtime analysis of stochastic search heuristics. careful attention is given to the
very popular artificial fitness levels and drift analyses techniques for which several variants are
presented. to aid the reader’s comprehension of the presented mathematical methods, these
are applied to the analysis of simple evolutionary algorithms for artificial example functions.
the chapter is concluded by providing references to more complex applications and further
extensions of the techniques for the obtainment of advanced results.