2110793 Advanced Topic in Digital Systems
2018
Prabhas Chongstitvatana
Office: Engineering Building 4, floor 18,
room 13
phone: 02-2186982
email: prabhas at chula dot ac dot th
Class meeting: Thurs 9:30-11:00, Eng 100/403, Fri
9:30-11:00, Eng 4, 20-2.
This semester we will discuss Evolutionary Computation. 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.
Previous lectures on ADV
2017
Announcement
Final exam is on 7 May 2018, 13:00, at room floor 20, Eng building 3.
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 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
wiki
No Free Lunch theorem
wiki (paper local copy )
Coevolution ( in nature wiki
) cooperative coevolutionary algorithms (
local copy pdf )
12 Summary
Supplementary materials
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
text)
2)
COIN
homepage
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
copy)
7) Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for
Optimization," IEEE Transactions on Evolutionary Computation 1, 67. ( local
copy )
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)
13) Flowshop problems: 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. (
local copy )
14) K. Suksen and P. Chongstitvatana, "Exploiting
Building Blocks in Hard Problems with Modified Compact Genetic
Algorithm," (draft) 2018
15) Yann Dujardin, Iadine Chadès, "Solving multi-objective optimization
problems in conservation with the reference point method," PLoS ONE 13(1):
e0190748. https://doi.org/10.1371/journal.pone.0190748 (local
copy)
Homework
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 What kind of operators are suitable for TSP ?
. . .
Project
Think of an interesting multi-objective Combinatorial Optimization
problem. Use COIN to solve it. The first step to solve the problem is
how to map the instant of solutions to be suitable for COIN. Supawadee
has written a prototype TSP-COIN (a kind of golden model for COIN
written in C). It is COIN that solves TSP problem. It is all in one
file. The input "input15.txt" (and input26.txt) is an example.
You can use it to check the correctness your implementation of COIN. You can
compile (tspcoin.c) and run it. The output is like this:
C:\temp\TSP-COIN>tsp
The algorithm found optimal solution, terminate in gen 15!!!
The best result is 291
traverse : 13 1 11 4 6 8 10 14 12 3 7 5 9 15 2
You must deliver the following:
1) a running program that solve your problem
2) present your project (8 minutes max)
3) a short report describing your project and method.
Here is the TSP-COIN (tsp-coin.zip)
...
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.
Source code for Differential Evolution (from Storn)
http://www1.icsi.berkeley.edu/~storn/code.html
Assessment
homework 30
individual study 30 (final project)
final exam 40
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
galib247.zip
myga example
last update 7 May 2018