RAC UNALNI STVO Algoritem na osnovi obnašanja netopirjev Karin Ljubic in Iztok Fister ml. -» Algoritmi po vzorih iz narave so posebna vrsta računalniških algoritmov za reševanje težkih optimizacijskih problemov v računalništvu, matematiki, medičini in tudi v industriji [3]. Do danes so znanstveniki razvili že veliko tovrstnih algoritmov, med njimi najbolj izstopajo vzori mravelj, čebel, kresnic in tudi kukavic. Algoritmi po vzorih iz narave Eden najnovejših predstavnikov teh algoritmov je algoritem, ki deluje na osnovi obnašanja netopirjev [4, 5]. Netopirji spadajo med sesalce in so edini sesalci z letalno mreno; ta jim omogoča letenje (ne samo jadranje). Med letenjem večina netopirjev »cvilka«. To je posebno zvočno valovanje, ki ga zaradi visokih frekvenc imenujemo tudi ultrazvočno valovanje. Ti ultrazvočni valovi se odbijajo od predmetov v okolici in tako potujejo nazaj k netopirjem. Netopirji tako slišijo odmeve svojih poslanih glasov in na podlagi gostote prejetih odmevov določijo, kako blizu je ovira. Ce je ovira zelo blizu, se bo oddani zvočni signal vrnil zelo hitro in z gosto frekvenco. Ce pa je ovira dlje, se bo oddani zvočni signal vrnil kasneje in z redkejšo frekvenco, kakor je bil oddan. Ta mehanizem zaznavanja ovir med letom s pomočjo ultrazvočnih valov se imenuje eholokačija. Poleg netopirjev se s pomočjo eholokačije orientirajo tudi nekatere druge živalske vrste. ■ Delfini: Ultrazvočne valove uporabljajo za naviga-čijo, komunikačijo, lov in obrambo v temnih vodah. ■ Kiti: Ultrazvočne valove proizvajajo s premikanjem zraka med zračnimi prostori (sinusi) v glavi. Uporabljajo ga za detektiranje hrane in podvodno navigačijo. ■ Rovke: Rovke so majhni sesalči. Ultrazvočne valove uporabljajo pri gibanju v svojem naravnem habitatu, ne toliko za plenilstvo in iskanje hrane. Postavlja se vprašanje, kako omenjeni mehanizem eholokačije uporabiti v računalništvu. Odgovor na to vprašanje je našel profesor Xin-She Yang leta 2010, ko je tedaj deloval na univerzi v Cambridgu. Ustvaril je zelo zanimiv, preprost in učinkovit algoritem. Algoritem je povezal z vzori iz narave ter eholokačije in zasnoval tri idealizirana pravila: 1. Vsi netopirji uporabljajo eholokačijo za spremljanje razdalje do tarčnih objektov. 2. Netopirji letijo naključno s hitrostjo vt na pozičijo xt s fiksno frekvenčo Qmin, variabilno valovno dolžino \t in glasnostjo At v iskanju plena. Samodejno lahko prilagajajo valovno dolžino (ali frekvenčo) svojih oddanih pulzov in prilagajo raven oddajanja pulzov rt G [0,1 ] glede na bližino tarče. 26 PRESEK 42 (2014/2015) 3 RAČUNALNIŠ TVO 3. Glasnost variira od največje (pozitivne) A0 do minimalne Amin vrednosti konstante. Psevdokod algoritma je predstavljen v spodnjem zapisu (1) in sestoji iz naslednjih glavnih korakov: ■ Vhod algoritma predstavlja populacija netopirjev, ki je predstavljena z realnimi števili. Izhod pa predstavlja najboljša rešitev ter njena pripadajoča vrednost. Iničializačija začetne populačije netopirjev se izvede s pomočjo naključnega generatorja realnih števil. Generiranje nove rešitve se izvede s premikom navideznih netopirjev glede na naslednje enačbe [4]: Q)tl = Q min + (Q max Qmin)N(0, 1), (t+1) x(t+1) = ^ = vt + (xt - best)Qi (t+i) (t) (1) vi jo optimiramo. V našem primeru bo boljša tista, ki bo bližja minimumu funkcije. Zatem sledi glavna zanka, ki teče do ustavitvenega pogoja (npr. število generačij). Znotraj te zanke teče še ena zanka, ki gre skozi vse populacije. Tukaj se generirajo rešitve s pomočjo prej predstavljenih formul. Novo rešitev torej dobimo tako, da vzamemo rešitev iz prejsnje generačije in seštejemo s hitrostjo, ki smo jo izračunali v tej generaciji. Po generiranju nove rešitev sledi korak lokalnega iskanja, kjer poskušamo s pomočjo hevristike RWDE še malo izboljšati rešitev. To poteka s pomočjo enačbe y(t) = x* + eAi"' vi' l (tKr(t) (2) kjer je N(0,1) naključno število. ■ Lokalno iskanje skrbi za izboljšanje najboljše rešitve z uporabo hevristike RWDE (random walk with direct exploitation - naključni sprehod z neposrednim izkoriščanjem). ■ Ocenjevanje najboljše rešitve in shranjevanje najboljše rešitve glede na verjetnost (parameter A določa verjetnost shranjevanja najboljše rešitve). ■ Iskanje najboljše rešitve. Delovanje si lahko še ogledamo na praktičnem primeru, kjer moramo najti minimum funkcije Sphere: F(xi) = Xn=1 x2 in pri kateri iščemo rešitev v prostoru -100,00 < xi < 100,00. Ta funkčija ima minimum pri 0 ■ (f(x1,..., xn) = f(0,..., 0) = 0). Na začetku določimo parametre algoritma, kot so velikost populačije NP, parameter A (glasnost), parameter r (raven pulza), parameter Qmin (frekvenčni minimum), parameter Qmax (frekvenčni maksimum) ter dimenzijo problema D. Obširen opis parametrov je opisan v [4]. Potem uvedemo naključno populačijo z naključnim generatorjem, ki generira vrednost med podanima mejama. V našem primeru bo to med -100 in 100. Zatem očenimo populačijo ter poiščemo najboljšo rešitev. Očenitev poteka tako, da vstavimo vrednosti v eni populačiji v funkčijo, ki kjer N(0,1) označuje naključno generirano število z intervala [-1,1], e je skalirni faktor, x* je trenutno najboljša rešitev in Ait) je glasnost. Zatem korakom sledi očenjevanje nove rešitve ter pogojno shranjevanje najboljše rešitve. Na konču pa poiščemo najboljšo rešitev. Algoritem 1 Algoritem na osnovi obnašanja netopirjev_ Vhod: Populacija netopirjev xi = (xi1,... ,xiD)T for i = 1 ...Np, MAX_FE. Izhod: Najboljša rešitev x^est in njena pripadajoča vrednost fmin = min(f(x)). 1: inicializiraj(); 2: eval = oceni_novo_populacijo(); 3: fmin = najdi_najboljšo_rešitev(xbest); 4: while ustavitveni_pogoj_ni_dosežen do 5: for i = 1 to Np do 6: y = generiraj_novo_rešitev(xi); 7: if rand(0,1) > ri then 8: y = izboljšaj_najboljšo_rešitev(xbest) 9: end if { korak lokalnega iskanja } 10: fnew = oceni_novo_rešitev(y); 11: eval = eval + 1; 12: if fnew < fi and N(0,1) a < 00 > m * £ a 7 6 1 1 5 2 8 2 5 7 3 2 6 3 1 6 3 8 1 2 S 2 1 17 L 8 3 9 L 6 8 E 1 S 17 Z L L S Z 8 3 6 17 17 E 9 8 S 2 L L 3 8 7 5 17 9 Z L 9 17 Z L E L S 8 2 5 17 L 9 1 8 E 8 1 E 6 Z 17 7 S www.presek.si XXX 28 PRESEK 42 (2014/2015) 3 28