UVOD
Genetski algoritmi, kao jedni
od evolucijskih algoritama, heuristička su metoda optimiranja koja imitira
prirodni evolucijski proces. Predstavljaju model strojnog učenja čije ponašanje
potječe iz procesa evolucije koji se neprekidno odvija u prirodi.
Ideju evolucijskog računarstva 1960. godine u svom djelu „Evolucijske
strategije“ donosi I. Rechenberg. Ideja je prihvaćena od strane istraživača na
području računalne znanosti te se počinje intenzivno proučavati. Genetski su
algoritmi rezultat istraživanja Johna Hollanda. Kao algoritmi koji se oslanjaju
na ideje iz prirode, pogodni su za pretraživanje velikog prostora mogućnosti s
ciljem pronalaska optimalnog rješenja.
Osnovna karakteristika evolucije u prirodi je prilagođavanje živih bića uvjetima
u prirodi. Analogija evolucije kao prirodnog procesa i genetskog algoritma kao
metode optimiranja očituje se u procesu selekcije i genetskim operatorima.
Mehanizam odabira u prirodnom evolucijskom procesu čine okolina i uvjeti u
prirodi. Kod genetskih algoritam ključ selekcije je funkcija cilja ili funkcija
dobrote koja na odgovarajući način predstavlja problem koji se rješava. U
prirodi jedinka koja je najbolje prilagođena uvjetima i okolini ima najveću
vjerojatnost preživljavanja i parenja pa tako i prenošenja vlastitog genetskog
materijala. Kod genetskih algoritama jednu jedinku predstavlja jedno rješenje.
Selekcijom se odabiru dobre jedinke (rješenja) koje se prenose u sljedeću
populaciju, a manipulacijom genetskog materijala stvaraju se nove jedinke. Takav
ciklus reprodukcije, selekcije i manipulacije ponavlja se sve dok nije
zadovoljen uvjet zaustavljanja genetskog algoritma.
Po načinu djelovanja, genetski algoritmi ubrajaju se u metode slučajnog
pretraživanja prostora rješenja u potrazi za globalnim optimumom. U tu skupinu
možemo ubrojiti još i evolucijske strategije, simulirano kaljenje te genetsko
programiranje. Snaga tih metoda, a ponajviše genetskih algoritama, leži u tome
što su u stanju odrediti položaj globalnog optimuma u prostoru s više lokalnih
ekstrema, u tzv. višedimenzionalnom prostoru. Klasične determinističke metode
tražit će lokalni ekstrem za koji ne znamo je li ujedno i globalni. Stohastičke
metode, kojima pripadaju i genetski algoritmi, mogu s nekom vjerojatnošću
odrediti globalni ekstrem funkcije cilja. Temeljna razlika između ova dva
pristupa jest u tome da determinističke metode daju siguran rezultat, ali manje
značajan (lokalni ekstrem), a uz rezultate dobivene stohastičkim metodama uvijek
stoji postotak koji označava vjerojatnost da je to rješenje uistinu ono za koje
ga se smatra, no, osim lokalnih, mogu dati i globalne optimume. Dakako,
vjerojatnost ispravnosti rješenja kod stohastičkih metoda povećava se s brojem
ponavljanja procesa rješavanja.