HEURISTICS AND METAHEURISTICS FOR OPTIMIZATION AND LEARNING
Academic Year 2023/2024 - Teacher: MARIO FRANCESCO PAVONEExpected Learning Outcomes
The aims of the course are focused on the design and develop of algorithms, included also the ones that take inspiration from nature and biology, as well as the key features required for developing a successful algorithm. All investigated algorithms will be analysed and applied in the following application fields: optimization; anomaly detection; decision theory; and game theory.
The goal of the course is to provide to each student:
1) good knowledge on the basic concepts;
2) good knowledge on the "intelligent systems" and their designing;
3) excellent ability in developing an efficient bio-, or nature-inspired algorithm;
4) problem-solving.
Course Structure
Classroom-taught lessons. Can be also included external seminars held by expert researchers on related topics.
Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Learning assessment may also be carried out on line, should the conditions require it.
Required Prerequisites
Attendance of Lessons
Detailed Course Content
- An introduction to Computational Theory and NP-complete problems
- An introduction to the base concepts in Machine Learning and Computational Learning Theory
- Landscape, Search Space and Optimization models
- Unconstrained optimization; constrained optimization; multiobjective optimization
- Optimization methods:
Algoritmi Greedy Metodi Esatti: dynamic programming; A*; branch & bound algorithm; constraint programming Meta-euristiche a singola soluzione: local search; tabu search; iterated local search; simulated annealing; guided local search; and GRASP Meta-euristiche basate su popolazione: concetti base
- Metaheuristics population based:
- Genetic Algorithms and Genetic Programming;
- Artificial Immune Systems;
- Swarm Intelligence: Particle Swarm Optimization, Ant Colony Optimization, Artificial Bee Colony
- Differential Evolution
- Hybird metaheuristics
- Parallel metaheuristics
- Multiobjective optimization evolutionary algorithms (MOEA)
- Metaheuristics in Decision Making
- Machine learning & Metaheuristics
- Examples of bio-inspired algorithms application in: Network Sciences; Games; Internet of Things; Computer Security; Robotics; Art and Design.
Textbook Information
- E.G. Talbi, "Metaheuristics: From Design to Implementation", Wiley, 2009
- C. Blum and G.R. Raidl, "Hybrid Metaheuristics: Powerful Tools for Optimization", Artificial Intelligence: Foundations, Theory, and Algorithms, 2016
- Slides.
Course Planning
| Subjects | Text References | |
|---|---|---|
| 1 | Introduzione alle Teoria della Computabilità: problemi NP-Completi | T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009 (chapter 34) |
| 2 | Introduzione a concetti di Machine Learning e Computational Learning Theory | E. Alpaydin, “Introduction to Machine Learning”, MIT Press, 2014 - Kearns, Vazirani, "An Introduction to Computational Learning Theory", MIT Press 1994 |
| 3 | Landscape e Search Space: topologie, significato e importanza | Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 - Blum & Raidl, ''Hybrid Metaheuristics: Powerful Tools for Optimization'', A.I.: Foundations, Theory, & Algorithms, 2016 + materiale fornito dal docente |
| 4 | Modelli per l’ottimizzazione: (i) Single-Objective Optimization; (ii) Constrained Optimization; (iii) Multi-Objective Optimization; (iv) Optimization under Uncertainty; (v) Dynamic Optimization | Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 - Blum & Raidl, ''Hybrid Metaheuristics: Powerful Tools for Optimization'', A.I.: Foundations, Theory, & Algorithms, 2016 |
| 5 | Greedy algorithms and Exact Methods | E.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 |
| 6 | Single solution Metaheuristics | E.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 |
| 7 | Algoritmi Bio-Inspirati: (i) Concetti comuni; (a) Selection methods; (b) Reproduction; (c) Replacement strategies; (ii) GAs; (ii) GPs (iii) AIS; (iv) Swarm Intelligence: PSO, ACO, ABC; and (v) DE | Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 - Blum & Raidl, ''Hybrid Metaheuristics: Powerful Tools for Optimization'', A.I.: Foundations, Theory, & Algorithms, 2016 - materiale fornito dal docente |
| 8 | Hybrid Metaheuristics | C. Blum and G.R. Raidl, ''Hybrid Metaheuristics: Powerful Tools for Optimization'', Artificial Intelligence: Foundations, Theory, and Algorithms, 2016 |
| 9 | Parallel Metaheuristics | E.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 |
| 10 | MultiObjective Optimization by Metaheuristics | E.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 |
| 11 | Machine Learning & Metaheuristics | Materiale fornito dal docente |
| 12 | Metaheuristics application examples in: Network Sciences; Games; Internet of Things; Computer Security; Robotics; Art and Design | Materiale fornito dal docente |
Learning Assessment
Learning Assessment Procedures
The evaluation is based on three tests:
THEORY TEST: it consists of a written test relating to the topics covered in class.
PROJECT AND REPORT: it consists on the development of an investigated algorithm to be applied and tested on a given complex problem. The following information will be provided: (1) problem to be solved; (2) set of problem instances on which to test the efficiency of the developed algorithm; (3) list of some heuristics and/or meta-heuristics, from which the student must choose the algorithm to be implemented; (4) objective function (if needed); (5) experimental protocol to follow for evaluating the efficiency of the algorithm. The project must be delivered within 15-20 days of its assignment. Expired the assigned time, the student must submit (by email) for the evaluation: (a) source code of the developed algorithm; and (b) report written in Latex. The algorithm must be developed using one of the following programming languages: C, C ++, Java, Python or Matlab.
ORAL INTERVIEW: oral discussion on the project, via PowerPoint or PDF presentation made by the student. The student will have a 10 minutes as maximum time, during which discuss on the algorithm carried out, the relative key points and the originalities introduced.
Examples of frequently asked questions and / or exercises
https://www.dmi.unict.it/mpavone/hemol.html