HEURISTICS AND METAHEURISTICS FOR OPTIMIZATION AND LEARNING

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.

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.

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:

• Introduzione alle Teoria della Computabilità: problemi NP-Completi
• Introduzione a concetti di Machine Learning e Computational Learning Theory
  
• Landscape, Search Space e Modelli per l’Ottimizzazione
• Ottimizzazione non vincolata; Ottimizzazione vincolata; Ottimizzazione multi-obiettivo
• Introduzione ai metodi di ottimizzazione

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 Optimization, Ant Colony Optimization, Artificial 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

• Applicazioni di met-euristiche in: Network Sciences; Games; Internet of Things; Computer Security; Robotics; Art and Design.

1. E.G. Talbi, "Metaheuristics: From Design to Implementation", Wiley, 2009
2. C. Blum and G.R. Raidl, "Hybrid Metaheuristics: Powerful Tools for Optimization", Artificial Intelligence: Foundations, Theory, and Algorithms, 2016
3. 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.

Il voto complessivo della parte di laboratorio viene attribuito secondo il seguente schema:

• non approvato: lo studente non ha acquisito i concetti di base e non è in grado di svolgere almeno il 60% degli esercizi pratici (sviluppare un algoritmo di base);
• 18-24: lo studente dimostra una padronanza minima dei concetti di base, e capacità di implementare semplici algoritmi o di base;
• 25-27: lo studente dimostra una buona padronanza dei contenuti del corso, un buona conoscenza dei contenuti ed è in grado di implementare versioni più avanzate degli algoritmi trattati a lezione;
• 28-30 e lode: lo studente ha acquisito ottima padronanza di tutti i contenuti del corso ed è in grado di implementare efficienti e originali algoritmi trattati nel corso, anche di particolare complessità.

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:

https://www.dmi.unict.it/mpavone/hemol.html