Programmazione genetica

La programmazione genetica (GP) è una metodologia di programmazione automatizzata ispirata dall'evoluzione biologica per scoprire programmi informatici che svolgano in maniera (quasi) ottimale un determinato compito. È una particolare tecnica di apprendimento automatico che usa un algoritmo evolutivo per ottimizzare una popolazione di programmi di computer secondo un paesaggio adattativo determinato dall'abilità del programma di arrivare ad un risultato computazionalmente valido (ovvero di saper svolgere il compito dato). I primi esperimenti con la GP sono stati eseguiti da Stephen F. Smith (1980) e Nichael L. Cramer (1985), come descritto nel famoso libro Genetic Programming: On the Programming of Computers by Means of Natural Selection di John Koza (1992).

I programmi creati con la GP possono essere scritti in molti linguaggi di programmazione. Nelle prime e tradizionali implementazioni della GP le istruzioni e i dati erano organizzati in strutture ad albero, quindi si preferiva l'uso di linguaggi che avessero queste strutture come tipo di dato primitivo; un esempio importante di linguaggio utilizzato da Koza è il Lisp. Sono state suggerite e implementate con successo anche altre forme di GP, come la più semplice rappresentazione lineare che ben si adatta ai normali linguaggi imperativi (vedere al riguardo, Banzhaf e al. (1998)). Il software commerciale che implementa la GP Discipulus, ad esempio, usa la programmazione genetica lineare combinata coi linguaggi in codice macchina per ottenere migliori prestazioni. In maniera diversa il MicroGP usa una rappresentazione interna simile alla programmazione genetica lineare per generare programmi che utilizzino pienamente la sintassi di un dato linguaggio assembly.

Poiché la programmazione genetica richiede una grande capacità computazione, negli anni 90 fu usata principalmente per risolvere problemi relativamente semplici. Tuttavia, più recentemente, grazie ai recenti sviluppi nella tecnologia GP e alla ben conosciuta legge di Moore, la GP ha cominciato a fornire un certo numero di risultati. Al momento della scrittura di questo articolo, sono stati ottenuti almeno quaranta risultati competitivi con gli esseri umani, in aree come l'informatica quantistica, il design di componenti elettronici, i giochi, gli algoritmi di ordinamento, di ricerca e molte altre aree. Questi risultati includono la replicazione di molte invenzioni fatte dopo l'anno 2000 e la produzione di due invenzioni brevettabili.

Lo sviluppo di una teoria per la programmazione genetica fu compito arduo, cosa per cui, negli anni 90, fu considerata una sorta di paria tra le varie tecniche di ricerca. Tuttavia, dopo una serie di risultati positivi nei primi anni dopo il 2000, la teoria della GP ha avuto un formidabile e rapido sviluppo; così rapido che è stato possibile costruire modelli probabilistici esatti della GP (teorie, diagrammi e modelli tramite catene di Markov) e mostrare che la GP è più generale e come tale include gli algoritmi genetici.

Le tecniche di programmazione genetica sono state applicate all'hardware evolutivo ed ai programmi per computer.

La programmazione meta-genetica è la tecnica utilizzata per fare evolvere un sistema di programmazione genetica utilizzando la stessa programmazione genetica. Nella meta-programmazione genetica, cromosomi, operatori di incrocio e mutazione evolvono essi stessi.

Bibliografia

• Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D. (1998), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann.
• Cramer, Nichael Lynn (1985), "A representation for the Adaptive Generation of Simple Sequential Programs" in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), Carnegie Mellon University.
• Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314. A thorough report, possibly used as a draft to his 1992 book.
• Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press.
• Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press.
• Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann.
• Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers.
• Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag.
• Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, Lulu.com, disponibile gratuitamente via internet, ISBN 978-1-4092-0073-4.
• Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, tesi di dottorato (University of Pittsburgh).

Collegamenti esterni

• (EN) Sorgenti di uGP3 Sorgenti di uGP3
• (EN) A Field Guide to Genetic Programming by Poli, Langdon, and McPhee. Disponibile gratuitamente in formato PDF, od in forma stampata presso Lulu.com.
• (EN) Genetic Programming FAQ
• (EN) Sito di programmazione genetica di John Koza
• Sito di programmazione genetica di Juergen Schmidhuber, con documenti sulla GP pre-Koza (1987)
• Bibliografia della GP di Bill Langdon
• Sito di programmazione meta-genetica
• Global Optimization Algorithms - Theory and Application