1. Uvod

Temelje prirodne evolucije opisao je engleski znanstvenik Charles Darwin još u 19. stoljeću. Prirodna se evolucija odvija tako da jedinke koje se prilagode novim okolnostima preživljavaju, a one koje se ne prilagode umiru. To se zove prirodna selekcija. Vanjske karakteristike svih organizama su zapisane u njihovim genima. Jedinke sa vanjskim karakteristikama bolje prilagođenim okolišu imaju veće šanse za preživljavanje i povećanje broja jedinki svoje vrste tijekom generacija, dok manje prilagođene jedinke izumiru, uzrokujući tako i izumiranje čitavih vrsta. Na taj način priroda osigurava da geni bolje prilagođenih jedinki imaju veće šanse za preživljavanje i povećanje brojnosti svoje populacije. Upotrebljavajući taj osnovni biološki model, znanstvenici su razvili mnoge algoritme koje su nazvali Evolucijski algoritmi (Evolutionary Algorithms).

U ovom su seminarskom radu prvo navedeni općeniti podaci o evolucijskim algoritmima. Objašnjeni su osnovni procesi poput selekcije, rekombinacije i mutacije, a nakon toga neki temeljni problemi koji se javljaju (odabir roditelja, kontrolni parametri, uvjet završetka evolucijskog procesa). Na kraju su nabrojane i detaljnije obrađene vrste evolucijskih algoritama. Pritom su objašnjene njihove posebnosti, prednosti i mane.

2. Evolucijski algoritmi

2.1 Općenito o evolucijskim algoritmima

Evolucijski algoritmi su stohastičke metode pretraživanja koje oponašaju prirodni tijek biološke evolucije. Osnovni cilj evolucijskih algoritama je pronalaženje rješenja nekog problema koje standardne (tradicionalne) determinističke metode ne mogu riješiti. No, za razliku od njih, evolucijski algoritmi ne daju uvijek optimalno rješenje. Pošto optimalno rješenje nije uvijek moguće naći, evolucijski algoritmi daju rješenje koje zadovoljava kriterij optimizacije, a on je definiran od strane korisnika. Pretragu ne započinju kao standardni algoritmi od jedinstvene točke, nego ju započinju od cijelog niza (populacije) rješenja. Populaciju potencijalnih rješenja razrađuju primjenjujući princip preživljavanja najspremnijeg (survivle of the fittest) da bi proizveli bolje i bolje aproksimacije rješenja. Takve iteracije se ponavljaju dok se ne pronađe zadovoljavajuće rješenje. Svaka iteracija podrazumijeva stvaranje nove generacije, koja sadrži novi skup aproksimacija. Nove aproksimacije su bolje od onih prethodnih.

Svaka iteracija evolucijskih algoritama sadrži selekciju i odbacivanje loših rješenja. Pojedinci se biraju prema stupnju njihove dobrote, koja predstavlja stupanj prikladnosti (pogodnosti) rješenja prema zadanom problemu. Bolja rješenja (ona sa većom dobrotom) su podvrgnuta djelovanju genetskih operatora, stvorenih na sliku onih iz prirodne genetike. Rekombiniraju se s drugim boljim rješenjima tako da se zamijene dijelovi rješenja, poput prirodne rekombinacije gena. Također su podvrgnuta i mutaciji, tj. nasumičnim odabirom im se mijenjaju određeni dijelovi. Rekombinacija i mutacija se koriste da bi se generirala nova rješenja usmjerena prema području u kojem su već viđena dobra rješenja. Tako se razvijaju pojedinačna rješenja koja su prikladnija nego rješenja od kojih su ona stvorena (slika 2.1). Cijeli se proces temelji na prirodnom procesu evolucije.

Slika 2.1. Rješavanje problema evolucijskim algoritmom

U početku računanja populacija se inicijalizira slučajnim odabirom. Tada se stvara funkcija cilja za tu populaciju. Na taj način je stvorena prva (inicijalna) generacija.

Ako kriterij optimizacije nije zadovoljen, započinje stvaranje nove generacije. Rješenja se prema svojoj dobroti odabiru za stvaranje potomstva. Roditelji se rekombiniraju da bi proizveli potomstvo, koje će biti podvrgnuto mutaciji s nekom slučajnom vjerojatnošću. Tada se računa dobrota potomstva (fitness), koje se potom ubacuje u populaciju zamjenjujući tako svoje roditelje i stvarajući novu generaciju. Ovaj se postupak ponavlja dok se ne dosegne kriterij završetka evolucijskog procesa (slike 2.2 i 2.3), koji je detaljnije objašnjen kasnije.

Evolucijski algoritam

{

t = 0; //inicijaliziraj vrijeme na nulu

generiraj početnu populaciju potencijalnih rješenja P(0);

evaluiraj P(t); //odredi dobrotu svih jedinki u populaciji

dok nije zadovoljen uvjet završetka evolucijskog procesa{

t = t + 1; //povećaj vrijeme

izaberi roditelje P'(t) za kreiranje potomstva;

rekombiniraj P'(t); //rekombiniraj gene izabranih roditelja

mutiraj P'(t); //poremeti populaciju slučajnim odabirom

evaluiraj P'(t); //odredi njenu novu dobrotu

P(t) = preživi P, P'(t); //izaberi preživjele prema dobroti

}

ispiši rješenje;

}

Slika 2.2. Pseudokod evolucijskog algoritma

Slika 2.3. Struktura jednostavnog evolucijskog algoritma

2.1.1 Selekcija

Tijekom selekcije (selection) biraju se jedinke koje daju potomstvo, tj. one koje vode prema konačnom rješenju koje zanima korisnika. Prvi je korak selekcije procjena dobrote (fitness selection). Zatim svaka jedinka unutar skupa dobiva vjerojatnost razmnožavanja, koja ovisi o iznosu dobrote te jedinke, ali i o iznosu dobrote ostalih jedinki. Što je jedinka bliže ciljanom rješenju u odnosu na druge jedinke, njezina vjerojatnost razmnožavanja se povećava. Analogno tome, ako je iznos dobrote jedinke manji u odnosu na onaj drugih jedinki, njezine mogućnosti preživljavanja se smanjuju.

2.1.2 Mutacija

Mutacija (mutation) je genetski operator koji se upotrebljava za dobivanje genetske raznolikosti sljedeće generacije rješenja od one postojeće. Najjednostavniji primjer mutacije je vjerojatnost da se neki bit u genetskom kodu (tj. rješenju) promijeni iz svog originalnog stanja u neko novo stanje. To se postiže uvođenjem neke varijable za svaki bit u nizu. Ta varijabla govori hoće li neki bit biti modificiran ili neće.

Mutacija sprječava da neka rješenja unutar populacije postanu preslična s drugima i na taj način uspore ili zaustave evoluciju. Tako se onemogućuje evolucijski algoritam da pronađe neki lokalni optimum, zanemarujući pritom mnogo bolji globalni (kojeg korisnik ujedno i traži).

2.1.3 Rekombinacija

U procesu rekombinacije (recombination) ili križanja (crossover) stvaraju se nove jedinke koje sadrže kombinirane informacije sadržane u dvoje ili više roditelja. To se postiže kombinacijom varijabli koje su sadržavali roditelji. Ovisno o prikazu tih varijabli, implementiraju se mnoge metode rekombinacije. Najpoznatije su:

križanje u jednoj točki (one-point crossover)

Odabire se jedna točka na roditeljima (jednako udaljena od početka za oba roditelja) i mijenja se desni dio kromosoma prvog roditelja s desnim dijelom kromosoma drugog roditelja.

križanje u dvije točke (two-point crossover)

Odabiru se dvije točke na roditeljima, pazeći da je pritom lijeva točka jednako udaljena od lijevog kraja kromosoma i desna od desnog kraja za oba roditelja. Roditelji međusobno mijenjaju dijelove kromosoma između tih točaka.

križanje rezanjem i spajanjem (cut and splice crossover)

Na roditeljima se odabire točka koja nije jednako udaljena od početka roditeljskih kromosoma. Mijenja se desni dio kromosoma jednog roditelja s desnim dijelom kromosoma drugog. Na taj način nastaju djeca koja imaju različite duljine kromosoma.

uniformno križanje (uniform crossover)

Uspoređuju se bit po bit oba roditelja i mijenjaju se sa fiksnom vjerojatnošću od 50%

polu-uniformno križanje (half-uniform crossover)

Uspoređuje se bit po bit oba roditelja i računa koliko ih se ne poklapa. Polovica od tih koji se ne poklapaju se mijenja.

Slika 2.4. Rekombinacija

2.1.4 Kontrolni parametri

Ako se poveća učestalost križanja i mutacije istražit će se širi prostor potencijalnih rješenja, ali će se i povećati rizik gubljenja dobrih rješenja i neuspješnosti njihova korištenja. Zato treba pronaći skup kontrolnih parametara (control parameters) koji određuju optimalan omjer između istraživanja i korištenja.

Primjer korištenja kontrolnih parametara je problem prebrze konvergencije rješenja, koji se često pojavljuje u evolucijskim algoritmima. On dovodi do situacije u kojoj većina članova populacije ima slična obilježja, ali ta obilježja nisu ona koja bi korisnik želio. Jedan način sprječavanja ovog problema je da se onemogući novim nizovima podataka da imaju manju Hammingovu udaljenost od neke određene (Hammingova udaljenost neka dva podatka jednaka je broju bitova u kojima se ti podaci razlikuju). Međutim, to uvelike ograničava potragu evolucijskog algoritma. Drugi način rješavanja problema prerane konvergencije je upotrebljavanje dviju točaka križanja umjesto jedne. Na taj način križanje donosi veću razliku (varijaciju), a dinamičkim mijenjanjem frekvencije križanja se dobiva kompromis između istraživanja i korištenja. Mora se paziti da roditelji koji se križaju nisu identični, jer u protivnom upotrebljavanje više točaka križanja nema smisla i ne donosi nikakvu prednost, već nastaje incest. Izbjegavanje incesta se postiže tako da se prije križanja nekih roditelja provjeri je li njihova Hammingova udaljenost iznad nekog minimalnog praga, koji je ranije definiran.

2.1.5 Problem definicije prostora rješenja

Evolucijski se algoritmi često opisuju kao neograničene metode optimiranja. Obzirom da većina problema u stvarnom svijetu ima svoja ograničenja, ona moraju nekako biti ukomponirana u sam algoritam. Algoritam ne može tražiti rješenja u intervalu [-∞,∞], nego mu se moraju odrediti neke granice, tako da traži u intervalu [donja granica, gornja granica]. Taj je problem poznatiji pod nazivom problem definicije prostora rješenja (problem constraints).

Postoji puno metoda koje rješavaju taj problem, ali prilikom njihove upotrebe treba biti pažljiv. Ukoliko se ne dopuste rješenja koja vode do narušavanja ograničenja, može se doći u situaciju u kojoj se pregledavaju brojna rješenja prije pronalaska izvedivog ili vjerojatnog. Na taj način se vrijeme računanja može uvelike povećati, ovisno o količini loših rješenja ispred onih dobrih (izvedivih). S druge strane, u algoritmu se može onemogućiti stvaranje neizvedivih rješenja pomoću popravnih algoritama (repair algorithms) i dekodera (decoder). Popravni algoritmi i dekoderi mogu raditi sasvim dobro, ali su specifični za svaki problem kojeg rješavaju pa ih je jako teško za implementirati i mogu biti vrlo naporni za računalo. Uz to, mogu i uništiti naslijeđene karakteristike evolucijskog algoritma. Zato se češće upotrebljavaju kaznene funkcije (penalty functions). To su funkcije devijacije ograničenja i broja prekršenih ograničenja, a mogu biti linearne, kvadratne, logaritamske ili neke druge.

2.1.6 Odabir roditelja

Da bi proizveli sljedeću generaciju jedinki, trebamo pronaći dobre roditelje i izabrati ih za razmnožavanje. Najpoznatiji načini odabira roditelja (parent selection shemes) su:

1. Proporcionalno razmnožavanje (Proportionate reproduction) - ovdje se jedinke biraju prema svojoj dobroti

2. Odabir po rangu (Ranking selection) - populacija se sortira od najboljih prema najgorima. Broj kopija koje jedinka dobije određuje se funkcijom (assignment function) i proporcionalan je rangu jedinke (tj. poziciji u odnosu na generaciju)

3. Turnirski odabir (Tournament selection) – bira se slučajan broj jedinki iz populacije (sa ili bez zamjena, ovisno o implementaciji), a najbolje od njih postaju roditelji sljedeće generacije. Ovaj se proces ponavlja dok se ne popuni cijela sljedeća generacija, tj. dok se ne izaberu svi njeni članovi

2.1.7 Kriterij završetka evolucijskog procesa

Proces generiranja sljedeće generacije se ponavlja dok se ne zadovolji uvjet završetka evolucijskog algoritma, koji se još naziva i uvjet kraja ili kriterij kraja. Kriterij kraja je najčešće jedan od sljedećih:

§ Pronađeno je rješenje koje zadovoljava minimalne kriterije

§ Dosegnut je unaprijed određeni broj generacija

§ Potrošen je budžet (vrijeme ili novac)

§ Rješenje sa najvećim stupnjem dobrote dostiže ili je već dostiglo granicu takvu da daljnje iteracije ne daju bolje rezultate

§ Ručno ispitivanje

§ Kombinacije gore navedenih

2.1.8 Višepopulacijski evolucijski algoritmi

Dosada prikazivani evolucijski algoritmi sastoje se od jedne populacije i pokazuju se vrlo moćnim na širokom aspektu problema. Međutim, bolji se rezultati mogu dobiti ukoliko uvedemo više podpopulacija. Svaka se podpopulacija razvija izolirana nekoliko generacija prije nego li se pojedine jedinke zamijene (tako da neke prijeđu iz jedne u drugu podpopulaciju, a druge obrnuto). Takvi evolucijski algoritmi koji koriste više podpopulacija nazivaju se višepopulacijski evolucijski algoritmi (multi – population evolutionary algorithm). Oni su sličniji prirodnom razvoju vrsta nego jednopopulacijski, pa zato i daju bolje rezultate. Procesi selekcije, mutacije i rekombinacije su isti kao i u jednopopulacijskima, a postoje još i procesi ubacivanja (reinsertion), migracije (migration) i kompetencije (competition) (slika 2.5).

Slika 2.5. Struktura višepopulacijskog evolucijskog algoritma

2.2 Vrste evolucijskih algoritama

Evolucijski algoritmi obuhvaćaju vrlo široko područje, pa ih se prema implementacijama dijeli na nekoliko tipova:

1. Genetski algoritmi

2. Evolucijsko programiranje

3. Evolucijska strategija

4. Genetsko programiranje

5. Klasifikatorski sustavi

2.2.1 Genetski algoritmi

Genetski algoritmi (Genetic algorithms) su najpopularnija vrsta evolucijskih algoritama, a predstavljaju model strojnog učenja čije ponašanje potječe iz procesa evolucije koji se odvija u prirodi. Postoje dva osnovna pristupa rješavanja problema genetskim algoritmom: problem se može prilagoditi genetskom algoritmu ili genetski algoritam problemu. Prije inicijalizacije genetskog algoritma, moraju se definirati dvije stvari: način na koji će se prikazivati rješenja i funkcija cilja.

Rješenja se najčešće prikazuju nizom bitova i binarnim brojevima. Na isti način se mogu koristiti i druge, složenije strukture poput matrica ili stabala. Glavna prednost takvog prikaza je u tome što se njegovi dijelovi zbog fiksne veličine mogu lako poravnati i uskladiti što omogućuje jednostavnu operaciju križanja. Mogu se koristiti i nizovi različite duljine, ali se tada križanje uvelike komplicira. Nakon definicije prikaza rješenja, definira se i funkcija cilja (fitness function) koja na odgovarajući način predstavlja ključ selekcije (tj. problem koji se rješava) i mjeri kvalitetu (dobrotu) pojedinog rješenja. Ona uvijek ovisi o problemu koji se rješava.

U početku se slučajnim odabirom stvara populacija jedinki koje predstavljaju rješenja. Veličina te početne populacije ovisi o prirodi problema, a obično sadrži nekoliko stotina ili tisuća rješenja. Početna se populacija najčešće stvara slučajnim odabirom rješenja iz domene. Međutim, moguće ju je generirati i uniformno ili usaditi (seed) početno rješenje u područja u kojima će se vjerojatno nalaziti optimalna rješenja (ako je to već dobiveno nekom drugom optimizacijskom metodom). Uniformno generiranje početne populacije nije preporučljivo jer su tada sve jedinke iste pa genetski algoritam u početku nije učinkovit.

Tijekom svake sljedeće generacije, bira se određen broj postojećih rješenja za generiranje sljedeće generacije. Rješenja se biraju ovisno o funkciji cilja: za bolja rješenja (sa većom dobrotom) postoji veća šansa da će biti izabrana. Neke metode selekcije ocjenjuju dobrotu svih rješenja, ali pošto taj proces uzima jako puno vremena, većina ih ipak ocjenjuje samo slučajno odabrani uzorak jedinki. Za većinu metoda karakteristično je da uzimaju mali dio lošijih rješenja za generiranje sljedeće generacije. Takvo ponašanje pomaže algoritmu da zadrži raznolikost rješenja, tj. sprječava preranu konvergenciju prema lošim rješenjima.

Sljedeći zadatak genetskog algoritma je generiranje sljedeće populacije rješenja, a to se postiže preko genetskih operatora rekombinacije i mutacije. Za svako sljedeće rješenje koje će se proizvesti, od postojećih se rješenja bira par rješenja roditelja za križanje. Na taj način nastaje novo rješenje koje obično sadrži mnoge karakteristike koje su mu sadržali i roditelji. Za svako dijete se biraju novi roditelji, a proces se nastavlja dok ne nastane nova populacija rješenja prikladne veličine. Na taj način nastaje sljedeća generacija rješenja koja je drukčija od početne generacije. Ona obično ima veći stupanj dobrote od početne generacije, jer su za razmnožavanje većinom birana rješenja sa visokim stupnjem dobrote. Ovakav se postupak ponavlja dok se ne zadovolji kriterij završetka evolucijskog procesa (slika 2.6).

Genetski algoritam

{

t = 0;

generiraj početnu populaciju potencijalnih rješenja P(0);

sve dok nije zadovoljen uvjet završetka evolucijskog procesa

{

t = t + 1;

selektiraj P’(t) iz P(t-1);

križaj jedinke iz P’(t) i djecu spremi u P(t);

mutiraj jedinke iz P(t);

}

ispiši rješenje;

}

Slika 2.6. Struktura genetskog algoritma

2.2.2 Evolucijsko programiranje

Evolucijsko programiranje (Evolutionary programming) je stohastička optimizacijska strategija slična genetskim algoritmima. Za razliku od genetskih algoritama koji emuliraju genetske operatore iz prirode, evolucijsko programiranje naglasak stavlja na ponašajnu vezu između roditelja i njihovog potomstva. Upotrebljava se kada analitička izračunavanja nisu moguća, a posebno je pogodno za probleme u kojima postoji mnogo lokalnih optimalnih rješenja. Sastoji se od 3 osnovna koraka (slika 2.7):

1. Izabire se inicijalna populacija i slučajnim se odabirom pregledavaju neka rješenja. Brzina optimizacije ovisi o broju početnih rješenja, ali ne postoje definicije koje bi rekle koliko je rješenja najbolje na početku staviti, a koliko bi ih bilo višak. To ovisi o problemu.

2. Svako rješenje se replicira u novu populaciju. Zatim je podvrgnuto mutaciji, čija jačina ovisi o funkcionalnim promjenama nametnutim od strane roditelja.

3. Računa se dobrota za svaki potomak stohastičkim ili determinističkim metodama. Evolucijsko programiranje ne koristi rekombinaciju kao genetski operator.

Kod evolucijskog programiranja veličina populacije se ne mora držati konstantnom, a svaki roditelj može dati više potomaka. Od genetskih operatora, koristi se mutacija koja ne zahtjeva linearno kodiranje pa nema ograničenja prikaza, već prikaz slijedi iz samog problema. Mutacija jednostavno mijenja pogled rješenja ovisno o statističkoj raspodjeli, koja ocjenjuje male promjene vrlo vjerojatnima, a one veće malo vjerojatnima. Učestalost mutacija se smanjuje kako se bližimo globalnom maksimumu. Postavlja se pitanje kako možemo znati jesmo li blizu globalnog maksimuma ili nismo. Odgovor na to pitanje daje Meta-Evolucijska metoda (Meta-Evolutionary technique) koja kaže da je odstupanje od mutacijske raspodjele podvrgnuto mutaciji fiksnog odstupanja i razvija se paralelno s rješenjima.

Evolucijsko programiranje{

t = 0;

generiraj početnu populaciju potencijalnih rješenja P(0);

evaluiraj P(0); //odredi dobrotu inicijalne populacije

sve dok nije zadovoljen uvjet završetka evolucijskog procesa

{

P'(t) = mutiraj(t); //nasumično promiješaj cijelu populaciju

evaluiraj P'(t); //odredi novu dobrotu

P(t+1) = preživi P(t),P'(t); //izaberi potomke prema dobroti

t = t + 1;

}

Slika 2.7. Struktura evolucijskog programiranja

2.2.3 Evolucijska strategija

Evolucijska strategija (Evolution strategy) je optimizacijska metoda bazirana na prilagođavanju i evoluciji. Podaci se prikazuju kao realni vektori, a od genetskih operatora se najčešće upotrebljava mutacija i selekcija (iako postoje slučajevi kada se upotrebljava i rekombinacija). Mutacija se provodi tako da se svakoj komponenti vektora doda neka slučajna vrijednost, koja je podložna normalnoj razdiobi. Selekcija je deterministička i bazirana na dobroti jedinki. Ne zanima ju točna vrijednost dobrote jedinke, već njen poredak u generaciji. To znači da će se mutant (jedinka nastala mutacijom) upotrebljavati za daljnje razmnožavanje samo onda ako je njegova dobrota veća od dobrote njegovog roditelja. U protivnome se mutant zanemaruje, a njegov roditelj postaje roditelj još jedne generacije. Takva se evolucijska strategija zove (1+1)ES, što znači da je od jednog roditelja nastao jedan mutant, a jedan od njih dvojice postaje roditelj u sljedećoj generaciji.

Međutim, jedan roditelj procesom mutacije može dati proizvoljan broj mutanata. Tada se svi oni natječu protiv njega, a samo najbolji mutant postaje roditelj sljedeće generacije. To se naziva (m+1)ES, što znači da je od jednog roditelja nastalo m mutanata i jedan od njih m+1 postaje roditelj u sljedećoj generaciji. Algoritam se može implementirati i tako da roditelj koji stvori m mutanata ne može biti roditelj i u sljedećoj generaciji. Takva se evolucijska strategija označava (m,1)ES, što znači da je od jednog roditelja nastalo m mutanata, a jedan od tih m mutanata će postati roditelj u sljedećoj generaciji. Zapisivanje se može generalizirati na (µ+ λ)ES ili (µ, λ)ES gdje µ označava veličinu populacije, a λ broj potomstva koji se kreira po generaciji (slika 2.8).

Evolucijska strategija{

t = 0;

generiraj početnu populaciju P(0);

evaluiraj P(0); //provjeri dobrotu inicijalne populacije

sve dok nije zadovoljen uvjet završetka evolucijskog procesa

{

izaberi najboljih µ roditelja iz P(t) i stavi ih u P_p(t);

iz P_p(t) reproduciraj λ potomaka i stavi ih u P_c(t);

mutiraj P_c(t);

evaluiraj P_c(t);

ako se koristi plus strategija P(t+1) = P_c(t) υ P(t);

inače P(t+1) = P_c(t);

t = t + 1;

}

Slika 2.8. Struktura evolucijske strategije

2.2.4 Genetsko programiranje

Genetsko programiranje (Genetic programming) je evolucijski algoritam čija se metodologija bazira na biološkoj evoluciji, a traži kompjutorske programe koji izvode zadatke koje su im zadali ljudi. To je način strojnog učenja koji se upotrebljava za optimiranje kompjutorskih programa prema stupnju njihove dobrote koja predstavlja mogućnost programa da obavi neki zadatak (slika 2.9).

Genetsko programiranje razvija kompjutorske programe koji su u memoriji prikazani kao stabla (slika 2.10). Stabla su pogodna za implementaciju jer se ona mogu rekurzivno vrlo jednostavno obići. Svaki unutarnji čvor stabla sadrži neki operator, dok listovi sadrže operande. Na taj se način matematički izrazi lako i efikasno računaju. Matematički operatori su najčešće aritmetički (+, -, *, /, sin, cos, exp), logički (i, ili, ne, nili, ni) ili specifični ovisno o problemu (min, max).

U genetskom se programiranju koriste dva osnovna genetska operatora: rekombinacija i mutacija. Rekombinacija se provodi tako da se neka dva čvora unutar stabla jednostavno zamijene. To podrazumijeva i zamjenu cijele grane, što čini rekombinaciju vrlo učinkovitom. Djeca nastala rekombinacijom se uvelike razlikuju od svojih roditelja. Mutacija utječe na jednu jedinku unutar populacije. Ona uzrokuje mijenjanje cijelog čvora, ili samo informacije koju taj čvor sadrži. Ovisno o implementaciji genetskog programiranja, mutacija se može i izostaviti.

Slika 2.9. Struktura genetskog programiranja

U posljednje se vrijeme razvija i Meta-Genetsko programiranje (Meta-Genetic programming). To je metoda razvijanja genetskog programiranja upotrebljavajući samo genetsko programiranje. U njemu kromosome, rekombinaciju i mutaciju ne razvija programer, nego im se dopušta da se razviju sami od sebe.

Slika 2.10. Prikaz programa u obliku stabla

2.2.5 Klasifikatorski sustavi

Klasifikatorski sustavi (Classifier systems) su kognitivni sustavi koji imaju mogućnost spoznaje događaja iz svoje okoline i reakcije na te događaje. Oni upotrebljavaju genetske algoritme da bi prilagodili svoje ponašanje prema okolini koja se neprestano mijenja. Zbog toga je za izgradnju klasifikatorskog sustava potrebno imati:

§ Okolinu

§ Receptore (receptors) koji će reći sustavu što se događa

§ Djelovatelje (effectors) koji omogućuju sustavu da manipulira okolinom

§ Sam sustav, tj. neku vrstu „crne kutije”. Sustav živi u okolini, a sadrži receptore i djelovatelje

Za računalo možemo reći da je najprimitivnija „crna kutija”. Ono ima svoje ulaze, izlaze i sustav između njih, koji mijenja ulazne poruke u izlazne (tj. računa nešto) pridržavajući se pritom skupa pravila koja se nazivaju program.

Ulazno sučelje generira poruke koje se zapisuju u listu poruka. Te se poruke tada uspoređuju sa uvjetnim dijelom svih klasifikatora da bi se saznalo koje korake treba poduzeti. Lista poruka se tada prazni, a kodirane akcije (koje su same po sebi također poruke) se stavljaju u listu. Tada izlazno sučelje provjerava listu poruka i traži one poruke koje se tiču djelovatelja. Zatim se opet ide na početak. Takav klasifikatorski sustav, koji nema mogućnost učenja, naziva se Non-Learning classifier system (slika 2.11).

Ideja klasifikatorskih sustava je da počinje ispočetka, bez ikakvog početnog znanja. Zatim slučajnim odabirom kreira inicijalnu populaciju i pušta sustav da uči svoj program indukcijom, što smanjuje ulazne nizove. Klasifikatorski sustav koji ima mogućnost učenja naziva se Learning classifier system.

Klasifikatorski sustav{

t = 0;

inicijaliziraj listu poruka; //stvaranje prazne liste poruka

inicijaliziraj populaciju klasifikatora;

dok nije zadovoljen uvjet završetka evolucijskog procesa{

t = t + 1;

ako ima poruka na detektorima spremi ih u listu poruka ML;

usporedi listu poruka ML(t) sa listom poruka klasifikatora;

poruke koje se poklapaju spremi u ML'(t);

obradi ML'(t) pomoću djelovatelja;

poruke od djelovatelja spremi u listu poruka ML;

}

Slika 2.11. Struktura klasifikatorskih sustava

3. Zaključak

Evolucijski algoritmi odlično aproksimiraju rješenja širokog spektra problema, pa su našli svoju primjenu u inženjerstvu, umjetnosti, biologiji, ekonomiji, genetici, robotici, fizici, kemiji i mnogim drugim djelatnostima. Iako postoje mnogi besplatni i komercijalni programi koji omogućuju primjenu evolucijskih algoritama, u mnogim se praktičnim primjenama pokazala potreba modifikacije barem nekog dijela postojećih programa kako bi se algoritam uspješno prilagodio zadatku, optimalno iskorištavajući resurse i memoriju koja mu je na raspolaganju.

Rasprostranjenost računala i opće povećanje njihove snage pogoduje praktičnoj primjeni evolucijskih algoritama. Popularizacija evolucijskih algoritama, jednostavnost njihove primjene i uspješna rješenja različitih praktičnih zadaća pomoću njih još su neki od razloga sa njihovu daljnju industrijsku primjenu. Međutim, valja naglasiti da evolucijski algoritmi nisu čarobni štapić pomoću kojeg treba rješavati sve zadatke, već su oni jedan od postupaka koji ponajprije mogu pomoći pri rješavanju složenih zadataka s mnogo parametara za koje ne postoje zadovoljavajuća rješenja tradicionalnim postupcima.

4. Literatura

[1] Golub, M. Genetski algoritam, prvi dio, http://www.zemris.fer.hr/~golub/ga/ga_skripta1.pdf, 05.04.2007.

[2] Grundler D., Rolich T. Evolucijski algoritmi (II) – Primjena. AUTOMATIKA - Časopis za automatiku, mjerenje, elektroniku, računarstvo i komunikacije, Vol. 42. No. 3-4 (21.12.2001.)

[3] Wikipedia, Evolutionaty algorithm, http://en.wikipedia.org/wiki/Evolutionary_algorithms, 30.03.2007.

[4] Wikipedia, Genetic algorithm, http://en.wikipedia.org/wiki/Genetic_algorithm, 30.03.2007.

[5] Wikipedia, Crossover (genetic algorithm), http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm), 30.03.2007.

[6] Evolutionary algorithm faq, http://www.cs.cmu.edu/Groups/AI/html/faqs/ai/genetic/part2/faq.html, 30.04.2007.

[7] Evolutonary algorithm, http://www.geatbx.com/docu/algindex.html, 20.03.2007.

[8] Evolutionary algorithms, http://www.cs.sandia.gov/opt/survey/ea.html, 20.03.2007.

5. Sažetak

Evolucijski algoritmi su stohastičke metode pretraživanja koje oponašaju prirodni tijek biološke evolucije. Pretragu ne započinju od jedinstvene točke, nego od inicijalne populacije rješenja. Ta je populacija zatim podvrgnuta djelovanju genetskih operatora koji su stvoreni na sliku onih iz prirode. Selektiraju se bolja rješenja koja se zatim međusobno rekombiniraju i dovode pod utjecaj mutacije, tj. nasumičnih promjena. Tako se stvara njihovo potomstvo, a postupak se ponavlja dok se ne ispuni kriterij završetka evolucijskog procesa. To ne mora značiti da je pronađeno optimalno rješenje, jer kriterij kraja ne znači nužno da je rješenje zadovoljilo korisnika. On može biti određen i budžetom (vremenom ili novcem), ručnim ispitivanjem, dostignutim brojem generacija ili pak stalnim ponavljanjem rješenja. Ukoliko algoritam radi ispravno, svaka sljedeća generacija će biti korak bliže ka traženom rješenju.

Jedan od glavnih problema na koji evolucijski algoritmi nailaze je prerana konvergencija rješenja, što dovodi do nalaženja lokalnog optimuma umjesto globalnog. Taj se problem rješava pažljivim odabirom kontrolnih parametara. Drugi problem je problem definiranja prostora rješenja, jer algoritam ne može tražiti rješenja u intervalu [-∞,∞] već mu moramo definirati granice unutar kojih da traži.

Najpoznatije vrste evolucijskih algoritama su:

1. Genetski algoritmi – najpoznatija vrsta evolucijskih algoritama u kojoj je ključ selekcije funkcija cilja, koja na odgovarajući način predstavlja problem koji se rješava. Selekcijom se odabiru dobre jedinke koje se prenose u slijedeću populaciju, a manipulacijom genetskog materijala stvaraju se nove jedinke.

2. Evolucijsko programiranje – naglasak je na ponašajnoj vezi između roditelja i potomstva. Od genetskih operatora ne koristi se rekombinacija, nego mutacija što omogućuje jednostavnu selekciju. Jedan roditelj mutacijom može dati više potomaka.

3. Evolucijska strategija – jedan roditelj mutacijom daje jednog ili više mutanata, a onaj sa najvećom dobrotom (može biti i roditelj i mutant) postaje roditelj u sljedećoj generaciji.

4. Genetsko programiranje - strojno učenje koje optimizira kompjutorske programe prema stupnju njihove dobrote koja predstavlja mogućnost programa da obavi neki zadatak. Programi su u memoriji prikazani kao stabla – u unutarnjim čvorovima su operatori, a u listovima operandi.

5. Klasifikatorski sustavi - kognitivni sustavi koji imaju mogućnost spoznaje događaja iz svoje okoline i reakcije na te događaje. Sastoje se od okoline, receptora, djelovatelja i sustava. Mogu i ne moraju imati sposobnost učenja (learning i non-learning classifier systems).

Evolucijski algoritmi nisu prikladni za rješavanje svih problema. Upotrebljavati ih treba za rješavanje složenih zadataka s mnogo parametara za koje ne postoje zadovoljavajuća rješenja tradicionalnim postupcima.