OPĆENITO O GENETSKIM ALGORITMIMA
Kao što sam već i u uvodu
napomenuo, genetski su algoritmi temeljeni na evoluciji u prirodi. Kako u
evoluciji preživljavaju najjači, tako će i kod genetskih algoritama preživjeti
skup najjačih, tj. najboljih rješenja. Pri reprodukciji dolazi do izmjene gena.
Isto tako u prijelazu s generacije na generaciju mijenjaju se i rješenja kod
genetskih algoritama. Taj proces zovemo križanjem. Uz križanje postoji još i
znatno rjeđi proces, mutacija. Mutacija je proces slučajne promjene genetskog
materijala do kojeg u prirodi dolazi pod utjecajem vanjskih uzroka. Križanje i
mutaciju u terminologiji GA-a nazivamo genetskim operatorima, a proces
izdvajanja najboljih jedinki unutar svake generacije odabirom ili selekcijom.
1. Populacija
Populacija je skup jedinki iste vrste smještenih na nekom području. Kako dio
populacije stari i umire, tako se razmnožavanjem stvaraju novi potomci i
veličina populacije u svakoj generaciji ostaje približno konstantna. U genetskom
algoritmu populacija je skup potencijalnih rješenja zadanog problema. Početna
populacija može biti odabrana slučajnim odabirom ili nekim drugim
optimizacijskim postupkom. Odumiranje slabijih jedinki, tj. lošijih
potencijalnih rješenja koje se nisu uspjele prilagoditi novim životnim uvjetima
i opstanak jedinki koje su to uspjele u genetskim se algoritmima određuje
uporabom funkcije cilja ili dobrote. Razmnožavanje jedinki koje su, zahvaljujući
svojim dobrim svojstvima, uspjele preživjeti provodi se operacijom križanja.
Svakim novim ponavljanjem jedinke u populaciji poprimaju sve bolja svojstva.
Algoritam obično završava dosezanjem zadanog broja ponavljanja, tj. broja
generacija ili istekom prethodno određenog vremena za rad algoritma. Kada je
uvjet završetka ispunjen, iz dobivene populacije odabire se najbolja jedinka i
ona predstavlja rješenje optimizacijskog problema.
2. Funkcija cilja ili dobrote
Funkcija cilja predstavlja prirodnu okolinu koja vrši selekciju nad jedinkama.
Što je jedinka bolje prilagođena okolini u kojoj živi, tj. što je rješenje
bolje, veće je vjerojatnost njenog preživljavanja, tj. prenošenja u novu
generaciju. Odabir odgovarajuće funkcije cilja ključan je problem kod
implementacije genetskog algoritma. Također, s obzirom na to da se radi o
funkciji koja se u algoritmu najviše koristi, funkcija cilja trebala bi biti što
je moguće jednostavnija i brža.
3. Odabir ili selekcija
Svrha selekcije je čuvanje i prenošenje dobrih svojstava na sljedeću generaciju
te izbacivanje loših svojstva. Selekcijom se biraju dobre jedinke koje se onda
prenose na novu populaciju. Najjednostavniji postupak selekcije bio bi takav da
se jedinke sortiraju po dobroti te da se izbaci ranije definiran broj najlošijih
jedinki. Na taj bi način proces optimiranja vrlo brzo završio. Zašto ipak onda
ne koristimo taj postupak? Zato što i one najlošije jedinke imaju neka dobra
svojstva koja treba iskoristiti. Kad se iz populacije izbace najlošije jedinke,
ostaju samo najbolje, no te najbolje ne predstavljaju ujedno i skup svih
najboljih svojstava. Čak i najlošije jedinke neka svojstva imaju bolja od
najboljih. Tu činjenicu ne smijemo zanemariti. No, nije dobro niti ako dozvolimo
da je vjerojatnost preživaljvanja svih jedinki podjednaka. Na taj bismo način
omogućili gubitak velikog broja dobrih jedinki. Prema tome, problem je jedino
smisleno riješiti dodjeljivanjem niske vjerojatnosti preživljavanja (ali veće od
0) lošim jedinkama, a visoke (no manje od 1) dobrim jedinkama. Određenom malom
broju jedinki s najboljim svojstvima, elitnim jedinkama, možemo dodijeliti
vjerojatnost preživaljavanja 1, tj. osigurati da će one sigurno nepromijenjene
preći u novu generaciju.
Genetske algoritme s obzirom na vrstu selekcije možemo podijeliti na
generacijske i eliminacijske. Generacijski genetski algoritmi u jednom
ponavljanju raspolažu s dvije populacije. Karakteristične vrste selekcija koje
koriste generacijski genetski algoritmi su jednostavna selekcija i turnirska
selekcija. Karakteristika eliminacijskog genetskog algoritma je eliminacijska
selekcija.
4. Elitizam
Kako se trenutno najbolja rješenja ne bi izgubila uptrebom genetskih operatora
ili eliminacijom, tijekom selekcije javlja se potreba za zaštitom najbolje ili
nekoliko najboljih jedinki od izmjena ili eliminacije. Zaštita najboljih jedinki
naziva se elitizam i osigurava da se svaka nova generacija kreće prema globalnom
optimumu. Zaštićene jedinke zovemo elitnim jedinkama. Ukoliko je populacija
velika, prilikom pretrage za najboljim jedinkama algoritam se usporava.