Programació genètica

La programació genètica (GP per les sigles de l'anglès Genetic programming) és una metodologia automatitzada inspirada per l'evolució biològica per trobar programes informàtics que millor realitzen una tasca definida per l'usuari. És per això una tècnica d'aprenentatge de màquines particular que utilitza un algorisme evolutiu per optimitzar una població de programes informàtics segons un paisatge d'adequació determinat per l'habilitat d'un programa per realitzar una tasca computacional donada. El primer a informar sobre els experiments amb GP van ser Stephen F. Smith (1980) i Nichael L. Cramer Arxivat 2005-12-03 a Wayback Machine. (1985), tal com es va descriure al famós llibre Genetic Programming: On the Programming of Computers by Means of Natural Selection ("Programació genètica: Sobre la programació de computadores mitjançant la selecció natural") de John Koza (1992).

Els programes d'ordinador en GP poden ser escrits en una varietat de llenguatges de programació. A les primeres (i tradicionals) implementacions de GP, les instruccions de programa i els valors de les dades estaven organitzats en estructures en arbre, afavorint la utilització de llenguatges que de manera natural tractaven aquesta estructura (un exemple important que va innovar Koza és Lisp). Altres formes de GP han estat suggerides i implementades amb èxit, com la més senzilla representació lineal que s'adapta als llenguatges imperatius més tradicionals, [veure, per exemple, Banzhaf i cols. (1998)]. El programari GP comercial Discipulus Arxivat 2006-08-16 a Wayback Machine., per exemple, utilitza programació genètica lineal combinada amb codi màquina per aconseguir més rendiment. Per una altra banda, el MicroGP Arxivat 2006-04-18 a Wayback Machine. utilitza una representació similar a la programació genètica lineal per generar programes que s'aprofiten al màxim de la sintaxi d'un llenguatge ensamblador donat.

GP és computacionalment molt intensiva i per això als anys 90 era utilitzada per resoldre problemes relativament simples. Però, més recentment, diverses millores en la tecnologia GP i a la ben conegut creixement esponencial en la potència de les CPUs, GP ha començat a proveir una sèrie de resultats excelents. Al moment d'escriure això, prop de 40 resultats competitius amb el ser humà han estat aconseguits, en àrees com la computació quàntica, disseny electrònic, jocs, ordenació, cerca i molts d'altres. Aquests resultats inclouen la replicació o usurpació de diverses invencions de després de l'any 2000, i la producció de dues invencions patentables.

Desenvolupar una teoria per la GP ha estat molt difícil i per això als anys 90 la programació genètica era considerarda una mena de paria entre les diverses tècniques de búsqueda. Però, després d'algunes millores significatives a principis dels 2000, la teoria de la GP ha tingut un desenvolupament formidable. Fins al punt que ha estat possible construir models de probabilitat exacta de la GP (teories d'esquemes i models de cadena de Markov) i demostrar que la programació genètica és més general, i de fet inclou, els algorismes genètics.

Les tècniques de la programació genètica han estat aplicades a maquinari evolutiu igual que a programes de computadora.

La meta-programació genètica és la tècnica de fer evolucionar un sistema de programes genètics utilitzant la programació genètica mateixa. Alguns crítics han argumentat que és teòricament impossible, però són necessàries més investigacions.

Enllaços externs en anglès

modifica

Implementacions:

Possiblement els més utilitzats: