Genetski algoritam

UVOD
U posljednjih petnaestak godina zabilježen je značajan razvoj genetskih algoritama. Genetski algoritam se rimjenjuje i daje dobre rezultate u području učenja kod neuronskih mreža, pri traženju najkraćeg puta, problemu trgovačkog putnika, strategiji igara, problemima sličnim transportnom problemu, problemu raspoređivanja procesa, problemu određivanja parametara sustava, optimiranju upita nad bazom podataka, itd. Genetski algoritam je heuristička metoda optimiranja koja imitira prirodni evolucijski proces. Evolucija je robustan proces pretraživanja prostora rješenja. Živa bića se tijekom evolucije prilagođavaju uvjetima u prirodi, tj. životnoj okolini. Analogija evolucije kao prirodnog procesa i genetskog algoritma kao metode optimiranja, očituje se u procesu selekcije i genetskim operatorima. Mehanizam odabira nad nekom vrstom živih bića u evolucijskom procesu čine okolina i uvjeti u prirodi. U genetskim algoritmima ključ selekcije je funkcija cilja, koja na odgovarajući način predstavlja problem koji se rješava. Slično kao što su okolina i uvjeti u prirodi ključ selekcije nad nekom vrstom živih bića, tako je i funkcija cilja ključ selekcije nad populacijom rješenja u genetskom algoritmu. Naime, u prirodi jedinka koja je najbolje prilagođena uvjetima i okolini u kojoj živi ima najveću vjerojatnost preživljavanja i parenja, a time i prenošenja svojega genetskog materijala na svoje potomke. Za genetski algoritam jedno rješenje je jedna jedinka. Selekcijom se odabiru dobre jedinke koje se prenose u slijedeć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 uvjet zaustavljanja evolucijskog procesa.

Genetski algoritmi predloženi su od strane Johna H. Hollanda još u ranim sedamdesetima. Tijekom nešto više od dva desetljeća, a posebno u posljednjih nekoliko godina, pokazali su se vrlo moćnim i u isto vrijeme općenitim alatom za rješ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 primjene; te doprinosu niza znanstvenika i inžinjera na njihovom prilagođavanju velikom broju problema i povećanju efikasnosti. Paralelno s povećanjem primjene povećava se i opseg istraživanja rada i svojstava genetskih algoritama i pokušavaju se svesti njihovi elementi na neke teorijske osnove. Nažalost, rezultati postignuti na teorijskom području su dvojbeni, a genetski algortimi ostaju i do danas u osnovi heurističke metode. Po načinu djelovanja ubrajaju se u metode usmjerenog slučajnog pretraživanja prostora rješ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 evolucijske strategije (evolutionary strategies), simulirano kaljenje (simulated annealing) i genetsko programiranje (genetic programming). Evolucijske strategije, razvijene u Njemačkoj u šezdesetim godinama ovoga stoljeća, imaju puno zajedničkih osobina sa genetskim algoritmima i često im se, kada su u pitanju razne varijante obaju pristupa, teško određuju granice. Obje metode održavaju populaciju rješenja nad kojom provode definirane operacije što se periodički ponavljaju. Zato se faze takvog procesa, po uzoru na prirodne evolucijske tokove, zovu i generacije. Simulirano kaljenje je proces koji je za svoj uzor upotrijebio termodinamičko kretanje materije prema stanju minimalne energije u postepenom snižavanju temperature kao parametra sustava. Metoda operira na jednom rješenju od koga se u svakoj iteraciji traži “susjedno” rješenje. Staro se uvijek zamjenjuje novim ako je postignut napredak u zadovoljavanju kriterija, a moguće je i da lošije rješenje zamijeni bolje ako se zadovolji određena mjera stohastičnosti koja se regulira sa “temperaturom” sustava. Što je veća temperatura, veća je vjerojatnost da novo, makar i lošije rješenje, zamijeni staro. Proces kreće od neke određene temperature koja dozvoljava relativno veliku vjerojatnost prihvaćanja (veća od 50%), a zatim se taj parametar eksponencijalno smanjuje sve dok kretanje ne postane gotovo determinističko.