Algoritme d'estimació de distribució

Els Algoritmes d'Estimació de Distribució (AED) constituïxen una família de metaheurísticas derivades dels algoritmes evolutius.

A diferència dels algoritmes evolutius "clàssics", en a on es busca trobar una solució a un problema codificant directament les seues variables, els AED busquen estimar la distribució de provabilitat de cada variable. La població de solucions candidates es recrea en cada generació, a partir de la distribució de provabilitat obtinguda a partir dels millors individus de la generació anterior.

Ya que la població no es regenera a partir d'individus, sino des de les distribucions de provabilitat obtingudes, no existixen operadors de cruzamiento ni de mutació

Algoritme

Archiu:Eda mono-variant gauss iterations.svg

Algoritme d'Estimació de Distribució. La llínea blava indica la funció objectiu, f(x), la qual posseïx un òptim O. En cada iteración s'efectuen dos accions: la primera és generar una població P en una distribució de provabilitat PDu. Després d'evaluats els individus, se seleccionen els millors (PS) i s'estima la seua distribució PDe. En este eixemple s'utilisa una distribució Normal per a l'estimació. D'esta manera, i a mida que alvancen les generacions, la distribució es concentra al voltant de l'òptim.

Els AED conserven el vocabulari utilisat en algoritmes evolutius. D'esta manera, s'entén com a individu una solució candidata, població al conjunt d'individus i funció d'eixercite a la funció objectiu del problema d'optimisació.

Estructura

El pseudocódigo d'un AED general és el següent:

Generar a l'encert M individus, formant la població $D_0$.

i = 0

Mentres no es complixca la condició de terme, fer:

i = i + 1

Seleccionar N individus (N < M) des de la població precedent ($D_{i-1}$), formant la poblaciónn :$D_{i-1}^S$.

Estimar la distribució de provabilitat $P_i(x)$ de cada variable del problema, usant la població $D_{i-1}^S$.

Generar a l'encert M individus utilisant les distribucions obtingudes $P_i(x)$, formant la població $D_i^S$.

Fi del cicle.