Course detail
Evolution Algorithms
FEKT-MPC-EALAcad. year: 2022/2023
The course is focused on deterministic and stochastic optimization methods for finding global minima. It focuses on evolutionary algorithms with populations such as genetic algorithms, controlled random search, evolutionary strategies, particle swarm method, the method of ant colonies and more.
Language of instruction
Czech
Number of ECTS credits
4
Mode of study
Not applicable.
Guarantor
Learning outcomes of the course unit
The graduate of the course is capable of:
Implement a simple analytical optimization method (steepest descent and Newton's method)
To implement the simplex method for finding global extreme
Explain the nature of stochastic optimization methods with populations
Explain the nature of binary and continuous genetic algorithms and the basic operations
Implement a simple analytical optimization method (steepest descent and Newton's method)
To implement the simplex method for finding global extreme
Explain the nature of stochastic optimization methods with populations
Explain the nature of binary and continuous genetic algorithms and the basic operations
Prerequisites
The knowledge on the Bachelor´s degree level is requested, namely on numerical mathematics. The laboratory work is expected knowledge of Matlab programming environment.
Co-requisites
Not applicable.
Planned learning activities and teaching methods
Teaching methods include lectures and computer laboratories. Course is taking advantage of e-learning system. Students have to write a single project/assignment during the course.
Assesment methods and criteria linked to learning outcomes
Requirements for completion of a course are specified by a regulation issued by the lecturer responsible for the course and updated for every year.
- 30 points can be obtained for activity in the laboratory exercises, consisting in solving tasks (for the procedure for the examination must be obtained at least 15 points)
- 70 points can be obtained for the written exam (the written examination is necessary to obtain at least 35 points)
- 30 points can be obtained for activity in the laboratory exercises, consisting in solving tasks (for the procedure for the examination must be obtained at least 15 points)
- 70 points can be obtained for the written exam (the written examination is necessary to obtain at least 35 points)
Course curriculum
1. Optimization based on mathematical analysis, optimality conditions, gradient, Hessian.
2. Method of steepest descent, Newton's method.
3. Stochastic algorithms for finding global minima, the simplex method.
4. Evolutionary algorithms with populations. Binary genetic algorithms.
5. Continuous genetic algorithms.
6. Controlled random search, evolutionary strategies, particle swarm.
7. Differential evolution, SOMA, ant colony.
8. Swarm algothms: BAT, FA, GSO.
9. Swarm algothms: GWO, BA, ABC.
10. Test function for checking optimization algorithms.
11. Experimental comparison of evolutionary algorithms.
12. Introduction to genetic programming.
2. Method of steepest descent, Newton's method.
3. Stochastic algorithms for finding global minima, the simplex method.
4. Evolutionary algorithms with populations. Binary genetic algorithms.
5. Continuous genetic algorithms.
6. Controlled random search, evolutionary strategies, particle swarm.
7. Differential evolution, SOMA, ant colony.
8. Swarm algothms: BAT, FA, GSO.
9. Swarm algothms: GWO, BA, ABC.
10. Test function for checking optimization algorithms.
11. Experimental comparison of evolutionary algorithms.
12. Introduction to genetic programming.
Work placements
Not applicable.
Aims
Obtaining an understanding about deterministic and stochastic optimization methods. Introduction to the evolutionary algorithms with populations for finding the global extremes multidimensional functions. Introduction to the genetic programming.
Specification of controlled education, way of implementation and compensation for absences
Delimitation of controlled teaching and its procedures are specified by a regulation issued by the lecturer responsible for the course and updated for every year (see Rozvrhové jednotky).
Basically:
- obligatory computer-lab tutorial (missed labs must be properly excused and can be replaced after agreement with the teacher)
- voluntary lecture
Basically:
- obligatory computer-lab tutorial (missed labs must be properly excused and can be replaced after agreement with the teacher)
- voluntary lecture
Recommended optional programme components
Not applicable.
Prerequisites and corequisites
Not applicable.
Basic literature
Tvrdík, J.: Evoluční algoritmy. Skripta, Přírodovědecká fakulta Ostravské univerzity, 2004 (CS)
Recommended reading
Hynek, J.: Genetické algoritmy a genetické programování. Grada Publishing, 2008 (CS)
Classification of course in study plans
- Programme MPC-BTB Master's 2 year of study, winter semester, compulsory
Type of course unit
Lecture
20 hod., optionally
Teacher / Lecturer
Syllabus
1. Optimization based on mathematical analysis, optimality conditions, gradient, Hessian
2. Method of steepest descent, Newton's method
3. Stochastic algorithms for finding global minima, the simplex method
4. Evolutionary algorithms with populations. Binary genetic algorithms.
5. Continuous genetic algorithms.
6. Controlled random search, evolutionary strategies, particle swarm
7. Differential evolution, SOMA, ant colony
8. contestants heuristics
9. Test function for checking optimization algorithms
10. Simple methods: climbing algorithm, prohibited search, simulated annealing
11. Experimental comparison of evolutionary algorithms
12. Introduction to genetic programming
2. Method of steepest descent, Newton's method
3. Stochastic algorithms for finding global minima, the simplex method
4. Evolutionary algorithms with populations. Binary genetic algorithms.
5. Continuous genetic algorithms.
6. Controlled random search, evolutionary strategies, particle swarm
7. Differential evolution, SOMA, ant colony
8. contestants heuristics
9. Test function for checking optimization algorithms
10. Simple methods: climbing algorithm, prohibited search, simulated annealing
11. Experimental comparison of evolutionary algorithms
12. Introduction to genetic programming
Exercise in computer lab
26 hod., compulsory
Teacher / Lecturer
Syllabus
1. Analytical method for finding the local minima.
2. Newton method
3. Nelder-Mead method (simplex method).
4. Binary genetic algorithm (GA). Basic selection, crossover and mutation techniques.
5. GA for finding minima in 2D case. Two point crossover method, roulette-wheel selection.
6. Continuous GA. Differences between binary and continuous GA.
7. Application of GA for rigid image registration.
8. Travel salesman problem (TSP). Basic heuristic algorithms - nearest neighboor algorithm, Greedy algorithm.
9. Permutation GA for solving the TSP.
10. Introduction to Particle swarm optimization (PSO) methods. Ant colony optimization for solving the TSP.
11. Student project - implementation of 0-1 knapsack problem or Packing problem.
12. PSO for finding minima of 2D function.
2. Newton method
3. Nelder-Mead method (simplex method).
4. Binary genetic algorithm (GA). Basic selection, crossover and mutation techniques.
5. GA for finding minima in 2D case. Two point crossover method, roulette-wheel selection.
6. Continuous GA. Differences between binary and continuous GA.
7. Application of GA for rigid image registration.
8. Travel salesman problem (TSP). Basic heuristic algorithms - nearest neighboor algorithm, Greedy algorithm.
9. Permutation GA for solving the TSP.
10. Introduction to Particle swarm optimization (PSO) methods. Ant colony optimization for solving the TSP.
11. Student project - implementation of 0-1 knapsack problem or Packing problem.
12. PSO for finding minima of 2D function.