Sažetak

Pri izvršavanju prostog genetskog algoritma, može doći do određenih anomalija: preuranjene konvergencije, spore konvergencije, gubljenja genetskog materijala, itd. Te anomalije direktno utiču na kvalitet dobijenog rešenja i brzinu konvergencije genetskog algoritma, a najčešće su posledica neodgovarajuće funkcije prilagođenosti ili neodgovarajućih operatora selekcije i ukrštanja.

Najčešći problem u primeni prostog GA je tzv. preuranjena konvergencija. Data pojava se dešava ukoliko jedna relativno dobra jedinka ili shema, ali ne i optimalna, postepeno preovlada u populaciji, i proces konvergira u lokalnom ekstremu. Pri tome selekcija i ukrštanje nemaju nikakvog, a mutacija vrlo malog efekta (populacija je sa istim jedinkama). Preuranjena konvergencija je najčešće posledica proste (rulet) selekcije.

Spora konvergencija se dešava po pravilu u kasnijoj fazi izvršavanja. Ako je srednja prilagođenost (fitness) svih jedinki u populaciji velika, a razlike između njih male, postoji nedovoljni gradijent u funkciji prilagođenosti koji bi pomogao GA da dostigne optimalnu vrednost.

Složeniji operatori selekcije su: selekcija bazirana na rangu (rank-based), turnirska selekcija (tournament) i selekcija primenom ostataka (stohastic reminder). Prve dve relativno uspešno rešavaju problem preuranjene konvergencije.

Neki od operatora ukrštanja su: dvopoziciono (two point), višepoziciono (multi point) i uniformno. Jednopoziciono ukrštanje je najpogodnije u problemima sa velikom međuzavisnošću bitova u genetskom kodu jedinke, jer je najmanje razbijanje celine jedinke. Ukoliko je međuzavisnost izuzetno mala preporučuje se uniformno ukrštanje, a u slučajevima između ovih ekstrema dvopoziciono i višepoziciono ukrštanje.

Osim binarnih postoje i GA nad alfabetima veće kardinalnosti od 2, i mišljenja o njihovoj teorijskoj i praktičnoj efikasnosti su podeljena. Javljaju se najčešće u numeričkim problemima i simboli (geni) su predstavljeni celim ili realnim brojevima.

Kritični momenti u radu GA su kodiranje i funkcija prilagođenosti, a ostali parametri manje utiču na performanse genetskih algoritama. Grefenstette zaključuje da je mehanizam GA toliko robustan i fleksibilan, da daje dobre rezultate u širokom opsegu vrednosti parametara (nivo ukrštanja, nivo mutacije, veličina populacije, itd).

U praksi je najbolje izabrati bijektivno kodiranje problema u skup genetskih kodova. Ukoliko takvo kodiranje nije moguće ili daje loše rezultate, dopušteni su samo slučajevi gde neke jedinke imaju više genetskih kodova i gde neki genetski kodovi ne odgovaraju nijednoj jedinki. Prvi slučaj iako sa teorijskog stanovišta nije preporučljiv, u praksi nema nikakvih problema.

U drugom slučaju moguće je:

• Nekorektne genetske kodove ignorisati i dodeliti im vrednost nula za funkciju prilagođenosti;
• U GA uključujemo i nekorektne jedinke, pri čemu ih kažnjavamo određenom kaznenom vrednosnom funkcijom;
• Nekorektne jedinke popravkom transformišemo u korektne. Pri tome su podeljena mišljenja o tome da li treba vratiti "popravljenu" jedinku na mesto "stare" ili ne;
• Korišćenje operatora ukrštanja i mutacije zavisnih od prirode problema.

Iako se u osnovnom obliku GA u svakoj generaciji zameni celokupna populacija (generational GA), u većini novijih radova zamenjuje se samo određeni deo populacije, dok ostatak uzimamo iz tekuće generacije (stedy-state GA ili elitist strategies).

Parametri GA ne moraju biti konstantni tokom rada GA. Pri tome je moguća fiksna unapred zadata promena parametara ili adaptivna promena parametara.

Imajući u vidu gorepomenute činjenice o genetskim algoritmima, implementirano je jezgro programskog sistema GA, pri čemu je laka dopuna funkcijama zavisnim od prirode problema.

Povratak | Poèetna strana