Computación evolutiva - Evolutionary computation

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 estudian estos algoritmos. En términos técnicos, son una familia de solucionadores de problemas de prueba y error basados en la población con un carácter de optimización metaheurística o estocástica .

En la 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. En terminología biológica, una población de soluciones está sujeta a selección natural (o selección artificial ) y mutació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 entornos de problemas, lo que las hace populares en la 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 usa a veces en biología evolutiva como un procedimiento experimental in silico para estudiar aspectos comunes de los procesos evolutivos generales.

Historia

El uso de principios evolutivos para la resolución automatizada de problemas se originó en la década de 1950. No fue hasta la década de 1960 que se empezaron a desarrollar tres interpretaciones distintas de esta idea en tres lugares diferentes.

La programación evolutiva fue introducida por Lawrence J. Fogel en los Estados Unidos, mientras que John Henry Holland llamó a su método un algoritmo genético . En Alemania, Ingo Rechenberg y Hans-Paul Schwefel introdujeron estrategias de evolución . Estas áreas se desarrollaron por separado durante unos 15 años. Desde principios de los noventa en adelante se unifican como diferentes representantes ("dialectos") de una tecnología, denominada computación evolutiva . También a principios de los noventa, había surgido una cuarta corriente que seguía las ideas generales: la programación genética . Desde la década de 1990, los algoritmos inspirados en la naturaleza se están convirtiendo en una parte cada vez más importante de la computación evolutiva.

Estas terminologías denotan el campo de la computación evolutiva y consideran la programación evolutiva, las estrategias de evolución, los algoritmos genéticos y la programación genética como subáreas.

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. 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 . La evolución artificial se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg en la década de 1960 y principios de la de 1970, quien utilizó estrategias de evolución para resolver problemas complejos de ingeniería. Los algoritmos genéticos, en particular, se hicieron populares a través de los escritos de John Holland . A medida que crecía el interés académico, los aumentos dramáticos en el poder de las computadoras permitieron aplicaciones prácticas, incluida la evolución automática de los programas de computadora. 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.

Técnicas

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

Algoritmos evolutivos

Los algoritmos evolutivos forman un subconjunto de la computación evolutiva en el sentido de que generalmente solo involucran técnicas que implementan mecanismos inspirados en la evolución biológica como la reproducción , mutación , recombinación , selección natural y 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 costes determina el entorno en el que "viven" las soluciones (véase también la 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, la mutación y el cruce 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 . Las piezas de información modificadas debido a la recombinación y la mutación se eligen al azar. Por otro lado, los operadores de selección pueden ser deterministas o estocásticos. En el último caso, los individuos con una mayor aptitud tienen una mayor probabilidad de ser seleccionados que los individuos con una menor aptitud , pero normalmente incluso los individuos débiles tienen la posibilidad de convertirse en padres o de sobrevivir.

Algoritmos evolutivos y biología

Los algoritmos genéticos ofrecen métodos para modelar sistemas biológicos y 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 forma vívida (pero 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 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 visión 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. Nos parece que las ideas más prometedoras sobre los paralelismos de desarrollo de programas 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. Por lo tanto, los sistemas biológicos son como máquinas computacionales que procesan información de entrada para calcular los siguientes estados, de modo que los sistemas biológicos están más cerca de un cálculo que el sistema dinámico clásico.

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

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 piensa que revela uno de los problemas más urgentes para explicar los orígenes de la vida.

Los autómatas evolutivos , una generalización de las máquinas evolutivas de Turing , se han introducido con el fin de investigar con más 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. Esto confirma el resultado inicial sobre la indecidibilidad de la evolución natural y los algoritmos y procesos evolutivos. Autómatas finitos evolutivos , la subclase más simple de autómatas evolutivos que trabajan en modo terminal pueden aceptar lenguajes arbitrarios sobre un alfabeto dado, incluidos lenguajes enumerables no recursivamente (por ejemplo, lenguaje de diagonalización) y recursivamente enumerables pero no recursivos (por ejemplo, lenguaje de la máquina universal de Turing ).

Practicantes notables

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.

Conferencias

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

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

Ver también

enlaces externos

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

Bibliografía

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 descripción general de los algoritmos evolutivos para la optimización de parámetros . Computación evolutiva, 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 de la Computación Evolutiva en el Mundo Real , Notas de la Conferencia Springer-Verlag en Ciencias de la Computación , 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. Prensa del MIT , 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, Nueva Jersey, 1995.
LJ Fogel, AJ Owens y MJ Walsh. Inteligencia artificial a través de la 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. Prensa de la Universidad de Michigan , Ann Arbor, 1975.
P. Hingston, L. Barone y Z. Michalewicz (Editores), Design by Evolution, Natural Computing Series , 2008, Springer , ISBN 3540741097
JR Koza. Programación genética: sobre la programación de ordenadores mediante la evolución natural. Prensa del MIT, 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 de evolución , 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. Evolutionstrategie: 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. Simón. Algoritmos de optimización evolutiva . Wiley, 2013.
M. Sipper, W. Fu, K. Ahuja y JH Moore (2018). "Investigando el espacio de parámetros de los algoritmos evolutivos" . Minería de Biodatos . 11 : 2. doi : 10.1186 / s13040-018-0164-x . PMC 5816380 . PMID 29467825 . Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
Y. Zhang y S. Li. (2017). "PSA: un algoritmo de optimización novedoso basado en reglas de supervivencia de porcellio scaber". arXiv : 1709.09840 [ cs.NE ]. Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )

Languages

In other projects