Programmazione genetica

La programmazione genetica, dall'inglese genetic programming (GP), è una metodologia di programmazione automatizzata, ispirata dall'evoluzione biologica, per scoprire programmi informatici che svolgano in maniera 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 a un risultato computazionalmente valido (ovvero di saper svolgere il compito dato).

Storia

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).

Sino agli anni '90, a causa delle grandi risorse di calcolo necessarie, il ricorso alla GP era limitato a problemi relativamente semplici. In seguito, col rapido migliorare delle prestazioni dei processori e grazie a sviluppi nella tecnologia GP, si sono ottenuti interessanti risultati in numerose aree. Al momento della scrittura di questo articolo, sono stati ottenuti almeno sessanta risultati competitivi con gli esseri umani, in aree quali gli algoritmi quantistici, il design di componenti elettronici e controller, i giochi, gli algoritmi di ordinamento / ricerca, l'hardware evolutivo e gli stessi programmi per computer. Questi risultati includono la replicazione di molte invenzioni fatte dopo l'anno 2000 e la produzione di alcune invenzioni brevettabili.

Teoria

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.

Struttura dei programmi

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.

Programmazione meta-genetica

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) Programmazione genetica, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (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, su cs.ucl.ac.uk.
• (EN) Sito di programmazione genetica di John Koza, su genetic-programming.com.
• Sito di programmazione genetica di Juergen Schmidhuber, con documenti sulla GP pre-Koza (1987), su idsia.ch.
• Bibliografia della GP di Bill Langdon, su cs.bham.ac.uk.
• Global Optimization Algorithms - Theory and Application (PDF), su it-weise.de.
• http://www.tc33.org/genetic-programming/genetic-programming-software-comparison/