Evolutionary Computation, 2011/2012

Index

• Course description
• Syllabus
• Bibliography
• Class notes
• Grading
• Tips for your project

Course description

Evolutionary Computation can be considered as a sub-field of Artificial Intelligence. Evolutionary algorithms use Nature as a metaphor and are inspired in the principles of natural selection and genetics. These algorithms have been applied successfully for solving difficult problems across a broad spectrum of fields, including engineering, economics and finance, architecture, design, automatic programming, art generation, and many others. In this course, you will learn the basic working principles of these algorithms.

Syllabus

• Week 1: What is Evolutionary Computation? Historical perspective. Major classes of Evolutionary Algorithms. Local vs global search methods.
• Week 2: Simple genetic algorithms and simple evolution strategies: basic principles.
• Week 3: Genetic programming. Problem difficulty and the NFL theorem.
• Week 4: Representations. Design of operators.
• Week 5: Constraint handling. Finding multiple optima. Multi-objective optimization.
• Week 6: Basic GA theory. Limitations of simple EAs. Goldberg's decomposition for competent GAs.
• Week 7: Parameter setting in EAs. Using problem specific information.
• Week 8: Estimation of Distribution Algorithms.

• Outline lecture by lecture

Bibliography

I will not follow a particular book for this course. But I will indicate specific chapters from the books below. I do recommend you have a look at the first 3 chapters of David Goldberg's 1989 book (a classic in the field), and also to Eiben and Smith's introductory book on Evolutionary Computation. Sean Luke's book (available for free on the net) also provides a nice introduction to many of the topics that we will cover. I will also give you research papers as supplement material.

• Genetic Algorithms in Search, Optimization and Machine Learning
  by David E. Goldberg, Addison-Wesley, 1989.
  
  
• Introduction to Evolutionary Computing
  by A. E. Eiben and J. E. Smith, Springer, 2003.
  
  
• Evolutionary Computation 1: Basic Algorithms and Operators
  edited by T. Bäck, D. B. Fogel, Z. Michalewicz, 2000.
  
  
• Evolutionary Computation 2: Advanced Algorithms and Operators
  edited by T. Bäck, D. B. Fogel, Z. Michalewicz, 2000.
  
  
• Essentials of Metaheuristics (available for free)
  by Sean Luke, 2010.
  
  
• A Field Guide to Genetic Programming (available for free)
  by Riccardo Poli, William Langdon, and Nicholas McPhee.
  
  

Class notes and documentation

Slides

1. A very quick introduction to Evolutionary Computation
2. Genetic Algorithms: Introduction
3. Genetic Algorithms: Commonly Used Selection, Replacement, and Variation Operators
4. Evolution Strategies (a tutorial by Thomas Bäck, presented at the ACM GECCO Conference in 2010)
5. Genetic Programming (a tutorial by John Koza, presented at the ACM GECCO Conference in 2010)
6. Links about Interactive Evolution
7. Problem difficulty
8. Constraint handling
9. Niching and speciation
10. Multi-Objective Optimization (a tutorial by Kalyanmoy Deb, presented at the ACM GECCO Conference in 2010)
11. Dynamic Optimization (slides by Philipp Rohlfshagen).
12. Basic GA theory
13. Population sizing models for GAs
14. Building block mixing and the scalability of simple GAs
15. Parameter-less GA
16. Estimation of Distribution Algorithms
17. Probabilistic model-building genetic algorithms (a tutorial by Martin Pelikan, presented at the ACM GECCO Conference in 2010)

Labs

• Implementing a simple GA
• Magic Square competition

Articles

For those papers without a link, I can provide you with a copy of the paper upon request.

1. Genetic Algorithms, by Martin Pelikan.
2. Evolution Strategies: A Comprehensive Introduction, by Hans-Georg Beyer and Hans-Paul Schwefel.
3. Genetic Programming, by John Koza and Riccardo Poli.
4. Simulated Binary Crossover for Continuous Search Space, by Kalyanmoy Deb and Ram Agrawal.
5. An Efficient Constraint Handling Method for Genetic Algorithms, by Kalyanmoy Deb.
6. An Investigation of Niche and Species Formation in Genetic Function Optimization, by Kalyanmoy Deb and David E. Goldberg.
7. A Tutorial on Evolutionary Multiobjective Optimization, by Eckart Zitzler, Marco Laumanns, and Stefan Bleuler.
8. Multi-Objective Optimization, by Kalyanmoy Deb.
9. Evolutionary Optimization in Uncertain Environments - A Survey, by Yaochu Jin and Jürgen Branke.
10. A Comparative Analysis of Selection Schemes Used in Genetic Algorithms, by David E. Goldberg and Kalyanmoy Deb.
11. Genetic Algorithms, Noise, and the Sizing of Populations, by David E. Goldberg, Kalyanmoy Deb, and James Clark.
12. The Gambler's Ruin Problem, Genetic Algorithms and the Sizing of Populations, by Georges Harik, Erick Cantu-Paz, David E. Goldberg, and Brad L. Miller.
13. Mixing in Genetic Algorithms, by Dirk Thierens and David E. Goldberg.
14. Scalability Problems of Simple Genetic Algorithms, by Dirk Thierens.
15. A parameter-less genetic algorithm, by Georges Harik and Fernando Lobo.
16. The compact genetic algorithm, by Georges Harik, Fernando Lobo, and David E. Goldberg.
17. Linkage learning via probabilistic modeling in the ECGA, by Georges Harik.
18. A survey of optimization by building and using probabilistic models, by Martin Pelikan, David E. Goldberg, and Fernando Lobo.

Code

• My own implementation of a simple genetic algorithm in C++. You can use and extend it as you wish. Make sure you read the readme.txt file.
• This is Kalyanmoy Deb's GA implementation in C. Allows real- and binary-coded values, as well as constraint handling.
• This is ECJ, a Java-based Evolutionary Computation Research System done by Sean Luke and others.
• This is Kalyanmoy Deb's NSGA-II in C, for multi-objective optimization.

Grading

The grading of this course is based on a project that you'll develop (alone or in a group of two students). The project consists of applying evolutionary computation to an application domain of your own choice. You can also choose to work on a theory-related topic in case you want to.

• write a technical report (10 page maximum) describing your application. (70%)
• make a 20-minute oral presentation of your work. (20%)
• read and carefully review 1 report from your classmates. (10%)

This process mimics what happens when researchers (professors, doctoral and master students) submit their work to scientific conferences worldwide. This should be helpful for getting you started in doing research.

Tips for your project

You may want to have a look at the following links to get ideas for you class project.

• A compendium of NP optimization problems.
• A cool application for evolving Mona Lisa (or any other image). Check it out Roger Alsing weblog, and also here.

As a final note, you may want to check David Goldberg's Technical Writing for Fun & Profit for tips on writing technical reports.