En inteligencia artificial, la programación genética ( PG ) es una técnica de desarrollo de programas, a partir de una población de programas no aptos (normalmente aleatorios), aptos para una tarea concreta mediante la aplicación de operaciones análogas a los procesos genéticos naturales a la población de programas.
Las operaciones son: selección de los programas más aptos para la reproducción (cruce), replicación y/o mutación de acuerdo con una medida de aptitud predefinida, generalmente la competencia en la tarea deseada. La operación de cruce implica intercambiar partes específicas de pares seleccionados (padres) para producir descendientes nuevos y diferentes que se convierten en parte de la nueva generación de programas. Algunos programas no seleccionados para la reproducción se copian de la generación actual a la nueva generación. La mutación implica la sustitución de alguna parte aleatoria de un programa con alguna otra parte aleatoria de un programa. Luego, la selección y otras operaciones se aplican recursivamente a la nueva generación de programas.
Por lo general, los miembros de cada nueva generación están, en promedio, más en forma que los miembros de la generación anterior, y el mejor programa de la generación suele ser mejor que los mejores programas de la generación anterior. La finalización de la evolución suele producirse cuando algún programa individual alcanza un nivel de aptitud o competencia predefinido.
Puede ocurrir, y a menudo ocurre, que una determinada ejecución del algoritmo dé como resultado una convergencia prematura hacia un máximo local que no sea una solución globalmente óptima o incluso buena. Por lo general, se necesitan múltiples ejecuciones (de docenas a cientos) para producir un muy buen resultado. También puede ser necesario tener un gran tamaño de población inicial y variabilidad de los individuos para evitar patologías.
El primer registro de la propuesta de desarrollar programas es probablemente el de Alan Turing en 1950. [1] Hubo un intervalo de 25 años antes de la publicación de Adaptación en sistemas naturales y artificiales de John Holland, que estableció las bases teóricas y empíricas de la ciencia. En 1981, Richard Forsyth demostró la evolución exitosa de pequeños programas, representados como árboles, para realizar la clasificación de evidencias de la escena del crimen para el Ministerio del Interior del Reino Unido. [2]
Aunque la idea de desarrollar programas, inicialmente en el lenguaje de programación Lisp , era común entre los estudiantes de John Holland, [3] no fue hasta que organizaron la primera conferencia sobre algoritmos genéticos (AG) en Pittsburgh que Nichael Cramer [4] publicó programas desarrollados en dos lenguajes especialmente diseñados, que incluían la primera declaración de programación genética moderna "basada en árboles" (es decir, lenguajes procedimentales organizados en estructuras basadas en árboles y operados por operadores de AG adecuadamente definidos). En 1988, John Koza (también estudiante de doctorado de John Holland) patentó su invención de un AG para la evolución de programas. [5] Esto fue seguido por la publicación en la Conferencia Conjunta Internacional sobre Inteligencia Artificial IJCAI-89. [6]
Koza continuó con 205 publicaciones sobre “Programación Genética” (PG), nombre acuñado por David Goldberg, también estudiante de doctorado de John Holland. [7] Sin embargo, es la serie de 4 libros de Koza, que comenzó en 1992 [8] con videos que los acompañaban, [9] lo que realmente estableció la PG. Posteriormente, hubo una enorme expansión del número de publicaciones con la Bibliografía de Programación Genética, superando las 10.000 entradas. [10] En 2010, Koza [11] enumeró 77 resultados donde la Programación Genética era competitiva para los humanos.
En 1996, Koza inició la conferencia anual de Programación Genética [12] , a la que siguió en 1998 la conferencia anual EuroGP [13] y el primer libro [14] de una serie sobre Programación Genética editado por Koza. En 1998 también se publicó el primer libro de texto sobre Programación Genética [15] . La Programación Genética siguió floreciendo, lo que dio lugar a la primera revista especializada sobre Programación Genética [16] y tres años más tarde (2003) Rick Riolo estableció el taller anual sobre Teoría y Práctica de la Programación Genética (GPTP). [17] [18] Se siguen publicando artículos sobre Programación Genética en una diversidad de conferencias y revistas asociadas. Hoy en día hay diecinueve libros sobre Programación Genética, incluidos varios para estudiantes. [15]
Los primeros trabajos que sentaron las bases para los temas y aplicaciones de investigación actuales en programación genética son diversos e incluyen síntesis y reparación de software, modelado predictivo, minería de datos, [19] modelado financiero, [20] sensores blandos, [21] diseño, [22] y procesamiento de imágenes. [23] Las aplicaciones en algunas áreas, como el diseño, a menudo hacen uso de representaciones intermedias, [24] como la codificación celular de Fred Gruau. [25] La adopción industrial ha sido significativa en varias áreas, incluidas las finanzas, la industria química, la bioinformática [26] [27] y la industria del acero. [28]
GP evoluciona programas de computadora, tradicionalmente representados en memoria como estructuras de árbol . [29] Los árboles pueden evaluarse fácilmente de manera recursiva. Cada nodo interno tiene una función de operador y cada nodo terminal tiene un operando, lo que hace que las expresiones matemáticas sean fáciles de desarrollar y evaluar. Por lo tanto, tradicionalmente GP favorece el uso de lenguajes de programación que incorporan naturalmente estructuras de árbol (por ejemplo, Lisp ; otros lenguajes de programación funcional también son adecuados).
Se han sugerido e implementado con éxito representaciones no arbóreas, como la programación genética lineal que quizás se adapte a los lenguajes imperativos más tradicionales . [30] [31] El software GP comercial Discipulus utiliza la inducción automática de código binario de máquina ("AIM") [32] para lograr un mejor rendimiento. μGP [33] utiliza multigrafos dirigidos para generar programas que explotan completamente la sintaxis de un lenguaje ensamblador dado . La programación de múltiples expresiones utiliza un código de tres direcciones para codificar soluciones. Otras representaciones de programas en las que se han realizado investigaciones y desarrollos importantes incluyen programas para máquinas virtuales basadas en pilas, [34] [35] [36] y secuencias de números enteros que se asignan a lenguajes de programación arbitrarios a través de gramáticas. [37] [38] La programación genética cartesiana es otra forma de GP, que utiliza una representación gráfica en lugar de la representación habitual basada en árboles para codificar programas de computadora.
La mayoría de las representaciones tienen un código estructuralmente no efectivo ( intrones ). Estos genes no codificantes pueden parecer inútiles porque no tienen efecto sobre el rendimiento de ningún individuo. Sin embargo, alteran las probabilidades de generar diferentes descendientes bajo los operadores de variación y, por lo tanto, alteran las propiedades variacionales del individuo . Los experimentos parecen mostrar una convergencia más rápida cuando se utilizan representaciones de programas que permiten estos genes no codificantes, en comparación con las representaciones de programas que no tienen ningún gen no codificante. [39] [40] Las instancias pueden tener árboles con intrones y sin ellos; estos últimos se denominan árboles canónicos. Se introducen operadores de cruce canónicos especiales que mantienen la estructura canónica de los padres en sus hijos.
La selección es un proceso mediante el cual se seleccionan ciertos individuos de la generación actual que servirán como padres para la próxima generación. Los individuos se seleccionan de manera probabilística, de modo que los individuos con mejor desempeño tienen una mayor probabilidad de ser seleccionados. [18] El método de selección más comúnmente utilizado en GP es la selección por torneo , aunque se ha demostrado que otros métodos como la selección proporcional a la aptitud , la selección de lexicase, [41] y otros funcionan mejor para muchos problemas de GP.
El elitismo, que implica sembrar la siguiente generación con el mejor individuo (o los mejores n individuos) de la generación actual, es una técnica que a veces se emplea para evitar la regresión.
En la programación genética, se eligen dos individuos aptos de la población para que sean los padres de uno o dos hijos. En la programación genética de árboles, estos padres se representan como árboles de tipo lisp invertido, con sus nodos raíz en la parte superior. En el cruce de subárboles, en cada padre se elige un subárbol al azar. (Resaltado en amarillo en la animación). En el padre donante de raíces (en la animación de la izquierda), el subárbol elegido se elimina y se reemplaza con una copia del subárbol elegido al azar del otro padre, para dar un nuevo árbol hijo.
A veces se utiliza el cruce de dos árboles secundarios, en cuyo caso el subárbol eliminado (en la animación de la izquierda) no se elimina simplemente, sino que se copia en una copia del segundo árbol primario (aquí a la derecha) reemplazando (en la copia) su subárbol elegido aleatoriamente. Por lo tanto, este tipo de cruce de subárboles toma dos árboles adecuados y genera dos árboles secundarios.
Algunos individuos seleccionados según criterios de aptitud no participan en el cruce, sino que se copian en la siguiente generación, de forma similar a la reproducción asexual en el mundo natural. Además, pueden estar sujetos a mutaciones.
Existen muchos tipos de mutaciones en la programación genética. Comienzan con un padre sintácticamente correcto y tienen como objetivo crear aleatoriamente un hijo sintácticamente correcto. En la animación, se elige aleatoriamente un subárbol (resaltado en amarillo). Se lo elimina y se lo reemplaza por un subárbol generado aleatoriamente.
Otros operadores de mutación seleccionan una hoja (nodo externo) del árbol y la reemplazan por una hoja elegida al azar. Otra mutación consiste en seleccionar al azar una función (nodo interno) y reemplazarla por otra función con la misma aridad (número de entradas). La mutación de elevación elige al azar un subárbol y lo reemplaza por un subárbol dentro de sí mismo. Por lo tanto, se garantiza que la mutación de elevación hará que el hijo sea más pequeño. El reemplazo de la hoja y la función con la misma aridad garantiza que el hijo tenga el mismo tamaño que el padre. Mientras que la mutación de subárbol (en la animación) puede, dependiendo de la función y los conjuntos terminales, tener un sesgo para aumentar o disminuir el tamaño del árbol. Otras mutaciones basadas en subárboles intentan controlar cuidadosamente el tamaño del subárbol de reemplazo y, por lo tanto, el tamaño del árbol hijo.
De manera similar, existen muchos tipos de mutación de programación genética lineal, cada uno de los cuales intenta garantizar que el niño mutado siga siendo sintácticamente correcto.
GP se ha utilizado con éxito como una herramienta de programación automática , una herramienta de aprendizaje automático y un motor automático de resolución de problemas. [18] GP es especialmente útil en los dominios donde la forma exacta de la solución no se conoce de antemano o una solución aproximada es aceptable (posiblemente porque encontrar la solución exacta es muy difícil). Algunas de las aplicaciones de GP son el ajuste de curvas, el modelado de datos, la regresión simbólica , la selección de características , la clasificación, etc. John R. Koza menciona 76 casos en los que la programación genética ha podido producir resultados que son competitivos con los resultados producidos por humanos (llamados resultados humanos-competitivos). [42] Desde 2004, la Conferencia anual de Computación Genética y Evolutiva ( GECCO ) celebra la competencia de Premios Humanos Competitivos (llamados Humies), [43] donde se otorgan premios en efectivo a los resultados humanos competitivos producidos por cualquier forma de computación genética y evolutiva. GP ha ganado muchos premios en esta competencia a lo largo de los años.
La programación metagenética es la técnica de metaaprendizaje propuesta para desarrollar un sistema de programación genética utilizando la propia programación genética. Sugiere que los cromosomas, el cruce y la mutación fueron ellos mismos evolucionados, por lo tanto, al igual que sus contrapartes de la vida real, se les debería permitir cambiar por sí mismos en lugar de ser determinados por un programador humano. La meta-GP fue propuesta formalmente por Jürgen Schmidhuber en 1987. [44] Eurisko de Doug Lenat es un esfuerzo anterior que puede ser la misma técnica. Es un algoritmo recursivo pero de terminación, lo que le permite evitar la recursión infinita. En el enfoque de "evolución autoconstructiva" para la programación metagenética, los métodos para la producción y variación de la descendencia están codificados dentro de los propios programas en evolución, y los programas se ejecutan para producir nuevos programas que se agregarán a la población. [35] [45]
Los críticos de esta idea suelen decir que este enfoque tiene un alcance demasiado amplio. Sin embargo, podría ser posible restringir el criterio de aptitud a una clase general de resultados y así obtener un GP evolucionado que produciría resultados para subclases de manera más eficiente. Esto podría tomar la forma de un GP metaevolucionado para producir algoritmos de caminata humana que luego se utilizarían para desarrollar algoritmos de carrera, salto, etc. humanos. El criterio de aptitud aplicado al GP meta sería simplemente uno de eficiencia.
{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)