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.