Algoritmi koji oponašaju procese u prirodi

Slika 3.1. - Građa i struktura DNA

Slika 4.1. - Pseudokod genetskog algoritma

Generacijski genetski algoritam radi s dvije populacije u jednoj iteraciji i opisan je slijedećim pseudokodom:

Generacijski genetski algoritam { t = 0; Generiraj početnu populaciju potencijalnih rjesenja p(0); Sve dok nije zadovoljen uvjet zavrsetka evolucijskog procesa { t = t+1; Selektiraj jedinke iz p(t-1) i prebaci ih u p’(t); Krizaj jedinke iz p’(t) i djecu spremi u p(t); Mutiraj jedinke iz p(t); } Ispisi rjesenje; }

Eliminacijski genetski algoritam za razliku od generacijskog radi samo s jednom populacijom te je opisan slijedećim pseudokodom:

Eliminacijski genetski algoritam { Generiraj početnu populaciju potencijalnih rjesenja p; Sve dok nije zadovoljen uvjet zavrsetka evolucijskog procesa { Selektiraj m losih jedinki iz populacije p; Izbrisi odabrane jedinke iz populacije p; Krizaj preostale jedinke iz p i djecu spremi u p; Mutiraj djecu u p; } Ispisi rjesenje; }

4.2.1. Jednostavna selekcija

Vjerojatnost izbora jedinke pri proporcionalnoj selekciji proporcionalna je njenoj dobroti. U generacijskom genetskom algoritmu vjerojatnost izbora jedinke računa se tako da se dobrota jedinke podijeli sa ukupnom dobrotom generacije (formula 4.2.). Tako je zapravo vjerojatnost izbora jednaka udjelu njene dobrote u ukupnoj dobroti populacije. Kako je izbor jedinki potpuno slučajan, elitizam se mora uvesti naknadno.

Postupak jednostavne selekcije opisan je pseudokodom na slici 4.5.

Jednostavna generacijska selekcija { Izračunaj sve vrijednosti dobrota(vi); Izračunaj ukupnu dobrotu D populacije P(t-1); Izračunaj kumulativnu dobrotu qi za svaki kromosom;  //formula(4.1) Za i = 1 do VEL_POP radi { Generiraj slučajni broj r između 0 i D; Selektiraj jedinku vi za koju vrijedi qi-1<r<qi; Prenesi odabranu jedinku u populaciju P'(t); } }

Eliminacijski genetski algoritam također može koristiti jednostavnu selekciju. U tom slučaju, umjesto funkcije dobrote uvodi se funkcija kazne. (formula 4.3.)

Umjesto kumulativne dobrote računa se kumulativna kazna, a jedinka se ne kopira u novu populaciju, već se briše iz trenutne. Ukupnu i kumulativnu kaznu treba računati u svakom koraku, jer jednom izbrisana jedinka više ne pridonosi ukupnoj dobroti. Zbog načina izračuna kazne, elitizam je inherentno ugrađen u selekciju. Algoritam je opisan na slici 4.6.

Eliminacijska selekcija { Izracunaj sve vrijednosti kazna(vi); Za i = 1 do m radi { Izracunaj ukupnu kaznu K populacije P; Izracunaj kumulativnu kaznu qi za svaku jedinku; Generiraj slučajni broj r između 0 i K; Selektiraj jedinku vi za koju vrijedi qi-1 < r < qi; Izbrisi odabranu jedinku iz populacije P; }

Nedostatci jednostavne selekcije su neučinkovitost kod malih razlika u dobroti jedinki, često pojavljivanje duplikata i nemogućnost korištenja negativnih vrijednosti dobrote. Te probleme moguće je ukloniti postupcima translacije ili linearne normalizacije.

Translacija ili pomak je jedan od načina rješavanja nedostataka jednostavne selekcije, kao što su  negativne vrijednosti dobrote, velikih vrijednosti i malih razlika dobrote. Rješenje je to da se od vrijednosti dobrote svake jedinke oduzme najmanja vrijednost dobrote iz trenutne populacije. Ukoliko se taj postupak obavi, jedna od jedinki će imati dobrotu jednaku nula i vjerojatnost izbora jednaku nula. Kako želimo da svaka jedinka ima bar malu mogućnost reprodukcije, to se može ispraviti oduzimanjem vrijednosti nešto manje od najmanje vrijednosti dobrote za pozitivne vrijednosti funkcije f(x). Kod eliminacijske selekcije to nije potrebno, jer nam odgovara da najbolja jedinka (najmanja vrijednost funkcije kazne) ima vjerojatnost eliminacije jednaku nula.

Linearnom normalizacijom jednostavna selekcija postaje linearno sortirajuća selekcija koja je opisana u slijedećem odjeljku.

4.2.2. Linearno sortirajuća selekcija

U linearno sortirajućoj selekciji vjerojatnost izbora jedinke proporcionalna je poziciji jedinke u poreku jedinki sortiranih prema dobroti.  Vjerojatnost selekcije jedinke dana je izrazom 4.5.

U generacijskom algoritmu, najbolja jedinka ima indeks N, a najgora 1. Za eliminacijsku selekciju koristi se isti izraz, samo najbolja jedinka ima indeks 1, a najgora N. Ova selekcija nema u sebi ugrađen elitizam, te ga je potrebno naknadno implementirati. Ipak, to je vrlo jednostavno napraviti.

	dobrota(v(x))
f(x)	730	720	710	705	700	700	698	695	690	680
Translacija f(x) – min(f(x))	50	40	30	25	20	20	18	15	10	0
Translacija f(x) – 0,99*min(f(x))	56	46	36	31	26	26	24	21	16	6
Lin. norm. s korakom 5 i MIN_D =10	50	145	40	35	30	30	25	20	15	10
Lin. norm. s korakom 1 i MIN_D =1	9	8	7	6	5	5	4	3	2	1

4.2.3. K-turnirska selekcija

K-turnirska selekcija je rangirajuća vrsta selekcije koja u svakom koraku za generiranje nove populacije odabire k jedinki iz stare populacije, rangira ih, te najbolju među njima stavlja u bazen za reprodukciju, nad kojim će se onda izvršiti genetski operatori reprodukcije. Eliminacijska turnirska selekcija odabire k jedinki te briše najslabiju od njih iz trenutne populacije, a može ju nadomjestiti djetetom preostale dvije jedinke.

4.3. Genetski operatori reprodukcije

4.3.1. Križanje

Križanje je genetski operator koji imitira prirodni proces križanja (crossover). U njemu sudjeluju dvije jedinke iz populacije, te se križanjem njihovog genetskog materijala dobiva jedna ili dvije nove jedinke. Novonastala jedinka nastaje iz dvije dobre jedinke, koje su prošle selekciju, te bi njihova svojstva trebala biti dobra. Prema tome, nova jedinka bi također trebala biti dobra. Križanje se može izvesti na nekoliko načina. Postupkom križanja se brzo postiže konvergencija optimumu, ali postoji opasnost da on bude lokalni. Najjednostavniji način je križanje s jednom točkom prekida kada se kromosom lomi u jednoj točki te spaja s dijelom drugog slomljenog na istom mjestu.

Slika 4.11. – Primjer križanja jedinki sa jednom točkom prekida.

Križanje sa više točaka prekida obavlja se na sličan način. Jedina razlika je u tome što se kromosomi lome u više točaka, a zatim se dijelovi roditelja A i B naizmjence spajaju. Krajnji slučaj ovog načina križanja je uniformno križanje, tj. križanje s b-1 prekidnih točaka na kromosomu sa b bitova. Kod uniformnog križanja, dijelovi kromosoma se ne spajaju naizmjence već se za svaki gen računa da li je naslijeđen od prve ili druge jedinke koja sudjeluje u križanju, gdje je vjerojatnost nasljeđivanja gena od svakog roditelja jednaka (p=0.5). P-uniformno križanje je uniformno križanje u kojem je vjerojatnost nasljeđivanja pojedinog gena od jednog roditelja drugačija od vjerojatnosti nasljeđivanja od drugog. Vrijednost parametra pi određuje koliko je vjerojatno da će nova jedinka i-ti gen naslijediti od prvrog, odnosno drugog roditelja. Ukoliko vrijedi p = 0, gen se uvijek nasljeđuje od prvog roditelja, a ako je p = 1, onda od drugog. Vrijednost parametra pi = 0.3 govori da će u tri od deset križanja i-ti gen biti od prvog roditelja, dok će u ostalih sedam biti od drugog.

Slika 4.12. – Primjer križanja jedinki sa više točaka prekida.

Slika 4.13. – Primjer uniformnog križanja

4.3.2. Mutacija

Mutacija je unarni genetski operator. Ona djeluje na jedan kromosom, te ga izmjenjuje. Mutacija je operator koji može unijeti novo svojstvo u vrstu ili obnoviti izgubljeno svojstvo. Ukoliko je vjerojatnost mutacije jednaka jedan, tada je algoritam zapravo algoritam traženja slučajnom pretragom prostora rješenja. Što je manja vjerojatnost mutacije, to je manja vjerojatnost nalaska globalnog optimuma. Ukoliko je vjerojatnost mutacije približno nula algoritam će vjerojatno završiti u lokalnom optimumu.

Slika 4.14. – Primjer jednostavne mutacije nad slučajno odabranim genom

Mutacija se može vršiti nad jednim slučajno odabranim genom, nad genima odabranim pomoću slučajno generirane maske, ili nad svim genima – potpuna mutacija. Jednostavna mutacija je najjednostavniji oblik mutacije. Odabranom genu izmjenjuje se vrijednost. Miješajuća mutacija izmiješa pozicije dva ili više odabranih gena. Potpuna miješajuća mutacija slučajno generira vrijednosti odabranih gena, dok invertirajuća miješajuća mutacija invertira vrijednost gena.

Slika 4.15. – Primjer miješajuće mutacije sa slučajno generiranom maskom

Slika 4.16. – Primjer potpune miješajuće mutacije sa slučajno generiranom maskom

4.4. Parametri algoritma

parametar	"manje" populacije	"veće" populacije
VEL_POP	30	100
pm	0,01	0,001
pc	0,9	0,6

parametar	"manje" populacije	"veće" populacije
VEL_POP	30	100
pm	0,01	0,001
M	VEL_POP/2	VEL_POP/4

Za različite vrijednosti parametara, algoritam daje različite rezultate. To se očituje u brzini (može biti brži ili sporiji) te u točnosti rješenja (može dati bolje ili lošije rješenje). Postavljanje djelotvornih parametara zahtjeva izvođenje velikog broja eksperimenata. Parametri mogu biti statički ili dinamički. Statički parametri se definiraju na početku i ne mijenjaju. Dinamički parametri se mogu mijenjati tijekom izvođenja algoritma. Taj proces izmjene parametara može kontrolirati drugi genetski algoritam, može biti funkcija vremena ili broja iteracija odnosno raspršenosti rješenja.

 

4.5. Simulator genetskog algoritma

U ovom poglavlju nalazi se opis genetskog algoritma - GA Appleta, koji simulira prirodni evolucijski proces. Cilj programa je naći što bolji obrazac ponašanja jedinke - umjetnu inteligenciju.

Svijet jedinki izjelica (eater) podijeljen je u malene kvadratiće. Svaki kvadrat može biti popunjen jedinkom, biljkom ili biti prazan. U jednom se kvadratu ne mogu nalaziti dvije stvari u isto vrijeme. Jedinka, koji ima oblik slova T, "vidi" jedan kvadrat ispred sebe. Ona može vidjeti četiri različite stvari: drugu jedinku, biljku, prazno polje ili zid. Jedinka ima memoriju koja sadrži broj od nula do petnaest. Taj broj predstavlja trenutno stanje jedinke. U svakom intervalu vremena, jedinka može napraviti jednu od ovih akcija:

Slika 5.1. – GA Applet

U svakom intervalu jedinka također može promijeniti svoje stanje, mijenjajući broj u svojoj memoriji. Ukoliko se pokuša pomaknuti u kvadrat koji je okupiran zidom ili drugom jedinkom, to joj neće biti dozvoljeno. Ipak, ona može u tom intervalu promijeniti stanje. Ukoliko se pomakne u kvadrat koji sadrži biljku, "pojede" ju i osvoji bod. Biljka tada može ili ne mora izrasti negdje drugdje, što ovisi o postavkama podešenim izborniku programa. Na kraju godine (iteracije), dobrota jedinke se određuje prema broju pojedenih biljki plus jedan. GA Applet koristi jednostavni genetski algoritam. Karakteristike su jednostavna selekcija, križanje s jednom točkom prekida i jednostavna mutacija.

Na kraju godine, program ispisuje broj iteracije, srednju vrijednost dobrote populacije i maksimalnu dobrotu. Ukoliko je došlo do nove najveće srednje vrijednosti dobrote, pokraj nje se ispisuje znak '*'. Nakon stotinu godina ili iteracija, rezultati se ispisuju svakih deset godina - desetogodišnji prosjek, maksimalnu dobrotu, te stogodišnji prosjek. Nakon tisuću godina, program ispisuje prosjeke svakih sto godina.

Slika 5.2. – Primjer izlaza GA Appleta

Program može raditi u pet brzina, od kojih najbrža ne prikazuje proces vizualno, što omogućuje brzo napredovanje u evoluciji umjetne inteligencije jedinki.

U programu se mogu podešavati parametri genetskog algoritma:

Osim parametara genetskog algoritma, mogu se promijeniti i postavke vezane uz rast biljaka te pozicija na kojoj se jedinke stvaraju (rađaju). Nakon što jedinka pojede biljku, ona može potpuno nestati ili ponovo izrasti – u blizini ili na slučajnoj poziciji. Biljke mogu rasti u nakupinama, nizovima, uz donji rub prozora, uz sve rubove prozora ili na slučajno generiranoj poziciji. Također se može mijenjati i broj biljaka koje izrastu na početku godine (iteracije programa). On se može izabrati iz skupa D.
D = {50, 100, 150, 250, 500}

Eateri se na početku godine mogu stvoriti u gornjem lijevom kutu, sredini prozora, na slučajno generiranoj poziciji ili na poziciji roditelja.

Pokretanjem programa sa različitim postavkama, može se uočiti kako brzina konvergencije prema boljem rješenju ovisi o parametrima genetskog algoritma, dok rješenje prema kojem će algoritam konvergirati ovisi o ostalim postavkama. Program pokrenut s malim i program pokrenut s velikim brojem jedinki u populaciji (VEL_POP) konvergirat će prema sličnom rješenju nakon dovoljnog broja iteracija. Programi pokrenuti s različitim postavkama koje određuju rast biljaka ili pojavljivanje jedinke, neće konvergirati prema istom rješenju.

U dodatku se nalaze grafovi koji uspoređuju srednje vrijednosti dobrote populacije za različite vrijednosti vjerojatnosti veličine populacije, mutacije i križanja. Ostale postavke: 500 biljki raste u nizovima, a nakon što ih jedinka pojede pojave se na slučajnoj lokaciji. Jedinke se također pojavljuju na slučajnoj lokaciji.

Najbolje rezultate u prvih stotinu iteracija dale su postavke:
                           VEL_POP = 100,
                           pc = 100%,
                           pm = 0.25%.

Najlošije rezultate u prvih stotinu iteracija dale su postavke:
                           VEL_POP = 25,
                           pc = 100%,
                           pm = 1%.

Iz grafova se može zaključiti da bi postavke VEL_POP = 25, pc = 10%, pm = 5% dale još lošije rezultate u prvih stotinu iteracija, jer se tako ne može postići uniformnost dobrih rješenja zbog male količine prenesenih dobrih, i velike količine novih slučajnih svojstava koja se unose svakom iteracijom posredstvom mutacije.

 

6. Zaključak

Genetski algoritam je vrlo moćno i praktično oruđe za rješavanje različitih problema optimiziranja. Njegova snaga je u apstraktnosti. Primjenjiv je na velik broj problema, a algoritam nudi puno stupnjeva slobode – nudi poboljšavanje efikasnosti algoritma malim zahvatima. Genetski algoritam daje skup  rješenja jednak veličini populacije, a najbolje među njima uvijek bi trebalo biti sasvim blizu optimuma, iako se ne može tvrditi da je sto posto točno. Algoritam se može primijeniti na bilo kojem tipu ili strukturi podataka, što ipak zahtjeva prilagodbu genetskih operatora. Uza svu prilagodljivost genetskog algoritma, i sama ideja algorima  je vrlo jednostavna i lako shvatljiva. Ipak, nekad je vrlo teško definirati funkciju dobrote, kako bi dobro opisivala rješenje problema koje tražimo. Stoga se često i problem mora prilagoditi sustavu koji koristimo. Također, podešavanje učinkovitih parametara iziskuje puno vremena i pokusa. Zbog izvođenja velikog broja računskih operacija GA zahtjeva veliku procesorsku snagu i to ga usporava, ali razvojem višejezgrenih i bržih procesora, te ostalih računalnih komponenti, taj problem će biti sve manji.

7. Literatura

1. Golub, Marin, Genetski algoritam: prvi dio. v.2.3. - 27. rujan 2004.,
   Zagreb, 2004.
2. Golub, Marin, Genetski algoritam: drugi dio. v.2.2. - 4. listopad 2004.,
   Zagreb, 2004.
3. David, Eck, A Demonstration of the Genetic Algorithm, 24. veljače 2001., http://math.hws.edu/xJava/GA/, 21. travanj 2007.
4. Wikipedia, DNA, http://en.wikipedia.org/wiki/DNA,
   21. travanja 2007.
5. Wikipedia, GA, http://en.wikipedia.org/wiki/Genetic_algorithm,
   21. travanja 2007.
6. Wikipedia, Evolution strategies, http://en.wikipedia.org/wiki/Evolution_strategies,
   21. travanja 2007.

8. Sažetak

Genetski algoritam je metoda optimizacije koji oponaša prirodni evolucijski proces. GA održava populaciju rješenja, evaluira ih, vrši selekciju nad njima, te ih reproducira i mutira.. Sve informacije o svojstvima neke jedinke u prirodi pohranjene su u jezgrama njenih stanica, u tvorevinama koje nazivamo kromosomima. Kromosomi se sastoje od jedne dugačke niti DNK na kojoj su pohranjene informacije. GA to oponaša, pa svaku jedinku predstavlja upravo jedan kromosom. GA može koristiti bilo koju strukturu i tip podataka u ulozi kromosoma.

Princip rada generacijskog genetskog algoritma temelji se na stvaranju nove populacije od odabranih jedinki iz stare. GA selekcijom odabire uglavnom bolje jedinke, ali i slabije imaju neku šansu preživljavanja. Kada su jedinke kopirane u novu populaciju, nad njima se izvršavaju genetski operatori križanja i mutacije, kako bi nastali njihovi potomci. Time se dobivaju nova rješenja. Eliminacijski genetski algoritam radi samo s jednom populacijom rješenja. Umjesto kopiranja dobrih rješenja, on eliminira loša, te ih nadomješta križanjem i mutacijom preostalih. Potomci mogu biti bolja ili lošija rješenja. GA konvergira k optimumu zahvaljujući križanju, dok se mutacija brine da to ne bude lokalni optumum.  Princip selekcije može biti jednostavni, turnirski, eliminacijski ili turnirski eliminacijski. Operatori križanja mogu biti s jednom ili više točaka prekida, dok mutacija može djelovati na jedan ili više bita, tako da im mijenja vrijednost ili zamjenjuje mjesta. Brzina i točnost konvergencije GA uvelike ovisi o parametrima algoritma, kao što su veličina populacije, vjerojatnosti križanja i mutacije, veličine populacije za eliminaciju itd. Optimiziranje tih parametara iziskuje puno vremena i pokusa.

Primjenjivost GA u razvoju jednostavne umjetne inteligencije vizualno dočarava GA Applet. GA Applet je slobodno dostupni simulator rada GA. Jedinkama u tom programu genetski kod određuje uzorak kretanja. Cilj jedinke je pojesti što više hrane. Što je bolji uzorak kretanja, to više hrane će određena jedinka pojesti, te će imati veću vjerojatnost za preživljavanje i reprodukciju.

Genetski algoritam je vrlo jak alat za rješavanje optimizacijskih problema. Prilagodljivost algoritma problemu jedna je od glavnih karakteristika algoritma. Nedostatak algoritma je teškoća definiranje dobre funkcije cilja. Zahvaljujući razvoju jačih računala u budućnosti će se ubrzati izvođenje genetskih algoritama koji traže veliku procesorsku snagu.

DODATAK

grafički prikaz napretka GA u GA Appletu za različite vrijednosti parametara vel_pop, pc i pm