06-12414
Introduction to Evolutionary Computation

Level 4/M

Dr A Kaban

10 credits in Sem1

The School of Computer Science Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)

Changes and Updates

Most recent update: 25 Nov 2003.

Changes possible until the start of the academic year.

Outline

Evolutionary computation is the study of computational systems that use ideas and get inspiration from natural evolution. Its techniques can be applied to optimisation, learning and design. Example topics covered in this module include natural and artificial evolution, evolutionary, chromosome representations, search operators, co-evolution, constraint handling techniques, niching and speciation, genetic programming, classifier systems and theoretical foundations.

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:	Assessed by:
Understand 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.	Examination
Understand the implementation issues of evolutionary algorithms.	Examination
Determine the appropriate parameter settings to make different evolutionary algorithms work well.	Examination
Design new evolutionary operators, representations and fitness functions for specific applications.	Examination

Restrictions, Prerequisites and Corequisites

Restrictions:

Excluded combination with 06-02411 Evolutionary Computation

Prerequisites:

None.

Co-requisites:

None.

Teaching

Teaching methods:

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

Contact hours:

Assessment

2 hr open book examination (100%).

Recommended Books

Title	Author(s)	Publisher, Date	Comments
Handbook on Evolutionary Computation	T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.)	IOS Press, 1997	Very good reference to evolutionary computation. Should read relevant sections after each lecture.
Genetic Algorithms + Data Structures = Evolution Programs (3rd edition)	Z Michalewicz	Springer-Verlag, 1996	Recommended reference book for this module. It is more up-to-date than Goldberg's book.
Genetic Algorithms in Search, Optimisation & Machine Learning	D E Goldberg	Addison-Wesley, 1989	Good reference book on genetic algorithms and classifier systems, but no other topics. Somewhat out of date.
Genetic Programming: An Introduction	W Banzhaf, P Nordin, R E Keller & Frank D Francone	Morgan Kaufmann, 1999	A comprehensive up-to-date textbook on genetic programming.
Evolutionary Computation: Theory and Applications	X Yao (ed)	World Scientific, 1999	Good for reference.
Various articles in journals and conference proceedings			Good for reference.

Detailed Syllabus

Introduction to Evolutionary Computation
- Biological and artificial evolution
- Evolutionary computation and AI
- Different historical branches of EC, e.g., GAs, EP, ES, GP, etc.
- A simple evolutionary algorithm
Search Operators
- Recombination/Crossover for strings (e.g., binary strings), e.g., one-point, multi-point, and uniform crossover operators
- Mutation for strings, e.g., bit-flipping
- Recombination/Crossover and mutation rates
- Recombination for real-valued representations, e.g., discrete and intermediate recombinations
- Mutation for real-valued representations, e.g., Gaussian and Cauchy mutations, self-adaptive mutations, etc.
- Why and how a recombination or mutation operator works
Selection Schemes
- Fitness proportional selection and fitness scaling
- Ranking, including linear, power, exponential and other ranking methods
- Tournament selection
- Selection pressure and its impact on evolutionary search
Search Operators and Representations
- Mixing different search operators
- An anomaly of self-adaptive mutations
- The importance of representation, e.g., binary vs. Gray coding
- Adaptive representations
Evolutionary Combinatorial Optimisation
- Evolutionary algorithms for TSPs
- Evolutionary algorithms for lecture room assignment
- Hybrid evolutionary and local search algorithms
Co-evolution
- Cooperative co-evolution
- Competitive co-evolution
Niching and Speciation
- Fitness sharing (explicit and implicit)
- Crowding and mating restriction
Constraint Handling
- Common techniques, e.g., penalty methods, repair methods, etc.
- Analysis
- Some examples
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
Multiobjective Evolutionary Optimisation
- Pareto optimality
- Multiobjective evolutionary algorithms
Learning Classifier Systems
- Basic ideas and motivations
- Main components and the main cycle
- Credit assignment and two approaches
Theoretical Analysis of Evolutionary Algorithms
- Schema theorems
- Convergence of EAs
- Computational time complexity of EAs
- No free lunch theorem
Summary

Relevant Links

Module Web Page

Page maintained by:	Dr P Coxhead
Content last updated:	25 Nov 2003
Source:	/resources/modules/2004/xml/12414.xml

06-12414Introduction to Evolutionary Computation