Page 85 - 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. 85
merjava osnovnega algoritma po vzoru obnašanja
netopirjev in njegove hibridne razlicˇ ice HBA
Žan Grajfoner Lucija Brezocˇnik
Fakulteta za elektrotehniko, Fakulteta za elektrotehniko,
racˇunalništvo in informatiko racˇunalništvo in informatiko
Koroška cesta 46 Koroška cesta 46
2000 Maribor, Slovenija 2000 Maribor, Slovenija
zan.grajfoner@student.um.si lucija.brezocnik@um.si
POVZETEK dom. Veˇc izvidniˇskih ˇcebel odleti na iskanje potencialne lo-
kacije, vendar dokonˇcno odloˇcitev o najprimernejˇsi lokaciji
V prispevku smo se osredotoˇcili na algoritme inteligence sprejmejo skupaj.
roja, ki ˇcrpajo navdih iz obnaˇsanja roja ˇzivali v naravi. Pri-
merjali smo osnovni algoritem po vzoru obnaˇsanja netopir- V prispevku, ki je povzetek diplomskega dela [6], se bomo
jev in njegovo hibridno razliˇcico. Raziskali smo razlike med osredotoˇcili na algoritem po vzoru obnaˇsanja netopirjev (angl.
osnovnima arhitekturama obeh algoritmov, pripadajoˇce pa- Bat Algorithm, krajˇse BA), ki ga uvrˇsˇcamo v skupino SI.
rametre, kot tudi nekaj drugih hibridnih razliˇcic algoritma Obstojeˇce ˇstudije so pokazale, da lahko algoritem BA hitreje
po vzoru obnaˇsanja netopirjev. Primerjavo smo izvedli na doseˇze boljˇse rezultate pri reˇsevanju optimizacijskih proble-
praktiˇcnem primeru optimizacije desetih testnih funkcij na mov glede na njegove predhodnike, kot je na primer genet-
treh razliˇcnih dimenzijah problema (10, 20, 30). Prav tako ski algoritem [10]. Algoritem BA posnema naravni fenomen
smo raziskali vpliv razliˇcnih velikosti populacije (20, 30, 50) netopirjev – eholokacijo. Netopirji med letenjem spuˇsˇcajo
pri obeh algoritmih. Ugotovili smo, da so rezultati optimi- visoke zvoke, kakrˇsnih ˇcloveˇsko uho ne zaznava. Zvok po-
zacije hibridne razliˇcice algoritma boljˇsi od osnovne razliˇcice tuje skozi zrak kakor val in se odbije od vsakega objekta.
algoritma. Netopirji posluˇsajo odbiti zvok in na podlagi tega doloˇcijo
oddaljenost, velikost ter obliko predmeta.
Kjucˇne besede
Ker osnovni algoritem BA ni primeren za reˇsevanje vseh dru-
algoritem po vzoru obnaˇsanja netopirjev, evolucijski algo- ˇzin problemov, so razliˇcni avtorji predlagali veˇc hibridnih
ritmi, hibridizacija, inteligenca roja, raˇcunska inteligenca razliˇcic, ki razˇsirjujejo osnovni algoritem BA z mehanizmi
drugih algoritmov [15, 11, 13]. Prav tako nekateri avtorji
1. UVOD navajajo razliˇcne nastavitve nadzornih parametrov, kot so
na primer velikost populacije in minimalna/maksimalna fre-
Algoritmi po vzoru iz narave posnemajo delovanje razliˇc- kvenca.
nih naravnih in bioloˇskih sistemov [17, 3]. Veˇcinoma se
uporabljajo za reˇsevanje kompleksnih optimizacijskih pro- Glavni cilj prispevka je primerjava osnovnega algoritma BA,
blemov [3], kot so na primer sestava urnikov, izbira naj- ki ga je predlagal Yang [16], in hibridnega algoritma po vzoru
boljˇse lokacije za postavitev antene in iskanje najkrajˇse poti obnaˇsanja netopirjev (angl. Hybrid Bat Algorithm, krajˇse
na grafu. Med tovrstne algoritme uvrˇsˇcamo tudi algoritme HBA), ki ga so ga predlagali Fister in ostali [5]. Algoritma
inteligence rojev [9], ki so dandanes prisotni v ˇstevilnih re- bomo uporabili pri optimizaciji veˇc testnih funkcij in s po-
alnih aplikacijah [8]. moˇcjo eksperimenta skuˇsali odgovorili na dve raziskovalni
vpraˇsanji (RV).
Inteligenca roja (angl. Swarm Intelligence, krajˇse SI) [1,
2] predstavlja ˇstudije kolektivnega obnaˇsanja mnoˇziˇcnih sis- RV1: Ali hibridni algoritem po vzoru obnaˇsanja netopir-
temov, ki se razvijajo s ˇcasom. Takˇsne sisteme v naravi jev dosega boljˇse rezultate kot osnovni algoritem po vzoru
tvorijo razni insekti (npr. ˇcebele in mravlje) in druge ˇzivali obnaˇsanja netopirjev pri veˇcji velikosti populacije?
(npr. ptice in ribe). Predstavimo primer inteligence roja na
ˇcebelah [7]. Cˇ ebela sledi sploˇsnim in enostavnim pravilom, RV2: Ali hibridni algoritem po vzoru obnaˇsanja netopirjev
vendar lahko v roju z drugimi ˇcebelami reˇsuje kompleksnejˇse dosega boljˇse rezultate kot osnovni algoritem po vzoru ob-
naloge, kot je na primer izbira prave lokacije za njihov novi naˇsanja netopirjev pri optimizaciji funkcij viˇsjih dimenzij?
V drugi sekciji predstavimo algoritem BA in njegovo hibri-
dno razliˇcico, tretja sekcija je namenjena orisu zasnove eks-
perimenta, analiza dobljenih rezultatov pa je zbrana v ˇcetrti
sekciji. Prispevek strnemo v peti sekciji in podamo smernice
za prihodnji razvoj.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.85-90 85
Koper, Slovenia, 10 October
netopirjev in njegove hibridne razlicˇ ice HBA
Žan Grajfoner Lucija Brezocˇnik
Fakulteta za elektrotehniko, Fakulteta za elektrotehniko,
racˇunalništvo in informatiko racˇunalništvo in informatiko
Koroška cesta 46 Koroška cesta 46
2000 Maribor, Slovenija 2000 Maribor, Slovenija
zan.grajfoner@student.um.si lucija.brezocnik@um.si
POVZETEK dom. Veˇc izvidniˇskih ˇcebel odleti na iskanje potencialne lo-
kacije, vendar dokonˇcno odloˇcitev o najprimernejˇsi lokaciji
V prispevku smo se osredotoˇcili na algoritme inteligence sprejmejo skupaj.
roja, ki ˇcrpajo navdih iz obnaˇsanja roja ˇzivali v naravi. Pri-
merjali smo osnovni algoritem po vzoru obnaˇsanja netopir- V prispevku, ki je povzetek diplomskega dela [6], se bomo
jev in njegovo hibridno razliˇcico. Raziskali smo razlike med osredotoˇcili na algoritem po vzoru obnaˇsanja netopirjev (angl.
osnovnima arhitekturama obeh algoritmov, pripadajoˇce pa- Bat Algorithm, krajˇse BA), ki ga uvrˇsˇcamo v skupino SI.
rametre, kot tudi nekaj drugih hibridnih razliˇcic algoritma Obstojeˇce ˇstudije so pokazale, da lahko algoritem BA hitreje
po vzoru obnaˇsanja netopirjev. Primerjavo smo izvedli na doseˇze boljˇse rezultate pri reˇsevanju optimizacijskih proble-
praktiˇcnem primeru optimizacije desetih testnih funkcij na mov glede na njegove predhodnike, kot je na primer genet-
treh razliˇcnih dimenzijah problema (10, 20, 30). Prav tako ski algoritem [10]. Algoritem BA posnema naravni fenomen
smo raziskali vpliv razliˇcnih velikosti populacije (20, 30, 50) netopirjev – eholokacijo. Netopirji med letenjem spuˇsˇcajo
pri obeh algoritmih. Ugotovili smo, da so rezultati optimi- visoke zvoke, kakrˇsnih ˇcloveˇsko uho ne zaznava. Zvok po-
zacije hibridne razliˇcice algoritma boljˇsi od osnovne razliˇcice tuje skozi zrak kakor val in se odbije od vsakega objekta.
algoritma. Netopirji posluˇsajo odbiti zvok in na podlagi tega doloˇcijo
oddaljenost, velikost ter obliko predmeta.
Kjucˇne besede
Ker osnovni algoritem BA ni primeren za reˇsevanje vseh dru-
algoritem po vzoru obnaˇsanja netopirjev, evolucijski algo- ˇzin problemov, so razliˇcni avtorji predlagali veˇc hibridnih
ritmi, hibridizacija, inteligenca roja, raˇcunska inteligenca razliˇcic, ki razˇsirjujejo osnovni algoritem BA z mehanizmi
drugih algoritmov [15, 11, 13]. Prav tako nekateri avtorji
1. UVOD navajajo razliˇcne nastavitve nadzornih parametrov, kot so
na primer velikost populacije in minimalna/maksimalna fre-
Algoritmi po vzoru iz narave posnemajo delovanje razliˇc- kvenca.
nih naravnih in bioloˇskih sistemov [17, 3]. Veˇcinoma se
uporabljajo za reˇsevanje kompleksnih optimizacijskih pro- Glavni cilj prispevka je primerjava osnovnega algoritma BA,
blemov [3], kot so na primer sestava urnikov, izbira naj- ki ga je predlagal Yang [16], in hibridnega algoritma po vzoru
boljˇse lokacije za postavitev antene in iskanje najkrajˇse poti obnaˇsanja netopirjev (angl. Hybrid Bat Algorithm, krajˇse
na grafu. Med tovrstne algoritme uvrˇsˇcamo tudi algoritme HBA), ki ga so ga predlagali Fister in ostali [5]. Algoritma
inteligence rojev [9], ki so dandanes prisotni v ˇstevilnih re- bomo uporabili pri optimizaciji veˇc testnih funkcij in s po-
alnih aplikacijah [8]. moˇcjo eksperimenta skuˇsali odgovorili na dve raziskovalni
vpraˇsanji (RV).
Inteligenca roja (angl. Swarm Intelligence, krajˇse SI) [1,
2] predstavlja ˇstudije kolektivnega obnaˇsanja mnoˇziˇcnih sis- RV1: Ali hibridni algoritem po vzoru obnaˇsanja netopir-
temov, ki se razvijajo s ˇcasom. Takˇsne sisteme v naravi jev dosega boljˇse rezultate kot osnovni algoritem po vzoru
tvorijo razni insekti (npr. ˇcebele in mravlje) in druge ˇzivali obnaˇsanja netopirjev pri veˇcji velikosti populacije?
(npr. ptice in ribe). Predstavimo primer inteligence roja na
ˇcebelah [7]. Cˇ ebela sledi sploˇsnim in enostavnim pravilom, RV2: Ali hibridni algoritem po vzoru obnaˇsanja netopirjev
vendar lahko v roju z drugimi ˇcebelami reˇsuje kompleksnejˇse dosega boljˇse rezultate kot osnovni algoritem po vzoru ob-
naloge, kot je na primer izbira prave lokacije za njihov novi naˇsanja netopirjev pri optimizaciji funkcij viˇsjih dimenzij?
V drugi sekciji predstavimo algoritem BA in njegovo hibri-
dno razliˇcico, tretja sekcija je namenjena orisu zasnove eks-
perimenta, analiza dobljenih rezultatov pa je zbrana v ˇcetrti
sekciji. Prispevek strnemo v peti sekciji in podamo smernice
za prihodnji razvoj.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.85-90 85
Koper, Slovenia, 10 October
