Obsah
Úvod
História
Základný tvar algoritmu
Prečo GA fungujú?
Modifikácie pre špeciálne typy problémov
Nastavenie parametrov
Hybridizácia GA
Koevolúcia
Paralelizácia GA
Aplikácie GA
Aplikácie GA na internete
Klasifikačné systémy
Evolučná stratégia
Evolučné programovanie
Prílohy
Literatúra a linky
O tejto kapitole



Ostatné kapitoly
Genetické algoritmy
Genetické programovanie
Umelá embryogenéza
Evolučný dizajn
Interaktívny evolučný výpočet
Ekogramatiky
Evolučný hardware


Hlavne menu
 O nás
 Tutoriály
 Archiv


Paralelizácia GA

GA sú vo všeobecnosti veľmi náročné na čas, preto by bolo vhodné ich nejakým spôsob urýchliť. Azda najlepším prostriedkom k dosiahnutiu tohto cieľa je práve paralelizácia, ktorú je tu možné robiť troma spôsobmi:

  • Globálna paralelizácia. Najjednoduchší spôsob, pričom cieľom je nemeniť štruktúru algoritmu, iba vykonať paralelne čo sa dá. Hlavnou doménou pri tomto prístupe je výpočet vhodnosti jedincov, keďže jednou z nevýhod GA je obrovské množstvo vyhodnocovania cieľovej funkcie. Okrem toho je to ešte napr. mutácia, kríženie, niektoré metódy selekcie (turnaje), ale neoplatí sa to robiť, pretože samotná réžia by bola dlhšia.
  • Hrubozrné algoritmy. Celá populácia sa rozdelí na subpopulácie (10 - 20) podľa počtu procesorov. Pričom subpopulácie sa vyvíjajú osobitne v procesore, ale keďže ich veľkosť je menšia, konvergencia je rýchlejšia. Tomu možno predchádzať špeciálnym operátorom migrácie. Ide o výber genetického materiálu z populácie a jeho rozoslanie (kedy, ako a kam ho rozoslať?). Frekvenciu migrácie je potrebné nastaviť optimálne (parameter). Vyberať genetický materiál možno buď náhodne alebo nejako deterministicky. Rozosielať ho každému procesoru, alebo hlavnému procesoru, ktorý to rozdistribuuje, prípadne použiť špeciálnu štruktúru, kde nesusedí každý s každým, a posielať genetický materiál len susedom (tzv. stepping stone - nemusí skončiť u suseda, ale môže sa šíriť ďalej vo vlnách).
  • Jemnozrné algoritmy. Rozdiel oproti hrubozrným je v počte subpopulácií (tu ich býva aj 1000). Typické je, že subpopuláciu tvorí jeden jedinec. Ťažko povedať, že by komunikoval každý s každým, potrebná je špeciálna architektúra siete a jej prispôsobený algoritmus. Jedinec komunikuje len so susedmi, pričom pri jeho evolvovaní sa druhý rodič vyberá z okolia jedinca, skríži sa, zmutuje a výsledok ostáva v danom procesore. Nie je potrebný špeciálny operátor migrácie, pretože takto sa zabezpečí aj prenos genetického materiálu (opäť si možno predstaviť jeho šírenie v celej populácii pomocou metafory
    stepping stone)
    .

Hore
Kontakty:     webmaster     admin     chief
Valid HTML 4.01! Valid CSS!