Page 24 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2017 4th Student Computer Science Research Conference. Koper: University of Primorska Press, 2017
P. 24
• Direktna kinematika (”Forward Kinematics”) - FK: Slika 2: Potek algoritma diferencialne evolucije.
opisuje matematiˇcni proces raˇcunanja koordinat konˇc-
nega sklepa E iz parametrov vseh predhodnih skle- 3. Mutacija - iz starˇsevskih vektorjev (XiG) ustvarimo
pov [?]. ti. mutiran vektor (MGi ).
• Inverzna kinematika (”Inverse Kinematics”) - IK: MiG = XGri1 + F ∗ (XGr2i − XrGi3 ); (1)
opisuje matematiˇcni proces doloˇcanja parametrov vseh 0 ≤ i < Np, r0i = r1i = r2i = i
sklepov, da se bo konˇcni sklep E nahajal na ˇzeljenih
koordinatah [?]. • XrGki - nakljuˇcni starˇsevski vektor; k={1,2,3}
• F - mutacijski faktor
Reˇsevanje FK je trivialno in obsega zgolj geometriˇcno raˇcu-
nanje, medtem ko IK povzroˇca veliko veˇcje probleme. Re- 4. Kriˇzanje - definira postopek, v katerem iz starˇsevskih
ˇsitev problema IK se namreˇc nahaja v kompleksnih, tesno in mutiranih vektorjev sestavimo preizkusni vektor (PiG):
povezanih in skrajno nelinearnih matematiˇcnih enaˇcbah, ki
vraˇcajo veˇc razliˇcnih reˇsitev [?, ?]. Zato ne preseneˇca, da PiG,j = MiG,j , ˇce je Randi,j[0,1) ≤ Cr (2)
je tema najrazliˇcnejˇsih metod in raziskav. Za mnoge pro- XiG,j , drugaˇce
bleme IK obstajajo ti. analitiˇcne reˇsitve, ki so na voljo v
zaprti obliki. Parametri, ki jih vraˇcajo te reˇsitve, so toˇcni • Cr - faktor kriˇzanja
in se izraˇcunajo v zgolj nekaj mikrosekundah [?]. Vendar
analitiˇcne reˇsitve bodisi ˇse niso odkrite za vse probleme ali 5. Selekcija - vsak i-ti preizkusni in pripadajoˇci starˇsevski
pa jih sploh ni mogoˇce pridobiti. V teh primerih se upora- vektor ocenimo s pomoˇcjo ocenitvene funkcije (eval ).
bijo ti. raˇcunske metode, katere pa vraˇcajo zgolj pribliˇzno V kolikor je ocena za preizkusni vektor boljˇsi od ocene
reˇsitev in so ponavadi raˇcunsko, in poslediˇcno tudi ˇcasovno za starˇsevski vektor, potem preizkusni vektor zamenja
dokaj zahtevne. Nekatere izmed teh metod so [?]: Jacobian starˇsevski vektor v populaciji, kot prikazuje naslednja
inversion method, Jacobian construction, iterativna metoda, enaˇcba:
optimizacijska metoda, Cyclic coordinate descent, Jacobian
transpose method, genetsko programiranje, itd. XGi +1 = PGi , ˇce je eval(PiG) ≥ eval(XiG) (3)
XiG, drugaˇce
3. DIFERENCIALNA EVOLUCIJA
Algoritem diferencialne evolucije (DE) predstavlja metodo
za globalno optimizacijo danega problema [?, ?]. Leta 1996
ga je predstavil K. Price kot eno izmed moˇznih metod za
reˇsevanje polinomov Cˇ ebiˇsova. Sˇe istega leta je algoritem
dosegel zavidljive rezultate na prvem tekmovanju evolucij-
skih algoritmov v Nagoyi. Zaradi uˇcinkovitosti in prepro-
stosti je bil uporabljen za reˇsevanje razliˇcnih probemov kot
so npr. uglaˇsevanje ˇsahovske ocenitvene funkcije [?], optimi-
zacijacija zvijanja proteinov [?], multimodalno optimizacijo
[?] itd. Nekatere prednosti DE so, da je izjemno stabilen pri
problemih, ki vkljuˇcujejo nekonveksne, multimodalne in ne-
linearne funkcije. Torej je nalaˇsˇc primeren za naˇs problem,
kjer reˇsujemo IK.
Naˇcin delovanja diferencialne evolucije prikazuje slika 2 in
vsebuje naslednje mehanizme:
1. Definiranje zaˇcetne populacije - nakljuˇcno definiramo
Np ˇstevilo posameznikov - XGi (imenovanih tudi star-
ˇsevski vektorji), kjer vsak posameznik predstavlja mo-
rebitno reˇsitev obravnavanega problema:
XiG = {x0, x1, . . . , xj}; 0 ≤ i < Np, 0 ≤ j < D, G = 0,
• xj - j-ta neznanka v problemu
• Np - ˇstevilo posameznikov znotraj populacije
• D - dimenzija problema
• G - generacija
2. Sprehod skozi vse generacije - v vsaki iteraciji DE se
izvede ena generacija (G), vse dokler ni zadoˇsˇceno za-
ustavitvenemu kriteriju, kot sta npr.: maksimalno ˇste-
vilo ovrednotenj in doseganje doloˇcene kvalitete reˇsi-
tve.
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 24
Ljubljana, Slovenia, 11 October
opisuje matematiˇcni proces raˇcunanja koordinat konˇc-
nega sklepa E iz parametrov vseh predhodnih skle- 3. Mutacija - iz starˇsevskih vektorjev (XiG) ustvarimo
pov [?]. ti. mutiran vektor (MGi ).
• Inverzna kinematika (”Inverse Kinematics”) - IK: MiG = XGri1 + F ∗ (XGr2i − XrGi3 ); (1)
opisuje matematiˇcni proces doloˇcanja parametrov vseh 0 ≤ i < Np, r0i = r1i = r2i = i
sklepov, da se bo konˇcni sklep E nahajal na ˇzeljenih
koordinatah [?]. • XrGki - nakljuˇcni starˇsevski vektor; k={1,2,3}
• F - mutacijski faktor
Reˇsevanje FK je trivialno in obsega zgolj geometriˇcno raˇcu-
nanje, medtem ko IK povzroˇca veliko veˇcje probleme. Re- 4. Kriˇzanje - definira postopek, v katerem iz starˇsevskih
ˇsitev problema IK se namreˇc nahaja v kompleksnih, tesno in mutiranih vektorjev sestavimo preizkusni vektor (PiG):
povezanih in skrajno nelinearnih matematiˇcnih enaˇcbah, ki
vraˇcajo veˇc razliˇcnih reˇsitev [?, ?]. Zato ne preseneˇca, da PiG,j = MiG,j , ˇce je Randi,j[0,1) ≤ Cr (2)
je tema najrazliˇcnejˇsih metod in raziskav. Za mnoge pro- XiG,j , drugaˇce
bleme IK obstajajo ti. analitiˇcne reˇsitve, ki so na voljo v
zaprti obliki. Parametri, ki jih vraˇcajo te reˇsitve, so toˇcni • Cr - faktor kriˇzanja
in se izraˇcunajo v zgolj nekaj mikrosekundah [?]. Vendar
analitiˇcne reˇsitve bodisi ˇse niso odkrite za vse probleme ali 5. Selekcija - vsak i-ti preizkusni in pripadajoˇci starˇsevski
pa jih sploh ni mogoˇce pridobiti. V teh primerih se upora- vektor ocenimo s pomoˇcjo ocenitvene funkcije (eval ).
bijo ti. raˇcunske metode, katere pa vraˇcajo zgolj pribliˇzno V kolikor je ocena za preizkusni vektor boljˇsi od ocene
reˇsitev in so ponavadi raˇcunsko, in poslediˇcno tudi ˇcasovno za starˇsevski vektor, potem preizkusni vektor zamenja
dokaj zahtevne. Nekatere izmed teh metod so [?]: Jacobian starˇsevski vektor v populaciji, kot prikazuje naslednja
inversion method, Jacobian construction, iterativna metoda, enaˇcba:
optimizacijska metoda, Cyclic coordinate descent, Jacobian
transpose method, genetsko programiranje, itd. XGi +1 = PGi , ˇce je eval(PiG) ≥ eval(XiG) (3)
XiG, drugaˇce
3. DIFERENCIALNA EVOLUCIJA
Algoritem diferencialne evolucije (DE) predstavlja metodo
za globalno optimizacijo danega problema [?, ?]. Leta 1996
ga je predstavil K. Price kot eno izmed moˇznih metod za
reˇsevanje polinomov Cˇ ebiˇsova. Sˇe istega leta je algoritem
dosegel zavidljive rezultate na prvem tekmovanju evolucij-
skih algoritmov v Nagoyi. Zaradi uˇcinkovitosti in prepro-
stosti je bil uporabljen za reˇsevanje razliˇcnih probemov kot
so npr. uglaˇsevanje ˇsahovske ocenitvene funkcije [?], optimi-
zacijacija zvijanja proteinov [?], multimodalno optimizacijo
[?] itd. Nekatere prednosti DE so, da je izjemno stabilen pri
problemih, ki vkljuˇcujejo nekonveksne, multimodalne in ne-
linearne funkcije. Torej je nalaˇsˇc primeren za naˇs problem,
kjer reˇsujemo IK.
Naˇcin delovanja diferencialne evolucije prikazuje slika 2 in
vsebuje naslednje mehanizme:
1. Definiranje zaˇcetne populacije - nakljuˇcno definiramo
Np ˇstevilo posameznikov - XGi (imenovanih tudi star-
ˇsevski vektorji), kjer vsak posameznik predstavlja mo-
rebitno reˇsitev obravnavanega problema:
XiG = {x0, x1, . . . , xj}; 0 ≤ i < Np, 0 ≤ j < D, G = 0,
• xj - j-ta neznanka v problemu
• Np - ˇstevilo posameznikov znotraj populacije
• D - dimenzija problema
• G - generacija
2. Sprehod skozi vse generacije - v vsaki iteraciji DE se
izvede ena generacija (G), vse dokler ni zadoˇsˇceno za-
ustavitvenemu kriteriju, kot sta npr.: maksimalno ˇste-
vilo ovrednotenj in doseganje doloˇcene kvalitete reˇsi-
tve.
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 24
Ljubljana, Slovenia, 11 October
