Programmazione genetica

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.
bussola Disambiguazione – Da non confondersi con Ingegneria genetica

La programmazione genetica (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[modifica | modifica wikitesto]

I primi esperimenti con la GP sono stati eseguiti da Stephen F. Smith[1] (1980) e Nichael L. Cramer[2] (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[3][4], 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.

Software disponibili[modifica | modifica wikitesto]

Nome Licenza Linguaggio Rappresentazione Note
AForge.net LGPL C Sharp Gene expression programming
Beagle LGPL C++ Albero
DEAP LGPL Python Albero
Disciplus Commerciale Lineare
ECJ Licenza Academic Free Java Multipla
EO LGPL C++ Multipla
EpochX LGPL Java Multipla
Eva2 LGPL Java Albero
GeneXproTools Commerciale Albero
JGAP LGPL Java Albero
MicroGP GPL C++ Lineare
PerlGP GPL Perl Albero
PushGP GPL C++, Java, Javascript, Lisp Stack
PyEvolve Licenza Python Python Albero
Pyro Python
PyStep MIT Python Albero
Slash/A GPL C++ Lineare
Vita MPL2 C++ Lineare

Note[modifica | modifica wikitesto]

  1. ^ Homepage di Stephen F. Smith
  2. ^ Homepage di Nichael L. Cramer
  3. ^ Risultati competitivi con gli esseri umani (A Field Guide to Genetic Programming)
  4. ^ Risultati competitivi con gli esseri umani (genetic-programming.com)

Bibliografia[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]