Genetické algoritmy

Genetické algoritmy (GA) sú biologicky motivované prehíadávacie algoritmy. Ich vznik sa spája s Johnom Hollandom, profes...


Genetické algoritmy (GA) sú biologicky motivované prehíadávacie algoritmy. Ich
vznik sa spája s Johnom Hollandom, profesorom na MIT. GA tvoria podmnožinu
evolučných algoritmov, spolu s GA patria medzi evolučné algoritmy ešte evolučné
stratégie a evolučné programovanie.
Biologická motivácia GA spočíva v práci s populáciou jedincov a v usmerňovaní
prehíadávania priestoru riešení spÖsobmi vlastnými živej prírode: sexuálnym
krížením, mutáciou a selekciou jedincov s uprednostňovaním vhodnejších jedincov
selekčným tlakom. Matematicky sú GA založené na tzv. schéme teorém a hypotéze
stavebných blokov.

Základný tvar algoritmu
GA v základnom tvare pozostáva z nasledujúcich krokov:
Inicializácia. Vyberú sa (spravidla náhodne) body stavového priestoru, ktoré
vytvoria populáciu jedincov. Vyhodnotí sa funkcia vhodnosti každého jedinca
(angl. fitness function).
Výber rodičov. Z existujúcej populácie sa vyberú jedinci, ktorý budú rodičmi
jedincov ďalšej populácie. Rodičia mÖžu byť dvaja alebo aj viacerí.
Kríženie. Vybratí rodičia si navzájom vymenia časť genetickej informácie, t.j.
svoje súradnice v stavovom priestore, predstavujúce parametre optimalizovaného
problému. Tým vzniknú noví jedinci potomkovia, ktorých je spravidla rovnaký
počet ako bolo rodičov.
Mutácia. Každý z potomkov je náhodným spÖsobom s určitou (spravidla veími
malou) pravdepodobnosťou mierne pozmenený.
Vyhodnotenie. Populácia potomkov je vyhodnotená, t.j. je vyhodnotená funkcia
vhodnosti každého potomka.
Nahradenie. Populácia rodičov je nahradená populáciou potomkov, ktorí sa sami
stávajú rodičmi nasledujúcej generácie. Algoritmus sa znova opakuje výberom
rodičov, krížením, mutáciou a náhradou populácie.
Pri výbere rodičov nie je zámerne použitý termín selekcia, pretože toto
označenie sa v kontexte GA spája s tzv. selekčným tlakom, t.j. s
uprednostňovaním jedincov s vyššou hodnotou fitness v optimalizačnom procese.
Aj keď práve výber rodičov je zvyčajným miestom, kde sa realizuje selekčný
tlak, je možné uprednostniť lepších jedincov aj v kroku náhrady starej
populácie novou.

Selekcia
Selekcia má za úlohu realizovať tzv. selekčný tlak, t.j. uprednostňovať
jedincov s vyššou hodnotou funkcie vhodnosti. MÖže byť použitá pri výbere
rodičov, alebo pri náhrade starej populácie novou. Existuje niekoíko základných
druhov selekcií:
Ruleta (alebo metódy založené na očakávaných hodnotách). Ide o najvšeobecnejší
spÖsob selekcie, pri ktorom je pravdepodobnosť vybratia jedinca priamoúmerná
jeho vhodnosti, t.j. čím lepší jedinec, tým s väčšou pravdepodobnosťou bude
selektovaný.
Pri samotnej selekcii sa vygeneruje náhodné číslo z intervalu [0, 1] a porovná
sa s vhodnosťou prvého jedinca. Ak je jeho vhodnosť (po uvedenej transformácii)
vyššia ako vygenerované číslo, selektuje sa tento jedinec. Ak je jeho vhodnosť
nižšia ako vygenerované číslo, toto číslo sa zmenší o hodnotu vhodnosti daného
jedinca a získané číslo sa porovná s vhodnosťou nasledujúceho jedinca. Pred
samotnou selekciou je vhodné poradie jedincov zamiešať.
Turnaj. Z populácie sa náhodne vyberie q jedincov a najlepší z nich sa stáva
rodičom. q sa volí zvyčajne 2, 3 alebo 4. Výhoda turnajovej selekcie je v jej
jednoduchosti a v možnosti dobre regulovať selekčný tlak. Táto metóda selekcie
vykazuje vysoký selekčný tlak už pri q = 2.
Orezanie. Jedinci sa zoradia podía vhodnosti a populácia sa rozdelí na dve
polovice. Jedinci sú za rodičov vyberaní iba z "lepšej" polovice, a to náhodne
alebo deterministicky.
Kríženie (crossover) je genetická operácia aplikovateíná na dvoch alebo
viacerých rodičov, pri ktorej si títo vymenia časť svojho genetického
materiálu. Podía počtu bodov, v ktorých ku kríženiu dochádza, hovoríme o
jedno-, dvojalebo viacbodovom krížení.
Najjednoduchšie bude vysvetliť kríženie na príklade. Pre jednoduchosť
predpokladajme dvoch rodičov a jednobodové kríženie. Nech rodičia A a B majú
genotypy:
A: [U-G-L-Y-W-O-M-A-N]
B: [N-I-C-E-H-O-R-S-E]
Náhodne sa vygeneruje bod kríženia od 1 po N 1, kde N je počet génov, t.j. v
našom prípade písmen v genóme jedincov. Predpokladajme, že N = 4. Preto ku
prekríženiu genotypov dÖjde medzi štvrtým a piatym génom, čoho výsledkom budú
dvaja noví potomkovia C a D:
C: [U-G-L-Y-H-O-R-S-E]
D: [N-I-C-E-W-O-M-A-N]
Vidíme, že napriek tomu, že nedošlo k pridaniu ani k strate žiadnej genetickej
informácie, ale iba k jej rekombinácii, výsledok kríženia mal na vlastnosti
jedincov silný vplyv. Krížením dochádza k výmene vlastností rodičov. Práve táto
operácia poskytuje GA možnosť efektívneho prehíadávania celého stavového
priestoru oproti napr. horolezeckým algoritmom a v kombinácii so selekčným
tlakom napomáha rýchlej konvergencii optimalizačného procesu. Kríženie však
nedokáže do "genofondu" priniesť novú informáciu; na to sa používa mutácia.

Mutácia
Mutácia je operácia, pri ktorej jedinci podliehajú malej náhodnej zmene. Keď sa
vrátime k vyššie uvedenému príkladu, tak novo vzniknutí jedinci C a D mÖžu po
aplikácii mutácie vyzerať napr. takto:
C: [U-G-L-Y-H-O-U-S-E]
D: [N-I-C-E-W-O-M-E-N]
Vidíme, že aj slabá mutácia priniesla do populácie novú informáciu. Aby mutácia
v GA nepÖsobila proti selekčnému tlaku, vykonáva sa iba s určitou
pravdepodobnosťou, zvyčajne veími malou (pod 10%). Platí, že ak je použitá
metóda selekcie s nízkym selekčným tlakom (napr. ruleta), tak musí byť použitá
aj nízka pravdepodobnosť mutácie.

Náhrada
Náhrada je tá časť GA, ktorá zabezpečuje výber jedincov, ktorí prežívajú a
prechádzajú do ďalšej generácie. Rozlišujeme dva hlavné typy metód náhrady:
Do ďalšej generácie sa vyberá iba spomedzi potomkov; populácia prežíva iba
jednu generáciu. Takýto prístup sa nazýva generačný. Pri výbere jedincov možno
použiť akúkoívek metódu selekcie. Spravidla sa pri tomto prístupe selekčný tlak
realizuje pri výbere rodičov a generuje sa iba taký počet potomkov, aký je
počet jedincov v populácii. Pri náhrade sa jednoducho celá populácia rodičov
nahradí všetkými vytvorenými potomkami.
Do ďalšej generácie sa vyberá tak spomedzi potomkov, ako aj spomedzi rodičov.
Pri tomto prístupe sa zvyčajne rodičia volia náhodne, vytvorí sa populácia
potomkov a vhodnou metódou selekcie (napr. turnajom) sa zo všetkých rodičov aj
potomkov vyberú jedinci ďalšej generácie. V súvislosti s náhradou populácie a
selekciou je potrebné spomenúť tzv. elitizmus, pri ktorom najlepší jedinec
(alebo niekoíko najlepších jedincov) prechádza do nasledujúcej populácie
deterministicky, bez selekcie, čím je zaručené prenesenie "dobrej" genetickej
informácie. Elitizmus výrazne ovplyvňuje mieru konvergencie algoritmu.
Zastavenie GA
V základnej schéme GA v úvode tohto článku bolo uvedené opakovanie populácií,
ale nebolo uvedené, kedy sa má GA zastaviť. V praxi sa dosť často používa
subjektívne ohraničenie maximálneho počtu generácií GA. Pri tomto spÖsobe však
hrozia dve nebezpečenstvá:
Algoritmus skonverguje do extrému či už globálneho alebo lokálneho omnoho skÖr,
ako sa dosiahne maximálny počet generácií. Značné množstvo času bude strávené
skúšaním nových a nových riešení, pričom nedÖjde k žiadnemu zlepšeniu nájdeného
riešenia. (Optimalizácia niektorých problémov trvá aj pri distribuovanom
počítaní na mnohých počítačoch celé dni alebo týždne.)
Algoritmus nestihne skonvergovať a nájsť vyhovujúce riešenie, hoci by mu možno
na nájdenie tohto riešenia stačilo už len niekoíko relatívne málo generácií v
porovnaní s počtom generácií, ktoré už algoritmus trval.
Z uvedeného je zrejmé, že moment zastavenia GA nie je vhodné zvoliť vopred, ale
až počas jeho behu. Na tento účel sa používa parameter usporiadania populácie
(ordering). Tento parameter udáva, nakoíko sú si jedinci populácie navzájom
podobní. Na začiatku optimalizáce, keď sú jedinci homogénne rozmiestnení v
celom stavovom priestore, je parameter usporiadania blízky nule. Jeho hodnota
sa postupne zvyšuje a keď sú všetci jedinci sústredení okolo toho istého bodu
stavového priestoru, parameter usporiadania je blízky jednotke. Zvyčajná
hodnota na zastavenie GA je okolo 0,8. Pri dosiahnutí tejto hodnoty nemusí
nutne dÖjsť k zastaveniu optimalizácie algoritmus sa napr. mÖže "prepnúť" z GA
na horolezecký algoritmus a v lokálnom okolí najlepšieho doposiaí nájdeného
riešenia nájsť lokálny extrém.

Kódovanie informácií
V príklade v predchádzajúcej kapitole boli použité písmená na zakódovanie
genetickej informácie. Pretože sa ale GA implementujú takmer výlučne ako
počítačové programy, kódovanie informácie v praxi bude pravdepodobne iné.
Zvyčajne sa genóm kóduje ako nula-jednotkový reťazec. Genotyp však má spravidla
reprezentovať reálne čísla, preto je potrebné tento reťazec jednotiek a núl
previesť nejakým spÖsobom na reálne číslo. Ako sa to robí, si ukážeme na
príklade.
Nech sa hodnota híadaného parametra pohybuje v intervale [0; 100] a na jeho
zakódovanie sa použijú 4 bity nula-jednotkového reťazca. Na štyroch bitoch
mÖžeme reprezentovať 16 rÖznych hodnÖt, t.j. parameter budeme reprezentovať s
presnosťou približne 6,67. Hodnota binárneho reťazca 0000 bude teda znamenať
dekadickú hodnotu 0, hodnota reťazca 0001 hodnotu 6,67, atď., až nakoniec
binárna hodnota 1111 bude reprezentovať dekadickú hodnotu 100.

Hammingova bariéra
Až doposiaí bolo všetko jednoduché. Problém ale spočíva v spÖsobe transformácie
binárneho kódu na dekadický. Vezmime si ako príklad dekadické hodnoty 7 a 8
vyjadrené binárnym kódom: 0111 a 1000. Kým v dekadickom tvare sú tieto hodnoty
"tesne" pri sebe, v binárnom tvare sa líšia vo všetkých štyroch bitoch. Je
nepravdepodobné, že by sa operácii mutácie podarilo pretransformovať hodnotu 7
na hodnotu 8, pretože takáto mutácia na úrovni binárneho kódu by musela byť
veími silná. Tento jav sa nazýva Hammingova bariéra. Bolo vytvorených niekoíko
postupov na odstránenie Hammingovej bariéry. Jedným z nich je zavedenie
ďalšieho operátora transformácie, ktorý pracuje tak, že počnúc od určitej
náhodne vygenerovanej pozície v genóme invertuje jeho zvyšné bity. Jeho
použitie počas behu algoritmu je podobne ako mutácia aj kríženie podmienené
vopred zadanou pravdepodobnosťou.
Výpočtovo náročnejším spÖsobom riešenia problému prítomnosti Hammingovej
bariéry je použitie tzv. Grayovho kódu na zakódovanie dekadickej premennej do
binárneho reťazca. Tento spÖsob priamo odstraňuje Hammingovu bariéru čísla sú v
binárnom tvare zakódované tak, že dve vedía seba ležiace dekadické čísla sa v
Grayovom kóde líšia práve o jeden bit. Nevýhodou tohto kódovania je nutnosť
vykonávania transformácie Grayovho kódu do normálneho binárneho kódu pri
prevode genómu na reálne parametre.
Kódovanie binárnym reťazcom je pre GA praktické z híadiska manipulácie s
genómom pri krížení a mutácii. Ak je však do binárneho reťazca potrebné
zakódovať reálne číslo z veíkého intervalu a s dostatočnou presnosťou, neúmerne
rastie potrebná dížka reťazca (napr. na zakódovanie reálneho čísla v presnosti
údajového typu float v programovacom jazyku Java by bol potrebný reťazec dížky
viac ako tisíc bitov). Preto sa v takomto prípade používa reprezentácia
jedincov reálnymi číslami. Pre túto reprezentáciu je ale potrebné použiť
špeciálnu metódu mutácie, tzv. dynamickú mutáciu navrhnutú Z. Michalewiczom.
Operácia kríženia sa používa v prakticky nezmenenej podobe.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.