Il corso introduce alla progettazione e implementazione di euristiche e meta-euristiche, inclusi gli algoritmi che prendono ispirazione dalla natura e dalla biologia, nonché alle caratteristiche chiavi necessari all'ottenimento di algoritmi di successo. Verranno altresì analizzate varie applicazioni di diverse metodologie di ottimizzazione e learning in ambito dell'ottimizzazione, della sicurezza, della teoria delle decisioni e della teoria dei giochi.
Le lezioni si svolgeranno in modalità frontale. Alcune specifiche lezioni potranno però essere svolte in laboratorio.
Il corso può inoltre prevedere seminari tenuti da esperti esterni su argomenti correlati e d'attualità.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.
Il corso presuppone una buona conoscenza di strumenti matematici (discreti e continui), algoritmi e strutture dati, nonchè ottima conoscenza dei linguaggi di programmazione C, C++, Java Python e/o Matlab.
La frequenza è fortemente consigliata per garantire un adeguato grado di comprensione degli argomenti proposti.
Il corso si suddivide in tre parti fondamentali:
PRIMA PARTE:
SECONDA PARTE:
Argomenti | Riferimenti testi | |
---|---|---|
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 |
L'esame consiste di tre prove: (i) prova scritta; (ii) progetto e relazione; e (iii) colloquio orale.
PROVA SCRITTA: consiste di un test a risposta multipla e/o aperta sugli argomenti analizzati durante le lezioni.
PROGETTO E RELAZIONE: lo studente dovrà sviluppare un algoritmo trattato a lezione da applicare e testare su un dato problema complesso. Per la prova verranno fornite le seguenti informazioni: (1) problema da risolvere; (2) insieme di istanze del problema su cui testare la validità e qualità dell'algoritmo implementato; (3) elenco di alcune euristiche e/o meta-euristiche, e relative caratteristiche, dal quale lo studente deve scegliere l'algoritmo da implementare; (4) funzione obiettivo (se necessaria); (5) protocollo sperimentale da seguire per la validazione dell'algoritmo implementato. Il progetto dovrà essere consegnato entro 15-20 giorni. Alla conclusione del progetto, inoltre, lo studente dovrà consegnare per la valutazione del proprio elaborato: (a) codice sorgente dell’algoritmo sviluppato; e (b) relazione scritta in Latex. L'algoritmo dovrà essere sviluppato in uno dei seguenti linguaggi di programmazione: C, C++, Java, Python o Matlab.
COLLOQUIO ORALE: discussione orale del progetto sviluppato, attraverso presentazione in PowerPoint or PDF. Lo studente avrà un tempo massimo di 10 minuti per descrivere l'elaborato svolto, i relativi punti chiavi e le originalità introdotte.
Si noti che le tre prove sono da superare nell'ordine indicato.
Nota: la verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.
Esempi dei progetti assegnati saranno disponibili nella pagina ufficiale del corso al seguente link: