Algorisme d'estimació de distribució

Estimació de l'algoritme de distribució. Per a cada iteració i, es realitza un sorteig aleatori d'una població P en una distribució Pdu. Aleshores s'estimen els paràmetres de distribució PDe utilitzant els punts PS seleccionats. L'exemple il·lustrat optimitza una funció objectiu contínua f(X) amb un òptim únic O. El mostreig (seguint una distribució normal N ) es concentra al voltant de l'òptim a mesura que avança l'algorisme de desenrotllament.

Els algorismes d'estimació de distribució (EDA), de vegades anomenats algorismes genètics de construcció de models probabilistes (PMBGA), són mètodes d'optimització estocàstica que guien la cerca de l'òptim mitjançant la construcció i el mostreig de models probabilístics explícits de solucions candidates prometedores. L'optimització es veu com una sèrie d'actualitzacions incrementals d'un model probabilístic, començant pel model que codifica una priorització no informativa sobre solucions admissibles i acabant amb el model que genera només els òptims globals.

Els EDA pertanyen a la classe dels algorismes evolutius. La principal diferència entre els EDA i la majoria dels algorismes evolutius convencionals és que els algorismes evolutius generen noves solucions candidates mitjançant una distribució implícita definida per un o més operadors de variació, mentre que els EDA utilitzen una distribució de probabilitat explícita codificada per una xarxa bayesiana, una distribució normal multivariant o una altra. classe de model. De la mateixa manera que altres algorismes evolutius, els EDA es poden utilitzar per resoldre problemes d'optimització definits sobre una sèrie de representacions des de vectors fins a expressions S d'estil LISP, i la qualitat de les solucions candidates sovint s'avalua utilitzant una o més funcions objectius.

El procediment general d'una EDA es descriu a continuació:

t := 0 inicialitzar el model M(0) per representar una distribució uniforme sobre solucions admissibles

mentre que (no es compleixen els criteris de terminació) calcular

P := genera N>0 solucions candidates mostrant M(t)

F := avalueu totes les solucions candidates a P

M(t + 1) := model_ajust ( P, F, M(t))

t := t + 1

L'ús de models probabilístics explícits en l'optimització va permetre als EDA resoldre de manera viable problemes d'optimització que eren notòriament difícils per a la majoria dels algorismes evolutius convencionals i les tècniques d'optimització tradicionals, com ara problemes amb alts nivells d'epistasi. No obstant això, l'avantatge dels EDA és també que aquests algorismes proporcionen al professional de l'optimització una sèrie de models probabilístics que revelen molta informació sobre el problema que es resol. Aquesta informació es pot utilitzar al seu torn per dissenyar operadors de barri específics per a problemes per a la cerca local, per esbiaixar les futures execucions d'EDA en un problema similar o per crear un model computacional eficient del problema.

Per exemple, si la població es representa per cadenes de bits de longitud 4, l'EDA pot representar la població de la solució prometedora utilitzant un sol vector de quatre probabilitats (p1, p2, p3, p4) on cada component de p defineix la probabilitat d'aquesta. la posició és 1. Utilitzant aquest vector de probabilitat és possible crear un nombre arbitrari de solucions candidates.

Estimació d'algorismes de distribució (EDA)

Aquesta secció descriu els models construïts per alguns EDA coneguts de diferents nivells de complexitat. Sempre es suposa una població $P(t)$ a la generació $t$, un operador de selecció $S$, un operador de modelisme $\alpha$ i un operador de mostreig $\beta$.

Factoritzacions univariants

Els EDA més simples assumeixen que les variables de decisió són independents, és a dir $p(X_1,X_2)=p(X_1)\cdot p(X_2)$. Per tant, les EDA univariades es basen només en estadístiques univariades i les distribucions multivariables s'han de factoritzar com el producte de $N$ distribucions de probabilitat univariades,

$D_{\text{Univariate}}:=p(X_1,\dots ,X_N)=\prod _{i=1}^{N}p(X_i).$

Aquestes factoritzacions s'utilitzen en moltes EDA diferents, a continuació en descriurem algunes.

Algorisme de distribució marginal univariada (UMDA)

L'UMDA és un EDA senzill que utilitza un operador ${\alpha }_{UMDA}$ per estimar probabilitats marginals d'una població seleccionada $S(P(t))$. En assumir $S(P(t))$ contenir $\lambda$ elements, ${\alpha }_{UMDA}$ produeix probabilitats:

$p_{t+1}(X_i)=\frac{1}{\lambda }\sum _{x\in S(P(t))}{x}_i,\mathrm{\forall }i\in 1,2,\dots ,N.$

Cada pas UMDA es pot descriure de la següent manera

$D(t+1)={\alpha }_{\text{UMDA}}\circ S\circ {\beta }_{\lambda }(D(t)).$

Aprenentatge incremental basat en la població (PBIL)

El PBIL, representa la població implícitament pel seu model, a partir del qual mostra noves solucions i actualitza el model. A cada generació, $\mu$ es mostren els individus i $\lambda \le \mu$ estan seleccionats. A continuació, aquestes persones s'utilitzen per actualitzar el model de la manera següent

$p_{t+1}(X_i)=(1-\gamma )p_t(X_i)+(\gamma /\lambda )\sum _{x\in S(P(t))}{x}_i,\mathrm{\forall }i\in 1,2,\dots ,N,$

on $\gamma \in (0,1]$ és un paràmetre que defineix la taxa d'aprenentatge, un valor petit determina que el model anterior $p_t(X_i)$ només s'hauria de modificar lleugerament per les noves solucions mostrejades. PBIL es pot descriure com

$D(t+1)={\alpha }_{\text{PIBIL}}\circ S\circ {\beta }_{\mu }(D(t))$

Algorisme genètic compacte (cGA)

El CGA, també es basa en les poblacions implícites definides per distribucions univariades. A cada generació $t$, dos individus $x,y$ es mostren, $P(t)={\beta }_2(D(t))$. La població $P(t)$ aleshores s'ordena en ordre decreixent d'aptitud, $S_{\text{Sort}(f)}(P(t))$, amb $u$ sent el millor i $v$ sent la pitjor solució. El CGA estima les probabilitats univariants de la següent manera

$p_{t+1}(X_i)=p_t(X_i)+\gamma (u_i-v_i),\mathrm{\forall }i\in 1,2,\dots ,N,$

on, $\gamma \in (0,1]$ és una constant que defineix la taxa d'aprenentatge, normalment establerta a $\gamma =1/N$. El CGA es pot definir com

$D(t+1)={\alpha }_{\text{CGA}}\circ S_{\text{Sort}(f)}\circ {\beta }_2(D(t))$