HEURISTICS AND METAHEURISTICS FOR OPTIMIZATION AND LEARNING

Anno accademico 2023/2024 - Docente: CLAUDIA CAVALLARO

Risultati di apprendimento attesi

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.

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

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

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

    Testi di riferimento

    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.

    Programmazione del corso

     ArgomentiRiferimenti testi
    1Introduzione alle Teoria della Computabilità: 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 TheoryIntroduzione a concetti di Machine Learning e Computational Learning Theory
    3Landscape e Search Space: topologie, significato e importanzaLandscape e Search Space: topologie, significato e importanza
    4Modelli per l’ottimizzazione: (i) Single-Objective Optimization; (ii) Constrained Optimization; (iii) Multi-Objective Optimization; (iv) Optimization under Uncertainty; (v) Dynamic OptimizationModelli per l’ottimizzazione: (i) Single-Objective Optimization; (ii) Constrained Optimization; (iii) Multi-Objective Optimization; (iv) Optimization under Uncertainty; (v) Dynamic Optimization
    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 MetaheuristicsParallel Metaheuristics
    10MultiObjective Optimization by MetaheuristicsMultiObjective Optimization by Metaheuristics
    11Machine Learning & MetaheuristicsMateriale fornito dal docente
    12Materiale fornito dal docenteMateriale fornito dal docente

    Verifica dell'apprendimento

    Modalità di verifica dell'apprendimento

    Modalità di verifica dell'apprendimento

    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 di domande e/o esercizi frequenti

    Esempi dei progetti assegnati saranno disponibili nella pagina ufficiale del corso al seguente link:

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