En inteligencia artificial, la programación genética ( GP ) 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. Es esencialmente una técnica de búsqueda heurística que a menudo se describe como "escalada de colinas" [¿ según quién? ] [ cita requerida ] , es decir, buscar un programa óptimo o al menos adecuado entre el espacio de todos los 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 intercambiar partes aleatorias de pares seleccionados (padres) para producir descendientes nuevos y diferentes que se vuelven parte de la nueva generación de programas. La mutación implica la sustitución de alguna parte aleatoria de un programa por 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 de forma recursiva 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 programa de la mejor generación suele ser mejor que los programas de la mejor generación de generaciones anteriores. La terminación de la recursividad es cuando algún programa individual alcanza un nivel de aptitud o competencia predefinido.
Puede suceder, y sucede a menudo, que una ejecución particular del algoritmo dé como resultado una convergencia prematura a un máximo local que no es una solución globalmente óptima o incluso buena. Por lo general, se necesitan varias ejecuciones (decenas a cientos) para producir un resultado muy bueno. También puede ser necesario aumentar el tamaño de la población inicial y la variabilidad de los individuos para evitar patologías.
Historia
El primer registro de la propuesta para desarrollar programas es probablemente el de Alan Turing en 1950. [1] Hubo una brecha de 25 años antes de la publicación de 'Adaptation in Natural and Artificial Systems' de John Holland, que establecía 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 las pruebas de la escena del crimen para el Ministerio del Interior del Reino Unido. [2]
Aunque la idea de desarrollar programas, inicialmente en el lenguaje informático Lisp , era corriente entre los estudiantes de John Holland, [3] no fue hasta que organizaron la primera conferencia de algoritmos genéticos (GA) en Pittsburgh que Nichael Cramer [4] publicó programas evolucionados en dos lenguajes especialmente diseñados, que incluían la primera declaración de la programación genética moderna "basada en árboles" (es decir, lenguajes procedimentales 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 de programas. [5] A esto le siguió la publicación en la Conferencia Internacional Conjunta sobre Inteligencia Artificial IJCAI-89. [6]
Koza siguió esto con 205 publicaciones sobre “Programación genética” (GP), 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 de acompañamiento, [9] lo que realmente estableció a GP. Posteriormente, hubo una enorme expansión del número de publicaciones con Bibliografía de Programación Genética, superando las 10.000 entradas. [10] En 2010, Koza [11] enumeró 77 resultados en los que 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 GP editada por Koza. 1998 también vio el primer libro de texto GP. [15] GP continuó floreciendo, lo que llevó a la primera revista especializada en GP [16] y tres años más tarde (2003) Rick Riolo estableció el taller anual de teoría y práctica de la programación genética (GPTP). [17] [18] Los artículos sobre programación genética continúan publicándose en una diversidad de conferencias y revistas asociadas. Hoy en día hay diecinueve libros de medicina general, incluidos varios para estudiantes. [15]
Trabajo fundacional en GP
El trabajo inicial que preparó el escenario 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, 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 aceptació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]
Métodos
Representación del programa
GP desarrolla programas de computadora, tradicionalmente representados en la memoria como estructuras de árbol . [29] Los árboles se pueden evaluar fácilmente de forma recursiva. Cada nodo de á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 evolucionar y evaluar. Así, tradicionalmente, GP favorece el uso de lenguajes de programación que incorporan naturalmente estructuras de árbol (por ejemplo, Lisp ; otros lenguajes de programación funcionales también son adecuados).
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)]. [30] El software comercial de GP Discipulus utiliza la inducción automática de código binario de máquina ("AIM") [31] para lograr un mejor rendimiento. µGP [32] usa multigrafos dirigidos para generar programas que explotan completamente la sintaxis de un lenguaje ensamblador dado . Otras representaciones de programas en las que se han realizado importantes investigaciones y desarrollos incluyen programas para máquinas virtuales basadas en pilas, [33] [34] [35] y secuencias de números enteros que se asignan a lenguajes de programación arbitrarios mediante gramáticas. [36] [37] 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 ningún efecto sobre el desempeño de ningún individuo. Sin embargo, alteran las probabilidades de generar descendencia diferente bajo los operadores de variación y, por lo tanto, alteran las propiedades de variación del individuo . Los experimentos parecen mostrar una convergencia más rápida cuando se utilizan representaciones de programas que permiten tales genes no codificantes, en comparación con representaciones de programas que no tienen genes no codificantes. [38] [39]
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 probabilísticamente de modo que los individuos con mejor desempeño tengan una mayor probabilidad de ser seleccionados. [18] El método de selección más comúnmente utilizado en GP es la selección de torneos , aunque se ha demostrado que otros métodos como la selección proporcional a la aptitud , la selección de lexicasa, [40] y otros funcionan mejor para muchos problemas de GP.
El elitismo, que implica 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
Se aplican varios operadores genéticos (es decir, cruzamiento y mutación) a los individuos seleccionados en el paso de selección descrito anteriormente para criar nuevos individuos. La tasa de aplicación de estos operadores determina la diversidad de la población.
Mutación
Voltee uno o más bits de la descendencia anterior para generar un nuevo hijo o una generación.
Aplicaciones
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 (denominados Human -resultados competitivos). [41] Desde 2004, la Conferencia anual de Computación Genética y Evolutiva (GECCO) celebra la competencia Human Competitive Awards (llamada Humies), [42] donde se otorgan premios en efectivo a los resultados de competencia humana 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
Meta-programación genética es la propuesta de aprendizaje meta técnica de la evolución de un sistema de programación genética utilizando programación genética en sí. Sugiere que los cromosomas, el cruce y la mutación fueron evolucionados, por lo tanto, al igual que sus contrapartes de la vida real, deberían poder cambiar por sí mismos en lugar de ser determinados por un programador humano. Meta-GP fue propuesto formalmente por Jürgen Schmidhuber en 1987. [43] El Eurisko de Doug Lenat es un esfuerzo anterior que puede ser la misma técnica. Es un algoritmo recursivo pero terminante, lo que le permite evitar la recursividad infinita. En el enfoque de la "evolución autoconstructiva" para la programación metagenética, los métodos para la producción y variación de la descendencia se codifican 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. [34] [44]
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 aptitud 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 médico de cabecera metaevolucionado para producir algoritmos de marcha humana que luego se utilizan para hacer evolucionar la carrera humana, el salto, etc. El criterio de aptitud aplicado al médico de cabecera meta sería simplemente de eficiencia.
Ver también
- Computación bioinspirada
- Estrategia de evolución de adaptación de la matriz de covarianza (CMA-ES)
- Aproximación de aptitud
- Programación de expresión genética
- Mejora genética
- Representación genética
- Evolución gramatical
- Programación inductiva
- Programación genética lineal
- Programación de expresiones múltiples
- Propagación de esquema
Referencias
- ^ "Inteligencia y maquinaria informática" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ "BEAGLE Un enfoque darwiniano para el reconocimiento de patrones" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ Una comunicación personal con Tom Westerdale
- ^ "Una representación para la generación adaptativa de programas secuenciales simples" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ "Algoritmos genéticos no lineales para la resolución de problemas" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ "Algoritmos genéticos jerárquicos que operan en poblaciones de programas informáticos" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ Goldberg. DE (1983), Operación de gasoductos asistida por computadora utilizando algoritmos genéticos y aprendizaje de reglas. Disertación presentada a la Universidad de Michigan en Ann Arbor, Michigan, en cumplimiento parcial de los requisitos para Ph.D.
- ^ "Programación genética: sobre la programación de ordenadores mediante selección natural" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ "Programación genética: la película" . gpbib.cs.ucl.ac.uk . Consultado el 20 de mayo de 2021 .
- ^ "Los efectos de la recombinación en la exploración fenotípica y la robustez en la evolución" . gpbib.cs.ucl.ac.uk . Consultado el 20 de mayo de 2021 .
- ^ "Resultados competitivos humanos producidos por programación genética" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "Programación genética 1996: Actas de la Primera Conferencia Anual" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ "Programación genética" . www.cs.bham.ac.uk . Consultado el 19 de mayo de 2018 .
- ^ "Programación genética y estructuras de datos: Programación genética + Estructuras de datos = Programación automática". . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ a b "Programación genética - Introducción; sobre la evolución automática de programas informáticos y sus aplicaciones" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ Banzhaf, Wolfgang (1 de abril de 2000). "Introducción editorial". Programación genética y máquinas evolutivas . 1 (1–2): 5–6. doi : 10.1023 / A: 1010026829303 . ISSN 1389-2576 .
- ^ "Teoría y práctica de la programación genética" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ a b c "Una guía de campo para la programación genética" . www.gp-field-guide.org.uk . Consultado el 20 de mayo de 2018 .
- ^ "Minería de datos y descubrimiento de conocimiento con algoritmos evolutivos" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "EDDIE gana a los corredores de apuestas" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "Aplicar la inteligencia computacional cómo crear valor" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "Invención de la máquina competitiva humana por medio de la programación genética" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "Descubrimiento de programas de extracción de características de textura de imagen competitiva humana utilizando programación genética" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "Tres formas de hacer crecer diseños: una comparación de embriogenias para un problema de diseño evolutivo" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "La codificación celular como gramática gráfica - Publicación de la conferencia IET" . ieeexplore.ieee.org . Abril de 1993. págs. 17 / 1–1710 . Consultado el 20 de mayo de 2018 .
- ^ "Decodificación de algoritmos genéticos para la interpretación de espectros infrarrojos en biotecnología analítica" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "Programación genética para la minería de datos de chips de ADN de pacientes con cáncer" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ "Programación genética y modelado de pruebas Jominy" . www.cs.bham.ac.uk . Consultado el 20 de mayo de 2018 .
- ^ Nichael L. Cramer "Una representación para la generación adaptativa de programas secuenciales simples" Archivado 2005-12-04 en Wayback Machine .
- ^ Garnett Wilson y Wolfgang Banzhaf. "Una comparación de la programación genética cartesiana y la programación genética lineal" .
- ↑ ( Peter Nordin , 1997, Banzhaf et al., 1998, Sección 11.6.2-11.6.3)
- ^ Giovanni Squillero. "µGP (MicroGP)" .
- ^ "Programación genética basada en pilas" . gpbib.cs.ucl.ac.uk . Consultado el 20 de mayo de 2021 .
- ^ a b Spector, Lee; Robinson, Alan (1 de marzo de 2002). "Programación genética y evolución autoconstructiva con el lenguaje de programación Push". Programación genética y máquinas evolutivas . 3 (1): 7–40. doi : 10.1023 / A: 1014538503543 . ISSN 1389-2576 . S2CID 5584377 .
- ^ Spector, Lee; Klein, Jon; Keijzer, Maarten (25 de junio de 2005). La pila de ejecución Push3 y la evolución del control . ACM. págs. 1689-1696. CiteSeerX 10.1.1.153.384 . doi : 10.1145 / 1068009.1068292 . ISBN 978-1595930101. S2CID 11954638 .
- ^ Ryan, Conor; Collins, JJ; Neill, Michael O (1998). Apuntes de conferencias en informática . Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 83–96. CiteSeerX 10.1.1.38.7697 . doi : 10.1007 / bfb0055930 . ISBN 9783540643609.
- ^ O'Neill, M .; Ryan, C. (2001). "Evolución gramatical". Transacciones IEEE sobre Computación Evolutiva . 5 (4): 349–358. doi : 10.1109 / 4235.942529 . ISSN 1089-778X . S2CID 10391383 .
- ^ Julian F. Miller. "Programación genética cartesiana" . pag. 19.
- ^ Janet Clegg; James Alfred Walker; Julian Francis Miller. Una nueva técnica cruzada para la programación genética cartesiana " . 2007.
- ^ Spector, Lee (2012). Evaluación de la modalidad del problema por desempeño diferencial de la selección de lexicasa en la programación genética: un informe preliminar . Actas de la 14ª Conferencia Anual Companion on Genetic and Evolutionary Computation . Gecco '12. ACM. págs. 401–408. doi : 10.1145 / 2330784.2330846 . ISBN 9781450311786. S2CID 3258264 .
- ^ Koza, John R. (2010). "Resultados competitivos humanos producidos por programación genética" . Programación genética y máquinas evolutivas . 11 (3–4): 251–284. doi : 10.1007 / s10710-010-9112-3 .
- ^ "Humn = Human-Competitive Awards" .
- ^ "1987 TESIS DE APRENDER A APRENDER, METALAPRENDIZAJE, PROGRAMACIÓN META GENÉTICA, ECONOMÍA DEL APRENDIZAJE MÁQUINA CONSERVADORA DEL CRÉDITO" .
- ^ Acompañante de GECCO '16: actas de la Conferencia de Computación Genética y Evolutiva 2016: 20-24 de julio de 2016, Denver, Colorado, EE . UU . Neumann, Frank (informático), Association for Computing Machinery. SIGEVO. Nueva York, Nueva York. ISBN 9781450343237. OCLC 987011786 .CS1 maint: otros ( enlace )
enlaces externos
- Aymen S Saket y Mark C Sinclair
- Programación genética y máquinas evolutivas , una revista
- Evo2 para programación genética
- Bibliografía GP
- La guía del autoestopista para la computación evolutiva
- Riccardo Poli, William B. Langdon, Nicholas F. McPhee, John R. Koza, " Una guía de campo para la programación genética " (2008)
- Programación genética, un recurso mantenido por la comunidad