2110742 Evolutionary Computation 2010

Prabhas Chongstitvatana

Office: Engineering Building 4, floor 18, room 13
phone: 02-2186982
email: prabhas at chula dot ac dot th
class webpage: http://www.cp.eng.chula.ac.th/faculty/pjw/

Class meeting: Tue/Thurs 9:00-10:30, Eng Bld 4, floor 17 room 01 (behind the xerox room).

This class discusses evolutionary computation in all aspects. Many established topics in this field will be studied: Genetic algorithms, Genetic programming, Evolution strategies. Advanced topics such as Estimation of distribution algorithms and multiple objective optimisation are included. Theory as well as practical aspects are emphasized.

How the class is conducted?

Because the nature of the topics is the study of algorithms, it renders itself suitable for experimentation. Weekly assignment requires students to run the experiment based on the algorithm in the lecture. It is a graduate class, so students are expected to do a lot of self-study. Individual studies are designed to let students study a specific topic in depth. The results are presented in the group discussion as well as submission of written reports.

Announcement

16 Nov 2010    No class on 18 Nov 2010, I will be at NCSEC Chiangmai for steering committee meeting
25 Nov 2010    No class on 2 Dec 2010, I will give a invited talk at EECON. (my paper is related to EC here) (reference. see year 2010)

Previous lectures 2008 2006   2005 2003 2000

Weekly lecture

1 Genetic algorithms (Whitley tutorial on GA)    Intro to GA
2 Theoretical basis   GA implementation
3 Probabilistic algorithms
4 Genetic programming read from http://www.genetic-programming.org/    GP in design
5 Evolution strategies slides: one two three four five six
6 Estimation of distribution algorithms (Pelikan slides)
7 EDA 2 Baluja, Population-based incremental learning, CMU CS-94-163, 1994
8 Multiple objective optimisation Deb, NSGA II ieee-trans-ec 2002
9-10 Discussion of the recent topic in EC
11 Summary

Supplementary materials

Genetic Operators

(from students' homework)
Single point crossover, uniform, arithmetic crossover <pravit_5370532721.pdf>
Selection <pattarasri_geneticop.pdf>
General <suppat_Genetic_Operators_5370368121.pdf>
Stochastic universal sampling, rank selection <sura_Selection_methods.pdf>
Crossover: cut and splice; inversion <suwat_homework_5370375521.pdf>
General <warisa.pdf>
tournament selection <yutana_genetic_operators.pdf>
Recombination permutation-based: PMX, OCX, CX, real value recombination <thiti_5271806821_EVO1.pdf>

Solving n-queen by genetic algorithms

(from students' homework)
n-queen with C code and comparison with Probabilistic algorithm <pravit-8queen.pdf>
8-queen with galib (very short because use library) <Sura-8queen.pdf>
8-queen with uniform crossover <Thiti-8queen.pdf>
8-queen explanation <warisa_queen.pdf>
Result of the experiment 8-queen GA (convergence rate) <yutana-8queen.pdf>

Application of Genetic Programming

(from students' homework)
Linear Genetic Programming <suwat_linear_gp.pdf> (I need a full reference)
Genetic Programming to play Snake game <Sura_gp_snake.pdf> (I need a full reference)

Homework

1 Read about various kinds of genetic operators: recombination, inversion, selection. Prepare 2-3 pages summary and prepare to present it to the class.
2 Run a version of GA to solve 8-queen problem. You can write, use some package, modify code from any source. Please submit your homework in pdf file explaining what you have done, and a bit of the result of your experiment. If you cannot or not comfortable writing a program, just write down a kind of "pseudo code" of GA to solve it. You can read about 8-queen here. 8-queen code the 92 solutions
3 Find an application of Genetic Programming. Prepare to present it to the class for 5 minutes.

Individual study

1. Compare Linear Genome GP with similar scheme, including GP.
2. Compare Bibliographic Optimization with ES and similar scheme.
Select your algorithm. Choose some benchmarks. Run it, compare and discuss the result. Write a short report. Prepare to present your finding in 5 minutes.

External references

Applet (animation) for GA

http://www.rennard.org/alife/english/gavgb.html

Genetic Algorithm Viewer 1.0 is a demonstration applet of the functioning of a Genetic Algorithm (GA). It aims at showing the power of GA and of the main mechanisms used while permitting a certain form of visualization of the general functioning.
http://www.ads.tuwien.ac.at/raidl/tspga/TSPGA.html
Visualisation of Genetic Algorithms for the Traveling Salesman Problem in Java
http://www.stellaralchemy.com/ice/
The applet executes what is called a genetic algorithm (GA). To facilitate understanding, every step in the GA is animated. This particular GA evolves solutions to a simple board game. This program also detects and reports if any irreducibly complex (IC) solutions arise during the evolution of its population of solutions to the board game.
http://www.obitko.com/tutorials/genetic-algorithms/example-function-minimum.php
Minimum of Function: The problem is expressed as looking for extreme of a function. Some function is given and GA tries to find minimum of the function. For other problems we just have to define search space and the fitness function which means to define the function, which we want to find extreme for.

Assessment

homework 20
individual study 30
final exam 50

Text

1. Mitchell, M., An introduction to genetic algorithms, MIT press, 1996.
2. Goldberg, D., The design of innovation, Kluwer pub, 2002.
3. Holland, J. H., Adaptation in natural and artificial systems, MIT press, 1992.
4. Koza, J., "Genetic Programming Vol 1, 2, 3", MIT Press, 1992, 1994, 1999.
5. Goldberg, D., Genetic algorithms, Addison-Wesley, 1989.
6. Banzhaf, W., Nordin, P., Keller, R. and Francone, F., Genetic Programming: An Introduction, Morgan Kaufmann, 1998.
6. Winter, G., Periaux, J., Galan, M., Cuesta, P. (eds), Genetic algorithms in engineering and computer science, John Wiley, 1995.

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

Tools

devcpp (please visit the original site)
galib247.zip
myga example
8-queen code in C

last update 4 Jan 2011