Code

COMPGI06 (Also taught as: COMPM057 Evolutionary Computation)

Year

MSc

Prerequisites

Discrete Mathematics and Calculus

Term

1

Taught By

Mark Herbster (Part A) (50%)

Chris Watkins (Part B) (50%)

Aims

Part A: This course introduces the ideas and practical techniques behind the various sub-fields that make up evolutionary computation (EC). The course will focus on the established evolutionary paradigms as well as the most significant new developments, covering genetic algorithms, genetic programming, evolutionary programming, evolutionary strategies, ant-colony optimisation, swarm intelligence and artificial life amongst other topics. Students will be taught how these approaches identify and exploit biological processes in nature, allowing a wide range of applications to be solved in business and industry. Key problem domains will be examined for example design, scheduling, function regression, fraud detection, anomaly detection, robot control and some of the newer domains, for example music composition and the generation of art may be covered. Part B: 'Evolutionary computation is a loose collection of techniques that are widely used in practice for optimisation. As their name suggests they were inspired by the idea of simulating biological evolution - but the theory (such as it is) of evolutionary computation has has made little contact with mathematical genetics. In Part B, Chris Watkins will survey the biological inspiration for evolutionary computation, and then cover some core topics of mathematical genetics, and show how they are relevant to designing and problem-shooting evolutionary algorithms. Some parts of the course will be of general relevance to other courses, specifically Bioinformatics and to Probabilistic and Unsupervised Learning.

Learning Outcomes

To be able to: understand the concepts, advantages and disadvantages of the techniques in evolutionary computation, be able to design suitable genetic representations with appropriate fitness functions for simple problems, to know of the key issues in using these techniques for search of difficult search-spaces, to be aware of the different approaches and different applications in the field.

Part A

Context

Role of biologically inspired software
Difficulties in search, optimisation and machine learning

Evolution

Overview of natural evolution and its abilities
Genetic Algorithms
Genetic Programming
Evolutionary Programming/Evolutionary Strategies
Issues in evolutionary search
Applying an evolutionary algorithm

New topics in EC

Artificial Life
Ant colony optimisation
Swarm intelligence

Application areas

Optimisation, function regression
Scheduling

Fraud detection
Anomaly detection
Design
Robot or agent control
Interactive tools such as music composition and art generation

Part B

1. The Biological Inspiration: a brief survey of natural mechanisms of genetics and evolution

2. Changes in Gene Frequencies: effects of selection, drift, population size, mutation rate. Classical population genetic theory applied to evolutionary computation.

3. Quantitative genetics: effects of correlations of parents with offsrping, rate and direction of change of quantitative characteristics of population. Estimation and heritability. Again, we will study the classical linear theory of quantitative genetics, and apply it to evolutionary computation.

4. 'Estimation of Distribution' algorithms. /these algorithms go under many names and have been studied by many people. Different variants may be analysed as models of evolution, as EM optimisation, or as Gibbs sampling.

5. Practical aspects of design, control, and diagnostics for evolutionary algorithms. Visulaisation, particularly with t-SNE.

Lecture presentations with associated class problems.

The course has the following assessment components:

•  Written Examination (2.5 hours, 50%)
 
• Coursework Section (50%) (for full details of coursework requirements see the course web page)

To pass this course, students must:

 
• Obtain an overall pass mark of 50% for all sections combined
 

The examination rubric is:
Answer three questions out of four. All questions carry equal marks.

Part A

An Introduction to Genetic Algorithms Melanie Mitchell. Mit Press. 1998. ISBN 0262631857

Lecture notes

MSc Machine Learning Homepage

Part B

Selected materials from the following books will be used (normally photocopies or summaries will be handed out in class).

Kenneth De Jong, Evolutionary Computation: a Unified Approach (MIT Press 2006)

A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing (Natural Computing Series) (Springer 2010)

Michael Lynch, The Origins of Genetic Architecture (Sinauer 2007)

John Maynard Smith, Evolutionary Genetics (2nd Edition) (OUP 1998)

David Mackay, Information, Inference and LEarning Algorithms (especially chapter 19 on evolution) (CUP 1993)