Module 22753 (2010)

Syllabus page 2010/2011

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

Module Web Page


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:
1Demonstrate 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
2Demonstrate 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
4Determine the appropriate parameter settings to make different evolutionary algorithms work well Examination
5Design new evolutionary operators, representations and fitness functions for specific applications Examination
6Apply 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:

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

TitleAuthor(s)Publisher, Date
Handbook on Evolutionary ComputationT. Baeck, D. B. Fogel, and Z. Michalewicz (eds.)IOS Press, 1997
Genetic Algorithms + Data Structures = Evolution Programs (3rd edition)Z MichalewiczSpringer-Verlag, 1996
Multi-Objective Optimization Using Evolutionary AlgorithmsDeb KalyanmoyWiley, 2001
Introduction to Stochastic Search and OptimizationJames C. SpallWiley, 2003
Markov Chain Monte Carlo in Practice W.R. Gilks, S. Richardson & D.J. Spiegelhalter Chapman & Hall, 1996
Genetic Algorithms in Search, Optimisation & Machine LearningD E GoldbergAddison-Wesley, 1989
Genetic Programming: An IntroductionW Banzhaf, P Nordin, R E Keller & Frank D FranconeMorgan Kaufmann, 1999
Evolutionary Computation: Theory and ApplicationsX 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
    • 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

Last updated: 9 Jul 2009

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

Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus