Algoritmi Evolutivi  (6 crediti)  

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.

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.

Programmazione. Elementi di  probabilita' e statistica.

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.

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.

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.

E-mail del docente: mailto:grusso@temple.edu

Obiettivi

Programma di massima

Cenni di Bioinformatica: Introduzione ai database Biologici. Allineamento di sequenze. Predizione di geni e promotori. Genomica e Proteomica

• [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)

• [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.