MATEMATICA E INFORMATICAInformaticaAnno accademico 2023/2024

9796656 - HEURISTICS AND METAHEURISTICS FOR OPTIMIZATION AND LEARNING

Docente: Vincenzo CUTELLO

Risultati di apprendimento attesi

l 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.

  1. Conoscenza e capacità di comprensione (knowledge and understanding): l'obiettivo del corso è quello di far acquisire conoscenze base e avanzate che consentano allo studente di comprendere i meccanismi chiave, teorici e applicativi, che stanno alla base delle euristiche e meta-euristiche necessari all’ottenimento di algoritmi di successo
  2. Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): lo studente acquisirà le competenze necessarie per progettare una euristica e una meta-euristica, definendo in modo opportuno la rappresentazione delle soluzioni e i necessari operatori di ricerca della soluzione, nonché la necessaria conoscenza per l’utilizzo di un idoneo protocollo sperimentale atto a valutare correttamente l’efficienza e la robustezza dell’algoritmo sviluppato.
  3. Autonomia di giudizio (making judgements): Attraverso esempi applicativi lo studente sarà in grado di elaborare autonomamente proprie soluzioni, al fine di sviluppare un algoritmo in grado di risolvere, anche approssimativamente, un qualunque problema del mondo reale.
  4. Abilità comunicative (communication skills): lo studente acquisirà ulteriori abilità comunicative e di appropriatezza espressiva nell'impiego del linguaggio tecnico nell'ambito generale della (i) complessità computazionale, (ii) teoria dei grafi, (iii) sistemi complessi, (iv) ottimizzazione, (v) learning, (vi) euristiche e (vii) meta-euristiche.
  5. Capacità di apprendimento (learning skills): il corso si propone, come obiettivo, di fornire allo studente le necessarie metodologie teoriche e pratiche per poter affrontare e risolvere autonomamente nuove problematiche che dovessero sorgere durante l'attività progettuale tipica di un Laureato Magistrale.

Modalità di svolgimento dell'insegnamento

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.

Prerequisiti richiesti

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.

Frequenza lezioni

La frequenza è fortemente consigliata per garantire un adeguato grado di comprensione degli argomenti proposti.

Contenuti del corso

Il corso si suddivide in tre parti fondamentali:

PRIMA PARTE:

SECONDA PARTE:

  1. METODI DI OTTIMIZZAZIONE:
    • 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
  2. ALGORITMI BIO-INSPIRED 
    • Algoritmi Genetici e Programmazione Genetica
    • Sistemi Immunitari Artificiali; 
    • Swarm Intelligence: Particle Swarm OptimizationAnt Colony OptimizationArtificial Bee Colony  
    • Differential Evolution
  3. HYBRID METAHEURISTICS
  4. PARALLEL METAHEURISTICS
  5. ALGORITMI BIO-INSPIRATI per l'ottimizzazione multi-obiettivo e decision making
  6. MACHINE LEARNING & METAHEURISTICS

TERZA PARTE

Programmazione del corso

 ArgomentiRiferimenti testi
1Introduzione alle Teoria della Complessità: problemi NP-CompletiT.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009 (chapter 34)
2Introduzione a concetti di Machine Learning e Computational Learning TheoryE. Alpaydin, “Introduction to Machine Learning”, MIT Press, 2014 - Kearns, Vazirani, "An Introduction to Computational Learning Theory", MIT Press 1994
3Landscape e Search Space: topologie, significato e importanzaTalbi, ''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
4Modelli per l’ottimizzazione: (i) Single-Objective Optimization; (ii) Constrained Optimization; (iii) Multi-Objective Optimization; (iv) Optimization under Uncertainty; (v) Dynamic OptimizationTalbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 - Blum & Raidl, ''Hybrid Metaheuristics: Powerful Tools for Optimization'', A.I.: Foundations, Theory, & Algorithms, 2016
5Greedy algorithms and  Exact MethodsE.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009
6Single solution MetaheuristicsE.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009
7Algoritmi 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) DETalbi, ''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
8Hybrid MetaheuristicsC. Blum and G.R. Raidl, ''Hybrid Metaheuristics: Powerful Tools for Optimization'', Artificial Intelligence: Foundations, Theory, and Algorithms, 2016
9Parallel MetaheuristicsE.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009
10MultiObjective Optimization by MetaheuristicsE.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009
11Machine Learning & MetaheuristicsMateriale fornito dal docente
12Metaheuristics application examples in: Network Sciences; Games; Internet of Things; Computer Security; Robotics; Art and DesignMateriale fornito dal docente

English version