Algoritmo de estimación de distribución

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

Los Algoritmos de Estimación de Distribución (AED) constiuyen una familia de metaheurísticas derivadas de los algoritmos evolutivos.

A diferencia de los algoritmos evolutivos "clásicos", en donde se busca encontrar una solución a un problema codificando directamente sus variables, los AED buscan estimar la distribución de probabilidad de cada variable. La población de soluciones candidatas se recrea en cada generación, a partir de la distribución de probabilidad obtenida a partir de los mejores individuos de la generación anterior.

Dado que la población no se regenera a partir de individuos, sino desde las distribuciones de probabilidad obtenidas, no existen operadores de cruzamiento ni de mutación

Algoritmo[editar]

Algoritmo de Estimación de Distribución. La línea azul indica la función objetivo, f(x), la cual posee un óptimo O. En cada iteración se efectúan dos acciones: la primera es generar una población P con una distribución de probabilidad PDu. Luego de evaluados los individuos, se seleccionan los mejores (PS) y se estima su distribución PDe. En este ejemplo se utiliza una distribución Normal para la estimación. De esta manera, y a medida que avanzan las generaciones, la distribución se concentra alrededor del óptimo.

Los AED conservan el vocabulario utilizado en algoritmos evolutivos. De esta manera, se entiende como individuo una solución candidata, población al conjunto de individuos y función de desempeño a la función objetivo del problema de optimización.

Estructura[editar]

El pseudocódigo de un AED general es el siguiente:

Generar al azar M individuos, formando la población D_0.
i = 0
Mientras no se cumpla la condición de término, hacer:
i = i + 1
Seleccionar N individuos (N < M) desde la población precendente (D_{i-1}), formando la poblaciónn :D^S_{i-1}.
Estimar la distribución de probabilidad P_i(x) de cada variable del problema, usando la población D^S_{i-1}.
Generar al azar M individuos utilizando las distribuciones obtenidas P_i(x), formando la población D^S_i.
Fin del ciclo.