Algoritmo de estimación de distribución

Los Algoritmos de Estimación de Distribución (AED) constituyen 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

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

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 precedente ($D_{i-1}$), formando la poblaciónn :$D_{i-1}^{S}$.

Estimar la distribución de probabilidad $P_{i}(x)$ de cada variable del problema, usando la población $D_{i-1}^{S}$.

Generar al azar M individuos utilizando las distribuciones obtenidas $P_{i}(x)$, formando la población $D_{i}^{S}$.

Fin del ciclo.

• Datos: Q2835887