Computación evolutiva

En informática , la computación evolutiva es una familia de algoritmos de optimización global inspirados en la evolución biológica , y el subcampo de la inteligencia artificial y la computación blanda que estudia estos algoritmos. En términos técnicos, son una familia de solucionadores de problemas de ensayo y error basados ​​en la población con un carácter de optimización metaheurística o estocástica .

En computación evolutiva, se genera un conjunto inicial de soluciones candidatas y se actualiza iterativamente. Cada nueva generación se produce eliminando estocásticamente las soluciones menos deseadas e introduciendo pequeños cambios aleatorios, así como, dependiendo del método, mezclando la 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 . Como resultado, la población evolucionará gradualmente para aumentar su aptitud , en este caso la función de aptitud elegida del algoritmo.

Las técnicas de computación evolutiva pueden producir soluciones altamente optimizadas en una amplia gama de situaciones problemáticas, lo que las hace populares en la ciencia informática . Existen muchas variantes y extensiones, adecuadas para familias más específicas de problemas y estructuras de datos. 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 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. ^[1] Las máquinas u de tipo B de Turing se asemejan a redes neuronales primitivas , y las conexiones entre neuronas se aprendieron a través de 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 que aprenda ciertos comportamientos. Sin embargo, el artículo de Turing no se publicó hasta 1968, y murió en 1954, por lo que este trabajo temprano tuvo poco o ningún efecto en el campo de la computación evolutiva que se desarrollaría. ^[2]

La computación evolutiva como campo comenzó a desarrollarse en serio en los años 1950 y 1960. ^[1] Hubo varios intentos independientes de utilizar el proceso de evolución en la computación en ese momento, que se desarrollaron por separado durante aproximadamente 15 años. Tres ramas surgieron en diferentes lugares para alcanzar este objetivo: estrategias de evolución , programación evolutiva y algoritmos genéticos . Una cuarta rama, la programación genética , finalmente surgió 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. En 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 denotar un campo que existe en los cuatro paradigmas. ^[3]

En 1962, Lawrence J. Fogel inició la investigación de la Programación Evolutiva en los Estados Unidos, que se consideró un esfuerzo de inteligencia artificial . En este sistema, se utilizan máquinas de estados finitos para resolver un problema de predicción: estas máquinas se mutarían (añadiendo o eliminando estados, o cambiando las reglas de transición de estados), y la mejor de estas máquinas mutadas se seguiría desarrollando en generaciones futuras. La máquina de estados finitos final se puede utilizar 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. Con el tiempo se amplió para manejar datos de series temporales y para modelar la evolución de estrategias de juego. ^[3]

En 1964, Ingo Rechenberg y Hans-Paul Schwefel introdujeron el paradigma de las estrategias de evolución en Alemania. ^[3] Dado que las técnicas tradicionales de descenso de gradiente producen resultados que pueden quedarse estancados en mínimos locales, Rechenberg y Schwefel propusieron que se pueden utilizar mutaciones aleatorias (aplicadas a todos los parámetros de algún vector de solución) para escapar de estos mínimos. Las soluciones hijas se generaban a partir de las soluciones madre, y la más exitosa de las dos se conservaba para las generaciones futuras. Esta técnica fue utilizada por primera vez por los dos para resolver con éxito problemas de optimización en dinámica de fluidos . ^[4] Inicialmente, esta técnica de optimización se realizaba sin computadoras, en su lugar se basaba en dados para determinar mutaciones aleatorias. En 1965, los cálculos se realizaban completamente a máquina. ^[3]

John Henry Holland introdujo algoritmos genéticos en la década de 1960, y los desarrolló aún más en la Universidad de Michigan en la década de 1970. ^[5] Mientras que los 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 transformaron mediante un proceso de selección artificial, seleccionando bits "alélicos" 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 de la computación evolutiva que llegó a llamarse programación genética , defendido por John Koza, entre otros. ^[3] En esta clase de algoritmos, el sujeto de la evolución era en sí mismo un programa escrito en un lenguaje de programación de alto nivel (ya en 1958 hubo algunos intentos previos de utilizar código de máquina, pero tuvieron poco éxito). Para Koza, los programas eran S-expresiones 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 califican en función de lo bien que completan una determinada tarea, 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 todas 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 encajó en 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. ^[6] Otro pionero en la década de 1950 fue Alex Fraser , quien publicó una serie de artículos sobre simulación de selección artificial . ^[7] A medida que crecía el interés académico, los aumentos dramáticos en la potencia de las computadoras permitieron aplicaciones prácticas, incluida la evolución automática de programas informáticos. ^[8] Los algoritmos evolutivos ahora se utilizan 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. ^{[9] [10]}

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

• Modelado basado en agentes
• Optimización de colonias de hormigas
• Sistemas inmunológicos artificiales
• Vida artificial (ver también organismo digital )
• Algoritmos culturales
• Algoritmo coevolutivo
• Evolución diferencial
• Evolución de dos fases
• Algoritmo de estimación de distribución
• Algoritmo evolutivo
• Programación evolutiva
• Estrategia de evolución
• Programación de la expresión genética
• Algoritmo genético
• Programación genética
• Evolución gramatical
• Modelo de evolución que se puede aprender
• Sistema clasificador de aprendizaje
• Algoritmos meméticos
• Neuroevolución
• Optimización de enjambre de partículas
• Búsqueda de antenas de escarabajo
• Autoorganización como mapas autoorganizativos , aprendizaje competitivo
• Inteligencia de enjambre

En el Bestiario de Computación Evolutiva se ha publicado un catálogo completo con muchos otros algoritmos propuestos recientemente. ^[11] Es importante señalar que muchos algoritmos recientes, sin embargo, tienen una validación experimental deficiente. ^[12]

Los algoritmos evolutivos forman un subconjunto de la computación evolutiva, ya que generalmente solo involucran técnicas que implementan mecanismos inspirados en la evolución biológica, como la reproducción , la mutación , la recombinación , la selección natural y la supervivencia del más apto . Las soluciones candidatas al problema de optimización desempeñan el papel de los individuos en una población, y la función de costo determina el entorno en el que "viven" las soluciones (ver también función de aptitud ). La evolución de la población tiene lugar luego de la aplicación repetida de los operadores anteriores.

En este proceso, hay dos fuerzas principales que forman la base de los sistemas evolutivos: la recombinación (por ejemplo, el cruce ) 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 . Los datos modificados debido a la recombinación y la mutación se eligen aleatoriamente. Por otra parte, los operadores de selección pueden ser deterministas o estocásticos. En este último caso, los individuos con una aptitud más alta tienen una mayor probabilidad de ser seleccionados que los individuos con una aptitud más baja , pero por lo general, incluso los individuos más débiles tienen una oportunidad de convertirse en padres o de sobrevivir.

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

Sin embargo, el uso de algoritmos y de la 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 los paralelismos entre programas y desarrollo nos parecen las que apuntan a una analogía aparentemente estrecha entre los procesos dentro de las células y el funcionamiento de bajo nivel de las computadoras modernas. ^[13] Por lo tanto, los sistemas biológicos son como máquinas computacionales que procesan información de entrada para calcular los estados siguientes, de modo que los sistemas biológicos están más cerca de un cómputo que de un sistema dinámico clásico. ^[14]

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 metáfora burda detrás de la analogía entre células y computadoras”. ^[15]

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 urgentes a la hora de explicar los orígenes de la vida.

Los autómatas evolutivos ^{[16] [17] [18]} , una generalización de las máquinas de Turing evolutivas ^{[19] [20]} , 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 ^{[18] [21]} . 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 los 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 lenguajes recursivamente enumerables pero no recursivos (por ejemplo, el lenguaje de la máquina de Turing universal) ^[22] .

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. ^[23]

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

Si bien los artículos sobre computación evolutiva o que la utilizan permean la literatura, varias revistas se dedican a la computación evolutiva:

• Revista Evolutionary Computation ( fundada en 1993)
• Vida artificial (revista) (fundada en 1993)
• Transacciones IEEE sobre computación evolutiva (fundada en 1997)
• Programación genética y máquinas evolutivas (fundada en 2000)
• Swarm Intelligence (fundada en 2007)
• Inteligencia Evolutiva (fundada en 2008)
• Revista de evolución artificial y aplicaciones (2008-2010)
• Computación memética (fundada en 2009)
• Revista internacional de computación evolutiva aplicada (fundada en 2010)
• Swarm y Computación Evolutiva (fundada en 2011)
• Revista internacional de inteligencia de enjambre y computación evolutiva (fundada en 2012)

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

• Conferencia sobre 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 de problemas paralelos de la naturaleza (PPSN).

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

• 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 de las máquinas. 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, Natural Computing Series, 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ística moderna, 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). "Investigación del espacio de parámetros de 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 reglas de supervivencia de Porcellio scaber". arXiv : 1709.09840 [cs.NE].