Module 22753 (2011)
Syllabus page 2011/2012
06-22753
Introduction to Evolutionary Computation
Level 4/M
Ata Kaban
10 credits in Semester 1
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus
The Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)
Relevant Links
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: | 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).
Prerequisites:
None
Co-requisites:
None
Teaching
Teaching Methods:
2 hrs per week; a combination of lectures and tutorials.
Contact Hours:
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
-
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
- 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
- Fitness Landscapes
- Configuration spaces
- Properties of landscapes. Local optima; Basins
- Gradient walks and adaptive walks
- Spectral landscape theory
- Multi-population methods. Co-evolution
- Cooperative co-evolution
- Competitive co-evolution
- Niching and Speciation
- Fitness sharing (explicit and implicit)
- Crowding and mating restriction
- Multi-objective Evolutionary Optimisation
- Pareto optimality
- Multi-objective evolutionary algorithms
- Dynamic optimisation
- 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
- 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
- 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
- Introductory theoretical Analysis of Evolutionary Algorithms
- Schema theorems
- Convergence of EAs
- Computational time complexity of EAs
- No free lunch theorem
- Summary
Last updated: 9 Jul 2009
Source file: /internal/modules/COMSCI/2011/xml/22753.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus