| Abstract: | V magistrskem delu smo se ukvarjali z analizo numeričnih optimizacijskih algoritmov z najbolj pomembnega vidika, eksploracije in eksploatacije. Eksploracija in eksploatacija v znanstveni skupnosti je definirana le abstraktno, kar je povzročilo različna tolmačenja in metrike z različnimi uporabniško določenimi parametri. Največji problem je bil ta, da je določitev parametrov bila domensko specifična. Ta problem je bil zmanjšan z nedavno predlagano metriko, ki temelji na atrakcijskih bazenih. Atrakcijski bazen je podmnožica iskalnega prostora, katerega rešitve, ko uporabimo požrešno iskanje z izbiro najboljšega, vedno konvergirajo k optimumu, ki se imenuje atraktor. Atraktor ni vedno ena sama rešitev, lahko je množica enakovrednih rešitev oz. plato. Obstajajo rešitve, ki lahko konvergirajo k dvema ali več različnima atraktorjema in se nahajajo na meji atrakcijskih bazenov. Izkazalo se je, da računanje atrakcijskih bazenov ni tako enostaven problem. V tem magistrskem delu smo podali in razložili naš algoritem, ki je sestavljen iz treh delov: določitev potencialnih mej, polnjenje in odstranjevanje lažnih mej atrakcijskih bazenov. Vhod v ta algoritem je vnaprej diskretiziran iskalni prostor. Omejili smo se na 2-dimenzionalne in 3-dimenzionalne neomejene zvezne funkcije. Diskretizacijsko ločljivost pri 2-dimenzionalnimi funkcijami smo nastavili na 4000x4000, pri 3-dimenzionalnimi funkcijami na 500x500x500, upoštevajoč časovne ter omejitve računalniškega spomina. Poljubno smo izbrali množico testnih funkcij in sicer: Ackley, Booth, Branin, Dixon-Price, Goldstein-Price, Easom, Rastrigin, Schwefel, Shubert, Michalewicz, Sphere, Beale, Zakharov, Matyas in Griewank. Rezultati pričajo, da naš algoritem komaj izpolnjuje zahteve vseh uporabljenih funkcij. Atrakcijski bazeni funkcij Rastrigin, Schwefel, Ackley in podobnih (vključno z vsemi unimodalnimi) so bili izračunani natančno. Pri posebnih funkcijah, kot so Michalewicz, Shubert in Branin, se je izkazalo, da problem računanja ni tako enostaven. Problem je nastal, predvsem zaradi nezmožnosti algoritma, da posebno postopa pri platojih, ki so na mejah atrakcijskih bazenov. Izkazalo se je tudi, da napaka predstavitve s plavajočo vejico vpliva na naš algoritem. Potreben je aproksimacijski algoritem, ki bo čim bolj minimiziral vpliv te napake. Vendar se teh napak ne moremo popolnoma izogniti.
V populaciji (pri populacijskih algoritmih) se posameznik nahaja v fazi eksploracije, če se noben izmed njegovih staršev ne nahaja v istem atrakcijskem bazenu. Drugače pa se posameznik nahaja v fazi eksploatacije. V magistrskem delu smo za testiranje metrike in ne za primerjalno preučevanje, poljubno izbrali dva algoritma: algoritem PSO in algoritem DE. Pri PSO, je značilno to, da pri ustvarjanju novega posameznika oz. rešitve v osnovi sodeluje posameznik sam, njegova najboljša rešitev ter globalna najboljša rešitev v tem času. Torej, posameznik ima tri starše, podobno kot pri DE. Da bi zmanjšali vpliv stohastičnosti teh dveh algoritmov, smo zagnali eksperiment 50 krat. Merili smo razmerje eksploracije in eksploatacije, ter opazovali kdaj so posamezniki v določeni fazi. Izkazalo se je, da pri teh algoritmih so posamezniki večinoma v fazi eksploracije v začetku optimizacijskega procesa, potem pa preidejo v fazo eksploatacije. Algoritem PSO se dlje časa nahaja v fazi eksploracije, kot DE, vendar pa to ne jamči boljše rešitve. Rezultati so implicirali relevantnost nedavno predlagane metrike in nam odprli plodno področje za nadaljnje preiskave. Ena izmed glavnih prednosti metrike je ta, da ne zahteva nobenega uporabniško določenega parametra, saj upošteva konkreten problem oz. funkcijo – eksploracija in eksploatacija sta natančno določeni. Poleg izboljšave algoritma za računanje atrakcijskih bazenov, nadaljnje delo vključuje tudi razširitev metrike in to tako, da upošteva število, velikost, razmerje in število obiskanih atrakcijskih bazenov. |
|---|
