Page 18 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016
P. 18
e je standardni odklon oziroma razprˇsenost populacije manjˇsa
od praga, ki ga doloˇcimo pri testiranju, ponastavimo 90 %
najslabˇsih posameznikov na zaˇcetne vrednosti in s tem po-
veˇcamo raznolikost populacije.
4. KUKAVIcˇJE ISKANJE
V nadaljevanju predstavljamo osnovni algoritem s kukavi-
ˇcjim iskanjem [11] (angl. Cuckoo Search, krajˇse CS), kjer je
vhod v algoritem zaˇcetna populacija, sestavljena iz posame-
znikov inicializiranih z nakljuˇcnimi vrednostmi elementov,
ki predstavljajo reˇsitve. Izhod algoritma je najboljˇsa reˇsi-
tev oz. najboljˇsi posameznik glede na kriterijsko funkcijo.
Osnovni algoritem vsebuje inicializacijo in glavno zanko, ki
teˇce do pogoja ustavljanja. Za vsakega posameznika iz po-
pulacije najprej generiramo novo reˇsitev z distribucijo Levy
in jo ocenimo s kriterijsko funkcijo. Iz populacije izberemo
nakljuˇcnega posameznika, njegovo vrednost kriterijske funk-
cije primerjamo z vrednostjo kriterijske funkcije potencialne
nove reˇsitve in tega zamenjamo z novo reˇsitvijo v primeru,
da je ta boljˇsa. Sledi zamenjava najslabˇsega posameznika s
posameznikom, ki ga dobimo z nakljuˇcno inicializacijo po-
sameznika v primeru, da je nakljuˇcno generirano ˇstevilo iz
intervala [0, 1] < pα. Na koncu vsake iteracije poiˇsˇcemo in
shranimo najboljˇso reˇsitev v populaciji v globalno reˇsitev, ki
je izhod algoritma. Model algoritma s kukaviˇcjim iskanjem
je prikazan na sliki 3.
Psevdo-kod originalnega algorithma CS prikazuje algoritem 2.
Algoritem 2 Algoritem CS
1: in−n−ai−cj−ibao−lli−jz−sa−aciV−j−ar;−e−d−n−o→st0 ← oceniVseResitve;
2:
3: while pogojUstavljanjaIzpolnjen do
4: for i ← 1, Np do
5: xip ← generirajPoskusnoResitev(xit);
6: poskusnaVrednost ← oceniPoskusnoResitev(xip);
7: jrand ← U(1, Np);
8: if poskusnaVrednost > najboljsaVrednostjtrand
then
9: xt ← xpi ; Slika 3: Model algoritma s kukaviˇcjim iskanjem
jrand algoritmom je v tem, da generiramo Np novih reˇsitev in ne
10: najboljsaVrednosttjrand ← poskusnaVrednost; izbiramo nakljuˇcne reˇsitve za primerjavo z novo reˇsitvijo,
11: end if ampak primerjamo kar reˇsitve z istim indeksom.
12: if U(0, 1) < pα then 4.1.2 Hibridizacija z mutacijsko strategijo DE
13: inicializacija(xtnajslabsi);
Odkrite posameznike modificiramo po vzoru mutacijske stra-
14: end if tegije DE [8]. Tu gre za neke vrste pristransko nakljuˇcno
iskanje, kjer razliko nakljuˇcno izbranih posameznikov pri-
15: shraniGlobalnoNajboljsoResitev; ˇstejemo reˇsitvi posameznika, ki ga trenutno zavraˇcamo. Na-
kljuˇcne posameznike izberemo tako, da generiramo dve polji
16: end for permutacij dolˇzine Np, nato izraˇcunamo razliko vektorjev z
istim indeksom in vsakokrat dobimo drugo razliko. Modifi-
17: end while cirano nakljuˇcno iskanje izrazimo z naslednjo enaˇcbo:
4.1 Modificirano kukavicˇje iskanje xti+1 = xti + U (0, 1) × H (pα − ε) × xtj − xkt ,
Modificirana verzija CS (krajˇse MoCS) vsebuje dve glavni kjer sta xjt in xkt nakljuˇcno izbrana posameznika iz popula-
izboljˇsavi. Najprej razˇsirimo algoritem CS z generiranjem cije, U (0, 1) funkcija, ki vrne nakljuˇcno realno ˇstevilo z uni-
Np kukaviˇcjih jajc v eni iteraciji, nato uvedemo hibridizacijo formno porazdelitvijo iz intervala [0,1], H (pα − ε) je funk-
z mutacijsko strategijo DE. cija Heaviside, s katero odloˇcimo, ali zavrˇzemo ali obdrˇzimo
novega posameznika, katere rezultat je 0, ˇce je pα − ε < 0
4.1.1 Razširitev algoritma CS
Najprej generiramo Np novih reˇsitev (kukaviˇcja gnezda) in
jih ocenimo s kriterijsko funkcijo. Vrednosti kriterijske funk-
cije novih reˇsitev primerjamo z vrednostmi kriterijske funk-
cije reˇsitev iz trenutne populacije na vsakem indeksu od 1
do Np in nove reˇsitve zamenjamo z reˇsitvami iz trenutne
populacije v primeru, da so te boljˇse. Razlika z osnovnim
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 18
Ljubljana, Slovenia, 12 October
od praga, ki ga doloˇcimo pri testiranju, ponastavimo 90 %
najslabˇsih posameznikov na zaˇcetne vrednosti in s tem po-
veˇcamo raznolikost populacije.
4. KUKAVIcˇJE ISKANJE
V nadaljevanju predstavljamo osnovni algoritem s kukavi-
ˇcjim iskanjem [11] (angl. Cuckoo Search, krajˇse CS), kjer je
vhod v algoritem zaˇcetna populacija, sestavljena iz posame-
znikov inicializiranih z nakljuˇcnimi vrednostmi elementov,
ki predstavljajo reˇsitve. Izhod algoritma je najboljˇsa reˇsi-
tev oz. najboljˇsi posameznik glede na kriterijsko funkcijo.
Osnovni algoritem vsebuje inicializacijo in glavno zanko, ki
teˇce do pogoja ustavljanja. Za vsakega posameznika iz po-
pulacije najprej generiramo novo reˇsitev z distribucijo Levy
in jo ocenimo s kriterijsko funkcijo. Iz populacije izberemo
nakljuˇcnega posameznika, njegovo vrednost kriterijske funk-
cije primerjamo z vrednostjo kriterijske funkcije potencialne
nove reˇsitve in tega zamenjamo z novo reˇsitvijo v primeru,
da je ta boljˇsa. Sledi zamenjava najslabˇsega posameznika s
posameznikom, ki ga dobimo z nakljuˇcno inicializacijo po-
sameznika v primeru, da je nakljuˇcno generirano ˇstevilo iz
intervala [0, 1] < pα. Na koncu vsake iteracije poiˇsˇcemo in
shranimo najboljˇso reˇsitev v populaciji v globalno reˇsitev, ki
je izhod algoritma. Model algoritma s kukaviˇcjim iskanjem
je prikazan na sliki 3.
Psevdo-kod originalnega algorithma CS prikazuje algoritem 2.
Algoritem 2 Algoritem CS
1: in−n−ai−cj−ibao−lli−jz−sa−aciV−j−ar;−e−d−n−o→st0 ← oceniVseResitve;
2:
3: while pogojUstavljanjaIzpolnjen do
4: for i ← 1, Np do
5: xip ← generirajPoskusnoResitev(xit);
6: poskusnaVrednost ← oceniPoskusnoResitev(xip);
7: jrand ← U(1, Np);
8: if poskusnaVrednost > najboljsaVrednostjtrand
then
9: xt ← xpi ; Slika 3: Model algoritma s kukaviˇcjim iskanjem
jrand algoritmom je v tem, da generiramo Np novih reˇsitev in ne
10: najboljsaVrednosttjrand ← poskusnaVrednost; izbiramo nakljuˇcne reˇsitve za primerjavo z novo reˇsitvijo,
11: end if ampak primerjamo kar reˇsitve z istim indeksom.
12: if U(0, 1) < pα then 4.1.2 Hibridizacija z mutacijsko strategijo DE
13: inicializacija(xtnajslabsi);
Odkrite posameznike modificiramo po vzoru mutacijske stra-
14: end if tegije DE [8]. Tu gre za neke vrste pristransko nakljuˇcno
iskanje, kjer razliko nakljuˇcno izbranih posameznikov pri-
15: shraniGlobalnoNajboljsoResitev; ˇstejemo reˇsitvi posameznika, ki ga trenutno zavraˇcamo. Na-
kljuˇcne posameznike izberemo tako, da generiramo dve polji
16: end for permutacij dolˇzine Np, nato izraˇcunamo razliko vektorjev z
istim indeksom in vsakokrat dobimo drugo razliko. Modifi-
17: end while cirano nakljuˇcno iskanje izrazimo z naslednjo enaˇcbo:
4.1 Modificirano kukavicˇje iskanje xti+1 = xti + U (0, 1) × H (pα − ε) × xtj − xkt ,
Modificirana verzija CS (krajˇse MoCS) vsebuje dve glavni kjer sta xjt in xkt nakljuˇcno izbrana posameznika iz popula-
izboljˇsavi. Najprej razˇsirimo algoritem CS z generiranjem cije, U (0, 1) funkcija, ki vrne nakljuˇcno realno ˇstevilo z uni-
Np kukaviˇcjih jajc v eni iteraciji, nato uvedemo hibridizacijo formno porazdelitvijo iz intervala [0,1], H (pα − ε) je funk-
z mutacijsko strategijo DE. cija Heaviside, s katero odloˇcimo, ali zavrˇzemo ali obdrˇzimo
novega posameznika, katere rezultat je 0, ˇce je pα − ε < 0
4.1.1 Razširitev algoritma CS
Najprej generiramo Np novih reˇsitev (kukaviˇcja gnezda) in
jih ocenimo s kriterijsko funkcijo. Vrednosti kriterijske funk-
cije novih reˇsitev primerjamo z vrednostmi kriterijske funk-
cije reˇsitev iz trenutne populacije na vsakem indeksu od 1
do Np in nove reˇsitve zamenjamo z reˇsitvami iz trenutne
populacije v primeru, da so te boljˇse. Razlika z osnovnim
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 18
Ljubljana, Slovenia, 12 October
