Computación evolutiva

La computación evolutiva (CE) de la informática es una familia de algoritmos para la optimización global inspirados en la evolución biológica , y un subcampo de la inteligencia computacional y la computación blanda que estudia estos algoritmos. ^{[ 1 ] [ 2 ] [ 3 ]} En términos técnicos, son una familia de solucionadores de problemas de ensayo y error basados ​​en poblaciones con un carácter metaheurístico o de optimización estocástica .

En la computación evolutiva, se genera un conjunto inicial de soluciones candidatas que se actualiza iterativamente. Cada nueva generación se produce eliminando estocásticamente las soluciones menos deseables e introduciendo pequeños cambios aleatorios , además de, según el método, mezclar información parental . En terminología biológica, una población de soluciones está sujeta a selección natural (o selección artificial ), mutación y posiblemente recombinación . Estas funciones biológicas sirven como modelos para los operadores genéticos ( mutación , cruce y selección ) utilizados en los procedimientos de computación evolutiva. Como resultado, la población evolucionará gradualmente para aumentar su aptitud , en este caso la función de aptitud elegida por el algoritmo.

Las técnicas de computación evolutiva pueden generar soluciones altamente optimizadas en una amplia gama de problemas, lo que las hace populares en la informática . Existen numerosas variantes y extensiones, adaptadas a familias de problemas y estructuras de datos más específicas. La computación evolutiva también se utiliza a veces en biología evolutiva como un procedimiento experimental in silico para estudiar aspectos comunes de los procesos evolutivos generales.

El concepto de imitar procesos evolutivos para resolver problemas se originó antes de la llegada de las computadoras, como cuando Alan Turing propuso un método de búsqueda genética en 1948. ^{[ 4 ]} Las máquinas u de tipo B de Turing se asemejan a redes neuronales primitivas , y las conexiones entre neuronas se aprendían mediante una especie de algoritmo genético . Sus máquinas u de tipo P se asemejan a un método de aprendizaje por refuerzo , donde las señales de placer y dolor dirigen a la máquina para aprender ciertos comportamientos. Sin embargo, el artículo de Turing permaneció inédito hasta 1968, y él falleció en 1954, por lo que este trabajo inicial tuvo poca o ninguna influencia en el campo de la computación evolutiva que se desarrollaría posteriormente. ^{[ 5 ]}

La computación evolutiva como campo de estudio comenzó en serio en las décadas de 1950 y 1960. ^{[ 4 ]} En ese momento, hubo varios intentos independientes de utilizar el proceso de evolución en la computación, los cuales se desarrollaron por separado durante aproximadamente 15 años. Tres ramas surgieron en diferentes lugares para lograr este objetivo: estrategias evolutivas , programación evolutiva y algoritmos genéticos . Una cuarta rama, la programación genética , surgió finalmente a principios de la década de 1990. Estos enfoques difieren en el método de selección, las mutaciones permitidas y la representación de los datos genéticos. Para la década de 1990, las distinciones entre las ramas históricas habían comenzado a desdibujarse, y el término "computación evolutiva" se acuñó en 1991 para designar un campo que existe en los cuatro paradigmas. ^{[ 6 ]}

En 1962, Lawrence J. Fogel inició la investigación de la Programación Evolutiva en Estados Unidos, considerada un campo de la inteligencia artificial . En este sistema, se utilizan máquinas de estados finitos para resolver un problema de predicción: estas máquinas se modifican (añadiendo o eliminando estados, o cambiando las reglas de transición de estados), y la mejor de estas máquinas modificadas evoluciona en generaciones futuras. La máquina de estados finitos final puede utilizarse para generar predicciones cuando sea necesario. El método de programación evolutiva se aplicó con éxito a problemas de predicción, identificación de sistemas y control automático. Posteriormente, se extendió para el manejo de datos de series temporales y para modelar la evolución de estrategias de juego. ^{[ 6 ]}

En 1964, Ingo Rechenberg y Hans-Paul Schwefel introdujeron el paradigma de las estrategias evolutivas en Alemania. ^{[ 6 ]} Dado que las técnicas tradicionales de descenso de gradiente producen resultados que pueden quedar atrapados en mínimos locales, Rechenberg y Schwefel propusieron que las mutaciones aleatorias (aplicadas a todos los parámetros de algún vector de solución) podrían utilizarse para escapar de estos mínimos. Se generaron soluciones hijas a partir de soluciones padre, y la más exitosa de las dos se conservó para generaciones futuras. Esta técnica fue utilizada por primera vez por ambos para resolver con éxito problemas de optimización en dinámica de fluidos . ^{[ 7 ]} Inicialmente, esta técnica de optimización se realizaba sin ordenadores, basándose en dados para determinar mutaciones aleatorias. En 1965, los cálculos se realizaban completamente por máquina. ^{[ 6 ]}

John Henry Holland introdujo los algoritmos genéticos en la década de 1960, y estos se desarrollaron aún más en la Universidad de Michigan en la década de 1970. ^{[ 8 ]} Mientras que otros enfoques se centraban en la resolución de problemas, Holland se propuso principalmente utilizar algoritmos genéticos para estudiar la adaptación y determinar cómo se podía simular. Las poblaciones de cromosomas, representadas como cadenas de bits, se transformaban mediante un proceso de selección artificial, seleccionando bits de "alelos" específicos en la cadena de bits. Entre otros métodos de mutación, se utilizaron interacciones entre cromosomas para simular la recombinación de ADN entre diferentes organismos. Mientras que los métodos anteriores solo rastreaban un único organismo óptimo a la vez (haciendo que los hijos compitieran con los padres), los algoritmos genéticos de Holland rastreaban grandes poblaciones (haciendo que muchos organismos compitieran en cada generación).

En la década de 1990, surgió un nuevo enfoque para la computación evolutiva que llegó a denominarse programación genética , defendido, entre otros, por John Koza . ^{[ 6 ]} En esta clase de algoritmos, el objeto de la evolución era en sí mismo un programa escrito en un lenguaje de programación de alto nivel (ya en 1958 se habían realizado algunos intentos previos de utilizar código máquina, pero tuvieron poco éxito). Para Koza, los programas eran expresiones S de Lisp , que pueden considerarse como árboles de subexpresiones. Esta representación permite a los programas intercambiar subárboles, lo que representa una especie de mezcla genética. Los programas se puntúan en función de su eficacia para completar una tarea determinada, y la puntuación se utiliza para la selección artificial. La inducción de secuencias, el reconocimiento de patrones y la planificación fueron aplicaciones exitosas del paradigma de la programación genética.

Muchas otras figuras desempeñaron un papel en la historia de la computación evolutiva, aunque su trabajo no siempre se ajustó a una de las principales ramas históricas del campo. Las primeras simulaciones computacionales de la evolución utilizando algoritmos evolutivos y técnicas de vida artificial fueron realizadas por Nils Aall Barricelli en 1953, con los primeros resultados publicados en 1954. ^{[ 9 ]} Otro pionero en la década de 1950 fue Alex Fraser , quien publicó una serie de artículos sobre la simulación de la selección artificial . ^{[ 10 ]} A medida que creció el interés académico, los aumentos drásticos en la potencia de las computadoras permitieron aplicaciones prácticas, incluida la evolución automática de programas informáticos. ^{[ 11 ]} Los algoritmos evolutivos se utilizan ahora para resolver problemas multidimensionales de manera más eficiente que el software producido por diseñadores humanos, y también para optimizar el diseño de sistemas. ^{[ 12 ] [ 13 ]}

Las técnicas de computación evolutiva implican principalmente algoritmos de optimización metaheurística . En términos generales, el campo incluye:

• Modelado basado en agentes
  • optimización de colonias de hormigas
  • Optimización por enjambre de partículas
  • Inteligencia de enjambre
• Sistemas inmunitarios artificiales
• vida artificial
  • Organismo digital
• algoritmos culturales
• Evolución diferencial
• Evolución de dos fases
• Algoritmo de estimación de distribución
• Algoritmo evolutivo
  • Algoritmo genético
  • Programación evolutiva
  • Programación genética
    • Programación de la expresión génica
    • Evolución gramatical
  • Estrategia de evolución
• Modelo de evolución aprendible
• Sistema de clasificación de aprendizaje
• Algoritmos meméticos
• Neuroevolución
• Autoorganización como mapas autoorganizados , aprendizaje competitivo

En los últimos años se han propuesto muchos algoritmos dudosos, que a menudo son simples copias de algoritmos existentes (frecuentemente de la Optimización por Enjambre de Partículas), donde solo cambia la metáfora, pero el algoritmo en sí no es nuevo en absoluto. Un catálogo exhaustivo con muchos de estos algoritmos dudosos se ha publicado en el Evolutionary Computation Bestiary . ^{[ 14 ]} También es importante señalar que muchos de estos algoritmos supuestamente "novedosos" tienen una validación experimental deficiente. ^{[ 15 ]}

Los algoritmos evolutivos constituyen un subconjunto de la computación evolutiva, ya que generalmente solo emplean técnicas que implementan mecanismos inspirados en la evolución biológica, como la reproducción , la mutación , la recombinación y la selección natural . Las soluciones candidatas al problema de optimización actúan como individuos en una población, y la función de coste determina el entorno en el que se desenvuelven dichas soluciones (véase también la función de aptitud ). La evolución de la población se produce tras la aplicación repetida de los operadores mencionados.

En este proceso, existen dos fuerzas principales que constituyen la base de los sistemas evolutivos: la recombinación (por ejemplo, el entrecruzamiento ) y la mutación crean la diversidad necesaria y, por lo tanto, facilitan la novedad, mientras que la selección actúa como una fuerza que aumenta la calidad.

Muchos aspectos de este proceso evolutivo son estocásticos . La información que cambia debido a la recombinación y la mutación se elige al azar. Por otro lado, los operadores de selección pueden ser deterministas o estocásticos. En este último caso, los individuos con mayor aptitud tienen más probabilidades de ser seleccionados que aquellos con menor aptitud , pero, por lo general, incluso los individuos más débiles tienen la posibilidad de convertirse en progenitores o de sobrevivir.

Los algoritmos genéticos proporcionan métodos para modelar sistemas biológicos y la biología de sistemas , vinculados a la teoría de sistemas dinámicos , ya que se utilizan para predecir los estados futuros del sistema. Esta es solo una forma ilustrativa (aunque quizás engañosa) de resaltar el carácter ordenado, controlado y altamente estructurado del desarrollo biológico.

Sin embargo, el uso de algoritmos e informática, en particular de la teoría computacional , más allá de la analogía con los sistemas dinámicos, también es relevante para comprender la evolución misma.

Esta perspectiva tiene el mérito de reconocer que no existe un control central del desarrollo; los organismos se desarrollan como resultado de interacciones locales dentro y entre las células. Las ideas más prometedoras sobre paralelismos entre el desarrollo de programas nos parecen aquellas que apuntan a una analogía aparentemente cercana entre los procesos dentro de las células y el funcionamiento de bajo nivel de las computadoras modernas. ^{[ 16 ]} Así, los sistemas biológicos son como máquinas computacionales que procesan información de entrada para calcular estados posteriores, de modo que los sistemas biológicos están más cerca de una computación que de un sistema dinámico clásico. ^{[ 17 ]}

Además, siguiendo conceptos de la teoría computacional , los microprocesos en los organismos biológicos son fundamentalmente incompletos e indecidibles ( completitud (lógica) ), lo que implica que “hay más que una simple metáfora detrás de la analogía entre células y computadoras. ^{[ 18 ]}

La analogía con la computación se extiende también a la relación entre los sistemas de herencia y la estructura biológica, que a menudo se considera que revela uno de los problemas más acuciantes para explicar los orígenes de la vida.

Los autómatas evolutivos ^{[ 19 ] [ 20 ] [ 21 ]} , una generalización de las máquinas de Turing evolutivas ^{[ 22 ] [ 23 ]} , se han introducido para investigar con mayor precisión las propiedades de la computación biológica y evolutiva. En particular, permiten obtener nuevos resultados sobre la expresividad de la computación evolutiva ^{[ 21 ] [ 24 ]} . Esto confirma el resultado inicial sobre la indecidibilidad de la evolución natural y los algoritmos y procesos evolutivos. Los autómatas finitos evolutivos , la subclase más simple de autómatas evolutivos que funcionan en modo terminal, pueden aceptar lenguajes arbitrarios sobre un alfabeto dado, incluidos los no recursivamente enumerables (por ejemplo, el lenguaje de diagonalización) y los recursivamente enumerables pero no recursivos (por ejemplo, el lenguaje de la máquina de Turing universal) ^{[ 25 ]} .

La lista de investigadores activos es naturalmente dinámica y no exhaustiva. En 2007 se publicó un análisis de la red de la comunidad. ^{[ 26 ]}

• Kalyanmoy Deb
• Kenneth A. De Jong
• Peter J. Fleming
• David B. Fogel
• Stephanie Forrest
• David E. Goldberg
• Juan Enrique Holanda
• Theo Jansen
• Juan Koza
• Zbigniew Michalewicz
• Melanie Mitchell
• Pedro Nordin
• Riccardo Poli
• Ingo Rechenberg
• Hans-Paul Schwefel

Si bien la literatura está plagada de artículos sobre computación evolutiva o que la utilizan, varias revistas especializadas se dedican exclusivamente a este campo:

• Computación Evolutiva (revista) (fundada en 1993, MIT Press )
• Vida Artificial (revista) (fundada en 1993, MIT Press )
• IEEE Transactions on Evolutionary Computation (fundada en 1997, IEEE )
• Programación genética y máquinas evolutivas (fundada en 2000, Springer Nature )
• Inteligencia de enjambre (fundada en 2007, Springer Nature )
• Inteligencia Evolutiva (fundada en 2008, Springer Nature )
• Revista de Evolución Artificial y Aplicaciones (2008–2010, Hindawi )
• Computación memética (fundada en 2009, Springer Nature )
• Revista Internacional de Computación Evolutiva Aplicada (fundada en 2010, fr:IGI Global )
• Computación Evolutiva y de Enjambres (fundada en 2011, Elsevier )
• Revista Internacional de Inteligencia de Enjambre y Computación Evolutiva (fundada en 2012, Walsh Medical Media )

Las principales conferencias en el área de computación evolutiva incluyen:

• Conferencia de Computación Genética y Evolutiva de la ACM (GECCO),
• Congreso IEEE sobre Computación Evolutiva (CEC),
• EvoStar , que comprende cuatro conferencias: EuroGP, EvoApplications, EvoCOP y EvoMUSART,
• Resolución paralela de problemas inspirada en la naturaleza (PPSN).

• Th. Bäck, DB Fogel y Z. Michalewicz (editores), Manual de computación evolutiva , 1997, ISBN 0750303921
• Th. Bäck y H.-P. Schwefel. Una visión general de los algoritmos evolutivos para la optimización de parámetros . Archivado el 12 de julio de 2018 en Wayback Machine Evolutionary Computation, 1(1):1–23, 1993.
• W. Banzhaf, P. Nordin, RE Keller y FD Francone. Programación genética: una introducción. Morgan Kaufmann, 1998.
• S. Cagnoni, et al., Aplicaciones en el mundo real de la computación evolutiva , Springer-Verlag Lecture Notes in Computer Science , Berlín, 2000.
• R. Chiong, Th. Weise, Z. Michalewicz (editores), Variantes de algoritmos evolutivos para aplicaciones del mundo real , Springer , 2012, ISBN 3642234232
• KA De Jong, Computación evolutiva: un enfoque unificado. MIT Press , Cambridge, MA, 2006.
• AE Eiben y JE Smith, De la computación evolutiva a la evolución de las cosas , Nature, 521:476-482, doi:10.1038/nature14544, 2015
• AE Eiben y JE Smith, Introducción a la computación evolutiva, Springer, Primera edición , 2003; Segunda edición , 2015
• DB Fogel. Computación evolutiva. Hacia una nueva filosofía de la inteligencia artificial . IEEE Press, Piscataway, NJ, 1995.
• LJ Fogel, AJ Owens y MJ Walsh. Inteligencia artificial mediante evolución simulada . Nueva York: John Wiley, 1966.
• DE Goldberg. Algoritmos genéticos en búsqueda, optimización y aprendizaje automático. Addison Wesley, 1989.
• JH Holland. Adaptación en sistemas naturales y artificiales. University of Michigan Press , Ann Arbor, 1975.
• P. Hingston, L. Barone y Z. Michalewicz (editores), Diseño por evolución, Serie de computación natural , 2008, Springer , ISBN 3540741097
• JR Koza. Programación genética: Sobre la programación de computadoras mediante la evolución natural. MIT Press, Massachusetts, 1992.
• FJ Lobo, CF Lima, Z. Michalewicz (Editores), Configuración de parámetros en algoritmos evolutivos , Springer , 2010, ISBN 3642088929
• Z. Michalewicz , Algoritmos genéticos + Estructuras de datos – Programas evolutivos , 1996, Springer , ISBN 3540606769
• Z. Michalewicz y DB Fogel, Cómo resolverlo: Heurísticas modernas , Springer , 2004, ISBN 978-3-540-22494-5
• I. Rechenberg. Estrategia de evolución: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Stuttgart, 1973. (en alemán)
• H.-P. Schwefel. Optimización numérica de modelos informáticos. John Wiley & Sons, Nueva York, 1981. 1995 – 2ª edición.
• D. Simon. Algoritmos de optimización evolutiva. Archivado el 10 de marzo de 2014 en Wayback Machine . Wiley, 2013.
• M. Sipper; W. Fu; K. Ahuja; JH Moore (2018). "Investigando el espacio de parámetros de los algoritmos evolutivos" . BioData Mining . 11 2. doi : 10.1186/s13040-018-0164-x . PMC  5816380. PMID  29467825 .
• Y. Zhang; S. Li. (2017). "PSA: Un nuevo algoritmo de optimización basado en las reglas de supervivencia de Porcellio scaber". arXiv : 1709.09840 [ cs.NE ].

• Artículo de la Enciclopedia de Filosofía de Stanford sobre Información Biológica (en inglés)