Estrategia evolutiva

En informática, las estrategias evolutivas son un tipo de algoritmos evolutivos que se caracterizan principalmente por: La selección de individuos para la recombinación es imparcial y es un proceso determinista, se diferencian del resto de los Algoritmos Evolutivos principalmente por la forma del operador de mutación y son aplicadas principalmente en problemas de optimización continua donde la representación es a través de vectores de números reales. Fueron originalmente creadas en la Universidad Técnica de Berlín en 1964.

La forma general de los algoritmos Estrategias Evolutivas tiene la siguiente notación:

Donde

  • µ: Tamaño de la población
  • ρ: Número de padres seleccionados para recombinarse
  • λ: Número de individuos en la descendencia

Un seudocódigo para el algoritmo general puede ser el siguiente:

0 given ρ, µ, λ ϵ N+
1 initialize P = {(xk; f(xk)) | 1 ≤ k ≤ µ}
2 while not happy
3 Q = {}
4 for k ϵ {1, ... , λ}
5 selected = select_mates(ρ, P)
6 xk = recombine(selected)
7 xk  = mutate(xk)
8 Q = Q + (xk; f(xk))
9 P = P U Q
10 P = select_by_age(P) 
11 P = select_best(µ, P) // by f-ranking

En el cual se tiene inicialmente un conjunto de µ padres. En cada iteración del algoritmo se crea la descendencia (λ), para esto se seleccionan aleatoriamente ρ padres que van a recombinarse, se muta el producto de la recombinación y se forma el nuevo individuo. Luego de formarse el conjunto de la descendencia, se seleccionan los mejores µ individuos entre la población anterior y la nueva descendencia.

Una de las características distintivas de las Estrategias Evolutivas dentro de los Algoritmos Evolutivos es el operador de mutación. Dicho operador se realiza a través de una distribución normal multivariante:

  • Un vector aleatorio n-dimensional X, distribuye normal multivariante con parámetro y matriz de covarianza definida positiva C si su función de densidad es:
  • En notación corta:

Las distribuciones más usadas en Estrategias Evolutivas son:

Existen otras variantes de Estrategias Evolutivas:

  • (1+1)-ES (Solo un padre genera una descendencia mutando, luego se selecciona el mejor de ambos. Necesita de otros parámetros que se autoajustan)
  • (µ, λ)-MSC-ES
  • DR1, DR2, DR3
  • CMA-ES (Es uno de los más usados en la práctica, mantiene una matriz de parámetros que se autoajusta)

Referencias

    Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.