Evolutionary Algorithms

The purpose of the course is to present a intelligible survey of available engineering problem solving techniques for those, who are not familiar with numerical optimization methods. The emphasis is put on creative thinking, namely on the ability to frame "real word problems", task decomposition, and adjusting representation to the most convenient form. First basic concepts are considered: importance of the model, the representation, the objective and the evaluation function. Then some classic algorithms for numerical optimization are reviewed.
Finally modern heuristic methods, for global search, such as simulated annealing, tabu search, controlled random search and evolutionary algorithms are presented. Considered algorithms are quite easy to understand and to implement for non-mathematicians with basic knowledge of programming.



Lecture contents

1. Introduction to optimization methods: modeling of the problem, size of the search space, objective and evaluation function, declaration of search problem, multiple criterion problems, neighborhood and local optima, dynamically changing environment.


2. Classic optimization methods: local search and hill climbing methods, nonlinear programming, stochastic optimization methods, simulation cost, convergence and quality of optimization algorithm, saddle point crossing.


3. Meta-heuristic methods of optimization: global optima search, simulated annealing, tabu search and controlled random search.


4. Evolutionary algorithms principles: random number generation, binary problem coding, simple genetic algorithm, traveling salesman problem (TSP), simulation of algorithm execution.


5. Evolutionary strategies and evolutionary programming: real number coding, strategy (1+1), strategy (?+?) and (?,?), evolutionary programming, genetic programming, evolving programs, tree coding.


6. Coding and variation operators: phenotype and genotype representation, vectors of symbols/numbers, permutations, finite state machines, symbolic expressions, mutation and perturbation (cross-over) operators.


7. Population management: initialization, reproduction, succession, explorative and exploitative behavior of algorithm


8. Constraints handling techniques: finding feasible solution, preserving feasibility of the solution, repair algorithms, penalization of infeasible individuals, maintaining population using special representation and variation operators, decoders,


9. Use of problem-specific heuristics.


10. Hybrid Algorithms: combination with local search, local search methods.


11. Learning classifier systems: evolving management and factory production systems.


12. Parallel processing in evolutionary computation: parallelization of evolutionary algorithm, island algorithm, diffusion models.


13. Tuning evolutionary algorithm: premature convergence, Baldwin effect, taxonomy of control techniques, parameters control, self adaptive algorithms.


14. Neural Networks: neurons and linear discriminated functions, multilayer perceptrons, back propagation, hybrid neural/evolutionary systems


15. Fuzzy Logic: fuzzy sets and probability measures, fuzzy operations and relationships, fuzzy TSP

1. Simple genetic algorithm (SGA): main framework, coding, operators, selection methods.


2. Application of SGA to traveling salesmen problem


3. Evolutionary strategy ES: optimization of multimodal objective function using (?+?) ES and (?,?) ES


4. Experiments with variation operators and population management.


5. Self adaptation and tuning of parameters of the evolutionary algorithm.


6. Hybrid evolutionary algorithm with local search.


7. Constrained optimization of multi-objective function

1. David E. Goldberg "Genetic Algorithms in Search, Optimization and Machine Learning", Addison-Wesley Publishing Co. 1989


2. Zbigniew Michalewicz "Genetic Algorithms + Data Structures = Evolution Programs", Springer-Verlag 1998


3. John Hertz ? "Introduction to the Theory of Neural Computation", Addison-Wesley Publishing Co. 1991


4. Zbigniew Michalewicz, David B. Fogel<i.>