Algoritmi Evolutivi (6 crediti)
Ultima modifica: 21 Luglio 2008.
url: http://www.disi.unige.it/person/MasulliF/didattica/AEgenova07.html
Docente: Francesco
Masulli.
E-mail
del docente: mailto:masulli@disi.unige.it
Corso:
Attivazione
Motivazioni
Prerequisiti
Obiettivi
Organizzazione
Programma
Corso Integrativo per l'AA 2007/08
Testi di Riferimento
Home
Page - Informazioni On-Line
Appello di Luglio
2008
Venerdi 25 Luglio ore 14.30 demo e discussione progetti di laboratorio
Martedi 29 Luglio ore 14.30 orali
Attivazione
Il corso viene offerto agli studenti della Laurea ed Laurea
Specialistica in Informatica ed e'
attivato una volta ogni due anni accademici, in alternanza con il corso
di
Intelligenza Computazionale.
Nell'anno accademico 2007/2008 il
corso e' attivato.
Motivazioni
Gli Algoritmi Evolutivi sono procedure di ricerca
ispirate ai meccanismi dell'evoluzione biologica. Negli Algoritmi
Evolutivi viene mantenuta una popolazione di strutture dati, chiamate
cromosomi, che codificano soluzioni candidate per un problema.
L'algoritmo seleziona i cromosomi genitori dalla popolazione e opera su
di essi in modo da produrre cromosomi che progressivamente
rappresentano soluzioni migliori. Il processo di selezione e'
ispirato alla selezione naturale. I cromosomi che rappresentano
migliori soluzioni hanno maggiore probabilita' di diventare genitori.
La ricombinazione e la mutazione genetica ispirano gli operatori che
producono nuove soluzioni candidate. L'operatore con cui un Algoritmo
Evolutivo combina il materiale genetico di due cromosomi genitori per
produrre un figlio e' chiamato crossover. La mutazione modifica
un singolo cromosoma genitore. I principali tipi di
Algoritmi Evolutivi sono gli Algoritmi Genetici, la Programmazione
Evolutiva, le Strategie Evolutive e la Programmazione Genetica. Gli
Algoritmi Evolutivi da soli o eventualmente in combinazione con altre
tecniche del Soft Computing come le Reti Neurali e la Logica Sfumata,
permettono di affrontare problemi problemi complessi in vari domini
applicativi come routing, scheduling, allocazione ottimale
di
risorse, progettazione automatica, controllo, identificazione di
sistemi, analisi di immagini, stock prediction, credit scoring, risk
assessment, ecc.
Prerequisiti
Programmazione.
Elementi
di probabilita' e statistica.
Obiettivi
Il corso, dopo una introduzione schematica all'ispirazione
biologica degli algoritmi Evolutivi, presenta le basi matematiche e i
problemi implementativi degli Algoritmi Genetici, introduce gli aspetti
fondamentali delle Strategie Evolutive e della Programmazione Genetica,
confronta questi approcci con Simulated Annealing e metodi di
Swarm Intelligence
e analizza alcuni casi applicativi di interesse.
Organizzazione del Corso
Il corso e' organizzato in lezioni
teoriche, seminari degli studenti e esercitazioni di laboratorio.
Al corso puo' essere collegato un
Laboratorio Specialistico per un'attivita' di implentazione e
applicazione degli algoritmi studiati.
Programma del Corso
Metodi di ricerca analitici,
enumerativi e casuali - Steepest Ascend/Descent Procedures -
Simulated
Annealing - Applicazione al problema TSP - Algoritmi Genetici - Teorema
degli schemi - Funzioni GA-hard - Minimal Deceptive Problem -
Convergenza prematura - Stagnazione - Operatori avanzati di selezione -
Operatori avanzati di crossover - GA per ottimizzazione combinatoria -
Stategie Evolutive - Programmazione Genetica - Swarm Intelligenge -
Particle Swarm Optimization - Generatori di
numeri Pseudo-Casuali - Casi di studio -
Progetto di
laboratorio.
Corso Integrativo per l'AA 2007/08: Introduzione alla Bioinformatica e alla
Systems Biology
Docente: Prof.
Giuseppe Russo - Temple University,
Philadelphia, PA, USA.
Il corso tratta dei sofisticati metodi computazionali oggi utlizzati
per il trattamento dell'informazione genomica e introduce i
programmi e data base bioinformatici piu' diffusi in
Bioinformatica. Verranno introdotte le pricipali problematice
della System Biology che studia le interazioni tra i componenti dei
sistemi biologici e come queste
interazioni provochino la funzione ed il comportamento del sistema.
Programma di massima
Cenni di Bioinformatica: Introduzione ai database Biologici.
Allineamento di sequenze. Predizione di geni e promotori. Genomica e
Proteomica
Cenni di Systems Biology: Ricostruzione di networks biologici. Tecniche
di Reverse Engineering e di trattamento dati. Simulazione cellulare
Testi di riferimento
Libri di testo
- [GOLD89] D.E. Goldberg. Genetic Algorithms in Search,
Optimization and Machine Learning, Addison Wesley, 1989 (MAT
68-1989-48IN, CHI M.9, ING1 A.ELE.T.0264)
Altri testi consigliati
- [BNK97] W. Banzhaf, P. Nordin, R. E. Keller, F.D. Francone,
Genetic Programming: An Introduction, Morgan Kaufmann, 1997, ISBN:
155860510X.
- [EK01] R.C. Eberhart, J. Kennedy, Swarm Intelligence,
Morgan Kaufmann, 2001, ISBN: 1558605959.
- [HH98] R. L. Haupt, S. E.Haupt, Practical Genetic Algorithms,
Wiley-Interscience, 1998, ISBN: 0471188735.
- [KOZ92] J.R. Koza, Genetic Programming, MIT Press, 1992 (MAT
68-1992-038IN).
- [MIT96] M. Mitchell, An Introduction to Genetic Algoritms, MIT
Press, 1996 (MAT 68-1996-197, ARC C.4623, ING2 576.501 MIT
).
- [MIC96] Z. Michalewicz, Genetic Algorithms + Data Structures =
Evolution Programs, Springer-Verlag; 3rd Rev edition, 1996, ISBN:
3540606769
- [PL01] R. Poli, W.B. Langdon, Foundations of Genetic Programming,
Springer Verlag, 2001, ISBN: 3540424512.
- [SCH95] H.P. Schwefel, Evolution and Optimum Seeking, J. Wiley
& Sons, 1995 (MAT 68-1995-196).
- [PTV92] W.H. Press, S. A. Teukolsky, W.T. Vetterling, B.P.
Flannery, Numerical Recepies in C: the art of scientific computing (2nd
ed.), Cambridge University Press, 1992 ( CHI 517:519/13) Vedi anche
sito
web NUMERICAL RECEPIES.
- [TT01] A.Tettamanzi, M. Tomassini, Soft Computing: Integrating
Evolutionary, Neural, and Fuzzy Systems, Springer Verlag, 2001. ISBN:
354042204.
Ulteriore materiale didattico sara' reso disponibile agli studenti
durante il corso.