Theory of Randomised Search Heuristic

Dirk Sudholt (Sheffield), Per Kristian Lehre (Nottingham), Pietro S. Oliveto (Sheffield), Christine Zarges (Birmingham)

Randomised search heuristics (RSH) like evolutionary algorithms and artificial immune systems are general-purpose optimisation heuristics, which take inspiration from nature. Evolutionary algorithms mimic the process of natural evolution through mutation, recombination, and selection. Artificial immune systems are inspired by processes in immunology. These heuristics have been applied successfully to countless engineering and design problems. Their drawback is that the reasons behind their success are often elusive. We are just beginning to understand when and why they perform well, which is the best heuristic to be used for a particular problem, and how to use these heuristics most effectively. Understanding the fundamental working principles that determine their efficiency is a major challenge.

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.

Syllabus:

Lecture 1: Introduction to the Analysis of Randomised Search Heuristics (Dirk Sudholt)

Lecture 2: Drift Analysis: a Tool for Analysing RSH (Per Kristian Lehre)

Lecture 3: Theory of Evolutionary Algorithms for Combinatorial Optimisation (Pietro Oliveto)

Lecture 4: Mutation in Evolutionary Algorithms and Artificial Immune Systems (Christine Zarges)

Last modified: Wed Jan 22 16:16:23 GMT 2014