2110742 Evolutionary Computation 2012
Office: Engineering Building 4, floor 18,
email: prabhas at chula dot ac dot th
class webpage: http://www.cp.eng.chula.ac.th/faculty/pjw/
Class meeting: Thurs 11:00-12:30, Eng Bld 4206, Fri
10:00-11:30pm, meeting room pink Eng Bld 4, Floor 17.
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.
11 Jan 2013 Project is announced (it is counted as individual study).
23 Feb 2013 Final exam question is here.
Due date 1 March 2013, 4pm.
Previous lectures 2010
1 Genetic algorithms (Whitley
tutorial on GA) Intro to GA
2 Theoretical basis GA
3 Probabilistic algorithms
4 Genetic programming read from http://www.genetic-programming.org/
GP in design
5 Evolution strategies slides: one
6 Estimation of distribution algorithms (Pelikan
7 EDA 2 Baluja, Population-based
incremental learning, CMU CS-94-163, 1994
8 Multiple objective optimisation Deb,
NSGA II ieee-trans-ec 2002 slides Multiobjective
, Differential Evolution
9-11 Discussion of the recent topic in EC
Differential Evolution wiki
(paper local copy)
Particle Swarm Optimization (PSO) wiki
Ant colony optimization
No Free Lunch theorem
wiki (paper local copy )
Coevolution ( in nature wiki
) cooperative coevolutionary algorithms (
local copy pdf )
1) Georges R. Harik, Fernando G. Lobo, and David E. Goldberg, "The
Compact Genetic Algorithm," IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION,
VOL. 3, NO. 4, NOVEMBER 1999. (full
3) Wattanapornprom, W., Olanviwitchai, P., Chutima, P. and
Chongstitvatana, P., "Multi-objective Combinatorial Optimisation with
Coincidence Algorithm," IEEE Congress on Evolutionary Computation, Norway,
May 18-21, 2009. (
full text )
4) An easier read on COIN description : Chongstitvatana,
P., Wattanapornprom, W., Olanviwitchai, P., Sirovetnukul, R.,
Kampirom N., and Chutima, P., "Coincidence Algorithm for
Combinatorial Optimisation and Its Applications," (invited paper),
Proc. of Electrical Engineering Conference (33th), Chiangmai, Thailand,
1-3 Dec. 2010. (
full text )
5) A tutorial on
multiobjective evolutionary optimization, Zitzler (pdf)
6) Storn, R.; Price, K. (1997). "Differential evolution - a simple and
efficient heuristic for global optimization over continuous spaces". Journal
of Global Optimization 11: 341–359. (local
7) Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for
Optimization," IEEE Transactions on Evolutionary Computation 1, 67. ( local
8) R. Paul Wiegand, An Analysis of Cooperative Coevolutionary
Algorithms, PhD thesis, Department of Computer Science, George Mason
University, 2003. ( local copy pdf
9) Omidvar, M.N., Xiaodong Li, Zhenyu Yang, Xin Yao,
"Cooperative Co-evolution for large scale optimization through more frequent
random grouping," IEEE Congress onEvolutionary Computation (CEC), 18-23 July
2010, pp.1-8. ( local copy )
10) Zhenyu Yang, Ke Tang, Xin Yao, "Large scale evolutionary
optimization using cooperative coevolution," Information Sciences 178 (2008)
2985–2999. (local copy)
11) Das, S., "Differential Evolution: A Survey of the
State-of-the-Art," IEEE Trans on Evolutionary Computation, vol 15, issue 1,
Feb. 2011, pp.4-31. (local copy)
12) Manuel Lopez-Ibanez, T. Devi Prasad, Ben Paechter,
"Representations and Evolutionary Operators for the Scheduling of Pump
Operations in Water Distribution Networks," Evolutionary Computation 19(3):
429–467. (local copy)
1 Try your hands on solving TSP with GA. Go to this site. It is
Java (applet) based. http://www.ads.tuwien.ac.at/raidl/tspga/TSPGA.html
2 Find out what kind GA recombination operator work for TSP problems?
3 Implement and run compact GA on 6xtrap-5 (30 bits) problem. Discuss
divergence, parameters setting issues
4 Read NSGA II, prepare to discuss this algorithm.
5 Read No Free Lunch paper (the first few pages) and prepare to discuss how
the authors proof their theory.
6 Read Cooperative Coevolutionary Algorithm, prepare to discuss how a normal
EC be changed into a Coevolve one.
7 Prepare a presentation of applications of EC for next week class.
Try using EC or inventing (or mixing up) algorithms of your own, to solve
the flowshop problems. Using this reference to compare your method
with. You don't have to implement your own program. Use any available
method to do it. Warning, the benchmarks are tough to beat. I will
give more details about which data set we will use later. Do your
best. You must write around 4-5 pages of English report about your
experiment. Here is the reference:
Quan-Ke Pan, Ruben Ruiz, "Local search methods for the flowshop scheduling
problem with flowtime minimization," European Journal of Operational
Research, 222 (2012) 31-43. (
Applet (animation) for GA
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.
Visualisation of Genetic Algorithms for the Traveling Salesman Problem in
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.
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
Source code for Differential Evolution (from Storn) http://www1.icsi.berkeley.edu/~storn/code.html
individual study 30
final exam 50
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,
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
I have mentioned Heuristic
Lab as a good tool. Try it.
last update 23 Feb 2013