# Module 22753 (2010)

## Syllabus page 2010/2011

06-22753
Introduction to Evolutionary Computation

Level 4/M

Ata Kaban
10 credits in Semester 1

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

### 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: 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 Examination 2 Demonstrate an understanding of the implementation issues of evolutionary algorithms Examination 3 Explain population based search methods inspired from physical systems, similarities with and differences from population based evolutionary systems, and ways of combining these Examination 4 Determine the appropriate parameter settings to make different evolutionary algorithms work well Examination 5 Design new evolutionary operators, representations and fitness functions for specific applications Examination 6 Apply knowledge learned in this module to solve a non-trivial problem Continuous Assessment

### Restrictions, Prerequisites and Corequisites

#### Restrictions:

May not be taken by anyone who has taken or is taking 06-02411 (Evolutionary Computation).

None

None

### Teaching

#### Teaching Methods:

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

24

### Assessment

• Sessional: 1.5 hr examination (80%) and course work (20%).
• Supplementary (where allowed): 1.5 hr examination (80%). The continuous assessment mark will be carried forward.

### Recommended Books

 Title Author(s) Publisher, Date Handbook on Evolutionary Computation T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.) IOS Press, 1997 Genetic Algorithms + Data Structures = Evolution Programs (3rd edition) Z Michalewicz Springer-Verlag, 1996 Multi-Objective Optimization Using Evolutionary Algorithms Deb Kalyanmoy Wiley, 2001 Introduction to Stochastic Search and Optimization James C. Spall Wiley, 2003 Markov Chain Monte Carlo in Practice W.R. Gilks, S. Richardson & D.J. Spiegelhalter Chapman & Hall, 1996 Genetic Algorithms in Search, Optimisation & Machine Learning D E Goldberg Addison-Wesley, 1989 Genetic Programming: An Introduction W Banzhaf, P Nordin, R E Keller & Frank D Francone Morgan Kaufmann, 1999 Evolutionary Computation: Theory and Applications X Yao (ed) World Scientific, 1999 Various articles in journals and conference proceedings

### Detailed Syllabus

1. 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
• 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

Last updated: 9 Jul 2009

Source file: /internal/modules/COMSCI/2010/xml/22753.xml