Module 02411 (2005)
Syllabus page 2005/2006
06-02411
Evolutionary Computation
Level 3/H
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
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: | |
| 1 | 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 |
| 2 | understand the implementation issues of evolutionary algorithms | Examination |
| 3 | determine the appropriate parameter settings to make different evolutionary algorithms work well | Examination |
| 4 | design new evolutionary operators, representations and fitness functions for specific applications | Examination |
Restrictions, Prerequisites and Corequisites
Restrictions:
None
Prerequisites:
None
Co-requisites:
None
Teaching
Teaching Methods:
2 hrs per week; a combination of lectures and tutorials.
Contact Hours:
Assessment
- Supplementary (where allowed): As the sessional assessment
- 1.5 hr examination (100%).
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 |
| 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 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
Last updated: 13 May 2005
Source file: /internal/modules/COMSCI/2005/xml/02411.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus