Algoritmi euristici

A.A. 2014/2015
Insegnamento per
6
Crediti massimi
48
Ore totali
Lingua
Italiano

Struttura insegnamento e programma

Linea Milano
Edizione attiva
Responsabile
Informazioni sul programma
Introduzione.
* Ottimalità globale e locale.
* Convessità.
* Richiami di complessità.
* Approssimazione.
* Proprietà stocastiche di convergenza.
* Valutazione sperimentale degli algoritmi euristici.
* Classificazione degli algoritmi euristici.

Euristiche e metaeuristiche costruttive.
* greedy non adattivi e adattivi. Esempi.
* legame fra prestazioni degli algoritmi greedy e struttura del problema.
* GRASP. Esempi.
* Ant Colonies Optimization

Euristiche e metaeuristiche di ricerca locale.
* Il concetto di intorno.
* Classi di complessità per la ricerca locale.
* Classificazione: algoritmi singolo livello e multi-livello, singola soluzione e multi-soluzione, deterministici e non-deterministici.
* Strutture dati per l'esplorazione efficiente di intorni.
* Gerarchie di intorni e k-ottimalità. Esempi.
* Iterated local search e local search multi-livello (Lin-Kernighan). Esempi.
* Intorni complessi e variabili. Variable Neighborhood Descent e Variable Neighborhood Search. Esempi.
* Very Large Scale Neighborhood Search. Esempi.
* Tabu search. Esempi.

Euristiche di ricerca locale non deterministiche.
* Simulated Annealing e Threshold Accepting. Esempi.
* Macchina di Boltzmann.
* Mean-Field Annealing, Reti di Hopfield
* Reti elastiche per il TSP.

Euristiche a popolazione.
* Codifica di soluzioni.
* Scatter search.
* Algoritmi genetici
* Algoritmi evoluzionistici
Propedeuticità
Algoritmi e strutture dati. Programmazione. Ricerca Operativa.
Periodo
Primo semestre
Docente/i
Ricevimento:
Su appuntamento
DI - Via Celoria 18, Milano