Marin Golub
Evolucija u prirodi
Jednostavni genetski algoritam
Genetski operatori
Prikaz brojem s pomi
č
nom to
č
kom
Primjeri
Zadnja promjena obavljena 27. rujna 2004. godine (verzija 2.3)
Verzija 1.0 izašla 6.listopada 1997. godine
Zahvaljujem se Domagoju Jakobovi
ć
u na pomo
ć
i i sugestijama tijekom pripreme ovog teksta.
Domagoj je ujedno i autor poglavlja 3.8 Prilagodljivi genetski algoritam (AGA) i jednog dijela uvoda.
Zahvaljujem se studentu Zoranu Rušinovi
ć
u što mi je ukazao na niz grešaka koje su se potkrale u tekstu.
Verzije teksta 2.3 i 2.2 se razlikuju upravu u ispravljenim spomenutim greškama. Zadnja dva odlomka u
poglavlju 3.2.2 su rezultat Zoranovih primjedbi.
4
1. UVOD
U posljednjih petnaestak godina zabilježen je zna
č
ajan razvoj genetskih algoritama. Genetski algoritam se
primjenjuje 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.
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
uvijek 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 ovisne o nekoj eventualnoj po
č
etnoj to
č
ki i
mogu svojim postupkom pretraživanja s nekom vjerojatnoš
ć
u locirati globalni optimum odre
đ
ene ciljne funkcije.
Osnovna razlika u primjeni izme
đ
u klasi
č
nih i stohasti
č
kih metoda je ta što za rezultat neke, recimo, gradijentne
metode možemo sa sigurnoš
ć
u re
ć
i da je postignut lokalni ekstrem unutar željene preciznosti. Za rezultat rada
genetskog algoritma, me
đ
utim, nismo u mogu
ć
nosti sa stopostotnom vjerojatnoš
ć
u re
ć
i da li predstavlja globalni ili
samo lokalni optimum, te da li je isti odre
đ
en sa željenom preciznoš
ć
u. Koliko god se performanse stohasti
č
kih
metoda poboljšavale, one nikada ne
ć
e mo
ć
i dati niti jedan rezultat sa apsolutnom sigurnoš
ć
u. Sigurnost dobivenih
rezultata zna
č
ajno se pove
ć
ava postupkom ponavljanja procesa rješavanja, što kod klasi
č
nih metoda nema smisla.
Od kada su genetski algoritmi nastali, velika se pažnja poklanja istraživanjima vezanim za pove
ć
anje djelotvornosti
izvedbe.
5
2. PRIRODNI EVOLUCIJSKI PROCESI
2.1 Borba za opstanak
Charles Darwin je primijetio da živa bi
ć
a u pravilu stvaraju više potomaka od cijele njihove populacije. Prema
tome, broj jedinki koje
č
ine populaciju trebao bi eksponencijalno rasti iz generacije u generaciju. Unato
č
toj
č
injenici, broj jedinki jedne vrste teži ka konstantnom broju. Primijetivši razli
č
itosti me
đ
u jedinkama iste vrste,
zaklju
č
io je da priroda selekcijom jedinki regulira veli
č
inu populacije. Dobra svojstva jedinke, kao što su otpornost
na razne bolesti, sposobnost tr
č
anja, itd., pomažu da jedinka preživi u neprestanoj borbi za opstanak.
Evolucija je neprekidan proces prilago
đ
avanja živih bi
ć
a na svoju okolinu, tj. na uvjete u kojima žive. U prirodi
vlada nemilosrdna borba za opstanak u kojoj pobje
đ
uju najbolji, a loši umiru. Da bi neka vrsta tijekom evolucije
opstala, mora se prilago
đ
avati uvjetima i okolini u kojoj živi, jer se i uvjeti i okolina mijenjaju. Svaka slijede
ć
a
generacija neke vrste mora pamtiti dobra svojstva prethodne generacije, pronalaziti i mijenjati ta svojstva tako da
ostanu dobra u neprekidno novim uvjetima.
Svaka se jedinka može okarakterizirati nizom svojstava, kao što su npr.: sposobnost tr
č
anja, boja kože, boja o
č
iju,
oštrina vida, prilagodljivost na niske temperature, broj zubi, oblik zubi, i sl. Slabe jedinke, odnosno jedinke koje
imaju loša svojstva, imaju malu vjerojatnost preživljavanja u borbi za opstanak i one
ć
e najvjerojatnije odumrijeti, a
zajedno s njima i loša svojstva. Dakle, dobra svojstva imaju ve
ć
u vjerojatnost naslje
đ
ivanja, odnosno prenošenja na
slijede
ć
u generaciju.
Danas se pretpostavlja da su sva svojstva jedinke zapisana u kromosomima. Kromosomi su lan
č
aste tvorevine koje
se nalaze u jezgri svake stanice, što zna
č
i da svaka stanica biljnog ili životinjskog podrijetla posjeduje sve
informacije o svim svojstvima jedinke. Skup informacija koje karakteriziraju jedno svojstvo zapisano je u jedan
djeli
ć
kromosoma koji se naziva gen. Kromosomi dolaze uvijek u parovima: jedan kromosom je od oca, a drugi od
majke. Dakle, za svako svojstvo postoje dva gena ili dvije informacije. Takav par gena gdje jedan i drugi gen nosi
informaciju za jedno svojstvo naziva se alel. U genetskom paru geni mogu biti ravnopravni ili neravnopravni, tako
da je jedan dominantan, a drugi recesivan. U neravnopravnom paru dominantan gen odre
đ
uje rezultantno svojstvo,
dok se uz ravnopravni par gena dobiva svojstvo koje je negdje izme
đ
u svojstava oca i majke.
Sva svojstva jedinke obi
č
no nisu zapisana u samo jednom paru kromosoma, ve
ć
u nekoliko desetaka parova
kromosoma. Npr.,
č
ovjek ima 46 kromosoma odnosno 23 para kromosoma.
2.2 Molekula DNK kao nositelj informacije
Kemijsku strukturu koja je prisutna u kromosomima otkrili su Watson i Crick 1953. godine. Molekula
deoksiribonukleinske kiseline (DNK) je u obliku dvije spirale gra
đ
ene od fosforne kiseline i še
ć
era, a mostovi
izme
đ
u spiralnih niti gra
đ
eni su od duši
č
nih baza i to adenina (A), gvanina (G), timina (T) i citozina (C). Duši
č
ne
baze su me
đ
usobno povezane vodikovim vezama i to adenin s timinom i gvanin sa citozinom kako je prikazano na
slici 2.1.
Slika 2.1: Parovi baza u DNK
Pokazalo se da su upravo te duši
č
ne baze jedinice informacije. Sli
č
no kao što je u ra
č
unalu najmanja jedinica
informacije jedan bit (0 ili 1), tako je u prirodi najmanja jedinica informacija jedna duši
č
na baza (A, G, C ili T).
Jedan kromosom se sastoji od dvije komplementarne niti DNK i to ako je, npr. djeli
ć
jedne spiralne niti AAGTCA,
tada je ekvivalentan dio druge spirale TTCAGT. Ovakva struktura dviju spiralnih niti DNK omogu
ć
ava prenošenje
informacije dijeljenjem kromosoma pri diobi stanice. Naime, kada se stanica treba podijeliti, kromosomske niti se
razmotaju. Budu
ć
i da u jezgri stanice ima mnoštvo slobodnih baza, te baze se vežu na svoje parove na nitima DNK.
Tako je informacija sa
č
uvana, kopirana i prenešena na dva novonastala kromosoma.
Prirodni evolucijski procesi
7
Slika 2.3: Izmjena faktora (crossing-over)
Neka svojstva koja definira ili stekne jedinka u svojem životu (kao što je ožiljak) ne prenose se na potomke.
Mutacija je slu
č
ajna promjena gena. Neki geni mutiraju lakše, a neki teže, pa se dijele na stabilne i nestabilne gene.
Vjerojatnost mutacije jednog gena je konstantna. No, zanimljivo je da je vjerojatnost mutacije razli
č
ita za razli
č
ite
gene i kre
ć
e se od 10
-4
do 10
-5
. Zatim, vjerojatnost da gen A postane gen B nije ista kao i vjerojatnost da se gen B
mutacijom promijeni u gen A.
2.5 Genetski algoritam: slika evolucije vrsta
Pojedine vrste živih bi
ć
a se uz pomo
ć
evolucije prilago
đ
avaju uvijek novim prilikama i uvjetima u prirodi. Dakle, u
prirodi evolucija vrste nije potraga za rješenjem (jedinkom koja je najbolje prilago
đ
ena uvjetima u prirodi), ve
ć
prilago
đ
avanje postoje
ć
e populacije na nove uvjete.
Genetski algoritam (GA) kao metoda optimiranja nastao je oponašanjem evolucije. Simuliranje prirodnog
evolucijskog procesa na ra
č
unalu svodi se na grube aproksimacije rješenja. Naime, veli
č
ina genotipa, npr. žabe je
približno 3.2*10
9
nukleotida, što odgovara koli
č
ini podataka na ra
č
unalu od 0.8GB
1
za jednu jedinku. Zna
č
i, vjerna
simulacija evolucije jedne vrste od milijun jedinki zahtjeva memorijski prostor od približno milijun gigabajta, što je
unato
č
eksponencijalnom rastu mogu
ć
nosti ra
č
unala, danas, a i još
ć
e neko vrijeme biti, nedostižno i neizvodivo.
1
S pomo
ć
u jednog nukleotida, odnosno jedne duši
č
ne baze može se spremiti isto toliko informacija koliko i s pomo
ć
u dva bita u
binarnom prikazu, (4 razli
č
ite informacije). Dakle, 3.2*10
9
nukleotida imaju isti kapacitet kao i 6.4*10
9
bitova, što je
ekvivalentno kapacitetu od 6.4*10
9
/8=0.8*10
9
bajtova. To je približno 0.8GB.
