School of Computer Science

Module 06-22753 (2011)

Introduction to Evolutionary Computation

Level 4/M

Ata Kaban Semester 1 10 credits
Co-ordinator: Ata Kaban
Reviewer: Shan He

The Module Description is a strict subset of this Syllabus Page.

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:

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

Teaching methods

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


Assessment

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

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

Programmes containing this module