# Module 06-22753 (2013)

## Introduction to Evolutionary Computation

## Level 4/M

Ata Kaban | Semester 1 | 10 credits |

### Outline

### Aims

The aims of this module are to:

- introduce the main concepts, techniques and applications in the field of evolutionary computation
- give students some experience on when evolutionary techniques are useful, how to use them in practice and how to implement them with different programming languages

### Learning Outcomes

On successful completion of this module, the student should be able to:

1 Demonstrate an understanding of the relations between the most important evolutionary algorithms presented in the module, new algorithms to be found in the literature now or in the future, and other search and optimisation techniques

2 Demonstrate an understanding of the implementation issues of evolutionary algorithms

3 Explain population based search methods inspired from physical systems, similarities with and differences from population based evolutionary systems, and ways of combining these

4 Determine the appropriate parameter settings to make different evolutionary algorithms work well

5 Design new evolutionary operators, representations and fitness functions for specific applications

6 Apply knowledge learned in this module to solve a non-trivial problem

### Restrictions

### Cannot be taken with

- 06-02411 - Evolutionary Computation

### Teaching methods

2 hrs per week; a combination of lectures and tutorials.

Contact Hours: 23

### Assessment

Sessional: 1.5 hr examination (80%), continuous assessment (20%)

Supplementary (where allowed): 1.5 hr examination (80%). The continuous assessment mark will be carried forward.

### Detailed Syllabus

- Introduction

* Evolutionary computation as a computational paradigm inspired from evolutionary biology * Evolutionary computation as a stochastic search * Relation with AI and ML * When to use evolutionary methods * Different historical branches of EC: GA, EP, ES, GP. * A simple evolutionary algorithm 2. Genetic Representation, search operators, selection schemes and selection pressure * Representations for Continuous versus Discrete combinatorial optimisation * Crossover for strings and real-valued representations: One-point, multi-point, and uniform crossover operators. Discrete and intermediate recombination * Mutation for strings and real-valued representations. Gaussian and Cauchy mutations, self-adaptive mutations, etc. * Why and how a recombination or mutation operator works * Hybrid evolutionary and local search algorithms * Selection pressure and its impact on evolutionary search * Fitness proportional selection, fitness scaling, fitness ranking, tournament selection and (mu+,lambda) selection 3. Fitness Landscapes * Configuration spaces * Properties of landscapes. Local optima; Basins * Gradient walks and adaptive walks * Spectral landscape theory 4. Multi-population methods. Co-evolution * Cooperative co-evolution * Competitive co-evolution 5. Niching and Speciation * Fitness sharing (explicit and implicit) * Crowding and mating restriction 6. Multi-objective Evolutionary Optimisation * Pareto optimality * Multi-objective evolutionary algorithms 7. Dynamic optimisation 8. Genetic Programming Trees as individuals Major steps of genetic programming, e.g., functional and terminal sets, initialisation, crossover, mutation, fitness evaluation, etc. Search operators on trees Automatically defined functions Issues in genetic programming, e.g., bloat, scalability, etc. Examples 9. A case study of Evolutionary methods The role of domain knowledge; the risks of pure simulation based approach GA versus GP; goal oriented design Evolutionary design vs traditional design 10. Evolving learning-machines, e.g. Neural Networks or Learning Classifier Systems Basic ideas and motivations Encoding the individuals Main components and the main cycle Credit assignment and two approaches 11. Introductory theoretical Analysis of Evolutionary Algorithms Schema theorems Convergence of EAs Computational time complexity of EAs No free lunch theorem 12. Summary

### Programmes containing this module

- MEng Computer Science/Software Engineering [4754]
- MEng Computer Science/Software Engineering with an Industrial Year [9501]
- MRes Natural Computation [9048]
- MSc Advanced Computer Science [0014]
- MSc Computer Science [0008]
- MSc Human-Computer Interaction [9151]
- MSc Multidisciplinary Optimisation [9150]
- MSc Robotics [9889]
- MSci Computer Science [4443]
- MSci Computer Science with an Industrial Year [9509]
- MSci Computer Science with Study Abroad [5576]
- MSci Mathematics and Computer Science [5197]
- MSci Mathematics and Computer Science with an Industrial Year [9496]
- MSci Pure Mathematics and Computer Science [5256]
- MSci Pure Mathematics and Computer Science with an Industrial Year [9498]