Prírodou inšpirované algoritmy

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)
  .