Evolutionary Computation

2110742 Evolutionary Computation

Prabhas Chongstitvatana (email me)

Time: Mon 13:00-14:30, Thurs 13:00-14:30
Room: meeting room, floor 20, Eng. building 4.

Previous lecture (2000)

What's new

    26 Jan 2004    Paper: No Free Lunch Theorem
                           Application:   GA experiment One-max   (executable file by Nathee)
    20 Feb 2004   GA experiment (the missing files ) : ex1   gp373w32

Outline

Evolutionary Computation is an approach to computation that emphasize on a general-purpose search algorithm that use principles inspired by population genetics to evolve solutions to problems. Two most well-known methods are Genetic Algorithm (GA) and Genetic Programming (GP). GA and GP has become increasingly popular in recent years as a method for solving complex search problems in a large number of disciplines. This course will illustrate the basic concept of GA/GP and their current applications. The topics include Evolutionary Strategies (ES), the method of real-value optimization, and Classifier System (CFS), one of the most advanced study in Complex Adaptive System (CAS).

The content of the course will be a mixture of mathematical material and up-to-date research materials. The lecture will be mainly the foundation of the subject. Students are expected to do a number of self-study on to answer the questions posted weekly. Those questions concern the subject at a deeper level.

Weekly schedule

Introduction to Evolutionary Computation
Simple Genetic Algorithms
Foudation of Genetic Algorithms : Schemata Theory
Genetic Algorithms as Search in Hyperplane, k-arm bandit
Niching and other genetic operators
Genetic Algorithms Applications
Genetic Programming
Some examples of solving problems by GP
Schemata theorem for GP
Classifier systems
Evolutionary strategy
Social Intelligence
Multiple objectives optimisation
Current issues in GA/GP

Assesment

theory: written exam, mid/final 25/25
appliations: class discussion 25
practical: project 25
homework every week, no score (each takes 3-5 hours)

Text

Goldberg, D., Genetic algorithms, Addison-Wesley, 1989.
Holland, J. H., Adaptation in natural and artificial systems, MIT press, 1992.
Vose, M., The simple genetic algorithm: foundation and theory, MIT press, 1999.
Winter, G., Periaux, J., Galan, M., Cuesta, P. (eds), Genetic algorithms in engineering and computer science, John Wiley, 1995.
Mitchell, M., An introduction to genetic algorithms, MIT press, 1996.
Koza, J., "Genetic Programming Vol 1, 2, 3", MIT Presss, 1992, 1994, 1999.

Uptodate handouts on various current researches will be distributed in the class.

Resources

Artificial life
Some tutorial material : Introduction to Evolutionary Computation (slide) (full text) from my talk at NCSEC 1999.
FAQ from comp.ai.genetic A comprehensive writing of the field as a whole (more than 100 pages) download zip file for offline reading (151K) (a little dated)
Whitley, A Genetic Algorithm Tutorial, Colorado State U., a more mathematical exposure to GA. (ps file 37 pages)
GP source code in C (zip )

Assignments

1 Dec 2003 Select a paper on GA application from conference proceedings, write a summary for it.
12 Jan 2004 Try the GA experiment, varying parameters of the one-max problem, answer the question: What is the relation ship between problem-size, population-size and convergence rate?
20 Feb 2004 GA experiment (the missing files ) : ex1 gp373w32
26 Jan 2004 Read the NFL paper

last update 20 Feb 2004
P. Chongstitvatana