Algoritmi euristici (A.A. 2018/19)

Aule e orari


Le lezioni si tengono in Aula G30 (in via Golgi)

  • lunedì dalle 13.30 alle 15.30
  • giovedì dalle 13.30 alle 15.30

Avviso: Le lezioni di laboratorio si terranno al settore didattico di via Celoria

  • lunedì 29 ottobre dalle 13.30 alle 15.30 in aula 310
  • lunedì 12 novembre dalle 13.30 alle 15.30 in aula 310
  • lunedì 26 novembre dalle 13.30 alle 15.30 in aula 311
  • lunedì 10 dicembre dalle 13.30 alle 15.30 in aula 310
  • lunedì 7 gennaio dalle 13.30 alle 15.30 in aula 310
Per accedere ai computer dei laboratori informatici Unicloud, gli studenti devono registrarsi con le proprie credenziali di ateneo una volta per anno accademico presso i chioschi nelle aule o via internet.

Esame


L'esame si compone di

  1. un progetto pratico
  2. un colloquio orale sugli argomenti del corso

Il progetto pratico consiste nel

  • realizzare in linguaggio C (solo con la libreria standard) un algoritmo metaeuristico per un problema di Ottimizzazione Combinatoria
  • confrontare sperimentalmente varianti dell'algoritmo (valori diversi di parametri, presenza/assenza o realizzazioni alternative di procedure) su un benchmark di istanze
  • descrivere algoritmo e prove sperimentali in una relazione riassuntiva

Circa un mese prima di ciascun appello, saranno pubblicati su questa pagina web il tema e la data di consegna del progetto. È possibile accordarsi per un progetto personale diverso da quello pubblicato.

L'orale avrà luogo circa una settimana dopo la consegna. È possibile accordarsi per un rinvio dell'orale, di qualche giorno o settimana.

Progetto di gennaio

Si risolva il problema proposto dal Google Hash Code 2018 - Qualification round con un approccio metaeuristico. Discuteremo più a fondo il progetto nelle lezioni di giovedì 20 dicembre e soprattutto lunedì 7 gennaio 2019.

In alternativa, è possibile realizzare i materiali per le ultime 4 lezioni di laboratorio sull'MDP (codici, dispensa, prove computazionali, ecc...).

In alternativa, è possibile risolvere con un approccio metaeuristico il problema proposto dalla VeRoLog Solver Challenge 2019 (questo è più complicato dei precedenti).

Lezioni

I materiali del corso (lucidi, articoli di approfondimento, codici e dati per i laboratori) verranno pubblicati via via qui di seguito. Sono però disponibili sulla pagina della scorsa edizione i materiali vecchi, che differiscono da quelli nuovi solo per piccole correzioni.

In linea di massima il calendario ipotetico del corso è il seguente, ma la la disponibilità delle aule per i laboratori introdurrà certamente delle modifiche.

Prima lezione (1 ottobre 2018)

Introduzione agli algoritmi euristici: concetti di base e classificazione

Seconda (4 ottobre 2018)

Ottimizzazione Combinatoria: problemi su insiemi, funzioni logiche, matrici e grafi

Terza lezione (8 ottobre 2018)

Richiami di complessità computazionale, complessità parametrizzata e complessità nel caso medio

Quarta lezione (11 ottobre 2018)

Valutazione a priori degli algoritmi euristici: approssimazione e convergenza in probabilità

Quinta e sesta lezione (15 e 18 ottobre 2018)

Valutazione sperimentale degli algoritmi euristici

Settima e ottava lezione (22 e 25 ottobre 2018)

Euristiche costruttive/distruttive

Nona lezione (29 ottobre 2018)

Laboratorio sulle euristiche costruttive/distruttive

Decima e undicesima lezione (5 e 8 novembre 2018)

Metaeuristiche costruttive: GRASP, Ant System

Dodicesima lezione (12 novembre 2018)

Laboratorio sulle metaeuristiche costruttive/distruttive

Tredicesima e quattordicesima lezione (15 e 19 novembre 2018)

Euristiche di scambio, intorno, landscape e ricerca locale

Quindicesima lezione (22 novembre 2018)

Very Large Neighbourhood Search (VLNS)

Sedicesima lezione (26 novembre 2018)

Laboratorio sulle euristiche di scambio

Diciassettesima lezione (29 novembre 2018)

Multi-start, Iterated Local Search e Variable Neighbourhood Search
  • Lucidi
  • ILS (articolo di H.R. Lourenco, O.C. Martin e T. Stuetzle)
  • VNS (articolo di P. Hansen e N. Mladenovic)

Diciottesima lezione (3 dicembre 2018)

Variable Neighbourhood Descent e Dynamic Local Search

Diciannovesima lezione (6 dicembre 2018)

Simulated Annealing e Tabu Search
  • Lucidi
  • SA (capitolo di A.G. Nikolaev e S.H. Jacobson)
  • TS (capitolo di M. Gendreau e J.-Y. Potvin)

Ventesima lezione (10 dicembre 2018)

Laboratorio sulle metaeuristiche di scambio

Ventunesima lezione (13 dicembre 2018)

Scatter search e Path Relinking

Ventiduesima e ventitreesima lezione (17 e 20 dicembre 2018)

Algoritmi genetici e strategie evoluzionistiche

Ventiquattresima lezione (7 gennaio 2019)

Laboratorio sulle euristiche di ricombinazione