20.500.12556/DKUM-76775 An analysis of exploration and exploitation using attraction basins on 2D and 3D continuous functions master's thesis Analiza eksploracije in eksploatacije s pomočjo atrakcijskih bazenov na 2D in 3D zveznih funkcijah In this thesis we were discussing an analysis of numerical optimization algorithms from the most important aspect, that is exploration and exploitation. We focused on 2-dimensional and 3-dimensional unconstrained continuous functions, which were used to test the recently proposed metric based on attraction basins. The metric does not need any user-defined parameters. Attraction basins were expounded more profoundly and extensively. Our algorithm to calculate them consists of three steps such as making potential boundaries, filling, and then removing false boundaries from attraction basins. Results show that our algorithm is barely satisfying, depends on a particular problem function used. For example, attraction basins from Rastrigin, Schwefel, Ackley and similar functions (including all unimodal ones) were calculated accurately, while more special functions like Michalewicz, Shubert and Branin were proved to be not so easy. Further, we arbitrarly selected two algorithms, Particle Swarm Optimization and Self-adapting Differential Evolution, not for comparative study, rather to test the metric based on attraction basins. Results implied the relevance of recently proposed metric, and opened us a fruitful field for further investigation. 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. exploration exploitation attraction basins optimization metaheuristic eksploracija eksploatacija atrakcijski bazeni optimizacija metahevristika true true false [M. Baketarić] Angleški jezik Slovenski jezik Magistrsko delo/naloga 2020-07-04 12:14:37 2020-11-04 10:19:40 2022-08-09 13:57:33 2020-11-19 03:18:12 2020 0 Maribor 0 Maribor XI, 61 f. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.432.42.021(043.2) 36456707 URN:SI:UM:DK:6GNAJEQQ MAG_Baketaric_Mihael_2020.pdf MAG_Baketaric_Mihael_2020.pdf 1 584E0646A769B50C7D77F244A61E709B 5b424968601534e02e477dd8578cf093b79dc793168eb6442790774f9c852619 640b08b6-7c11-11eb-bb7a-00155d0001ca 20.500.12556/dkum/9d591d0a-4243-4333-baff-ecd3d4ad5d1a https://dk.um.si/Dokument.php?lang=slv&id=143381 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0