In the last 15 years analyses have appeared that study the efficiency of RSH from the perspective of theoretical computer science, using algorithmic analysis to study their efficiency. These runtime analyses capture how long a particular heuristic needs to find satisfactory solutions for interesting problems, a vital cornerstone in understanding their dynamic behavior and improving their design.
This tutorial will give an introduction to this emerging field at the interface of theoretical computer science, stochastic processes, and computational intelligence. We will start with the analysis of simple RSH on illustrative problems, highlighting the effect of design choices on efficiency. We introduce drift analysis, a powerful and versatile tool for analysing stochastic processes, and how it can be used to analyse RSH. This leads on to the analysis of evolutionary algorithms on classical combinatorial optimisation problems. We finish with insights on mutation operators used in evolutionary algorithms and artificial immune systems.
Lecture 1: Introduction to the Analysis of Randomised Search Heuristics (Dirk Sudholt)Course materials:
Lecture 2: Drift Analysis: a Tool for Analysing RSH (Per Kristian Lehre)Course materials:
Lecture 3: Theory of Evolutionary Algorithms for Combinatorial Optimisation (Pietro Oliveto)Course materials:
Lecture 4: Mutation in Evolutionary Algorithms and Artificial Immune Systems (Christine Zarges)Course materials: