Page 87 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 87
” generiramo novega potomca y. Izbran potomec je pod- so: N p = y, A = 0,5, r = 0,5, fmin = 0,0, fmax = 2,0,
vrˇzen delovanju normalne selekcije v algoritmu BA [4]. F = 0,5 in CR = 0,9.
Algoritem 2 Lokalno iskanje v algoritmu HBA Vsako konfiguracijo smo zagnali 25-krat, ustavitveni pogoj
pa je bil 1000 * D ovrednotenj funkcije uspeˇsnosti.
1: if rand(0,1) > ri then
2: ri=1...3 = rand(0,1) * Np + 1; Stolpec Min predstavlja najboljˇso dobljeno reˇsitev, stolpec
3: n = rand(1, D); Max predstavlja najslabˇso dobljeno reˇsitev, stolpec Mean
4: for i = 1 to D do pa predstavlja povpreˇcje dobljenih reˇsitev. Stolpec Median
5: if rand(0,1) < CR or n == D then predstavlja srediˇsˇce med zgornjo in spodnjo mejo dobljenih
6: yn = xr1,n + F ∗ (xr2,n + xr3,n); reˇsitev, stolpec Std pa predstavlja izraˇcun standardnega od-
7: n = (n + 1)%(D + 1); klona iz njih.
8: end if
9: end for Alg. Tabela 1: Rezultati Ackley Std
10: end if BA Nast. Min Max Mean Median 1,187
HBA D=10, 14,304 18,630 17,003 17,116 0,809
2.3 Primeri ostalih razlicˇic hibridnega BA BA Np=20 2E-06 2,013 0,782 1,155 1,189
HBA D=10, 13,772 18,273 16,701 17,002 1,035
Prednost BA je, da lahko zelo hitro doseˇze konvergenco v BA Np=30 2E-06 3,404 0,908 1,155 1,607
zaˇcetni fazi. Kadar je potrebna hitra reˇsitev, se algoritem HBA D=10, 10,837 18,760 16,925 17,192 0,987
BA izkaˇze kot zelo uˇcinkovit. Cˇ e pa mu dovolimo prehiter BA Np=50 2E-06 2,580 0,999 1,155 0,690
preklop v fazo izkoriˇsˇcanja, tako da se glasnost A in impulz HBA D=20, 15,997 18,960 17,970 18,034 0,935
r prehitro spremenita, lahko to povzroˇci stagnacijo v zaˇce- BA Np=20 2,171 5,473 3,494 3,490 0,679
tni fazi. Za izboljˇsanje uˇcinkovitosti in adaptacije osnovnega HBA D=20, 16,959 19,360 18,032 18,154 1,020
algoritma so ˇstevilni avtorji ustvarili nekaj razliˇcic. Kot pri- BA Np=30 1,155 5,240 3,240 3,222 0,710
mer lahko omenimo avtorje v [15], ki so hibridizirali osnovni HBA D=20, 16,553 19,120 17,861 17,948 1,203
algoritem BA z algoritmom iskanja harmonij (angl. Har- BA Np=50 4E-07 5,650 3,070 3,223 0,650
mony Search), avtorji v [11] so hibridizirali osnovni algori- HBA D=30, 15,879 18,940 17,950 18,062 1,504
tem BA z algoritmom ABC (angl. Artificial Bee Colony), BA Np=20 3,222 8,236 5,300 4,919 0,529
avtorji v [13] pa so hibridizirali osnovno razliˇcico algoritma HBA D=30, 17,211 19,360 18,202 18,162 1,831
BA z algoritmom kresnic (angl. Firefly Algorithm). BA Np=30 2,887 10,020 6,021 6,182 0,510
HBA D=30, 17,255 19,440 18,135 18,003 1,913
3. OPIS EKSPERIMENTOV Np=50 2,580 9,475 5,857 5,503
V sekciji opiˇsemo vzpostavitev razvojnega okolja in vkljuˇci- Alg. Tabela 2: Rezultati Griewank Std
tev programske knjiˇznice NiaPy ter definiramo testne funk- BA Nast. Min Max Mean Median 0,757
cije, ki smo jih uporabili v eksperimentih. HBA D=10, 1,856 4,835 3,244 3,260 0,115
BA Np=20 0,027 0,577 0,151 0,140 0,788
3.1 Vzpostavitev razvojnega okolja HBA D=10, 1,575 4,887 3,122 3,064 0,069
BA Np=30 1E-11 0,344 0,122 0,116 0,876
Program je bil napisan v odprtokodnem programskem jeziku HBA D=10, 1,736 4,698 3,083 3,217 0,074
Python v integriranem razvojnem okolju PyCharm (IDE: BA Np=50 0,027 0,310 0,124 0,106 1,678
Jetbrains). Pri razvoju smo uporabili odprtokodno knjiˇznico HBA D=20, 3,159 10,540 6,852 6,640 0,035
Python microframework for building nature-inspired algori- BA Np=20 5E-14 0,101 0,033 0,025 1,242
thms (krajˇse NiaPy) [14], katere namen je enostavnejˇsa in HBA D=20, 4,725 9,525 6,718 6,560 0,025
hitrejˇsa uporaba algoritmov po vzorih iz narave. BA Np=30 2E-14 0,096 0,027 0,020 1,741
HBA D=20, 3,953 11,700 7,220 7,249 0,028
3.2 Testne funkcije BA Np=50 1E-13 0,118 0,026 0,020 3,019
HBA D=30, 5,226 18,170 10,970 10,501 0,035
Eksperimente smo izvedli na naslednjih desetih razliˇcnih te- BA Np=20 1E-12 0,127 0,031 0,025 2,738
stnih funkcijah [14]: Ackley, Griewank, Levy, Rastrigin, Ridge, HBA D=30, 6,596 16,460 10,993 10,982 0,027
Rosenbrock, Salomon, Schwefel, Sphere in Whitley. BA Np=30 2E-12 0,107 0,025 0,015 2,348
HBA D=30, 7,005 15,310 10,785 10,685 0,021
4. REZULTATI Np=50 1E-12 0,069 0,020 0,012
V nadaljevanju je prikazana statistika zagonov testnih funk- Iz vseh zagonov optimizacij testnih funkcij (tabele 1-10) je
cij. V stolpcu Alg. imamo kratice imen algoritmov, ki jih razvidno, da je hibridna razliˇcica algoritma po vzoru obnaˇsa-
testiramo, in sicer algoritma BA in HBA. V stolpcu Nast. nja netopirjev uˇcinkovitejˇsa od osnovne razliˇcice algoritma.
so prikazane nastavitve parametrov, ki smo jih spreminjali Naˇsa raziskava je tako potrdila ˇze obstojeˇce raziskave [5].
pri zagonih eksperimentov. Spreminjali smo dva parametra:
dimenzijo testnih funkcij in velikost populacije. D pred- Dodatno smo preizkusili delovanje obeh algoritmov z raz-
stavlja dimenzijo problema testnih funkcij. Testne funkcije
smo zaganjali na treh dimenzijah (10, 20, 30). Viˇsja kot je
dimenzija, zahtevnejˇsa je optimizacija. Velikost populacije
predstavlja ˇstevilo kandidatnih reˇsitev, ki so uporabljene v
iskalnem prostoru. Uporabili smo tri razliˇcne velikosti popu-
lacij (20, 30, 50). Preostale vrednosti nadzornih parametrov
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 87
Koper, Slovenia, 10 October
vrˇzen delovanju normalne selekcije v algoritmu BA [4]. F = 0,5 in CR = 0,9.
Algoritem 2 Lokalno iskanje v algoritmu HBA Vsako konfiguracijo smo zagnali 25-krat, ustavitveni pogoj
pa je bil 1000 * D ovrednotenj funkcije uspeˇsnosti.
1: if rand(0,1) > ri then
2: ri=1...3 = rand(0,1) * Np + 1; Stolpec Min predstavlja najboljˇso dobljeno reˇsitev, stolpec
3: n = rand(1, D); Max predstavlja najslabˇso dobljeno reˇsitev, stolpec Mean
4: for i = 1 to D do pa predstavlja povpreˇcje dobljenih reˇsitev. Stolpec Median
5: if rand(0,1) < CR or n == D then predstavlja srediˇsˇce med zgornjo in spodnjo mejo dobljenih
6: yn = xr1,n + F ∗ (xr2,n + xr3,n); reˇsitev, stolpec Std pa predstavlja izraˇcun standardnega od-
7: n = (n + 1)%(D + 1); klona iz njih.
8: end if
9: end for Alg. Tabela 1: Rezultati Ackley Std
10: end if BA Nast. Min Max Mean Median 1,187
HBA D=10, 14,304 18,630 17,003 17,116 0,809
2.3 Primeri ostalih razlicˇic hibridnega BA BA Np=20 2E-06 2,013 0,782 1,155 1,189
HBA D=10, 13,772 18,273 16,701 17,002 1,035
Prednost BA je, da lahko zelo hitro doseˇze konvergenco v BA Np=30 2E-06 3,404 0,908 1,155 1,607
zaˇcetni fazi. Kadar je potrebna hitra reˇsitev, se algoritem HBA D=10, 10,837 18,760 16,925 17,192 0,987
BA izkaˇze kot zelo uˇcinkovit. Cˇ e pa mu dovolimo prehiter BA Np=50 2E-06 2,580 0,999 1,155 0,690
preklop v fazo izkoriˇsˇcanja, tako da se glasnost A in impulz HBA D=20, 15,997 18,960 17,970 18,034 0,935
r prehitro spremenita, lahko to povzroˇci stagnacijo v zaˇce- BA Np=20 2,171 5,473 3,494 3,490 0,679
tni fazi. Za izboljˇsanje uˇcinkovitosti in adaptacije osnovnega HBA D=20, 16,959 19,360 18,032 18,154 1,020
algoritma so ˇstevilni avtorji ustvarili nekaj razliˇcic. Kot pri- BA Np=30 1,155 5,240 3,240 3,222 0,710
mer lahko omenimo avtorje v [15], ki so hibridizirali osnovni HBA D=20, 16,553 19,120 17,861 17,948 1,203
algoritem BA z algoritmom iskanja harmonij (angl. Har- BA Np=50 4E-07 5,650 3,070 3,223 0,650
mony Search), avtorji v [11] so hibridizirali osnovni algori- HBA D=30, 15,879 18,940 17,950 18,062 1,504
tem BA z algoritmom ABC (angl. Artificial Bee Colony), BA Np=20 3,222 8,236 5,300 4,919 0,529
avtorji v [13] pa so hibridizirali osnovno razliˇcico algoritma HBA D=30, 17,211 19,360 18,202 18,162 1,831
BA z algoritmom kresnic (angl. Firefly Algorithm). BA Np=30 2,887 10,020 6,021 6,182 0,510
HBA D=30, 17,255 19,440 18,135 18,003 1,913
3. OPIS EKSPERIMENTOV Np=50 2,580 9,475 5,857 5,503
V sekciji opiˇsemo vzpostavitev razvojnega okolja in vkljuˇci- Alg. Tabela 2: Rezultati Griewank Std
tev programske knjiˇznice NiaPy ter definiramo testne funk- BA Nast. Min Max Mean Median 0,757
cije, ki smo jih uporabili v eksperimentih. HBA D=10, 1,856 4,835 3,244 3,260 0,115
BA Np=20 0,027 0,577 0,151 0,140 0,788
3.1 Vzpostavitev razvojnega okolja HBA D=10, 1,575 4,887 3,122 3,064 0,069
BA Np=30 1E-11 0,344 0,122 0,116 0,876
Program je bil napisan v odprtokodnem programskem jeziku HBA D=10, 1,736 4,698 3,083 3,217 0,074
Python v integriranem razvojnem okolju PyCharm (IDE: BA Np=50 0,027 0,310 0,124 0,106 1,678
Jetbrains). Pri razvoju smo uporabili odprtokodno knjiˇznico HBA D=20, 3,159 10,540 6,852 6,640 0,035
Python microframework for building nature-inspired algori- BA Np=20 5E-14 0,101 0,033 0,025 1,242
thms (krajˇse NiaPy) [14], katere namen je enostavnejˇsa in HBA D=20, 4,725 9,525 6,718 6,560 0,025
hitrejˇsa uporaba algoritmov po vzorih iz narave. BA Np=30 2E-14 0,096 0,027 0,020 1,741
HBA D=20, 3,953 11,700 7,220 7,249 0,028
3.2 Testne funkcije BA Np=50 1E-13 0,118 0,026 0,020 3,019
HBA D=30, 5,226 18,170 10,970 10,501 0,035
Eksperimente smo izvedli na naslednjih desetih razliˇcnih te- BA Np=20 1E-12 0,127 0,031 0,025 2,738
stnih funkcijah [14]: Ackley, Griewank, Levy, Rastrigin, Ridge, HBA D=30, 6,596 16,460 10,993 10,982 0,027
Rosenbrock, Salomon, Schwefel, Sphere in Whitley. BA Np=30 2E-12 0,107 0,025 0,015 2,348
HBA D=30, 7,005 15,310 10,785 10,685 0,021
4. REZULTATI Np=50 1E-12 0,069 0,020 0,012
V nadaljevanju je prikazana statistika zagonov testnih funk- Iz vseh zagonov optimizacij testnih funkcij (tabele 1-10) je
cij. V stolpcu Alg. imamo kratice imen algoritmov, ki jih razvidno, da je hibridna razliˇcica algoritma po vzoru obnaˇsa-
testiramo, in sicer algoritma BA in HBA. V stolpcu Nast. nja netopirjev uˇcinkovitejˇsa od osnovne razliˇcice algoritma.
so prikazane nastavitve parametrov, ki smo jih spreminjali Naˇsa raziskava je tako potrdila ˇze obstojeˇce raziskave [5].
pri zagonih eksperimentov. Spreminjali smo dva parametra:
dimenzijo testnih funkcij in velikost populacije. D pred- Dodatno smo preizkusili delovanje obeh algoritmov z raz-
stavlja dimenzijo problema testnih funkcij. Testne funkcije
smo zaganjali na treh dimenzijah (10, 20, 30). Viˇsja kot je
dimenzija, zahtevnejˇsa je optimizacija. Velikost populacije
predstavlja ˇstevilo kandidatnih reˇsitev, ki so uporabljene v
iskalnem prostoru. Uporabili smo tri razliˇcne velikosti popu-
lacij (20, 30, 50). Preostale vrednosti nadzornih parametrov
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 87
Koper, Slovenia, 10 October
