Estrategia evolutiva

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]