AUTO3120 (Spring 2012)

Lecturer Timo Mantere

According the study guide:

- 5 study credits
- Requires some programming skills
- Will handle evolutionary computation and such algorithms as genetic programming, ant colony optimization, cultural algorithms etc., but we will also go through differential evolution and co-evolution, particle swarm optimization etc.
- Intensity course, 10h lectures + 20h project work
- Course will include examination(?) and project work

Spring 2012

Week 10: Thursday 14-17 TF4110 and Friday 9-12 TF4110

Week 11: Thursday 14-17 TF4104 and Friday 9-12 TF4110

Week 12: Thursday 14-17 TF4110 and Friday 9-12 TF4110

Week 13: Thursday 14-17 TF4104 and Friday 9-12 TF4110

Week 14: Tuesday 14-17 TF4104

Note, all 9 times in computer room, usually thursday is mainly lectures and friday mainly programming and exercises.

- Pre-filmed introduction lecture in finnish, this lecture is about genetic algorithms
- Lecture 1. Introduction to evolutionary algorithms (EA), basic principles and operation.
- Lecture 2. Differential evolution (DE), more principles, different problem types, constrained and multi-objective problems and EAs.
- Lecture 3. Cellular automata, swarm intelligence, cellular EAs, cultural algorithms, principle of co-evolution etc.
- Extra slides for lectures 1-3 These things I more or less draw in to the table, but they may not appear similarly in my own slides
- Lecture 4. Permutations, applications and examples, ways to modify EAs more fit to the problem, alternate fitness functions etc.
- Extra slides for lecture 4
- Lecture 5. Other EAs, GP, new variants, hybrids, genetic art etc. with Eiben and Smith slides chapters 4, 5, 6, 7, and 10.

Examination of this course will be held at wednesday 25.4.2012 9:15-12:15 in classroom F119

The re-examination will take place at the summer examinations, either 16.6. or 7.7. for those who needs study credits during the summer. THe examination area will be this Wikibook (pages 1-223) to which I tried to combine all the stuff from Wikipedia that relates to this course. You can also read the slides if you need more visual examples.

In the exercises we will program EAs with Java or Matlab, one can use other programming languages if feels so. Pre-programmed toolboxes are not used, except maybe in the last exercise.

- 1. Exercise, recab, we program binary genetic algorithm for Onemax problem. We will need a) population table b) binary crossover operation c) binary mutation operation d) fitness function e) sorting the population according the fitness value f) elitism operation g) favor the best when mating, we may also test our algorithm with and without Gray-code
- 2. Exercise, we program real-coded differential evolution algorithm for floating point Onemax, we need a) float/double-style popuation table, b) mixing vector c) calculating the differentials d) ways to handle value range crossings e) one against one tournament selection, we may also test different variants of DE. If we have time we could test our algorithm to different test functions like Rastrigin, Rosenbrock and Himmelblau (see Wikipedia)
- 3. Exercise, let's consider this time how to solve Sudoku's with Ant colony optimization. First, you need to think how to represent Sudoku, there are three conditions optimal solution must fulfill, each line must contain all integers {1,2,3,4,5,6,7,8,9} once and only once, the same applies to columns and 3x3 subgrids. You can fix one of them so that your will prevent violations. Sudoku may sound simple, but handling all the things conserned takes a quite a lot of considering and programming. The ACO is fairly simple, you have 9x9x9 pheremone matrix, where you update pheremones for the values appearing in the best solutions inversely proportionally to the fitness value. You have to consider also how the old pheremones will fade.
- Benchmark Sudoku problems are available here Note! Start from the easiest, the harder ones are very difficult for ACO to solve.
- You can hardcore Sudoku problem into your code first, and later add read class similar to this distance table reader
- CHALLENGE(home exercise): Those who have time might consider how to program cultural algorithm that solves Sudoku, basically it means you need GA that solves Sudoku, and collecting pheremones from the GA population, pheremone table is already a kind of belief space. Your belief space will then effect to the GA reproduction by inserting some new individuals to the population in ACO way. So, basically GA+ACO hybrid is already a simple cultural algorithm.
- 4. Exercise. Optimize FIR filters with GA and DE in Matlab. We program real-coded GA and DE with Matlab .m function and try to find best possible FIR filter (as close to ideal frequency response as possible).

FIR response is calculated with: b=fir1(N, wn, ga(j,2:52)); [h,w]=freqz(b,1,1000); where ga(j, x:xx) is the chromosome representin FIR coefficients and ga(j, 1) is the fitness value, N=FIR degree, wn=frequency window.

The end result can be compared to the ideal FIR filter Matlab gives you with the function firpm - At the end of exercise take a look and test of Ant colony based TSP solver Matlab code.
- At home you can take a look of Particle swarm toolbox and Genetic programming toolbox

- FirstGA.java
- BinaryGA.java other version of binary GA

- Some01.java
- DE.java DE class source, place in the same directory as Some01.java

- ACOsudo1.java version where numbers are drawn freely
- ACOsudo2.java version that forces all lines to have all integers {1, 2, ..., 9} once on and only once all the time

- GAFIR1.m GA version of FIR designer. There were some problems in class, but
**b**is what we want to find. - DEFIR1.m DE version of FIR designer.

Will add some possible project subjects soon

In the project work you should:

- 1. Choose some problem and get to know it throughly, this could be either some optimization problem or modelling some real-life system, or generating evolutionary art
- 2. Coose evolutionary algorithm that fits to your problem (e.g. GA works well with binary problems, DE with real number, ACO with route search, GB with function finding, PSO with multiobjective problems etc.) look Wikipedia pages for which kind of ploblems each method is good and for which not suited.
- 3. Model your problem for your algorithm, modelhow you code the search space and represent the solution vectors >li>4. Program EA and fitness function with some programming language (Java, C(+), Matlab, etc.)
- 5. Test and improve your algorithm, optimize parameters and operator
- 6. Report your algorithm, reasoning behind why you chooe to do previous steps as you did and your results, and xonclusions, what did you learn, what should be done differently if doing the whole thing again.

Links to the information about course subjects:

- Tutorial on evolutionary algorithms and the Matlab GA toolbox documentation
- Introduction to genetic algorithms
- Scholarpedia pages on evolutionary computation
- Wikipedia pages on evolutionary computation, evolutionary algorithms, genetic algorithms, genetic programming and interactive evolutionary computation

Some basic optimization problem types:

One main problem type is also linear problems, but there exists more efficients algorithms for them, therefore we do not try to optimize them in the projects.Many of the real-world optimization problems belongs to the groups above, or many of the groups, e.g. Sudoku is constrained combinatorial problem, but also integer problem, since the possible values are integers.

Evolutionary algorithms are used for basically eveything in the world, you can try by writing Google scholar some keywords evolutionary algorithms + something