Los algoritmos evolutivos o algoritmos evolutivos ( algoritmos evolutivos en inglés) son una familia de algoritmos cuyo principio se basa en la teoría de la evolución para resolver diversos problemas. Por tanto, son métodos de cálculo bioinspirados . La idea es desarrollar un conjunto de soluciones a un problema dado, con miras a encontrar los mejores resultados. Estos son los llamados algoritmos estocásticos , porque utilizan iterativamente procesos aleatorios .
La gran mayoría de estos métodos se utilizan para resolver problemas de optimización , ya que son metaheurísticas , aunque el marco general no está necesariamente dedicado a los algoritmos de optimización en sentido estricto. También se clasifican entre los métodos de inteligencia computacional .
Estos algoritmos manipulan poblaciones de soluciones.
Los algoritmos evolutivos se inspiran en la evolución de los seres vivos, considerando que estos últimos tienden a producir organismos más adaptados a su entorno .
Según la teoría de la evolución , existen varios mecanismos para hacer esto. Esquemáticamente:
Todos los algoritmos evolutivos desarrollan un conjunto (una "población") de soluciones ("individuos"). Los individuos están representados por su genotipo, que se expresa en forma de fenotipo, al que asociamos una cualidad, "aptitud". Los algoritmos están diseñados de tal manera que cuanto mayor sea la aptitud de un individuo, más probabilidades hay de que transmita su genotipo dentro de la población.
Cada paso del algoritmo está asociado con un "operador", que describe cómo manipular a los individuos. Los diferentes operadores a veces se agrupan bajo términos genéricos:
Para hacer esto, usamos el siguiente algoritmo general:
construction et évaluation d'une population initiale ; Jusqu'à atteindre un critère d'arrêt : sélection d'une partie de la population, reproduction des individus sélectionnés, mutation de la descendance, évaluation du degré d'adaptation de chaque individu, remplacement de la population initiale par une nouvelle population.Después de haber inicializado una primera población de individuos, se itera un número finito de veces, hasta que se alcanza un criterio de parada (por ejemplo, un número máximo de generaciones). El primer paso de selección permite separar a los individuos que participarán en la reproducción de los que no. Los individuos seleccionados (los “padres”) Reproducir (también decimos que nos Cruce ), dando un conjunto de “niños” que comparten algunas de las características de sus antepasados. Estos niños luego pasan por una etapa de mutación, que modifica aleatoriamente su genotipo. A continuación, se evalúan los nuevos individuos (su valor se actualiza llamando a la función objetivo ). Finalmente, se elige un número determinado de individuos entre el conjunto de padres + hijos, para formar la próxima generación.
Siempre hay al menos un operador que utiliza un proceso aleatorio, como mínimo para la construcción de la población inicial y para la mutación, pero a menudo también para la selección y reproducción. Dependiendo del método, el énfasis está en uno u otro de los operadores.
Sigue siendo una práctica común mantener la “diversidad genética” de la población el tiempo suficiente para evitar una convergencia prematura. Cuando un algoritmo evolutivo utiliza un procedimiento de búsqueda local para cada individuo, se denomina " algoritmo memético ".
En terminología histórica, tratamos de maximizar el valor de la función objetivo, con la ayuda de operadores que muestran comportamientos de explotación o exploración . Estos términos corresponden a las nociones de intensificación y diversificación, más bien utilizadas en el campo de las metaheurísticas , donde generalmente se busca minimizar el valor de la función objetivo. Sin embargo, estas dos áreas son bastante similares, y los algoritmos evolutivos tienden a clasificarse como metaheurísticas.
Históricamente, tres grandes familias de algoritmos se desarrollaron de forma independiente, entre mediados de los 60 y los 70. Los primeros métodos fueron las estrategias de evolución , propuestas por I. Rechenberg en 1965, para resolver problemas de optimización continua. Al año siguiente, Fogel, Owens y Walsh concibieron la programación evolutiva como un método de inteligencia artificial para el diseño de autómatas de estados finitos . Finalmente, en 1975, JH Holland propuso los primeros algoritmos genéticos para la optimización combinatoria. La publicación en 1989 del libro de DE Goldberg sobre algoritmos genéticos los hizo particularmente populares.
Posteriormente, estos diferentes enfoques han evolucionado mucho y se han unido, para acabar agrupados bajo el término genérico de algoritmos evolutivos. Hoy en día, la literatura sobre el tema es extremadamente abundante y estos algoritmos se consideran un área de investigación muy prolífica.
En su versión básica, el algoritmo manipula iterativamente un conjunto de vectores de variables reales, utilizando operadores de mutación y selección. La selección se realiza mediante una elección determinista de los mejores individuos, según la escala de valores de la función objetivo. La etapa de mutación se lleva a cabo convencionalmente agregando un valor aleatorio, extraído de una distribución normal . Un rasgo característico de estos algoritmos es la autoadaptación de la matriz de varianza-covarianza de la distribución normal.
Un algoritmo representativo de las estrategias evolutivas es la evolución diferencial . En esta clase de método, la diferencia ponderada entre subpoblaciones se usa para sesgar un operador de mutación diferencial .
Históricamente, estos algoritmos fueron diseñados para aprender problemas de máquinas de estados finitos y solo usaban operadores de mutación y reemplazo. Sin embargo, hoy en día ya no se limitan a una representación, sino que aún no utilizan un operador cruzado. Se diferencian de las estrategias de evolución en que favorecen a los operadores de reemplazo estocásticos.
Los algoritmos genéticos son los más populares de los algoritmos evolutivos. Diferencian explícitamente el genotipo del fenotipo, el genotipo generalmente se codifica de forma binaria . La elección de la codificación del genotipo (cómo se relaciona con el fenotipo) es crucial para un algoritmo genético. Convencionalmente, utilizan un operador de selección proporcional, un reemplazo generacional y el operador cruzado es el operador principal.
Los algoritmos evolutivos que utilizan otras representaciones y operadores a menudo se denominan algoritmos genéticos , aunque los especialistas evitan este abuso del lenguaje.
Estos algoritmos utilizan una representación en árboles de expresiones lógicas, porque históricamente se aplican al aprendizaje y modelado estadísticos. Utilizan el mismo algoritmo básico que los algoritmos genéticos para hacer esto. Sin embargo, la programación genética se ocupa específicamente de la construcción automática de programas .
A diferencia de los algoritmos evolutivos “clásicos”, el corazón de estos métodos consiste en estimar las relaciones entre las diferentes variables de un problema de optimización, gracias a la estimación de una distribución de probabilidad, asociada a cada punto de la muestra. Por tanto, no utilizan operadores de cruce o mutación, la muestra se construye directamente a partir de los parámetros de distribución, estimados en la iteración anterior.