Geneticke algoritmy

CO JE TO GENETICKY ALGORITMUS (GA)?

Geneticky algoritmus je model strojoveho uceni, ktery odvozuje sve chovani od procesu evoluce v prirode. To se deje vytvorenim populace (population) jedincu representovanych chromozomy (chromosomes), v podstate mnozinou textovych retezcu, ktere jsou analogiji chromozomu v nasi DNA, jez obsahuje ctyri baze = C, T, G, A. Jedinci v teto populaci pak podlehaji procesu evoluce (evolution).

Meli bychom pznamenat, ze evoluce (at uz v prirode nebo kdekoliv jinde) neni cileny nebo rizeny proces. To znamena, ze neexistuje zadne svedectvi, ktere by podporilo predpoklad, ze cilem evoluce je vytvorit lidstvo. Skutecne se zda, ze procesy v prirode smeruji k ruznym idividuim, soutezicim o zdroje v nejakem prostredi. Nektera jsou lepsi nez jina. Ta, ktera jsou lepsi maji vetsi sanci prezit a rozsirit svuj geneticky material.

V prirode vidime, ze kodovani nasi geneticke vybavy je udelano takovym zpusobem, ze pripousti nepohlavni reprodukce (reproduction) - napriklad puceni, jehoz vysledkem je typicky potomek (offspring) geneticky totozny s rodicem (parent). Pohlavni rozmnozovani dovoluje vznik radikalne odlisneho potomka, ktery je ale ma se svym rodicem stale neco spolecneho - druh.

Co se deje na moekularni urovni (toto je velmi zjednodusene!) je, ze do sebe narazi dvojice chromozomu, vymeni si retezce geneticke informace a zase se vzdali. Toto je operace rekombinace (recombination), ktere se rika crossover kvuli zpusobu jakym se geneticky material prekrizuje z jednoho chromozomu do druheho.

Crossover se odehrava v prostredi, kde vyber jedince pro mnozeni zavisi na jeho zdatnosti (fitness), to znamena jak je tento jedinec dobry v soutezeni ve svem prostredi. Nektere geneticke algoritmy pouzivaji jednoduchou funkci zdatnosti na vyber (prvdepodobnostni) jedincu pro crossover nebo reprodukci (propagace nezmeneneho genetickeho materialu). Jine implementace pouzivaji model, v nemz jisti nahodne vybrani jedinci soutezi mezi sebou a nejlepsi z nich je vybran. Toto se nazyva turnajovy system a vidime ho v prirode, kdyz jeleni bojuji o pravo parit se se skupinou lani. Dva procesy, ktere nejvice prispivaji k evoluci, jsou crossover a vyber jedincu podle zdatnosti.

Jak se ukazuje, existuji matematicke dukazy, ktere naznacuji, ze proces vyberu podle zdatnosti je v jistem smyslu temer optimalni. Mutace v tomto procesu hraje take dulezitou roli, i kdyz jeji dulezitost je stale diskutovana (nekteri ji chapou jako pomocny operator, zatimco jini ji prisuzuji dominantni roli v procesu evoluce). Geneticky algoritmus (jako simulace genetickeho procesu) vsak rozhodne neni nahodnym hledanim reseni problemu (vysoce zdatneho jedince). Geneticky algoritmus pouziva stochasticke metody, ale vysledek jednoznacne neni nahodny (je lepsi nez nahodny).

Geneticke algoritmy se pouzivaji pro mnoho ruznych aplikaci. Prikladem mohou byt mnohorozmerne optimalizacni problemy, v nichz retezec chromozomu muze reprezentovat hodnoty ruznych parametru, ktere optimalizujeme.

V praxi tedy muzeme implementovat tak, ze budeme mit pole bitu nebo znaku, reprezentujici chromozomy. Crossover a mutaci pak implementujeme pomoci jednoduchych bitovych operaci. Prestoze bylo v oblasti retezcu a jinych struktur byla vykonana spousta vyzkumu, vetsina prace s genetickym algoritmy se zameruje na retezce s pevnou delkou. Meli bychom se zamerit na pevnou delku retezcu a na potrebu zakodovat reseni, ktere hledame jako retezec znaku, protoze toto jsou klicove momenty, jez odlisuji geneticke programovani, ktere nema reprezentaci pevne delky a typicky neexistuje zadne kodovani problemu.

Kdyz je geneticky algoritmus implementovan, deje se tak vetsinou zpusobem, ktery zahrnuje nasledujici cyklus: Spocitej zdatnost vsech jedincu v populaci. Vytvor novou populaci pomoci operaci jako crossover, reprodukce podle zdatnosti a mutace jedincu, jejichz zdatnost byla prave zjistena. Zahod starou populaci a iteruj dale s pouzitim nove populace.

Kazda iterace tohoto cyklu se nazyva generace (generation). Tento implementacni model nema zadne teoreticke zduvodneni. Ve skutecnosti nevidime v prirode presne takoveto chovani, kde by byly oddelene generace, ale je to vhodny implementacni model.

Prvni generace pracuje s populaci nahodne vygenerovanych jedincu. Od te chvile geneticke operace spolecne se zdatnosti pracuji na zlepsovani populace.

PSEUDOKOD GENETICKEHO ALGORITMU
	  // nastav cas na nulu
	  t := 0;

	  // inicializuji, vetsinou nahodne, populaci jedincu
	  initpopulation P (t);

	  // spocitej zdatnost vsech jedincu v populaci
	  evaluate P (t);

	  // test podminky pro ukonceni (cas, zdatnost, atd.)
	  while not done do

	       // zvetsi citac casu
	       t := t + 1;

	       // vyber jedince, kteri budou mit potomky
	       P' := selectparents P (t);

	       // rekombinuj "geny" vybranych rodicu
	       recombine P' (t);

	       // proved nahodne mutace
	       mutate P' (t);

	       // spocitej zdatnost jedincu v nove populaci
	       evaluate P' (t);

	       // vyber ty, kteri preziji - podle zdatnosti
	       P := survive P,P' (t);
	  od
 
LITERATURA
 
Vaclav Petricek,