Page 15 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2015 2nd Student Computer Science Research Conference. Koper: University of Primorska Press, 2015
P. 15
re in merjenjem ˇcasa odmeva. Poslediˇcno lahko ob znani Algoritem 1 Algoritem na osnovi obnaˇsanja netopirjev
hitrosti potovanja zvoka po zraku doloˇcimo oddaljenost od
plena ali ovire. Vpis: Populacija netopirjev xi = (xi1, . . . , xiD)T za i = 1 . . . N p,
M AX F E.
Obnaˇsanje netopirja lahko zapiˇsemo z matematiˇcnim mode- Izpis: Najboljˇsa reˇsitev xbest in njena vrednost fmax =
lom, ki temelji na naslednjih osnovnih pojmih: max(f (x)).
• dejanski frekvenci oddajanja Qi, 1: init bat();
• dejanski hitrosti leta vi(t) in 2: eval = vrednoti novo populacijo;
• dejanskemu poloˇzaju netopirja x(it), 3: fmax = iˇsˇci najboljˇso reˇsitev(xbest );
4: while termination condition not met do
medtem ko nakljuˇcni let netopirja zapiˇsemo kot kombinacijo 5: for i = 1 to N p do
treh enaˇcb: 6: y = generiraj novo reˇsitev(xi);
7: if rand(0, 1) < ri then
Qi = Qmin + (Qmin − Qmin ) · β, (5) 8: y = izboljˇsaj najboljˇso reˇsitev(xbest )
9: end if { lokalno iskanje }
vi(t+1) = vi(t) + x(it) − xb(te)st · Qi, (6) 10: fnew = vrednoti novo reˇsitev(y);
11: eval = eval + 1;
x(it+1) = xi(t) + vi(t), (7) 12: if fnew ≤ fi and N(0, 1) < Ai then
13: xi = y; fi = fnew;
kjer Qmax in Qmin predstavljata zgornjo in spodnjo mejo 14: end if { shrani najboljˇso reˇsitev pogojno }
15: fmax =iˇsˇci najboljˇso reˇsitev(xbest );
frekvence inicializiranih ob zagonu, krmilni parameter β je 16: end for
nakljuˇcno ˇstevilo generirano v intervalu [0, 1] in x(bte)st trenu- 17: end while
tna najboljˇsa reˇsitev.
Slednji ima najviˇsjo vrednost ocenjevalne funkcije in pred-
Proces iskanja v algoritmu BA je odvisen od dveh procesov, stavlja trenutno najboljˇso globalno reˇsitev. Jedro algoritma
tj. preiskovanja (angl. exploration) in izkoriˇsˇcanja (angl. predstavlja globalna zanka, ki se izvaja dokler ne preseˇzemo
exploitation). Preiskovanje je moˇcnejˇse zlasti ob zaˇcetku op- maksimalnega ˇstevila iteracij, oz. dovolj kakovostne predpi-
timizacije, ko so poloˇzaji posameznikov razmetani nakljuˇcno sane reˇsitve. V tej zanki iz vsakega posameznika generiramo
po preiskovalnem prostoru. Izkoriˇsˇcanje pomeni, da zaˇcne novo reˇsitev s pomoˇcjo preiskovanja. Glede na verjetnost, da
preiskovalni proces izboljˇsevati najdeno reˇsitev obiˇcajno z emisija pulzov pade pod doloˇceno mejo ˇce je ta dovolj blizu
metodami lokalnega iskanja. Vsak posameznik se pri pre- reˇsitve pa nadaljujemo tudi na proces izkoriˇsˇcanja, imeno-
iskovanju prostora giba v smeri trenutne najboljˇse reˇsitve, vanega tudi lokalno iskanje. Novo pridobljeno reˇsitev shra-
kar v naravi pomeni, da netopir oddaja ultrazvoˇcne pulze nimo le, ˇce je glasnost oddajanja ultrazvoˇcnih pulzov dovolj
visokih glasnosti Ai, ki poslediˇcno potujejo dlje. Te pulze majhna, kar pomeni, da se netopir nahaja blizu plena. V
oddaja le nekajkrat v sekundi, npr. osem do desetkrat, kar nasprotnem primeru reˇsitev zavrˇzemo.
definiramo s parametrov emisija pulzov ri. Ko netopir opazi
plen, se mu zaˇcne pribliˇzevati, glasnost zaˇcne upadati, med- Algoritem iˇsˇce optimalne parametre za nastavitev regula-
tem ko emisija pulzov raste. V tej fazi zaˇcne preiskovalni torja v omejenem definicijskem obmoˇcju, ki prepreˇcuje ne-
algoritem preiskani prostor reˇsitev izkoriˇsˇcati. Matematiˇcno stabilno delovanje robota. Po vsakem izraˇcunanem premiku
obstajata torej dva raˇcunska postopka za opis obeh kom- novo nastale parametre vpiˇse v regulator ter poˇcaka na izvr-
ponent preiskovalnega proces, tj. preiskovanje je zapisano ˇsitev le-teh. Kriterijska funkcija vsako dvojico parametrov
v enaˇcbah (5)-(7), medtem ko izkoriˇsˇcanje sledi zapisu v ovrednoti ter rezultat posreduje algoritmu. Vsako ovredno-
enaˇcbi (8): tenje zaradi mehanskih omejitev traja natanˇcno deset se-
kund, zato za nas hitrost izvajanja algoritma ni pomembna.
xnovi = xstari + · A¯(t). (8) Vsekakor pa s poveˇcevanjem ˇstevila posameznikov ter ge-
neracij premo sorazmerno poveˇcujemo tudi ˇcas potreben za
Glasnost Ai in emisija pulzov ri se sicer v originalnem al- optimizacijo.
goritmu spreminjata, vendar se je za potrebe naˇse optimi-
zacije izkazalo najbolje, da oba parametra nastavimo fiksno 4. REZULTATI
in s tem uravnavamo mejo med procesoma preiskovanja in
izkoriˇsˇcanja. S tem doseˇzemo nekoliko niˇzjo konvergenco V tem poglavju predstavljamo rezultate pridobljene na re-
v zaˇcetnih generacijah. Oba parametra sta v originalnem alni laboratorijski aplikaciji. Zaradi stohastiˇcnosti algoritma
algoritmu odvisna od funkcijskih predpisov, ki pa zaˇcetno je posnetih veˇc odzivov na stopniˇcno funkcijo, ˇceprav se v
vrednost parametra v nekaj generacijah fiksirata na kon- praksi uporablja le osnovno testiranje, ko deluje robot brez
stantne vrednosti, zato se parametra v poznejˇsih generaci- prenihaja. Rezultati so bili posneti s pomoˇcjo orodja MA-
jah obnaˇsata podobno, kot ˇce bi ju fiksirali. Vse omenjene TLAB/Simulink ter vmesniˇske kartice DSP-2 Roby. Prika-
enaˇcbe lahko strnemo v optimizacijski algoritem, katerega zani rezultati veljajo za dvoosnega robota (n = 2). Krmilni
psevdokod je prikazan v algoritmu 1. Algoritem zaˇcnemo z parametri algoritma BA so bili nastavljeni med eksperimenti
inicializacijo nakljuˇcnih posameznikov. Populacijo ovredno- na naslednje vrednosti:
timo ter poiˇsˇcemo posameznika z najkakovostnejˇso reˇsitvijo.
• ˇstevilo posameznikov Np = 10,
• ˇstevilo iteracij ngen = 10,
• emisijo pulzov ri = 0.1,
• glasnost oddajanja pulzov Ai = 0.9 in
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 15
Ljubljana, Slovenia, 6 October
hitrosti potovanja zvoka po zraku doloˇcimo oddaljenost od
plena ali ovire. Vpis: Populacija netopirjev xi = (xi1, . . . , xiD)T za i = 1 . . . N p,
M AX F E.
Obnaˇsanje netopirja lahko zapiˇsemo z matematiˇcnim mode- Izpis: Najboljˇsa reˇsitev xbest in njena vrednost fmax =
lom, ki temelji na naslednjih osnovnih pojmih: max(f (x)).
• dejanski frekvenci oddajanja Qi, 1: init bat();
• dejanski hitrosti leta vi(t) in 2: eval = vrednoti novo populacijo;
• dejanskemu poloˇzaju netopirja x(it), 3: fmax = iˇsˇci najboljˇso reˇsitev(xbest );
4: while termination condition not met do
medtem ko nakljuˇcni let netopirja zapiˇsemo kot kombinacijo 5: for i = 1 to N p do
treh enaˇcb: 6: y = generiraj novo reˇsitev(xi);
7: if rand(0, 1) < ri then
Qi = Qmin + (Qmin − Qmin ) · β, (5) 8: y = izboljˇsaj najboljˇso reˇsitev(xbest )
9: end if { lokalno iskanje }
vi(t+1) = vi(t) + x(it) − xb(te)st · Qi, (6) 10: fnew = vrednoti novo reˇsitev(y);
11: eval = eval + 1;
x(it+1) = xi(t) + vi(t), (7) 12: if fnew ≤ fi and N(0, 1) < Ai then
13: xi = y; fi = fnew;
kjer Qmax in Qmin predstavljata zgornjo in spodnjo mejo 14: end if { shrani najboljˇso reˇsitev pogojno }
15: fmax =iˇsˇci najboljˇso reˇsitev(xbest );
frekvence inicializiranih ob zagonu, krmilni parameter β je 16: end for
nakljuˇcno ˇstevilo generirano v intervalu [0, 1] in x(bte)st trenu- 17: end while
tna najboljˇsa reˇsitev.
Slednji ima najviˇsjo vrednost ocenjevalne funkcije in pred-
Proces iskanja v algoritmu BA je odvisen od dveh procesov, stavlja trenutno najboljˇso globalno reˇsitev. Jedro algoritma
tj. preiskovanja (angl. exploration) in izkoriˇsˇcanja (angl. predstavlja globalna zanka, ki se izvaja dokler ne preseˇzemo
exploitation). Preiskovanje je moˇcnejˇse zlasti ob zaˇcetku op- maksimalnega ˇstevila iteracij, oz. dovolj kakovostne predpi-
timizacije, ko so poloˇzaji posameznikov razmetani nakljuˇcno sane reˇsitve. V tej zanki iz vsakega posameznika generiramo
po preiskovalnem prostoru. Izkoriˇsˇcanje pomeni, da zaˇcne novo reˇsitev s pomoˇcjo preiskovanja. Glede na verjetnost, da
preiskovalni proces izboljˇsevati najdeno reˇsitev obiˇcajno z emisija pulzov pade pod doloˇceno mejo ˇce je ta dovolj blizu
metodami lokalnega iskanja. Vsak posameznik se pri pre- reˇsitve pa nadaljujemo tudi na proces izkoriˇsˇcanja, imeno-
iskovanju prostora giba v smeri trenutne najboljˇse reˇsitve, vanega tudi lokalno iskanje. Novo pridobljeno reˇsitev shra-
kar v naravi pomeni, da netopir oddaja ultrazvoˇcne pulze nimo le, ˇce je glasnost oddajanja ultrazvoˇcnih pulzov dovolj
visokih glasnosti Ai, ki poslediˇcno potujejo dlje. Te pulze majhna, kar pomeni, da se netopir nahaja blizu plena. V
oddaja le nekajkrat v sekundi, npr. osem do desetkrat, kar nasprotnem primeru reˇsitev zavrˇzemo.
definiramo s parametrov emisija pulzov ri. Ko netopir opazi
plen, se mu zaˇcne pribliˇzevati, glasnost zaˇcne upadati, med- Algoritem iˇsˇce optimalne parametre za nastavitev regula-
tem ko emisija pulzov raste. V tej fazi zaˇcne preiskovalni torja v omejenem definicijskem obmoˇcju, ki prepreˇcuje ne-
algoritem preiskani prostor reˇsitev izkoriˇsˇcati. Matematiˇcno stabilno delovanje robota. Po vsakem izraˇcunanem premiku
obstajata torej dva raˇcunska postopka za opis obeh kom- novo nastale parametre vpiˇse v regulator ter poˇcaka na izvr-
ponent preiskovalnega proces, tj. preiskovanje je zapisano ˇsitev le-teh. Kriterijska funkcija vsako dvojico parametrov
v enaˇcbah (5)-(7), medtem ko izkoriˇsˇcanje sledi zapisu v ovrednoti ter rezultat posreduje algoritmu. Vsako ovredno-
enaˇcbi (8): tenje zaradi mehanskih omejitev traja natanˇcno deset se-
kund, zato za nas hitrost izvajanja algoritma ni pomembna.
xnovi = xstari + · A¯(t). (8) Vsekakor pa s poveˇcevanjem ˇstevila posameznikov ter ge-
neracij premo sorazmerno poveˇcujemo tudi ˇcas potreben za
Glasnost Ai in emisija pulzov ri se sicer v originalnem al- optimizacijo.
goritmu spreminjata, vendar se je za potrebe naˇse optimi-
zacije izkazalo najbolje, da oba parametra nastavimo fiksno 4. REZULTATI
in s tem uravnavamo mejo med procesoma preiskovanja in
izkoriˇsˇcanja. S tem doseˇzemo nekoliko niˇzjo konvergenco V tem poglavju predstavljamo rezultate pridobljene na re-
v zaˇcetnih generacijah. Oba parametra sta v originalnem alni laboratorijski aplikaciji. Zaradi stohastiˇcnosti algoritma
algoritmu odvisna od funkcijskih predpisov, ki pa zaˇcetno je posnetih veˇc odzivov na stopniˇcno funkcijo, ˇceprav se v
vrednost parametra v nekaj generacijah fiksirata na kon- praksi uporablja le osnovno testiranje, ko deluje robot brez
stantne vrednosti, zato se parametra v poznejˇsih generaci- prenihaja. Rezultati so bili posneti s pomoˇcjo orodja MA-
jah obnaˇsata podobno, kot ˇce bi ju fiksirali. Vse omenjene TLAB/Simulink ter vmesniˇske kartice DSP-2 Roby. Prika-
enaˇcbe lahko strnemo v optimizacijski algoritem, katerega zani rezultati veljajo za dvoosnega robota (n = 2). Krmilni
psevdokod je prikazan v algoritmu 1. Algoritem zaˇcnemo z parametri algoritma BA so bili nastavljeni med eksperimenti
inicializacijo nakljuˇcnih posameznikov. Populacijo ovredno- na naslednje vrednosti:
timo ter poiˇsˇcemo posameznika z najkakovostnejˇso reˇsitvijo.
• ˇstevilo posameznikov Np = 10,
• ˇstevilo iteracij ngen = 10,
• emisijo pulzov ri = 0.1,
• glasnost oddajanja pulzov Ai = 0.9 in
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 15
Ljubljana, Slovenia, 6 October
