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:
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 facilitan así 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]
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:
Las principales conferencias en el área de computación evolutiva incluyen
{{cite book}}: CS1 maint: others (link){{cite journal}}: Requiere citar revista |journal=( ayuda )