- Algoritmo de estimación de distribución
-
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
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 efectuan 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 D0.
- 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 (Di − 1), formando la poblaciónn :
. - Estimar la distribución de probabilidad Pi(x) de cada variable del problema, usando la población .
- Generar al azar M individuos utilizando las distribuciones obtenidas Pi(x), formando la población
.
- Fin del ciclo.
Categorías:- Computación evolutiva
- Algoritmos
- Teoría de probabilidades
Wikimedia foundation. 2010.
