COMPUTAZIONE NATURALE E BIOISPIRATA
Anno accademico 2016/2017 - 1° annoCrediti: 6
SSD: INF/01 - Informatica
Organizzazione didattica: 150 ore d'impegno totale, 126 di studio individuale, 24 di lezione frontale
Semestre: 2°
Obiettivi formativi
Il corso introduce alla progettazione e implementazione di 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 diversi bio-inpisred algoritmi in ambito dell'ottimizzazione, sicurezza, e in ambiro della teoria delle decisioni e teoria dei giochi.
Alla fine del corso gli studenti avranno maturato:
- buona conoscenza dei concetti di base
- buona conoscenza del funzionamento dei “sistemi intelligenti”
- eccellente capacità autonoma di implementazione di un algoritmo bio- o nature-inspired
- problem-solving
Prerequisiti richiesti
Il corso presuppone una buona conoscenza di strumenti matematici (discreti e continui) e buona conoscenza di algoritmi e strutture dati.
Frequenza lezioni
La frequenza è fortemente consigliata.
Contenuti del corso
Il corso si suddivide in 2 parti fondamentali:
PRIMA PARTE:
- Definizione informale di Computazione Naturale
- Teoria della computabilità: problemi NP-Completi
- Teoria dei Grafi: una breve introduzione
- Sistemi Complessi: una breve introduzione
- Modellistica dei sistemi complessi
- Landscape e Search Space: topologie, significato e importanza
- Modelli per l’ottimizzazione
SECONDA PARTE:
- Metaheuristics: concetti principali
- Single-solution based Metaheuristics
- Population based Metaheuristics
Testi di riferimento
- E.G. Talbi, "Metaheuristics: From Design to Implementation", Wiley, 2009
- C. Blum and G.R. Raidl, "Hybrid Metaheuristics: Powerful Tools for Optimization", Artificial Intelligence: Foundations, Theory, and Algorithms, 2016
- Materiale fornito dal docente.
Programmazione del corso
| * | Argomenti | Riferimenti testi | |
|---|---|---|---|
| 1 | Definizione informale di Computazione Naturale | ||
| 2 | Teoria della computabilità | ||
| 3 | Teoria dei Grafi | Reinhard Diestel, ''Graph Theory'', Electronic Edition 2000 | |
| 4 | * | Sistemi Complessi | Hiroki Sayama, ''Introduction to the Modeling and Analysis of Complex Systems'', Electronic Edition 2015 |
| 5 | * | Modellistica dei sistemi complessi | Hiroki Sayama, ''Introduction to the Modeling and Analysis of Complex Systems'', Electronic Edition 2015 |
| 6 | * | Landscape e Search Space: topologie, significato e importanza | |
| 7 | * | Modelli per l’ottimizzazione: (i) Single-Objective Optimization; (ii) Constrained Optimization; (iii) Multi-Objective Optimization; (iv) Optimization under Uncertainty; (v) Dynamic Optimization | |
| 8 | * | Single-solution based Metaheuristics: (i) Local Search; (ii) Tabu Search; (iii) Hill Climbing | E.G. Talbi, ''Metaheuristics: From Design to Implementation'', Wiley, 2009 - C. Blum and G.R. Raidl, ''Hybrid Metaheuristics: Powerful Tools for Optimization'', Artificial Intelligence: Foundations, Theory, and Algorithms, 2016 |
| 9 | * | Population based Metaheuristics: (i) Concetti comuni; (a) Selection methods; (b) Reproduction; (c) Replacement strategies; (ii) ESs; (iii) EPs; (iv) GAs; (v) GPs; (vi) AIS; (vii) Swarm Intelligence | Talbi, ''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 |
N.B. La conoscenza degli argomenti contrassegnati con l'asterisco è condizione necessaria ma non sufficiente per il superamento dell'esame. Rispondere in maniera sufficiente o anche più che sufficiente alle domande su tali argomenti non assicura, pertanto, il superamento dell'esame.
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
L'esame consiste di tre prove: (i) test scritto; (ii) progetto e relazione; e (iii) colloquio orale.
TEST SCRITTO: Consiste di 15 domande a risposta multipla, i cui questiti riguardano la prima del programma.
PROGETTO E RELAZIONE: lo studente dovrà sviluppare un algoritmo evolutivo da applicare e testare su un problema complesso (algoritmo, problema e protocollo sperimentale verranno concordati con il docente). Alla conclusione del progetto, lo studente dovrà consegnare per la valutazione del proprio elaborato: (a) codice sorgente dell’algoritmo sviluppato; e (b) relazione scritta sull'originalità introdotte nell'elaborato.
COLLOQUIO ORALE: discussione orale, attraverso una presentazione in PowerPoint or PDF, sul progetto sviluppato. Lo studente avrà un tempo massimo di 10 minuti per descrivere il progetto svolto e i relativi punti chiavi e originali.