Se riscontri problemi nella visualizzazione dei caratteri, clicca qui

Programmazione genetica

Da Wikipedia, l'enciclopedia libera.
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]

CARATTERISTICHE :

  • GE = Grammatical Evolution
  • CFG = Whigham‘s Context-Free Grammar GP
  • CGP = Julian Miller’s Cartesian GP
  • GEP = Gene Expression Programming
  • ST = Strongly-Typed GP
  • MOO = Multi-Objective Optimization
  • REL. = Anno di ultimo rilascio

MODELLO :

Nome Licenza Linguaggio Modello GE CFG CGP GEP ST MOO Rel. Note
AForge.net LGPL .NET T Y
Beagle LGPL C++ T Y Y
BorgMoea Open Custom C
Deap LGPL Python T Y Y Creato dallo stesso team di Open BEAGLE. Integrazione con SCOOP per l'elaborazione parallela
Dgpf LGPL Java
Drp GPL Ruby Y
Discipulus or Discipulus Commerciale L
Ecf C++ T
Ecj Licenza Academic Free Java M Y Y Y Y
Eo LGPL C++ M
EllenGp GPL C++ L
Ep4js Apache Javascript T
EpochX LGPL Java M Y Y
Eva2 LGPL Java T Y
Evogen MIT Flex
GAlib Open Custom C++ T
Genetik LGPL Java T
GenPro Apache Java
GeneXproTools Commerciale T
Geva GPL Java M Y
GpAlta GPL Java T
GpC++ GPL C++ T
Gpe AFL .NET
GpLab Matlab T
GpOCL GPL C++ T
GpTips Matlab T
HeuristicLab GPL3 C Sharp M Y
Jaga Java T
Java GAlib Java
Jclec Java T
Jef Java
JGap LGPL Java T
JGe Java Y
JGprog Java
JRGp Java T
Karoo Gp MIT Python T
Lagep C++ T
Lil Gp C T
MicroGp GPL C++ L Y Supporta la customizzazione della sintassi di partenza (es. assembler)
Moea LGPL Java
PerlGp GPL Perl T
PmdGp C++ T
PonyGe Python T
PushGp GPL C++, Java, JavaScript, Lisp S
PyEvolve Licenza Python Python T
PyStep MIT Python T Y
Rmit GP C++ T
Slash/A GPL C++ L Evolve usando programmi in linguaggio SLASH (un assembler "ad hoc")
SmallGp C++ T
TinyGp Java T
Vita MPL2 C++ L
Watchmaker Apache Java T Y

Note[modifica | modifica wikitesto]

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]

Controllo di autoritàLCCN: (ENsh96010308 · BNF: (FRcb135090447 (data)