Computación evolutiva

En informática, la computación evolutiva es una familia de algoritmos para la optimización global inspirada en la evolución biológica, y el subcampo de inteligencia artificial y computación blanda que estudia estos algoritmos. En términos técnicos, son una familia de solucionadores de problemas de prueba y error basados ​​en poblaciones con un carácter metaheurístico u optimización 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 evolutivas pueden producir soluciones altamente optimizadas en una amplia gama de configuraciones de problemas, lo que las hace populares en las ciencias de la computación. Existen muchas variantes y extensiones, adaptadas a familias de problemas y estructuras de datos más específicas. 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 concepto de imitar procesos evolutivos para resolver problemas se origina antes de la llegada de las computadoras, como cuando Alan Turing propuso un método de búsqueda genética en 1948. Las u-máquinas de tipo B de Turing se parecen a las redes neuronales primitivas, y las conexiones entre las 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 para el 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 inicial tuvo poco o ningún efecto en el campo de la computación evolutiva que se desarrollaría.

La computación evolutiva como campo comenzó en serio en las décadas de 1950 y 1960. Hubo varios intentos independientes de utilizar el proceso de evolución en la informática en este momento, que se desarrollaron por separado durante aproximadamente 15 años. Tres ramas surgieron en diferentes lugares para lograr 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.

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, las máquinas de estados finitos se utilizan para resolver un problema de predicción: estas máquinas se mutarían (agregando o eliminando estados, o cambiando las reglas de transición de estado), y las mejores de estas máquinas mutadas evolucionarían aún más en las generaciones futuras. La máquina de estados finitos final puede usarse 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. Eventualmente se amplió para manejar datos de series temporales y para modelar la evolución de las estrategias de juego.

En 1964, Ingo Rechenberg y Hans-Paul Schwefel introducen el paradigma de las estrategias de evolución en Alemania. Dado que las técnicas tradicionales de descenso de gradientes producen resultados que pueden atascarse en los mínimos locales, Rechenberg y Schwefel propusieron que se pueden usar mutaciones aleatorias (aplicadas a todos los parámetros de algún vector de solución) para escapar de estos mínimos. Las soluciones secundarias se generaron a partir de soluciones principales, y la más exitosa de las dos se mantuvo 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. Inicialmente, esta técnica de optimización se realizaba sin computadoras, sino que se basaba en dados para determinar mutaciones aleatorias. Para 1965, los cálculos se realizaban íntegramente a máquina.

John Henry Holland introdujo los algoritmos genéticos en la década de 1960 y se desarrolló aún más en la Universidad de Michigan en la década de 1970. Mientras que los otros enfoques se centraron en la resolución de problemas, Holland se centró principalmente en utilizar algoritmos genéticos para estudiar la adaptación y determinar cómo se puede simular. Las poblaciones de cromosomas, representadas como cadenas de bits, se transformaron 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 niños 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 se denominó programación genética, defendido por John Koza, entre otros. En esta clase de algoritmos, el tema 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 de usar código de máquina, pero tuvieron poco éxito). Para Koza, los programas eran expresiones Lisp S, que pueden considerarse como árboles de subexpresiones. Esta representación permite que los programas intercambien subárboles, lo que representa una especie de mezcla genética. Los programas se puntúan 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 aplicaciones exitosas del paradigma de programación genética.

Muchas otras figuras jugaron un papel en la historia de la computación evolutiva, aunque su trabajo no siempre encajaba 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, y los primeros resultados se publicaron 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. 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 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.

Técnicas

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 inmunes artificiales
• Vida artificial (ver también organismo digital)
• algoritmos culturales
• Evolución diferencial
• Evolución de doble fase
• Estimación de algoritmos de distribución
• Algoritmos evolutivos
• programación evolutiva
• estrategia de evolución
• Programación de expresión génica
• Algoritmo genético
• programación genética
• evolución gramatical
• Modelo de evolución aprendible
• Sistemas clasificadores de aprendizaje
• Algoritmos meméticos
• neuroevolución
• Optimización de Enjambre de partículas
• Autoorganización, como mapas de autoorganización, aprendizaje competitivo
• Inteligencia de enjambre

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, 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 juegan el papel de individuos en una población, y la función de costo determina el entorno dentro del cual "viven" las soluciones (ver también función de aptitud). La evolución de la población tiene lugar después 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 tal 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 aptitud más alta tienen más posibilidades de ser seleccionados que los individuos con una aptitud más baja, pero por lo general, incluso los individuos débiles tienen la posibilidad de convertirse en padres o de sobrevivir.

Algoritmos evolutivos y biología.

Los algoritmos genéticos entregan 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. Las ideas más prometedoras sobre los paralelos de 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. Por lo tanto, los sistemas biológicos son como máquinas computacionales que procesan la información de entrada para calcular los siguientes estados, de modo que los sistemas biológicos están más cerca de la computación que los sistemas dinámicos clásicos.

Además, siguiendo los conceptos de la teoría computacional, los microprocesos en los organismos biológicos son fundamentalmente incompletos e indecidibles (integridad (lógica)), lo que implica que “hay más que una cruda 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 apremiantes para explicar los orígenes de la vida.

Los autómatas evolutivos, una generalización de las máquinas de Turing evolutivas, 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. 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 funcionan en modo terminal puede aceptar lenguajes arbitrarios sobre un alfabeto dado, incluidos lenguajes enumerables no recursivamente (por ejemplo, lenguaje de diagonalización) y enumerables recursivamente 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 red de la comunidad.

• kalyanmoy deb
• Kenneth A De Jong
• Pedro J. Fleming
• David B. Fogel
• Estefanía Forrest
• David E Goldberg
• John Henry Holanda
• Theo Jansen
• Juan Koza
• Zbigniew Michalewicz
• melanie mitchell
• pedro nordin
• Ricardo Poli
• Ingo Rechenberg
• Hans-Paul Schwefel

Conferencias

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

• Conferencia de computación genética y evolutiva 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).