Programación genética

En inteligencia artificial, la programación genética es una técnica de programas en evolución, a partir de una población de programas no aptos (generalmente aleatorios), aptos para una tarea particular 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) y la mutación de acuerdo con una medida de aptitud predefinida, generalmente competencia en la tarea deseada. La operación de cruce implica el intercambio aleatorio de partes de parejas seleccionadas (padres) para producir descendientes nuevos y diferentes que se convierten en parte de la nueva generación de programas. La mutación implica la sustitución de alguna parte aleatoria de un programa por alguna otra parte aleatoria de un programa. Algunos programas no seleccionados para reproducción se copian de la generación actual a la nueva generación. 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 generación suele ser mejor que los mejores programas de generación de generaciones anteriores. La terminación de la evolución generalmente ocurre cuando algún programa individual alcanza un nivel de aptitud o aptitud predefinido.

Puede suceder, ya menudo sucede, que una ejecución particular del algoritmo dé como resultado una convergencia prematura a algún máximo local que no sea una solución globalmente óptima o incluso buena. Por lo general, se necesitan varias 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.

Historia

El primer registro de la propuesta de desarrollar programas es probablemente el de Alan Turing en 1950. Hubo una brecha de 25 años antes de que la publicación de 'Adaptación en sistemas naturales y artificiales' de John Holland estableciera los fundamentos teóricos y empíricos de la ciencia. En 1981, Richard Forsyth demostró la exitosa evolución de pequeños programas, representados como árboles, para realizar la clasificación de la evidencia de la escena del crimen para el Ministerio del Interior del Reino Unido.

Aunque la idea de desarrollar programas, inicialmente en el lenguaje informático Lisp, era corriente entre los estudiantes de John Holland, no fue hasta que organizaron la primera conferencia sobre algoritmos genéticos (GA) en Pittsburgh que Nichael Cramer publicó programas evolucionados en dos lenguajes especialmente diseñados, que incluyó la primera declaración de la programación genética moderna "basada en árboles" (es decir, lenguajes de procedimiento organizados en estructuras basadas en árboles y operados por operadores GA adecuadamente definidos). En 1988, John Koza (también estudiante de doctorado de John Holland) patentó su invención de un GA para la evolución del programa. A esto le siguió la publicación en la Conferencia Internacional Conjunta sobre Inteligencia Artificial IJCAI-89.

Koza siguió con 205 publicaciones sobre “Programación genética” (GP), nombre acuñado por David Goldberg, también estudiante de doctorado de John Holland. Sin embargo, es la serie de 4 libros de Koza, que comenzó en 1992 con videos adjuntos, lo que realmente estableció a GP. Posteriormente, se produjo una enorme expansión del número de publicaciones con la Bibliografía de Programación Genética, superando las 10.000 entradas. En 2010, Koza enumeró 77 resultados en los que la programación genética era competitiva humana.

En 1996, Koza inició la conferencia anual de Programación Genética, a la que siguió en 1998 la conferencia anual EuroGP y el primer libro de una serie de GP editada por Koza. 1998 también vio el primer libro de texto de GP. GP siguió floreciendo, lo que llevó a la primera revista especializada en GP y tres años más tarde (2003) Rick Riolo estableció el taller anual Teoría y práctica de la programación genética (GPTP). Se siguen publicando artículos sobre programación genética en diversas conferencias y revistas asociadas. Hoy en día hay diecinueve libros de GP, incluidos varios para estudiantes.

Trabajo fundacional en GP

El trabajo inicial que sentó las bases para los temas y aplicaciones actuales de investigación de programación genética es diverso e incluye síntesis y reparación de software, modelado predictivo, extracción de datos, modelado financiero, sensores blandos, diseño y procesamiento de imágenes. Las aplicaciones en algunas áreas, como el diseño, a menudo hacen uso de representaciones intermedias, como la codificación celular de Fred Gruau. La aceptación industrial ha sido significativa en varias áreas, incluidas las finanzas, la industria química, la bioinformática y la industria del acero.

Métodos

Representación del programa

GP desarrolla programas de computadora, tradicionalmente representados en la memoria como estructuras de árbol. Los árboles se pueden evaluar fácilmente de forma recursiva. Cada nodo del árbol 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. Así, tradicionalmente, GP favorece el uso de lenguajes de programación que incorporan estructuras de árbol de forma natural (por ejemplo, Lisp; también son adecuados otros lenguajes de programación funcionales).

Se han sugerido e implementado con éxito representaciones que no son árboles, como la programación genética lineal que se adapta a los lenguajes imperativos más tradicionales [ver, por ejemplo, Banzhaf et al. (1998)]. El software comercial de GP Discipulus utiliza la inducción automática de código de máquina binario ("AIM") para lograr un mejor rendimiento. µGP usa multigrafos dirigidos para generar programas que explotan completamente la sintaxis de un lenguaje ensamblador dado. La programación de expresiones múltiples utiliza un código de tres direcciones para codificar soluciones. Otras representaciones de programas en las que se han llevado a cabo importantes investigaciones y desarrollos incluyen programas para máquinas virtuales basadas en pilas,y secuencias de números enteros que se asignan a lenguajes de programación arbitrarios a través de gramáticas. 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 informáticos.

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 ningún 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 usan representaciones de programas que permiten tales genes no codificantes, en comparación con representaciones de programas que no tienen genes no codificantes.

Selección

La selección es un proceso mediante el cual se seleccionan ciertos individuos de la generación actual que servirían 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 tengan una mayor probabilidad de ser seleccionados. El método de selección más utilizado en GP es la selección de torneo, aunque se ha demostrado que otros métodos, como la selección proporcional de aptitud, la selección de lexicase y otros, funcionan mejor para muchos problemas de GP.

El elitismo, que consiste en sembrar la próxima 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.

Transversal

En la Programación Genética se eligen dos individuos aptos de la población para ser padres de uno o dos hijos. En la programación genética de árboles, estos padres se representan como árboles ceceosos invertidos, con sus nodos raíz en la parte superior. En el cruce de subárboles en cada padre, se elige aleatoriamente un subárbol. (Resaltado en amarillo en la animación). En el padre donante raíz (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 usa el cruce de dos hijos, 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 padre (aquí a la derecha) reemplazando (en la copia) su elegido al azar subárbol. Por lo tanto, este tipo de cruce de subárboles toma dos árboles de ajuste y genera dos árboles secundarios.

Mutación

Hay muchos tipos de mutaciones en la programación genética. Comienzan con un padre adecuado 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 elimina y se reemplaza por un subárbol generado aleatoriamente.

Otros operadores de mutación seleccionan una hoja (nodo externo) del árbol y la reemplazan con una hoja elegida al azar. Otra mutación es seleccionar al azar una función (nodo interno) y reemplazarla con otra función con la misma aridad (número de entradas). La mutación de elevación elige aleatoriamente un subárbol y lo reemplaza con un subárbol dentro de sí mismo. Por lo tanto, se garantiza que la mutación de elevación hará que el niño sea más pequeño. El reemplazo de la misma función de hoja y aridad garantiza que el niño tenga el mismo tamaño que el padre. Mientras que la mutación del subárbol (en la animación) puede, según la función y los conjuntos de 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 secundario.

De manera similar, hay muchos tipos de mutaciones de programación genética lineal, cada una de las cuales intenta garantizar que el niño mutado aún sea sintácticamente correcto.

Aplicaciones

GP se ha utilizado con éxito como herramienta de programación automática, herramienta de aprendizaje automático y motor de resolución automática de problemas. 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 instancias en las que la programación genética ha podido producir resultados que son competitivos con los resultados producidos por humanos (llamados humanos). -resultados competitivos). Desde 2004, la Conferencia anual de computación genética y evolutiva (GECCO) lleva a cabo la competencia Human Competitive Awards (llamada Humies),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 competición a lo largo de los años.

Programación metagenética

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 evolucionaron, por lo tanto, al igual que sus contrapartes de la vida real, se les debe permitir cambiar por sí mismos en lugar de ser determinados por un programador humano. Meta-GP fue propuesto formalmente por Jürgen Schmidhuber en 1987.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 recursividad infinita. En el enfoque de "evolución autoconstructiva" de 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.

Los críticos de esta idea a menudo dicen que este enfoque tiene un alcance demasiado amplio. Sin embargo, podría ser posible restringir el criterio de adecuación a una clase general de resultados, y así obtener un GP evolucionado que produciría resultados de manera más eficiente para las subclases. Esto podría tomar la forma de un GP meta evolucionado para producir algoritmos de caminata humana que luego se utilizan para evolucionar humanos corriendo, saltando, etc. El criterio de aptitud aplicado al meta GP sería simplemente uno de eficiencia.