Banaketa estimatzeko algoritmo

Banaketa-algoritmoaren estimazioa. P populazio batentzat PDu banaketa batean ausazko zozketa bat egiten da i iterazio bakoitzeko, Ondoren, PDe banaketa-parametroekin estimazio bat egiten da, hautatutako PS puntuak erabiliz. Irudiko adibidean f(X) helburu-funtzio jarraitu bat optimizatzen du O optimo bakar batekin. Laginketa (N banaketa normal bati jarraituz) optimoaren inguruan kontzentratzen da desbobinatzeko algoritmoan zehar joaten den heinean.

Banaketa estimatzeko algoritmoa (ingelesez: Estimation of distribution algorithms, 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.^[1]^[2]^[3]^[4]

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

↑ (Ingelesez) Pelikan, Martin. (2005-02-21). «Probabilistic Model-Building Genetic Algorithms» Hierarchical Bayesian Optimization Algorithm. in: Studies in Fuzziness and Soft Computing. 170 Springer Berlin Heidelberg, 13–30 or. doi:10.1007/978-3-540-32373-0_2. ISBN 9783540237747..
↑ Larrañaga, Pedro. (2002). Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. (1st ed. argitaraldia) Springer ISBN 978-1-4615-1539-5. (kontsulta data: 2026-01-05).
↑ Lozano, José A.; Larrañaga, Pedro; Inza, Iñaki; Bengoetxea, Endika. (2006). Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms. Springer-Verlag Berlin Heidelberg ISBN 978-3-540-32494-2. (kontsulta data: 2026-01-05).
↑ Pelikan, Martin. (2006). Scalable Optimization Via Probabilistic Modeling: From Algorithms to Applications. Springer Berlin / Heidelberg ISBN 978-3-540-34953-2. (kontsulta data: 2026-01-05).

Kanpo estekak

Datuak: Q2835887

[1] (Ingelesez) Pelikan, Martin. (2005-02-21). «Probabilistic Model-Building Genetic Algorithms» Hierarchical Bayesian Optimization Algorithm. in: Studies in Fuzziness and Soft Computing. 170 Springer Berlin Heidelberg, 13–30 or. doi:10.1007/978-3-540-32373-0_2. ISBN 9783540237747..

[2] Larrañaga, Pedro. (2002). Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. (1st ed. argitaraldia) Springer ISBN 978-1-4615-1539-5. (kontsulta data: 2026-01-05).

[3] Lozano, José A.; Larrañaga, Pedro; Inza, Iñaki; Bengoetxea, Endika. (2006). Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms. Springer-Verlag Berlin Heidelberg ISBN 978-3-540-32494-2. (kontsulta data: 2026-01-05).

[4] Pelikan, Martin. (2006). Scalable Optimization Via Probabilistic Modeling: From Algorithms to Applications. Springer Berlin / Heidelberg ISBN 978-3-540-34953-2. (kontsulta data: 2026-01-05).

[1]

[2]

[3]

[4]