En informática , la computación evolutiva es una familia de algoritmos para la 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 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 y actualiza iterativamente un conjunto inicial de soluciones candidatas. Cada nueva generación se produce eliminando estocásticamente las soluciones menos deseadas e introduciendo pequeños cambios aleatorios y, según el método, mezclando información de los padres. En terminología biológica, una población de soluciones está sometida 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 entornos de problemas, lo que las hace populares en la informática . Existen muchas variantes y extensiones, adecuadas para 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 origina 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 parecen a las redes neuronales primitivas , y las conexiones entre neuronas se aprendían mediante una especie de algoritmo genético . Sus máquinas u tipo P se asemejan a un método de aprendizaje por refuerzo , donde señales de placer y dolor dirigen a la máquina a aprender ciertos comportamientos. Sin embargo, el artículo de Turing no se publicó hasta 1968 y murió en 1954, por lo que estos primeros trabajos tuvieron poco o ningún efecto en el campo de la computación evolutiva que se desarrollaría. [2]
La informática evolutiva como campo comenzó en serio en las décadas de 1950 y 1960. [1] 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. Para lograr este objetivo surgieron tres ramas en diferentes lugares: estrategias de evolución , programación evolutiva y algoritmos genéticos . Una cuarta rama, la programación genética , surgió finalmente a principios de los años 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 en 1991 se acuñó el término "computación evolutiva" 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 Estados Unidos, que se consideraba 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 mutarían (agregando o eliminando estados, o cambiando las reglas de transición de estados), y lo mejor de estas máquinas mutadas evolucionaría aún más en las 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 modelar la evolución de las estrategias de juego. [3]
En 1964, Ingo Rechenberg y Hans-Paul Schwefel introducen 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 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 ambos para resolver con éxito problemas de optimización en dinámica de fluidos . [4] Inicialmente, esta técnica de optimización se realizó sin computadoras, confiando en lugar de dados para determinar mutaciones aleatorias. En 1965, los cálculos se realizaban íntegramente a máquina. [3]
John Henry Holland introdujo los algoritmos genéticos en la década de 1960 y se desarrollaron aún más en la Universidad de Michigan en la década de 1970. [5] Mientras que los otros enfoques se centraban en resolver problemas, Holland pretendía principalmente 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 rastrearon 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 denominarse programación genética , defendido por John Koza, entre otros. [3] 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 previos de utilizar código de 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 califican en función de qué tan bien 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 desempeñaron un papel en la historia de la informática 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. [6] Otro pionero en la década de 1950 fue Alex Fraser , quien publicó una serie de artículos sobre simulación de seleccion artificial . [7] A medida que crecía el interés académico, los espectaculares aumentos en la potencia de las computadoras permitieron aplicaciones prácticas, incluida la evolución automática de los programas informáticos. [8] 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. [9] [10]
Las técnicas de computación evolutiva implican principalmente algoritmos de optimización metaheurística . En términos generales, el campo incluye:
En Evolutionary Computation Bestiary 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 en el sentido de que generalmente sólo 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 de una población, y la función de costos determina el entorno dentro del cual "viven" las soluciones (ver también función de aptitud ). La evolución de la población se produce entonces tras 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 (p. ej., 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 tal proceso evolutivo son estocásticos . Los fragmentos de información modificados 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 mayores posibilidades de ser seleccionados que los individuos con una menor aptitud , pero normalmente incluso los individuos débiles tienen posibilidades de convertirse en padres o de sobrevivir.
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 sólo 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 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 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 paralelismos entre el desarrollo de programas nos parecen aquellas 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 siguientes estados, de modo que los sistemas biológicos están más cerca de una computación que los sistemas dinámicos clásicos. [14]
Además, siguiendo 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 burda metáfora 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 piensa que revela uno de los problemas más apremiantes a la hora de explicar los orígenes de la vida.
Se han introducido autómatas evolutivos [16] [17] [18] , una generalización de las máquinas evolutivas de Turing [19] [20] , 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 evolutivos finitos , la subclase más simple de autómatas evolutivos que trabajan en modo terminal , pueden aceptar lenguajes arbitrarios sobre un alfabeto dado, incluidos lenguajes no recursivamente enumerables (p. ej., lenguaje de diagonalización) y recursivamente enumerables pero no recursivos (p. ej., el lenguaje de la máquina universal de Turing). ) [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]
Si bien los artículos sobre la computación evolutiva o su uso impregnan la literatura, varias revistas se dedican a la computación evolutiva:
Las principales conferencias en el área de la computación evolutiva incluyen
{{cite book}}: CS1 maint: others (link){{cite journal}}: Citar diario requiere |journal=( ayuda )