Algoritmi Evolutivi  (3 crediti)   A.A. 2007/08

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.

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 - Simulated Annealing - Generatori di numeri Pseudo-Casuali - Casi di studio - Progetto di laboratorio.

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