Se riscontri problemi nella visualizzazione dei caratteri, clicca qui

Programmazione genetica

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
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
  • MO = Multi-Objective

MODELLO :

Nome Description Licenza Linguaggio Framework / Application Model Network (Island) GE CFG CGP GEP ST MO Note
AForge.net Evolution programming library LGPL .NET F T Y
Beagle A generic C++ framework for evolutionary computation LGPL C++ F T Y Y
BorgMoea The Borg Multiobjective Evolutionary Algorithm (MOEA) Open Custom C A Y
BraneCloud Evolution Industrial-Strength Evolutionary Computation for .NET 4.0 Apache C# F Fork of ECJ for .NET 4.0 - This is an independent port of Sean Luke's venerable ECJ project (GMU EC Lab) Version 20
DCTG-GP Prolog-based GP system. Grammar-guided GP using logic-based attribute grammars Prolog A
Deap Distributed Evolutionary Algorithms in Python LGPL Python F T Y Y Y Creato dallo stesso team di Open BEAGLE. Integrazione con SCOOP per l'elaborazione parallela
Dgpf Distributed Genetic Programming Framework LGPL Java F Y
Drp Grammatical Evolution + Genetic Programming = Directed Programming GPL Ruby F Y
Discipulus or Discipulus Commercial Genetic Programming Software from RML Technologies, Inc Commerciale A L
Ecf Evolutionary Computation Framework. different genotypes, parallel algorithms, tutorial C++ F T MPI
Ecj A Java-based Evolutionary Computation Research System Licenza Academic Free Java F / A M Y Y Y Y Y
Eo C++ evolutionary computation components framework LGPL C++ F M MPI
EllenGp Linear genetic programming system for symbolic regression and classification GPL C++ F L Y
Ep4js GA/EP framework written in JavaScript Apache JavaScript F T
EpochX EpochX is an open source genetic programming framework LGPL Java F M Y Y
Eureqa/Formulize GP based Symbolic Regression Commerciale A
Eva2 A Java based framework for Evolutionary Algorithms -- formerly known as JavaEvA/EvA LGPL Java F T RMI Y Y
Evogen Evogen is a general-purpose Actionscript 3 library for generating genetic algorithms MIT Flex F
EvoJ EvoJ project is a lightweight extensible Java framework which simplifies coding and refactoring of genetic algorithm applications. Creative Commons Java F
FlexGP Cloud based platform for generating transparent non-linear large scale regression problems Java F P2P TODO
GAlib Object oriented framework with 4 different GA implementations and 4 representation types (arbitrary derivations possible) Open Custom C++ F T
Genetik A generic framework that supports evolutionary algorithms. LGPL Java F T
Genotick. It's Artificial Intelligence Trading Software GPL Java A
GenPro Reflective Object Oriented Genetic Programming. Open Source Framework. Extend with POJO's, generates plain Java code Apache Java F
GeneXproTools Commercial gene expression programming software for logistic regression, classification and regression Commerciale A T
Geva GEVA is an implementation of Grammatical Evolution in Java GPL Java F M Y
GpAlta Genetic programming toolbox that aims for simplicity and speed GPL Java A T
GpC++ Genetic Programming C++ Class Library GPL C++ F T
GPdotNET Artificial intelligence tool for applying Genetic Algorithm and Artificial Neural Networks in modeling, prediction, optimization and pattern recognitions MIT .NET A
Gpe Framework for conducting experiments in Genetic Programming AFL .NET F
GpLab A Genetic Programming Toolbox for MATLAB Matlab F T
GpLearn Implements Genetic Programming in Python, with a scikit-learn inspired and compatible API. Python F TODO
GpOCL Genetic Programming in OpenCL is a parallel implementation of genetic programming targeted at heterogeneous devices, such as CPU and GPU GPL OpenCL A T
GpTips Genetic Programming & Symbolic Regression Toolbox for MATLAB. Aimed at performing multigene symbolic regression Matlab F T
HeuristicLab A Paradigm-Independent and Extensible Environment for Heuristic Optimization, rich graphical user interface, open source, plugin-based architecture GPL3 C Sharp A M Y
Jaga Extensible and pluggable open source API for implementing genetic algorithms and genetic programming applications Java F T
Java GAlib Source Forge open source Java genetic algorithm library, complete with Javadocs and examples (see bottom of page) Java F
Jclec Evolutionary Computation Library in Java, expression tree encoding, syntax tree encoding Java F T Y
JefNet Distributed genetic programming framework for the Java language LGPL Java F JXTA
Jenetics Advanced Genetic Algorithm, Evolutionary Algorithm and Genetic Programming library Java F Y TODO
JGap Java Genetic Algorithms and Genetic Programming, an open-source framework LGPL Java F T
JGe Java Grammatical Evolution Java F Y
JGprog Groovy Java Genetic Programming Groovy
JRGp Java A T Y
Karoo Gp A Genetic Programming platform for Python with TensorFlow for wicked-fast CPU and GPU support. MIT Python A / F T https://arxiv.org/pdf/1708.03157.pdf
Lagep Supporting single/multiple population genetic programming to generate mathematical functions. Open Source, OpenMP used. C++ A T
Lil Gp C A T
MicroGp General purpose tool, mostly exploited for assembly language generation GPL C++ A L Y Supporta la customizzazione della sintassi di partenza (es. assembler)
Moea Multiobjective Evolutionary Algorithm Framework LGPL Java F Y Y
Monkeys A strongly-typed genetic programming framework for Python Python F Y TODO
PerlGp Grammar-based genetic programming in Perl GPL Perl F T Y
PmdGp Object oriented framework for solving genetic programming problems C++ F T
PolyGP Haskell A
PonyGe A small, one source file implementation of GE, with an interactive graphics demo application GPL Python F T
PushGp A strongly typed, stack-based genetic programming system that allows GP to manipulate its own code (auto-constructive evolution) GPL C++, Java, JavaScript, Lisp A S
PyEvolve Pyevolve was developed to be a complete genetic algorithm framework written in pure pytho Licenza Python Python F T
Pyvolution Evolutionary Algorithms Framework Apache Python F
PyStep Python Strongly Typed gEnetic Programming MIT Python F T Y
Rmit GP A Genetic Programming Package with support for Automatically Defined Functions C++ F T Y
RoboGP Robust Genetic Programming System C++ F
Slash/A Programming language and C++ library for (linear) genetic programming GPL C++ F L Evolve usando programmi in linguaggio SLASH (un assembler "ad hoc")
SmallGp C++ T
spark-ml-gp Package provides java implementation of big-data genetic programming for Apache Spark Java F TODO
TinyGp A tiny genetic programming system Java A T
Vita Vita Genetic Programming Framework MPL2 C++ F L
Watchmaker Extensible, high-performance, object-oriented framework for implementing platform-independentevolutionary/genetic algorithms in Java Apache Java F T Hadoop Terracotta 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)