Programació genètica

De Viquipèdia

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 algoritme evolutiu per optimitzar una població de programes informàtics segons un paisatge de adequació determinat per l'habilitat d'un programa per realitzar una tasca computacional donada. El primer en informar sobre els experiments amb GP van ser Stephen F. Smith (1980) i Nichael L. Cramer (1985), tal i 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 l'utilització de llenguatges que de forma natural tractaven aquesta estructura (un exemple important que va innovar Koza es 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 et al. (1998)]. El programari GP comercial Discipulus, per exemple, utilitza programació genètica lineal combinada amb codi màquina per aconseguir més rendiment. Per un altra banda, el MicroGP utilitza una representació similar a la programació genètica lineal per generar programes que s'aprofiten al màxim de la sintaxis de un llenguatge ensamblador donat.

GP es computacionalment molt intensiva i per això als anys 90 era utilitzada per resoldre problemes relativament simples. Però, més recentment, varies millores en la tecnologia GP i a la ben conegut creixement esponencial en la potencia de les CPUs, GP ha començat a proveir una serie de resultats excelents. Al moment d'escriure això, prop de 40 resultats competitius amb el ser humà han estat aconseguits, in àreas com la computación cuà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ò, desrpés de algunes millores significatives a principis dels 2000, la teoria de la GP ha tingut un desenvolupament formidable. Fins al punt que ha estat posible construir models de probabilitat exacta de la GP (teories d'esquemes i models de cadena de Markov) i demostrar que la programació genètica es més general, i de fet inclou, els algoritmes genètics.

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

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