Evolutionary Optimization Algorithms

Lecturer:

Petr Pošík, Jiří Kubalík (gar.)

Tutor:

Petr Pošík, Jiří Kubalík (gar.)

Supervisor:

Department of Cybernetics

Synopsis:

The students will get acquainted with various forms of evolutionary algorithms -- optimization metaheuristics that use analogies with natural evolution to solve complex optimization tasks. The subject builds on and extends knowledge from the subject Bio-inspired algorithms. The main goal of this subject is to introduce various forms of evolutionary algorithms along with suitable application areas. In the seminar and lab lectures, the students will get hands-on tutorials and will be obliged to implement their own evolutionary algorithm to solve an optimization task as part of their project.

Requirements:

Basic knowledge of evolutionary algorithms (A4M33BIA)

Syllabus of lectures:

1. Standard evolutionary algorithms (EAs). A relation of EAs to the classical optimization techniques.

2. No-Free-Lunch theorem. Evaluation EAs performance.

3. Working with constraints -- special representation, penalization, decoders and repairing algorithms, multiobjective approach.

4. EA's control parameters -- tuning and adaptation.

5. Statistical dependence of solution components. Perturbation methods.

6. Estimation of distribution algorithms (EDA).

7. Evolutionary strategy with covariance matrix adaptation.

8. Parallel EAs.

9. Genetic programming (GP) -- representation, initialization, genetic operators, typed GP, automatically defined functions.

10. Grammatical evolution, gene expression programming.

11. Linear genetic programming, graph-based genetic programming.

12. GP issues -- 'bloat', diversity preservation.

13. Coevolution.

14.

Syllabus of tutorials:

1. Implementation of simple genetic algorithm (SGA). Influence of individual parameter values.

2. Analysis of the topics for the seminar project.

3. Seminar project elaboration. Part I - local optimization algorithm.

4. Seminar project elaboration. Part I - local optimization algorithm.

5. Hand-in of the seminar project I.

6. Seminar project elaboration. Part II - a simple EA vs. specialized EA or memetic algorithm.

7. Seminar project elaboration. Part II - a simple EA vs. specialized EA or memetic algorithm.

8. Seminar project elaboration. Part II - a simple EA vs. specialized EA or memetic algorithm.

9. Successful applications of EAs.

10. Seminar project elaboration. Part II - a simple EA vs. specialized EA or memetic algorithm.

11. Hand-in of the seminar project and presentations of the results.

12. Test.

13. Hand-in of the seminar project and presentations of the results.

14.

Study Objective:

The main goal of this subject is to introduce several forms of evolutionary optimization algorithms in detail along with suitable application areas. The emphasis is given to problems encountered when applying the evolutionary algorithms, and on the methods usable to overcome them.

Study materials:

- Luke, S.: Essentials of Metaheuristics, 2009

http://cs.gmu.edu/~sean/book/metaheuristics/

- Poli, R., Langdon, W., McPhee, N.F.: A Field Guide to Genetic Programming, 2008

http://www.gp-field-guide.org.uk/

Note:

Time-table for winter semester 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon	roomKN:E-126 Kubalík J. Pošík P. 16:15–17:45 (lecture parallel1) Karlovo nám. Trnkova posluchárna K5roomKN:E-220 Kubalík J. Pošík P. 18:00–19:30 (lecture parallel1 parallel nr.101) Karlovo nám. Laboratoř BIO
Tue
Fri
Thu
Fri

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans: