Heuristic algorithms

A.A. 2019/2020
Insegnamento per
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Inglese
Obiettivi formativi
Il corso illustra i principali paradigmi per progettare e realizzare algoritmi euristici per problemi decisionali complessi con particolare riferimento ai problemi di ottimizzazione combinatoria. E' previsto che gli studenti svolgano attività sperimentale con gli algoritmi descritti nel corso.
Progettazione di algoritmi euristici per problemi di ottimizzazione

Struttura insegnamento e programma

Edizione attiva
Responsabile
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Cordone Roberto
STUDENTI FREQUENTANTI
Programma
Introduzione
* Classificazione degli algoritmi euristici
* Alcuni problemi significativi di Ottimizzazione Combinatoria
* Complessita' computazionale: definizioni e complessita' parametrizzata
* Analisi teorica di prestazione: algoritmi approssimati
* Analisi sperimentale di prestazione

Euristiche e metaeuristiche costruttive
* Algoritmi greedy
* Algoritmi di roll-out
* GRASP
* Ant Colony Optimization

Euristiche e metaeuristiche di ricerca locale
* Intorno: definizione ed esplorazione efficiente
* Very Large Neighborhood Search
* Iterated local search e Variable Neighborhood Search
* Simulated Annealing
* Tabu search

Euristiche di ricombinazione
* Scatter search e Path Relinking
* Algoritmi genetici e strategie evoluzionistiche
Informazioni sul programma
Introduzione
* Classificazione degli algoritmi euristici
* Alcuni problemi significativi di Ottimizzazione Combinatoria
* Complessita' computazionale: definizioni e complessita' parametrizzata
* Analisi teorica di prestazione: algoritmi approssimati
* Analisi sperimentale di prestazione

Euristiche e metaeuristiche costruttive
* Algoritmi greedy
* Algoritmi di roll-out
* GRASP
* Ant Colony Optimization

Euristiche e metaeuristiche di ricerca locale
* Intorno: definizione ed esplorazione efficiente
* Very Large Neighborhood Search
* Iterated local search e Variable Neighborhood Search
* Simulated Annealing
* Tabu search

Euristiche di ricombinazione
* Scatter search e Path Relinking
* Algoritmi genetici e strategie evoluzionistiche
Propedeuticità
programmazione C, algoritmi e ricerca operativa
(C programming, algorithms and operations research)
Prerequisiti e modalità di esame
Le modalita' d'esame sono in via di rielaborazione, probabilmente con il passaggio a un esame scritto.
Fino a settembre 2019, l'esame si compone di un progetto pratico e di un esame orale.
Il progetto richiede lo sviluppo di un algoritmo per risolvere un problema di Ottimizzazione Combinatoria,
la realizzazione del relativo programma in linguaggio C standard,
la valutazione delle sue prestazioni su istanze di benchmark e la stesura di una relazione.
L'orale consiste in una discussione, in particolare su come applicare concretamente
le tecniche trattate nel corso a possibili problemi di esempio

The exam is going to be reprocessed, probably shifting to a written exam.
Up to September 2019, the exam consists in a practical project and an oral interview.
The project requires to develop an algorithm to solve a Combinatorial Optimization problem,
to implement it as a C program, to evaluate its performance on benchmark instances
and to write a report. The oral interview consists in a discussion on how to apply
in practice the techniques discussed in the course to possible problems.
Metodi didattici
Lezioni frontali e di laboratorio (theoretical lessons and laboratory sessions)
Materiale didattico e bibliografia
Lucidi, dispense e articoli di approfondimento sulla pagina web del corso
(Slides, lecture notes and survey papers on the course web page)
STUDENTI NON FREQUENTANTI
Programma
Introduzione
* Classificazione degli algoritmi euristici
* Alcuni problemi significativi di Ottimizzazione Combinatoria
* Complessita' computazionale: definizioni e complessita' parametrizzata
* Analisi teorica di prestazione: algoritmi approssimati
* Analisi sperimentale di prestazione

Euristiche e metaeuristiche costruttive
* Algoritmi greedy
* Algoritmi di roll-out
* GRASP
* Ant Colony Optimization

Euristiche e metaeuristiche di ricerca locale
* Intorno: definizione ed esplorazione efficiente
* Very Large Neighborhood Search
* Iterated local search e Variable Neighborhood Search
* Simulated Annealing
* Tabu search

Euristiche di ricombinazione
* Scatter search e Path Relinking
* Algoritmi genetici e strategie evoluzionistiche
Prerequisiti e modalità di esame
programmazione C, algoritmi e ricerca operativa
(C programming, algorithms and operations research)
Materiale didattico e bibliografia
Lucidi, dispense e articoli di approfondimento sulla pagina web del corso
(Slides, lecture notes and survey papers on the course web page)
Periodo
Primo semestre
Periodo
Primo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
Su appuntamento
DI - Via Celoria 18, Milano