Genetski algoritmi

ŠTA JE GENETIKA?

Genetika (grčki γεννώ – geno, znači dati rod, roditi) je nauka koja proučava gene, naslednost i varijaciju između organizama. Reč genetika je prvi put upotrebljena kada je Engleski naučnik Vilijam Bejtson poslao pismo Adamu Sedviku, 18-og aprila 1905. u kojem je opisao nauku koja za cilj ima proučavanje procesa nasleđivanja i varijacije između organizama.
Ljudi su koristili genetiku još u preistorijskom dobu za pripitomljavanje divljih životinja i gajenje biljaka. U modernim eksperimentima, genetičari svakodnevno pronalaze nove načine za izučavanje funkcije gena, kao što je analiza genetskih interakcija. U samom organizmu, genetske informacije se nalaze u hromozomima, koji su predstavljeni hemijskim strukturama kao što je DNK molekul.
Geni su šifre koje nose informacije neophodne za sintezu sekvenci amino kiselina koje se ispoljavaju u proteinima, koji na kraju igraju važnu ulogu u građi fenotipa organizma.

GENETSKI ALGORITAM

Genetski ili genetički algoritam (GA) je heuristička metoda optimizacije koja imitira prirodni evolucioni proces. Evolucija je proces pretraživanja prostora rešenja. Živa bića se tokom evolucije prilagođavaju uslovima u prirodi, tj. životnoj okolini. Analogija evolucije kao prirodnog procesa i genetskog algoritma kao metode optimizacije, ogleda se u procesu selekcije i genetskim operatorima. Mehanizam odabira nad nekom vrstom živih bića u evolucijskom procesu čine okolina i uslovi u prirodi. U genetskim algoritmima ključ selekcije je funkcija cilja, koja na odgovarajući način predstavlja problem koji se rešava. Slično kao što su okolina i uslovi u prirodi ključ selekcije nad nekom vrstom živih bića, tako je i funkcija cilja ključ selekcije nad populacijom rešenja u genetskom algoritmu. Naime, u prirodi jedinka koja je najbolje prilagođena uslovima i okolini u kojoj živi ima najveću verovatnoću preživljavanja i parenja, a time i prenošenja svojeg genetskog materijala na svoje potomke. Za genetski algoritam jedno rešenje je jedna jedinka. Selekcijom se biraju dobre jedinke koje se prenose u sledeću populaciju, a manipulacijom genetskog materijala stvaraju se nove jedinke. Takav ciklus selekcije, reprodukcije i manipulacije genetskim materijalom jedinki ponavlja se sve dok nije zadovoljen uslov zaustavljanja evolucionog procesa. Konačan rezultat je populacija jedinki (potencijalnih rešenja). Najbolja jedinka u poslednjoj iteraciji predstavlja rešenje optimizacije.
Genetski algoritmi predloženi su od strane Johna H. Hollanda još u ranim sedamdesetim. Tokom nešto više od 20 godina, a posebno u poslednjih nekoliko godina, pokazali su se vrlo moćnim i u isto vreme opštim alatom za rešavanje čitavog niza problema iz inžinjerske prakse. To se može objasniti njihovom jednostavnošću; kako same ideje na kojoj su osnovani, tako i njihove primene; te doprinosu niza naučnika i inžinjera na njihovom prilagođavanju velikom broju problema i povećanju efikasnosti. Paralelno s povećanjem primene povećava se i opseg istraživanja rada i svojstava genetskih algoritama. Nažalost, rezultati postignuti na teorijskom području su upitni, a genetski algortimi ostaju i do danas u osnovi heurističke metode.

Po načinu delovanja ubrajaju se u metode usmerenog slučajnog pretraživanja prostora rešenja (guided random search techniques) u potrazi za globalnim optimumom. U istu grupu možemo ubrojiti još neke metode koje se temelje na sličnim principima: to su evolucione strategije (evolutionary strategies), simulirano zagrevanje (simulated annealing) i genetsko programiranje (genetic programming).
Snaga tih metoda, a pogotovo genetskih algoritama, leži u činjenici da su oni sposobni odrediti položaj globalnog optimuma u prostoru s više lokalnh ekstrema, u tzv. višemodalnom prostoru. Klasične determinističke metode će se uvek kretati prema lokalnom minimumu ili maksimumu, pri čemu on može biti i globalni, ali to se ne može odrediti iz rezultata. Stohastičke metode, tako i genetski algoritmi, nisu zavisne od neke eventualne početne tačke i mogu svojim postupkom pretraživanja s nekom verovatnoćom locirati globalni optimum određene ciljne funkcije.