Banaketa estimatzeko algoritmo

Banaketa estimatzeko algoritmoa (, EDAk), batzuetan eredu probabilistiko-eraikitzaile algoritmo genetikoak deituak, optimoaren bilaketa gidatzen duten optimizazio-metodo estokastikoak dira, esperantzagarriak diren soluzio hautagaien eredu probabilistiko esplizituak eraiki eta lagintzen dituztenak. Optimizazioa eredu probabilistiko baten eguneraketa inkremental bat gisa ikusten da, soluzio onargarrien arteko bat kodetzen duen eredutik hasi eta soilik optimo globala sortzen duen ereduarekin amaituta.

EDAk algoritmo ebolutiboen klasekoak dira. EDA algoritmoen eta algoritmo ebolutibo konbentzional gehienen arteko desberdintasun nagusia da algoritmo ebolutiboek soluzio hautagai berriak sortzen dituztela, aldakuntza-operadore batek edo gehiagok definitutako banaketa inplizitu bat erabiliz; EDA algoritmoek, berriz, sare bayesiar batek, aldagai anitzeko banaketa normal batek edo beste eredu-klase batek kodetutako probabilitate-banaketa esplizitu bat erabiltzen dute. Beste algoritmo ebolutibo batzuk bezala, EDAk bektoreetatik LISP estiloko S adierazpenetara doan errepresentazio batzuetan definitutako optimizazio problemak ebazteko erabil daitezke, eta askotan soluzio hautagaien kalitatea ebaluatzen da funtzio objektibo bat edo gehiago erabiliz.

Hona hemen EDA baten prozedura orokorra:
 t := 0
 Hasieratu m(0) eredua, banaketa uniformea adierazteko soluzio onargarrien gainean
 bitartean (amaitzeko irizpideak ez dira bete) egin
    P := sortu N>0 soluzio hautagai M(t) laginduz
    F := ebaluatu soluzio hautagai guztiak P-n
    M(t + 1) := doiketa_eredua(P, F, M(t)))
    t := t + 1
Optimizazioan eredu probabilistiko esplizituak erabiliz, EDA algoritmoek ohiko algoritmo ebolutibo gehienentzat eta optimizazio-teknika tradizionalentzat nabarmen zailak ziren optimizazio-problemak modu bideragarrian ebaztea ahalbidetu zuten, hala nola epistasi-maila altuko problemak. Hala ere, EDA algoritmoen abantaila da algoritmo horiek optimizazio-praktikatzaile bati eredu probabilistiko batzuk ematen dizkiotela, eta eredu horiek ebazten ari den arazoari buruzko informazio asko erakusten dutela. Informazio hori, aldi berean, arazo espezifikoetarako auzoko operadoreak diseinatzeko erabil daiteke, bilaketa lokaletarako, EDA algoritmoen etorkizuneko exekuzioak antzeko arazo batean alboratzeko ("bias"), edo problemaren eredu konputazional eraginkorra sortzeko.

Adibidez, populazioa 4. luzerako bit kateren bidez adierazten bada, EDAk  soluzio esperantzagarriaren populazioa adieraz dezake lau probabilitateko p bektore bakarra erabiliz  (p1, p2, p3, p4), non p-ren osagai bakoitzak posizio hori 1 izateko probabilitatea definitzen duen. Probabilitate-bektore hori erabiliz, hainbat soluzio hautagai sor daiteke, kopuru arbitrario bat .

 Erreferentziak 

 Kanpo estekak 

Kategoria:Konputazio ebolutiboa