Page 86 - 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. 86
ALGORITMI PO VZORU OBNAŠANJA ˇstevilo, ki definira velikost izhodnega pulza. Parameter xtbest
NETOPIRJEV definira trenutno najboljˇso globalno pozicijo oziroma reˇsitev.
V sekciji 2.1 predstavimo osnovno razliˇcico algoritma BA, v Druga strategija izboljˇsa trenutni poloˇzaj virtualnega neto-
sekciji 2.2 njegovo hibridno razliˇcico, sekcija 2.3 pa zajema pirja po enaˇcbi 3:
predstavitev nekaterih drugih hibridnih razliˇcic BA.
xt = xbtest + Atiϕ, (3)
2.1 Algoritem po vzoru obnašanja netopirjev
v kateri ϕ ∈ [0, 1] definira nakljuˇcno ˇstevilo iz Gaussove
Algoritem po vzoru obnaˇsanja netopirjev spada v druˇzino distribucije s srednjo vrednostjo 1 in standardnim odklonom
algoritmov SI in ga je leta 2010 razvil Xin-She Yang na uni- 0, ϕ > 0 je skalirni faktor in Ati predstavlja glasnost.
verzi v Cambridgeu [16]. Njegov namen je bil razviti enosta-
ven in uˇcinkovit algoritem, ki bi bil primeren za uporabo v Ta strategija je namenjena izkoriˇsˇcanju najboljˇse reˇsitve, saj
razliˇcnih aplikacijah za reˇsevanje optimizacijskih problemov. je usmerjena k raziskovanju obmoˇcja najboljˇse reˇsitve in po-
V algoritmu je poskuˇsal posnemati pojav eholokacije pri mi- nazarja vrsto nakljuˇcnega sprehoda (angl. Random Walk
kronetopirjih. Originalni algoritem BA obravnava netopirje Direct Exploitation, krajˇse RWDE) [4]. Algoritem BA nad-
kot roj, ki se pomika po prostoru in iˇsˇce svoj plen. Obna- zorujeta dva parametra in sicer stopnja pulza ri in glasnost
ˇsanje netopirjev je kompleksno in zahtevno, zaradi ˇcesar je Ai. Matematiˇcno lahko to prikaˇzemo z enaˇcbo 4:
neposredni prenos v t. i. raˇcunalniˇski sistem prezahteven.
Zato je njihovo obnaˇsanje opisal v algoritmu z naslednjimi Ai(t+1) = αAit, rit = ri0[1 − exp(−γ )], (4)
poenostavljenimi pravili [4]:
v kateri α in γ predstavljata konstante. Obe vplivata na
1. Vsi netopirji uporabljajo eholokacijo za spremljanje stopnjo konvergence algoritma [16].
razdalje do ciljnih objektov.
Psevdokoda algoritma BA je prikazana v algoritmu 1.
2. Netopirji pri iskanju hrane letijo nakljuˇcno s hitrostjo
vi na pozicijo xi s fiksno frekvenco fmin, variabilno Algoritem 1 Algoritem BA
valovno dolˇzino λi in glasnostjo Ai. Samodejno lahko
prilagajajo valovno dolˇzino (ali frekvenco) pulzov, ki Vhod: populacija xi = (xi,1, xi,2, . . . , xi,D) for i =
jih oddajajo, in prilagajajo raven oddajanja pulzov 1 . . . N p, MAX FE.
r i ∈ [0, 1] glede na bliˇzino cilja. Izhod: najboljˇsa reˇsitev xbest in njena vrednost fmin
3. Glasnost variira od najveˇcje (pozitivne) A0 do mini- 1: inicializacija populacije;
malne vrednosti Amin. 2: eval = oceni novo populacijo;
3: fmin = najdi najboljˇso reˇsitev (xbest);
BA vzdrˇzuje populacijo virtualnih netopirjev med delova- 4: while ustavitveni pogoj ni doseˇzen do
njem. Vsak poloˇzaj netopirja predstavlja reˇsitev problema 5: for i = 1 to N p do
in vsaka reˇsitev problema je predstavljena kot vektor realnih 6: generiraj novo reˇsitev (xi);
ˇstevil (enaˇcba 1): 7: if rand(0,1) > ri then
8: y = izboljˇsaj najboljˇso reˇsitev (xbest);
x(t) = {x(i,t1), . . . , xi(,tD) }, za i = 1, . . . , N p, (1) 9: end if
10: fnew = oceni novo reˇsitev (y);
v kateri D oznaˇcuje dimenzijo problema, t predstavlja tre- 11: if fnew ≤ fi and rand(0,1) < Ai then
nutno generacijo, N p pa ˇstevilo virtualnih netopirjev v po- 12: xi = y;
pulaciji. Vsak vektor doloˇca poloˇzaj virtualnega netopirja 13: fi = fnew;
v iskalnem prostoru. Netopirji se gibajo v obmoˇcju proti 14: end if
uˇcinkovitejˇsim reˇsitvam in pri tem odkrivajo nova obetavna 15: fmin = poiˇsˇci najboljˇso reˇsitev (xbest);
podroˇcja. Algoritem BA omogoˇca dve strategiji preiskova- 16: end for
nja. 17: end while
Prvo strategijo za gibanje netopirjev prikazujejo naslednje 2.2 Hibridni algoritem po vzoru obnašanja ne-
enaˇcbe 2:
topirjev
fit = fmin + (fmax − fmin)β, (2)
vit+1 = vit + (xit − xtbest)fit, Hibridni algoritem po vzoru obnaˇsanja netopirjev je eden
xti+1 = xit + vi(t+1) od prvih hibridnih razliˇcic BA. HBA je hibridiziran z muta-
cijskimi strategijami diferencialne evolucije [12]. Strategija
lokalnega iskanja osnovnega algoritma BA je zamenjana s
strategijo mutacije DE, ki je prikazana v algoritmu 2.
V intervalu fit ∈ (fmax, fmin) se spreminja frekvenca pulza. V algoritmu HBA se na zaˇcetku izberejo tri nakljuˇcne reˇsitve
Iz uniformne porazdelitve β ∈ [0, 1] se generira nakljuˇcno v populaciji. S pomoˇcjo diferencialne evolucije “DE/rand/1/
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 86
Koper, Slovenia, 10 October
NETOPIRJEV definira trenutno najboljˇso globalno pozicijo oziroma reˇsitev.
V sekciji 2.1 predstavimo osnovno razliˇcico algoritma BA, v Druga strategija izboljˇsa trenutni poloˇzaj virtualnega neto-
sekciji 2.2 njegovo hibridno razliˇcico, sekcija 2.3 pa zajema pirja po enaˇcbi 3:
predstavitev nekaterih drugih hibridnih razliˇcic BA.
xt = xbtest + Atiϕ, (3)
2.1 Algoritem po vzoru obnašanja netopirjev
v kateri ϕ ∈ [0, 1] definira nakljuˇcno ˇstevilo iz Gaussove
Algoritem po vzoru obnaˇsanja netopirjev spada v druˇzino distribucije s srednjo vrednostjo 1 in standardnim odklonom
algoritmov SI in ga je leta 2010 razvil Xin-She Yang na uni- 0, ϕ > 0 je skalirni faktor in Ati predstavlja glasnost.
verzi v Cambridgeu [16]. Njegov namen je bil razviti enosta-
ven in uˇcinkovit algoritem, ki bi bil primeren za uporabo v Ta strategija je namenjena izkoriˇsˇcanju najboljˇse reˇsitve, saj
razliˇcnih aplikacijah za reˇsevanje optimizacijskih problemov. je usmerjena k raziskovanju obmoˇcja najboljˇse reˇsitve in po-
V algoritmu je poskuˇsal posnemati pojav eholokacije pri mi- nazarja vrsto nakljuˇcnega sprehoda (angl. Random Walk
kronetopirjih. Originalni algoritem BA obravnava netopirje Direct Exploitation, krajˇse RWDE) [4]. Algoritem BA nad-
kot roj, ki se pomika po prostoru in iˇsˇce svoj plen. Obna- zorujeta dva parametra in sicer stopnja pulza ri in glasnost
ˇsanje netopirjev je kompleksno in zahtevno, zaradi ˇcesar je Ai. Matematiˇcno lahko to prikaˇzemo z enaˇcbo 4:
neposredni prenos v t. i. raˇcunalniˇski sistem prezahteven.
Zato je njihovo obnaˇsanje opisal v algoritmu z naslednjimi Ai(t+1) = αAit, rit = ri0[1 − exp(−γ )], (4)
poenostavljenimi pravili [4]:
v kateri α in γ predstavljata konstante. Obe vplivata na
1. Vsi netopirji uporabljajo eholokacijo za spremljanje stopnjo konvergence algoritma [16].
razdalje do ciljnih objektov.
Psevdokoda algoritma BA je prikazana v algoritmu 1.
2. Netopirji pri iskanju hrane letijo nakljuˇcno s hitrostjo
vi na pozicijo xi s fiksno frekvenco fmin, variabilno Algoritem 1 Algoritem BA
valovno dolˇzino λi in glasnostjo Ai. Samodejno lahko
prilagajajo valovno dolˇzino (ali frekvenco) pulzov, ki Vhod: populacija xi = (xi,1, xi,2, . . . , xi,D) for i =
jih oddajajo, in prilagajajo raven oddajanja pulzov 1 . . . N p, MAX FE.
r i ∈ [0, 1] glede na bliˇzino cilja. Izhod: najboljˇsa reˇsitev xbest in njena vrednost fmin
3. Glasnost variira od najveˇcje (pozitivne) A0 do mini- 1: inicializacija populacije;
malne vrednosti Amin. 2: eval = oceni novo populacijo;
3: fmin = najdi najboljˇso reˇsitev (xbest);
BA vzdrˇzuje populacijo virtualnih netopirjev med delova- 4: while ustavitveni pogoj ni doseˇzen do
njem. Vsak poloˇzaj netopirja predstavlja reˇsitev problema 5: for i = 1 to N p do
in vsaka reˇsitev problema je predstavljena kot vektor realnih 6: generiraj novo reˇsitev (xi);
ˇstevil (enaˇcba 1): 7: if rand(0,1) > ri then
8: y = izboljˇsaj najboljˇso reˇsitev (xbest);
x(t) = {x(i,t1), . . . , xi(,tD) }, za i = 1, . . . , N p, (1) 9: end if
10: fnew = oceni novo reˇsitev (y);
v kateri D oznaˇcuje dimenzijo problema, t predstavlja tre- 11: if fnew ≤ fi and rand(0,1) < Ai then
nutno generacijo, N p pa ˇstevilo virtualnih netopirjev v po- 12: xi = y;
pulaciji. Vsak vektor doloˇca poloˇzaj virtualnega netopirja 13: fi = fnew;
v iskalnem prostoru. Netopirji se gibajo v obmoˇcju proti 14: end if
uˇcinkovitejˇsim reˇsitvam in pri tem odkrivajo nova obetavna 15: fmin = poiˇsˇci najboljˇso reˇsitev (xbest);
podroˇcja. Algoritem BA omogoˇca dve strategiji preiskova- 16: end for
nja. 17: end while
Prvo strategijo za gibanje netopirjev prikazujejo naslednje 2.2 Hibridni algoritem po vzoru obnašanja ne-
enaˇcbe 2:
topirjev
fit = fmin + (fmax − fmin)β, (2)
vit+1 = vit + (xit − xtbest)fit, Hibridni algoritem po vzoru obnaˇsanja netopirjev je eden
xti+1 = xit + vi(t+1) od prvih hibridnih razliˇcic BA. HBA je hibridiziran z muta-
cijskimi strategijami diferencialne evolucije [12]. Strategija
lokalnega iskanja osnovnega algoritma BA je zamenjana s
strategijo mutacije DE, ki je prikazana v algoritmu 2.
V intervalu fit ∈ (fmax, fmin) se spreminja frekvenca pulza. V algoritmu HBA se na zaˇcetku izberejo tri nakljuˇcne reˇsitve
Iz uniformne porazdelitve β ∈ [0, 1] se generira nakljuˇcno v populaciji. S pomoˇcjo diferencialne evolucije “DE/rand/1/
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 86
Koper, Slovenia, 10 October
