Empirical analysis of randomized algorithms

Heuristic algorithms are often difficult to analyse theoretically; this holds in particular for advanced, randomised algorithms that perform well in practice, such as high-performance stochastic local search (SLS) procedures (also known as metaheuristics) [1]. Furthermore, for various reasons, the practical applicability of the theoretical results that can be achieved is often very limited. Some theoretical results are obtained under idealised assumptions that do not hold in practical situations—as is the case, for example, for the well-known convergence result for simulated annealing [2]. Also, most complexity results apply to worst-case behaviour, and average-case results, which are fewer and typically much harder to prove, are often based on instance distributions that are unlikely to be encountered in practice. Finally, theoretical bounds on the run times of heuristic algorithms are typically asymptotic and do not reflect the actual behaviour accurately enough for many purposes, in particular, for comparative performance analyses. For these reasons, researchers (and practitioners) typically use empirical methods when analysing or evaluating heuristic algorithms.SCOPUS: ch.bSCOPUS: ch.bSCOPUS: ch.bSCOPUS: ch.bSCOPUS: ch.b