Evolutionary Computation, 2017/2018

Index

Instructor

Fernando Lobo (fernando.lobo@gmail.com), Ed. I, room 1.64.

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

Bibliography

I will not follow a particular book for this course. But I will indicate specific chapters from the books below.

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. Powerpoint file for chapter 4 of IEC book by A. E. Eiben, additional slides from that book made by the same author are available at http://www.cs.vu.nl/~gusz/ecbook/ecbook-course.html
  6. Genetic Programming
  7. Interactive evolutionary computation. Check these links
  8. Constraint handling
  9. Niching and speciation
  10. Multi-Objective Optimization (uses part of Kalyanmoy Deb's tutorial presented at the ACM GECCO Conference in 2010)
  11. Basic GA theory
  12. Problem difficulty
  13. Population sizing models for GAs
  14. Building block mixing and the scalability of simple GAs
  15. Parameter-less GA
  16. Model based EAs

Articles

For those articles without a link, I can provide you a copy upon request. Some of the articles only have free access inside the university.

  1. Genetic Algorithms, by Martin Pelikan.
  2. Evolution Strategies, by Nikolaus Hansen, Dirk Arnold, and Anne Auger.
  3. Genetic Programming, by John Koza and Riccardo Poli.
  4. Grammar-based Genetic Programming: a survey, by Robert McKay, Nguyen Hoai, Peter Whigham, Yin Shan, Michael O'Neill.
  5. Multi-Objective Optimization, by Kalyanmoy Deb.
  6. 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.
  7. Mixing in Genetic Algorithms, by Dirk Thierens and David E. Goldberg.
  8. Scalability Problems of Simple Genetic Algorithms, by Dirk Thierens.
  9. A parameter-less genetic algorithm, by Georges Harik and Fernando Lobo.
  10. Introduction to Estimation of Distribution Algorithms, by Martin Pelikan, Mark Hauschild, and Fernando Lobo.

Outline lecture by lecture

Main lectures

Note: In the suggested reading colum,

lecture # date contents suggested reading
01 19/Sep/17 Course introduction. What is evolutionary computation? What is it good for? Analogies between the natural and the artificial. IEC (chap 1,2).
EC-1 (chap 1,2,6).
02 26/Sep/17 Illustration of a sample application: evolving an image with polygons. Introduction to genetic algorithms. Major components: selection, recombination, mutation, replacement. Mechanics of binary tournament selection, one-point crossover, and bit-flip mutation. Simulating a genetic algorithm by hand on the onemax problem. IEC (chap 3).
Pelikan's tech report.
GASOML (chap 1,3).
03 27/Sep/17 Another application example: a network expansion problem.
Proportionate selection methods: roulette wheel, stochastic universal sampling (SUS). Drawbacks of proportionate-based selection methods.
Readings from lecture 2 + EC-1 (chap 24, 25).
04 03/Oct/17 Ordinal-based selection methods: tournament selection (with and without replacement), truncation selection. Replacement strategies: random and worst. Readings from lecture 2 + EC-1 (chap 24, 25).
05 04/Oct/17 Commonly used variation operators in genetic algorithms for binary and k-ary string codes. Approaches for handling other representations. Mapping real-valued representations to binary codes and its limitations. EC-1 (chap 32.2, 33.2).
06 10/Oct/17 Commonly used variation operators for manipulating real-valued vectors directly: Gaussian mutation. Discrete, Arithmetic, and Simulated Binary Crossover (SBX). EC-1 (chap 32.2, 33.2).
SBX paper.
07 11/Oct/17
08 17/Oct/17 Variation operators for manipulating permutations. Swap, Inversion, and Scramble mutation. Partially Matched Crossover (PMX), Uniform Order-Based Crossover. Edge Recombination: a problem specific operator for the Traveling Salesman Problem. EC-1 (chap 32.3, 33.3). IEC (chap 3.5.4).
09 18/Oct/17 Introduction to Evolution Strategies. Historical perspective. Major differences with respect to genetic algorithms. The (1+1)-ES algorithm and the 1/5-success rule. ES(mu+lambda) and ES(mu,lambda). EC-1 (chap 6.4, 9).
IEC (chap 4).
ES paper by Hansel et al.
10 24/Oct/17 Self-adaptation of strategy parameters with uncorrelated mutations: one and n uncorrelated mutations. Correlated mutations. Recombination in ES: local vs. global, discrete vs. intermediate. ES(mu+lambda) and ES(mu,lambda). same as previous lecture.
11 25/Oct/17 Genetic Programming: the basic ideas. FGGP (chap 1,2,3,4)
GP paper
12 31/Oct/17 Grammar-based Genetic Programming. FGGP (chap 6)
Grammar-based GP paper
13 07/Nov/17 Interactive Evolutionary Computation: the basic ideas and some illustrative examples. Check these links
14 08/Nov/17 Constraint handling methods commonly used in evolutinary algorithms. EC-2 (chap 6,7,8,9,10)
15 14/Nov/17 Niching and speciation methods for multimodal optimization. EC-2 (13,14)
16 15/Nov/17 Evolutionary multi-objective optimization: Pareto-dominance and Pareto-optimal solutions, preference articulation and decision making, objective aggregation, multi-objective ranking. The Non-Dominated Sorting Genetic Algorithm (NSGA-II). EC-2 (chap 5)
MOO paper
17 21/Nov/17
18 22/Nov/17 Basic genetic algorithm's theory. The notion of schema. GAs as schema processors. The schema theorem and the building block hypothesis. GASOML (chap 2).
19 28/Nov/17 Problem difficulty and deception, problems of bounded difficulty. The No Free Lunch Theorem. EC-1 (chap 3.1).
20 29/Nov/17 Population sizing models for genetic algorithms. Building block supply and decision models. paper
21 05/Dec/17 Building block mixing and scalability problems of simple genetic algorithms. paper
22 06/Dec/17 Automated parameter setting. Parameter-less GA. paper
23 12/Dec/17 Model based EAs. EDA survey paper

Labs

lecture # date contents
01 26/Sep/17 Introduction to the Mooshak platform for programming assignments. Programming assignment 1.
02 03/Oct/17 Programming assignment 2.
03 10/Oct/17 Programming assignment 3.
04 17/Oct/17 Time to finish previous programming assignments.
05 24/Oct/17 Programming assignment 4.
06 31/Oct/17 Programming assignment 4 (cont.)
07 07/Nov/17 Discussion of problems and ideas suitable for the course project.
08 14/Nov/17 Work on class project.
09 21/Nov/17 Work on class project.
10 28/Dec/17 Work on class project.
11 05/Dec/17 Work on class project.
12 12/Dec/17 Work on class project.

Programming Assignments

Here's the link to mooshak.

Grading

The grading of this course is based on programming assignments, a final exam and a project. 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. The project is individual.

For the project component, you'll have to:

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.

Your project will be graded based on the quality of your writing, the proper design, application, and testing of EC techniques, the quality of your code, the clarity of your oral presentation, and the quality of the review.

The final grade will be computed as follows:

Deadlines and schedule for the class project

Tips for your project

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

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