Page 17 - 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. 17
vdo-kod originalnega algorithma DE prikazuje algoritem 1. Pri tej izboljˇsavi gre za izbiro mutacijske strategije. Kombi-
niramo med strategijo DE/rand/1/bin in DE/best/1/bin .
Algoritem 1 Algoritem DE Privzeto uporabljamo strategijo DE/rand/1/bin . Verje-
tnost izbire strategije DE/best/1/bin v vsaki generaciji pri
1: inicializacija; vsakem posamezniku v populaciji je 10−5, ki smo jo dolo-
2: −n−a−j−bo−l−j−s−aV−−r−e−d−n−o→st0 ← oceniVseResitve; ˇcili po obˇcutku skozi testiranja. Izbiro strategije in s tem
baznega vektorja uvedemo pred zaˇcetkom mutacije.
3: while pogojUstavljanjaIzpolnjen do
DE/best/1/bin cˇe U (0, 1) < 10−5,
4: for i ← 1, Np do IzbiraStrategije =
xpopi s←kusgneanVerreirdanjoPsots←kusoncoeRniePsoitsekvu(sxnito);Resitev(xip);
5: DE/rand/1/bin drugacˇe.
6:
V zgornji enaˇcbi predstavlja U (0, 1) nakljuˇcno ˇstevilo iz in-
7: if poskusnaVrednost > f(xti) then tervala [0,1] iz uniformne porazdelitve. Vektor mutacije mi
8: xti ← xip; pri strategiji DE/best/1/bin izraˇcunamo po enaˇcbi:
9: najboljsaVrednostti ← poskusnaVrednost;
mi = xtbest + F · xtr1 − xtr2 ,
10: end if
kjer xtbest oznaˇcuje najboljˇsega posameznika v trenutni po-
11: end for pulaciji, F je krmilni parameter, xtr1 in xtr2 pa sta nakljuˇcno
izbrana vektorja iz trenutne populacije, kjer r1 = r2. Vektor
12: end while mutacije mi pri privzeti strategiji DE/rand/1/bin izraˇcu-
namo po enaˇcbi:
3.1 Samoprilagajanje nadzornih parametrov
mi = xrt 1 + F · xrt 2 − xrt 3 .
v diferencialni evoluciji (jDE)
V literaturi najdemo veliko razliˇcnih reˇsitev, kako nastaviti
nadzorna parametra F in Cr . Izbira primernih vrednosti
nadzornih parametrov je odvisna od problema, ki ga reˇsu-
jemo. Da se izognemo temu, so avtorji Brest in ostali v [2]
predlagali izboljˇsano verzijo algoritma DE, ki nadzorna pa-
rametra F in Cr samo-prilagaja med samim izvajanjem. Po- 3.2.2 Ponastavitev posameznika
imenovali so ga algoritem jDE. Vsak posameznik v popula-
Da se izognemo lokalnemu optimumu, uporabimo mehani-
ciji je razˇsirjen z vrednostjo omenjenih parametrov, ki se zem ponastavitve posameznika (angl. random restart) z na-
kljuˇcnimi vrednostmi elementov pri operaciji kriˇzanja. Kri-
prilagajata in izboljˇsujeta skozi evolucijo in poslediˇcno iz- ˇzanje je prikazano z naslednjo enaˇcbo:
boljˇsata posameznike v poskusni populaciji. Nova nadzorna
parametra Fip in Cr p izraˇcunamo pred mutacijo, tako da xmin,j + xmax,j − xmin,j · U (0, 1) cˇe Uj (0, 1) < Cr
i ∨ jrand = j ∧ Uj (0, 1) < 10−5,
cˇe Uj (0, 1) < Cr ∨ jrand = j,
imata vpliv na operatorje DE in izraˇcun poskusne reˇsitve v
drugacˇe.
trenutni generaciji, po enaˇcbah:
ki,j = mi,j
xti,j
Fip = Fl + U1 (0, 1) · Fu cˇe U2 (0, 1) < τ1,
FiG drugacˇe,
Cˇ e je pri kriˇzanju v vsaki iteraciji dimenzije problema slu-
Cr p = U3 (0, 1) cˇe U4 (0, 1) < τ2, ˇcajno ˇstevilo U (0, 1) pod pragom 10−5, takrat celoten vektor
i drugacˇe,
Cr t ki inicializiramo na zaˇcetne vrednosti in prekinemo kriˇzanje,
i drugaˇce pa na pozicijo, ki jo oznaˇcuje indeks j, v vsaki ite-
kjer je Uj (0, 1) , j ∈ {1, 2, 3, 4} nakljuˇcna uniformna vre- raciji kopiramo vrednost vektorja mutacije mi ali vrednost
dnost iz intervala [0,1] ter τ1 in τ2 verjetnosti za spremembo trenutnega posameznika xit z istim indeksom.
parametrov F in Cr (tudi hitrosti uˇcenja). Avtorji zanju
predlagajo vrednosti τ1 = τ2 = 0, 1. Vrednosti Fl = 0, 1 in 3.2.3 Razpršenost populacije in ponastavitev posa-
Fu = 0, 9 zagotavljata, da je novi parameter F vedno na-
kljuˇcno v intervalu [0.1, 1.0]. Novi parameter Cr pa zavzema meznikov
vrednosti v intervalu [0,1] [13].
Po selekciji izraˇcunamo razprˇsenost populacije. Razprˇsenost
3.2 Modificirana diferencialna evolucija populacije sluˇzi kot merilo raznolikosti populacije. Izraˇcu-
namo jo s standardnim odklonom od povpreˇcne vrednosti
Modificirana verzija diferencialne evolucije (krajˇse MoDE) kriterijske funkcije posameznikov v populaciji, ki ga izraˇcu-
za stiskanje slik vsebuje veˇc prilagoditev in izboljˇsav. Naj- namo po enaˇcbi:
prej prilagodimo osnovni algoritem na obstojeˇc algoritem
jDE, ki je opisan v prejˇsnjem poglavju. Nato razˇsirimo jDE Np
algoritem s strategijo DE/best/1/bin , s katero doseˇzemo,
da se posamezniki pribliˇzujejo najboljˇsi reˇsitvi, okrog katere f itnesi
bi lahko bil globalni maksimum. V primeru, da pride do
izgube raznolikosti v populaciji, uporabimo ponovno inicia- povprecˇje = i=1 ,
lizacijo veˇcine posameznikov, s ˇcimer raznolikost populacije Np
poveˇcamo.
kjer seˇstejemo vse vrednosti kriterijske funkcije posamezni-
kov v populaciji in jih delimo s ˇstevilom posameznikov Np.
Povpreˇcje uporabimo pri izraˇcunu standardnega odklona v
enaˇcbi:
3.2.1 Kombiniranje mutacijskih strategij Np
’DE/rand/1/bin’ in ’DE/best/1/bin’
(povprecˇje − f itnesi)2
stdOdklon = i=1 .
Np
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 17
Ljubljana, Slovenia, 12 October
niramo med strategijo DE/rand/1/bin in DE/best/1/bin .
Algoritem 1 Algoritem DE Privzeto uporabljamo strategijo DE/rand/1/bin . Verje-
tnost izbire strategije DE/best/1/bin v vsaki generaciji pri
1: inicializacija; vsakem posamezniku v populaciji je 10−5, ki smo jo dolo-
2: −n−a−j−bo−l−j−s−aV−−r−e−d−n−o→st0 ← oceniVseResitve; ˇcili po obˇcutku skozi testiranja. Izbiro strategije in s tem
baznega vektorja uvedemo pred zaˇcetkom mutacije.
3: while pogojUstavljanjaIzpolnjen do
DE/best/1/bin cˇe U (0, 1) < 10−5,
4: for i ← 1, Np do IzbiraStrategije =
xpopi s←kusgneanVerreirdanjoPsots←kusoncoeRniePsoitsekvu(sxnito);Resitev(xip);
5: DE/rand/1/bin drugacˇe.
6:
V zgornji enaˇcbi predstavlja U (0, 1) nakljuˇcno ˇstevilo iz in-
7: if poskusnaVrednost > f(xti) then tervala [0,1] iz uniformne porazdelitve. Vektor mutacije mi
8: xti ← xip; pri strategiji DE/best/1/bin izraˇcunamo po enaˇcbi:
9: najboljsaVrednostti ← poskusnaVrednost;
mi = xtbest + F · xtr1 − xtr2 ,
10: end if
kjer xtbest oznaˇcuje najboljˇsega posameznika v trenutni po-
11: end for pulaciji, F je krmilni parameter, xtr1 in xtr2 pa sta nakljuˇcno
izbrana vektorja iz trenutne populacije, kjer r1 = r2. Vektor
12: end while mutacije mi pri privzeti strategiji DE/rand/1/bin izraˇcu-
namo po enaˇcbi:
3.1 Samoprilagajanje nadzornih parametrov
mi = xrt 1 + F · xrt 2 − xrt 3 .
v diferencialni evoluciji (jDE)
V literaturi najdemo veliko razliˇcnih reˇsitev, kako nastaviti
nadzorna parametra F in Cr . Izbira primernih vrednosti
nadzornih parametrov je odvisna od problema, ki ga reˇsu-
jemo. Da se izognemo temu, so avtorji Brest in ostali v [2]
predlagali izboljˇsano verzijo algoritma DE, ki nadzorna pa-
rametra F in Cr samo-prilagaja med samim izvajanjem. Po- 3.2.2 Ponastavitev posameznika
imenovali so ga algoritem jDE. Vsak posameznik v popula-
Da se izognemo lokalnemu optimumu, uporabimo mehani-
ciji je razˇsirjen z vrednostjo omenjenih parametrov, ki se zem ponastavitve posameznika (angl. random restart) z na-
kljuˇcnimi vrednostmi elementov pri operaciji kriˇzanja. Kri-
prilagajata in izboljˇsujeta skozi evolucijo in poslediˇcno iz- ˇzanje je prikazano z naslednjo enaˇcbo:
boljˇsata posameznike v poskusni populaciji. Nova nadzorna
parametra Fip in Cr p izraˇcunamo pred mutacijo, tako da xmin,j + xmax,j − xmin,j · U (0, 1) cˇe Uj (0, 1) < Cr
i ∨ jrand = j ∧ Uj (0, 1) < 10−5,
cˇe Uj (0, 1) < Cr ∨ jrand = j,
imata vpliv na operatorje DE in izraˇcun poskusne reˇsitve v
drugacˇe.
trenutni generaciji, po enaˇcbah:
ki,j = mi,j
xti,j
Fip = Fl + U1 (0, 1) · Fu cˇe U2 (0, 1) < τ1,
FiG drugacˇe,
Cˇ e je pri kriˇzanju v vsaki iteraciji dimenzije problema slu-
Cr p = U3 (0, 1) cˇe U4 (0, 1) < τ2, ˇcajno ˇstevilo U (0, 1) pod pragom 10−5, takrat celoten vektor
i drugacˇe,
Cr t ki inicializiramo na zaˇcetne vrednosti in prekinemo kriˇzanje,
i drugaˇce pa na pozicijo, ki jo oznaˇcuje indeks j, v vsaki ite-
kjer je Uj (0, 1) , j ∈ {1, 2, 3, 4} nakljuˇcna uniformna vre- raciji kopiramo vrednost vektorja mutacije mi ali vrednost
dnost iz intervala [0,1] ter τ1 in τ2 verjetnosti za spremembo trenutnega posameznika xit z istim indeksom.
parametrov F in Cr (tudi hitrosti uˇcenja). Avtorji zanju
predlagajo vrednosti τ1 = τ2 = 0, 1. Vrednosti Fl = 0, 1 in 3.2.3 Razpršenost populacije in ponastavitev posa-
Fu = 0, 9 zagotavljata, da je novi parameter F vedno na-
kljuˇcno v intervalu [0.1, 1.0]. Novi parameter Cr pa zavzema meznikov
vrednosti v intervalu [0,1] [13].
Po selekciji izraˇcunamo razprˇsenost populacije. Razprˇsenost
3.2 Modificirana diferencialna evolucija populacije sluˇzi kot merilo raznolikosti populacije. Izraˇcu-
namo jo s standardnim odklonom od povpreˇcne vrednosti
Modificirana verzija diferencialne evolucije (krajˇse MoDE) kriterijske funkcije posameznikov v populaciji, ki ga izraˇcu-
za stiskanje slik vsebuje veˇc prilagoditev in izboljˇsav. Naj- namo po enaˇcbi:
prej prilagodimo osnovni algoritem na obstojeˇc algoritem
jDE, ki je opisan v prejˇsnjem poglavju. Nato razˇsirimo jDE Np
algoritem s strategijo DE/best/1/bin , s katero doseˇzemo,
da se posamezniki pribliˇzujejo najboljˇsi reˇsitvi, okrog katere f itnesi
bi lahko bil globalni maksimum. V primeru, da pride do
izgube raznolikosti v populaciji, uporabimo ponovno inicia- povprecˇje = i=1 ,
lizacijo veˇcine posameznikov, s ˇcimer raznolikost populacije Np
poveˇcamo.
kjer seˇstejemo vse vrednosti kriterijske funkcije posamezni-
kov v populaciji in jih delimo s ˇstevilom posameznikov Np.
Povpreˇcje uporabimo pri izraˇcunu standardnega odklona v
enaˇcbi:
3.2.1 Kombiniranje mutacijskih strategij Np
’DE/rand/1/bin’ in ’DE/best/1/bin’
(povprecˇje − f itnesi)2
stdOdklon = i=1 .
Np
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 17
Ljubljana, Slovenia, 12 October
