| Course Unit Code | 460-4086/02 |
|---|
| Number of ECTS Credits Allocated | 4 ECTS credits |
|---|
| Type of Course Unit * | Optional |
|---|
| Level of Course Unit * | Second Cycle |
|---|
| Year of Study * | |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | English |
|---|
| Prerequisites and Co-Requisites | Course succeeds to compulsory courses of previous semester |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| SKA206 | doc. Ing. Lenka Skanderová, Ph.D. |
| Summary |
|---|
The subject is focused on the biologically inspired algorithms used for optimization. Students will learn about the advantages and disadvantages of these methods compared to mathematical methods. They will be capable of distinguishing between evolutionary, swarm, and local algorithms and apply these algorithms to solve selected optimization problems. The course emphasizes both the diversity of optimization problems and the diversity of biologically inspired optimization techniques that are suitable for solving these problems. Students will then use the theoretical knowledge acquired in the lectures to complete practical tasks in the exercises. The exercises, therefore, closely correspond to the lectures.
The aim of the course is to deepen the basic knowledge of the modern computational methods derived from evolutionary and biological processes. Graduates will learn the eminent optimization problems and solve them using biologically inspired algorithms. Within the subject, mathematical methods will be mentioned briefly. At the end of the course, a student will be capable of applying an appropriate method to solve a specific optimization problem. Graduates will be capable of distinguishing between global and local optimization. He/she will learn the multiobjective and combinatorial optimization. The large-scale optimization will be mentioned.
The graduate of the course will be able to:
- define an optimization problem,
- define evolutionary/swarm algorithm and local search algorithm,
- distinguish among evolutionary algorithms,
- distinguish among evolutionary algorithms,
- solve optimization problem using a suitable biologically inspired algorithm, or choose a mathematical method,
- identify problem-dependent variables and set them correctly in connection with the special problem,
- suggest an appropriate method to speed up the optimization process. |
| Learning Outcomes of the Course Unit |
|---|
The aim of the course is to deepen the basic knowledge of the modern computational methods derived from evolutionary and biological processes. Graduates will learn the eminent optimization problems and solve them using biologically inspired algorithms. Within the subject, mathematical methods will be mentioned briefly. At the end of the course, a student will be capable of applying an appropriate method to solve a specific optimization problem. Graduates will be capable of distinguishing between global and local optimization. He/she will learn the multiobjective and combinatorial optimization. The large-scale optimization will be mentioned.
The graduate of the course will be able to:
- define an optimization problem,
- define evolutionary/swarm algorithm and local search algorithm,
- distinguish among evolutionary algorithms,
- distinguish among evolutionary algorithms,
- solve optimization problem using a suitable biologically inspired algorithm, or choose a mathematical method,
- identify problem-dependent variables and set them correctly in connection with the special problem,
- suggest an appropriate method to speed up the optimization process.
|
| Course Contents |
|---|
Lectures:
- A brief introduction to the history of evolutionary algorithms and metaheuristics. Classification of metaheuristics based on their principle. Types of optimization problems (global, combinatorial, and multi-objective optimization). Objective function, constraints. Space of feasible solutions. Basic terminology.
- Local search algorithms: Hill climbing, tabu search, simulated annealing. Getting stuck in a local extreme and the methods of solution.
- Differential evolution: principle and its use in global optimization. Current variants of differential evolution and their application in real-world optimization tasks. Trends for improving the basic algorithms.
- Particle swarm and Self-Organizing Migration Algorithm (SOMA) and their current variants. Trends for improving basic algorithms.
- Combinatorial optimization: Knapsack, Traveling salesman problem, Vehicle routing problem. Solving selected problems using genetic algorithms.
- Combinatorial optimization and Ant colony optimization.
- Multi-objective optimization, Pareto set, Pareto frontier. NSGA II algorithm and its current variants.
- Optimization with constraints. Soft vs. hard constraints. Methods of the evaluation of the individual within the population. Nurse scheduling problem. Use of biologically inspired algorithms to solve selected problems.
- Evolutionary strategy: basic principle. Evolutionary strategy using covariance matrix (CMA-ES) in optimization with constraints.
- Dynamic optimization with constraints. Use of biologically inspired algorithms vs. other optimization methods.
- Optimization of problems with a high number of dimensions (large-scale optimization). The curse of dimensionality.
- Parallelization of biologically inspired algorithms.
- Comparing the algorithms from the perspective of their efficiency (statistical comparison of algorithms). No free lunch theorem.
Exercises (in PC classroom):
- Global optimization, selected problems. Common basis for biologically inspired algorithms. Individual, popupation, generation. Ways of the algorithm termination.
- Hill Climbing, Tabu Search, Simmulated annealing for the global optimization. The role of the normal and uniform distribution within the biologically inspired algorithms.
- Differential evolution and its enhanced versions applied on the global optimization problems.
- Particle Swarm Optimization algorithm and Self-organizing migrating algorithm (SOMA) and their application on the global optimization problems.
- Gennetic algorithm and combinatorial optimization ( Knapsack, Traveling Salesman Problem, Vehicle Routing Problem).
- Ant Colony Optimization and its application of the combinatorial optimization problems.
- Multiobjective optimization, NSGA II.
- Constrained optimization and biologically inspired algorithms. Nurse schedulling problem.
- CMA-ES and the constrained optmization.
- Dynamical optimization with constraints - application of the selected algorithms (differential evolution, SOMA) on the selected problems.
- Large scale optimization and the role of the biologically inspired algorithms.
- Parallelization of the biologically inspired algorithms.
- Statistical comparison of the biologically inspired algorithms. |
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
[1] Scardua, L. A. (2021). Applied evolutionary algorithms for engineers using python. CRC Press.
[2] Moriarity, Sean. "Genetic Algorithms in Elixir: Solve Problems Using Evolution." (2021): 1-230.
[3] Kochenderfer, M. J., & Wheeler, T. A. (2019). Algorithms for optimization. Mit Press.
[4] Abualigah, L. (Ed.). (2024). Metaheuristic Optimization Algorithms: optimizers, analysis, and applications. Elsevier. |
[1] Scardua, L. A. (2021). Applied evolutionary algorithms for engineers using python. CRC Press.
[2] Moriarity, Sean. "Genetic Algorithms in Elixir: Solve Problems Using Evolution." (2021): 1-230.
[3] Kochenderfer, M. J., & Wheeler, T. A. (2019). Algorithms for optimization. Mit Press.
[4] Abualigah, L. (Ed.). (2024). Metaheuristic Optimization Algorithms: optimizers, analysis, and applications. Elsevier.
|
| Recommended Reading: |
|---|
[1] Zelinka I., Oplatková Z., Šeda M., Ošmera P., Včelař F., Evoluční výpočetní
techniky, principy a aplikace, BEN, 2008, Praha
[2] Kvasnička V., Pospíchal J., Tiňo P., Evolučné algoritmy, STU Bralislava, ISBN
80-227-1377-5, 2000
3. Zelinka I., Včelař F., Čandík M., Fraktální geometrie – principy a aplikace, BEN, 2006, 160 p., ISBN 80-7300-191-8
[3] Back, T., Fogel, B., Michalewicz, Z.: Handbook of Evolutionary Computation, Institute of Physics, London
[4] Davis L. 1996, Handbook of Genetic Algorithms, International Thomson Computer Press, ISBN 1850328250 |
[1] Zelinka I., Oplatková Z., Šeda M., Ošmera P., Včelař F., Evoluční výpočetní
techniky, principy a aplikace, BEN, 2008, Praha
[2] Kvasnička V., Pospíchal J., Tiňo P., Evolučné algoritmy, STU Bralislava, ISBN
80-227-1377-5, 2000
3. Zelinka I., Včelař F., Čandík M., Fraktální geometrie – principy a aplikace, BEN, 2006, 160 p., ISBN 80-7300-191-8
[3] Back, T., Fogel, B., Michalewicz, Z.: Handbook of Evolutionary Computation, Institute of Physics, London
[4] Davis L. 1996, Handbook of Genetic Algorithms, International Thomson Computer Press, ISBN 1850328250
|
| Planned learning activities and teaching methods |
|---|
| Lectures, Tutorials |
| Assesment methods and criteria |
|---|
| Tasks are not Defined |