Sadržaj
1. Uvod u evolucijske algoritme
2. Genetski algoritam
2.1 Prikaz ili predstavljanje rješenja
2.2 Inicijalizacija i uvjet završetka evolucijskog procesa
2.3 Funkcija dobrote
2.4 Postupci selekcije
2.4.1 Generacijski genetski algoritam
2.4.2 Eliminacijski genetski algoritam
2.4.3 Problem elitizma
2.5 Reprodukcija
2.5.1 Križanje
2.5.2 Mutacija
2.6 Parametri algoritma
3. Pregled ostalih evolucijskih algoritama
3.1 Genetsko programiranje
3.2 Evolucijske strategije
3.3 Evolucijsko programiranje
3.4 Klasifikatorski sustavi
4. Zaključak
5. Literatura
1. Uvod u evolucijske algoritme
Vjerujem da se svi možemo složiti da je biološka raznolikost života na Zemlji zaprepaštvajuća. Znanstvenici smatraju da na planetu postoji između 3 i 5 milijuna vrsta od kojih je preko 1.5 milijuna opisano. Uz preko 250 tisuća opisanih fosila, nije teško razumjeti zašto su ljudi toliko dugo vjerovali da dana raznolikost života mora biti rezultat stvaranja. Međutim, danas znamo da se ova pojava može, barem na razini shvaćanja, opisati vrlo jednostavnim konceptima. Križanje i mutacija genetskog materijala dovode do raznolikosti među vrstama nad kojom zatim priroda obavlja selekciju. Jedinke bolje prilagođene svojoj okolini i uvjetima u prirodi imaju veću vjerojatnost preživljavanja i parenja, a samim time i prenošenja svog genetskog materijala na sljedeće naraštaje. Ovim postupkom “bolji geni”, odnosno geni bolje prilagođene jedinke opstaju, dok geni lošije jedinke izumiru. Opisana metoda optimiranja naziva se evolucija, a evolucijski se algoritam zasniva upravo na imitiranju njezinih metoda.
Evolucijski algoritmi su skup stohastičkih metoda pretraživanja koji oponašaju prirodni tijek biološke evolucije. Slično kao što je su prilagođenost okolini i uvjetima u prirodi ključ odabira nad nekom živom vrstom, tako i evolucijski algoritmi sadrže mehanizam pomoću kog se obavlja selekcija. Nazivamo ga ključ selekcije. On selekciju obavlja nad populacijom jedinki, skupom rješenja genetskog algoritma koji su analogija živim bićima u prirodi. Dobre jedinke koje se po nekim traženim karakteristikama izdižu iz populacije prenosimo u sljedeću populaciju. Manipulacijom genetskog materijala pomoću takozvanih genetskih operatora iz odabranih se jedinki stvara nova populacija nad kojom se ponavlja cijeli proces sve dok nije zadovoljen uvjet zaustavljanja evolucijskog procesa.
Evolucijski algoritmi obuhvaćaju vrlo široko područje, te ih dijelimo na:
genetski algoritmi
genetsko programiranje
evolucijsko programiranje
evolucijska strategija
Iako su algoritmi podijeljeni u manje skupine, često je vrlo teško odrediti gdje jedna algoritam prestaje a drugi počinje. Te granice nisu strogo određene, te je dozvoljeno raditi brojne preinake s ciljem dobivanja kvalitetnog i brzog rješenja. O sličnostima i razlikama samih algoritama više u kasnijim poglavljima. Među evolucijske algoritme mnogi stručnjaci ubrajaju i klasifikatorske sustave, posebne sustave koji korištenjem evolucijskih algoritama i učenja s potkrjepljenjem imaju mogućnost prilagođavanja uvjetima u okolini.
U prvom dijelu ovog seminara najviše ćemo pozornosti pridodati genetskim algoritmima, najopsežnijem tipu evolucijskih algoritama. U sklopu genetskog algoritma proći ćemo kroz mnoge metode koje nisu specifične isključivo za genetske algoritme, već ih koristi mnogo drugih evolucijskih algoritama. U poglavljima 3, 4, 5 i 6 detaljnije ćemo se upoznati s ostalim evolucijskim algoritmima i njihovim primjenama. Na kraju ovog seminara osvrnut ćemo se na evolucijske algoritme, proći kroz neke uspjehe i neuspjehe, te pokušati vidjeti kuda nas budućnost vodi.
Genetski algoritam je heuristička metoda optimiranja koja imitira prirodni evolucijski proces. Prvi put ga je predložio Johna H. Holland još u ranim sedamdesetim godinama 20. stoljeća. U svom radu, Holland je predložio jednostavni genetski algoritam kao računarski proces koji imitira evolucijski proces u prirodi i primjenjuje ga na apstraktne jedinke. Kao što evolucija u prirodi djeluje nad skupom jedinki tako i svaki evolucijski program održava populaciju jedinki u nekoj određenoj generaciji. Svaka jedinka predstavlja potencijalno rješenje problema koji se obrađuje. U genetskom algoritmu svaka je jedinka predstavljena jednakom podatkovnom strukturom. Na primjer brojem, nizom, matricom itd. ovisno o problemu kojeg rješavamo. Te jedinke se nazivaju kromosomi. Svaka jedinka sadrži skup karakteristika kojima se pridružuje mjera kvalitete koja se obično naziva dobrota. Funkcija koja tu kvalitetu određuje naziva se funkcija cilja ili funkcija dobrote. Tada se iz stare generacije, po nekom postupku odabira odnosno selekcije, izdvajaju odabrane jedinke koje se podvrgavaju genetskim operatorima. Genetske operatore dijelimo na unarne, koji stvaraju novu jedinku mijenjajući samo manji dio genetskog materijala i operatore višeg reda, koji stvaraju novu jedinku kombinirajući osobine nekoliko jedinki. Skupinu nad kojom provodimo unarne operatore nazivamo mutacijska grupa dok skupinu nad kojom provodimo operatore višeg reda grupom križanja. Nakon nekog broja izvršenih generacija čitav postupak se zaustavlja kada se zadovolji uvjet zaustavljanja. Najbolji član trenutne populacije predstavlja rješenje koje bi trebalo biti sasvim blizu optimuma.
2.1 Struktura jednostavnog genetskog algoritma
Na slici 2.1 prikazana je struktura jednostavnog genetskog algoritma. Nakon inicijalizacije algoritma, koji se sastoji od kreiranja početne populacije i postavljanja parametara algoritma, slijedi proces koji se ponavlja sve dok ne istekne vrijeme predviđeno za obavljanje algoritma ili se zadovolji jedan od uvjeta zaustavljanja. Proces koji se ponavlja sastoji se od selekcije nove generacije iz prijašnje te primjene genetskih operatora, prvo križanja pa zatim mutacije. Tijekom selekcije loše jedinke odumiru, a bolje opstaju te se u sljedećem koraku razmnožavaju. Križanjem se svojstva prenose s roditelja na djecu dok se mutacijom mijenjaju svojstva jedinke slučajnom promjenom gena. Takvim se postupkom iz generacije u generaciju postiže sve veća i veća prosječna dobrota populacije.
Rješavanju specifičnog problema pomoću genetskog algoritma moguće je pristupiti na dva načina. Možemo problem prilagoditi genetskom algoritmu ili genetski algoritam prilagoditi problemu. Prilagođavanje genetskog algoritma danom problemu vrlo je složen proces koji zahtjeva dosta rada na prilagođavanju koji je ponekad ravan problemu koji se želi riješiti. Za vrlo veliki broj takvih slučajeva su razvijeni naročiti specijalizirani genetski algoritmi, koji se tada obično nazivaju evolucijskim programima. Tada se postiže veliko povećanje djelotvornosti i takvi proizvodi imaju veliku korisnost u primjeni. Općenito kompromis se postiže pravljenjem evolucijskog programa koji će se moći primijeniti na čitavu klasu problema. S druge strane, ako se odlučimo prilagoditi problem danom genetskom algoritmu nalazimo na drugu probleme. Moguća rješenja najčešće se prikazuju kao niz bitova, takozvani binarni prikaz. Međutim, postoji čitav niz problema za koje je teško ili nemoguće primijeniti binarni prikaz. Za takve probleme moramo primijeniti drugačiji oblik prikaza. Zatim uobičajni genetski operatori mogu generirati brojna nemoguća rješenja za dan problem. Zbog toga se moraju definirati usko specijalizirani genetski operatori koji su primjenjivi samo za određene probleme kako bi se izbjegla nemoguća rješenja. Promjenom prikaza i genetskih operatora dobiva se problemu prilagođeni genetski algoritam koji se naziva evolucijski program.
2.1 Prikaz ili predstavljanje rješenja
Svi podaci koji obilježavaju jedinku zapisani su u jednom kromosomu. Jedinka, odnosno kromosom predstavlja jedno od rješenja problema. Najjednostavniji način spremanja podataka u kromosomu je u obliku niza bitova. Ovakav prikaz podataka naziva se binarni prikaz. Međutim različiti problemi mogu zahtijevati različite strukture podataka. Tako jedan kromosom može biti i realan broj pa i polje brojeva ukoliko je problem višedimenzijski. Općenito, kromosom može biti bilo kakva struktura podataka koja opisuje svojstva jedne jedinka. Za genetski algoritam značajno je da kromosom predstavlja moguće rješenje zadanog problema. Zbog toga genetski operatori koji su definirani za određenu strukturu podatak ne smiju stvarati jedinke koje predstavljaju nemoguća rješenja problema. Time se naime, znatno umanjuje učinkovitost genetskog algoritma.
U praksi se je pokazalo da binarni prikaz daje najbolje rezultate u većini primjera gdje se on može iskoristiti. Tako je i većina teorije vezane uz genetske algoritme vezana upravo uz binarni prikaz. Kromosom kao binarni vektor predstavlja kodiranu vrijednost xϵ[dg,gg]. Dužina n binarnog broja označava broj bitova, odnosno broj jedinica ili nula u jednom kromosomu. U takav vektor moguće je zapisati 2n različitih kombinacija odnosno brojeve u rasponu od 0 do 2n-1. Binarni vektor v(0) = [00...0] predstavlja vrijednost x=dg, a vektor v(2n-1) = [11...1] predstavlja vrijednost x=gg.
Općenito vrijednost binarnog broja zadanog kao binarni vektor oblika v(b) = [Bn-1Bn-2…B1B0] gdje je Bi = 1 ili 0, računamo:
b = Bi*2i
Ekvivalentan realan broj uz granice xϵ[dg,gg] je:
x = dg + b/(2n - 1) * (gg - dg)
Proces pretvaranja binarnog broja u potencijalno rješenje naziva se dekodiranje. Potencijalno rješenje poprima bilo koji realan broj u intervalu [dg,gg] a postupak njegovog izračunavanja dan je formulom iznad.
Prikaz Grayevim kodom
Binarno kodiranje prikladno je za implementaciju zbog svoje velike jednostavnosti. Međutim, jedan veliki nedostatak binarnog kodiranja je velika moguća udaljenost između dva susjedna rješenja. Uzmimo na primjer binarne brojeve 25510 = 0111111112 i 25610 = 1000000002. Iako su brojevi susjedni oni se razlikuju u svih 9 bitova. Broj bitova u kom se dva binarna broja razlikuju naziva se Hammingova udaljenost. Problem je posebno naglašen kad je jedan od ovakvih brojeva pronađeno rješenje, a optimum se postiže za drugi broj. Kako bi se ispratio ovaj nedostatak, za kodiranje brojeva se koristi i Greyev kod.
Susjedni brojevi u Greyevom kodu razlikuju se u samo jednom bitu. Dakle, Hammingonova udaljenost između susjednih riječi u kodu je uvijek 1. Binarni broj b=bmbm_1...b2b1 pretvara se u Greyev kod g=gmgm_1...g2g1 sljedećim algoritmom.
gm = bm za k=m-1 do 1{ gk = bk+1 XOR bk }
Ovako generiran Greyev kod naziva se binarno reflektiran Greyev kod te se često implicitno podrazumijeva kad se govori o Greyevom kodu. Naziv reflektiran potječe od jednog od mogućih načina generacije koda.
2.2 Inicijalizacija i uvjet završetka evolucijskog procesa
Krenimo od početka. Kako generirati početnu populaciju jedinki? Jedno od mogućih rješenja je početnu populaciju odabrati uniformno. Sve jedinke bi u početku bile isti pa takav genetski algoritam ne bi bio učinkovit zbog čega se taj postupak ne preporučuje. Generiranje početne populacije slučajnim odabirom iz domene rješenja je implementacijski jednostavno a osigurava početnu raznolikost. Moguće je i usađivanje početnog rješenja, koje je dobiveno nekom drugom optimizacijskom metodom, kao dio početne populacije.
Veličina populacije potencijalnih rješenja predstavljena je s veličinom VEL_POP(t), gdje je t vrijeme ili redni broj generacije. Međutim, u praksi se obično uzima da je VEL_POP(t) = konst = VEL_POP, odnosno veličina populacije se ne mijenja tijekom evolucijskog procesa. Vrijednost VEL_POP je parametar algoritma.
Jedinku algoritma najjednostavnije je predstaviti binarnim vektorom duljine n. Proces inicijalizacije, odnosno generiranje početne populacije P(0), tada je vrlo jednostavan. Ako smo se odlučili za generiranje početne populacije slučajnim odabirom, generira se VEL_POP slučajnih brojeva u intervalu [0, 2n-1], tj. VEL_POP binarnih vektora dužine n bitova. Kao što je već spomenuto, početna populacija može biti uniformna te se u nju mogu dodati neka rješenja dobivena nekom drugom metodom.
Uvjet završetka evolucijskog procesa je najčešće unaprijed zadan broj iteracija. Budući da je vrijeme izvođenja pojedine iteracije približno konstantno, time je unaprijed zadano i trajanje optimiranja. Procesi selekcije, križanja i mutacije ponavljat će se sve do završetka optimiranja.
Za zadani optimizacijski problem najveću poteškoću predstavlja definiranje funkcije dobrote, koja treba vjerno odražavati problem koji se rješava. Naime, funkcija dobrote je ključ za proces selekcije. Što je dobrota jedinke veća, veća je vjerojatnost preživljavanja i križanja jedinke. U literaturi se funkcija dobrote naziva još fitness funkcija, funkcija sposobnosti, funkcija cilja ili eval funkcija. Najjednostavnija interpretacija funkcije dobrote je funkcija f koju optimiziramo:
dobrota(v) = f(x)
gdje binarni vektor v predstavlja realan broj unutar granica x ∈ [dg,gg]. U praksi se je pokazalo da se ova jednostavna funkcija može primijeniti samo uz neka ograničenja nad f(x) što nam naravno ne odgovara. Stoga postoji više načina definiranja funkcije dobrote.
Dobrota cijele populacije ogleda se u ukupnoj dobroti populacije D te prosječnoj dobroti populacije.
“Dobar” genetski algoritam generira, iz generacije u generaciju, populaciju čija je ukupna dobrota i prosječna dobrota sve bolja i bolja.
Selekcija je postupak izdvajanja jedinki iz stare populacije koje će sudjelovati u sljedećem koraku reprodukcije. Genetski materijal izabranih jedinki biti će prenesen, izvorno ili u djelomično izmijenjenom obliku, u sljedeću generaciju jedinki. Budući da je svrha genetskog algoritma optimizacija danog problema, selekcija pokušava očuvati i prenijeti dobra odnosno tražena svojstva na sljedeću generaciju jedinki. Odabirom dobrih jedinki dobar genetski materijal se prenosi na sljedeću populaciju jedinki, dok loš genetski materijal odumire. U nastavku ćemo razmatrati kako odabir postupka selekcije utječe na krajnji rezultat algoritma.
Najjednostavniji primjer selekcije je sortiranje i odabir N najboljih jedinki iz populacije jedinki veličine VEL_POP uz N < VEL_POP. Ovaj primjer selekcije dovodi do prerane konvergencije genetskog algoritma. Naime, izdvajanjem samo najboljih jedinki gubi se dobar genetski materijal koji mogu sadržavati loše jedinke. Zato je potrebno osigurati i prenošenje manjeg broja loših jedinki u sljedeću generaciju.
Genetske algoritme, s obzirom na vrstu selekcije, dijelimo na generacijske i eliminacijske. Generacijski genetski algoritam koristi jednostavnu i turnirsku selekciju, dok eliminacijski genetski algoritam koristi eliminacijsku selekciju.
2.4.1 Generacijski genetski algoritam
Generacijski genetski algoritam u jednoj iteraciji raspolaže s dvije populacije. Jednu populaciju dobiva iz prethodnog koraka, a drugu generira selekcija. Kad selekcija generira novu populaciju iz prethodne, prethodna populacija se briše. Ovo nepotrebno udvostručavanje populacije problem je generacijskih genetskih algoritama, a izbjegava se primjenom eliminacijske selekcije. Krenimo međutim prvo s primjerima generacijskih algoritama.
Jednostavna selekcija
Počnimo od jednostavne selekcije. Jednostavna selekcija (eng. roulette wheel parent selection) generira novu populaciju P’(t) iz stare populacije P(t-1) koja ima jednak broj jedinki kao i stara populacija. Cilj selekcije je odabir roditelja čija je vjerojatnost selekcije proporcionalna njihovoj dobroti.
Da bi lakše objasnili jednostavnu selekciju uzmimo da je problem optimiziranja zadan funkcijom f(x). Dobrotu smo dosad definirali jednostavno kao dobrota(v) = f(x). Radi lakšeg definiranja vjerojatnosti odabira, definirajmo funkciju dobrote malo drugačije. Ako f(x) poprima negativne vrijednosti, tada se dodaje pozitivna konstanta C:
dobrota(v) = f(x) + c
Zatim izračunamo sve vrijednosti dobrota(vi) za svaku jedinku u populaciji te ukupnu dobrotu populacije. Definiramo kumulativne dobrote qk za svaki kromosom tako da vjerojatnost selekcije pk za svaki kromosom vk iznosi:
qk = dobrota(vi) , gdje je k=1,2,..,VEL_POP =
Time se dobiva da je vjerojatnost selekcije proporcionalna dobroti kromosoma.
2.2 Vjerojatnost odabira kod jednostavne selekcije
Zatim se generira slučajan realan broj r u intervalu (0,D), gdje je D ukupna dobrota populacije, i nađe se i-ti kromosom za koji vrijedi da je r unutar intervala(qi-1,qi). Odabrani kromosom se prenosi u sljedeću populaciju. Što je jedinka bolja, odnosno što je veća dobrota(vk), to je veća vjerojatnost da ona bude odabrana u svakom od VEL_POP slučajnih izvlačenja. Ovim postupkom moguće je da će se jedan kromosom pojaviti više puta u sljedećoj populaciji. Teoretski, takvim postupkom se može desiti da u sljedećoj populaciji, prije križanja i mutiranja, postoji samo jedna jedinka u VEL_POP primjeraka.
Jednostavna selekcija sadrži nekoliko nedostataka. Prvo, funkcija f(x) ne smije poprimiti negativne vrijednosti ni za koji xi, jer bi tada i dobrota(v(xi)) bila negativna. Budući da je vjerojatnost odabira jedinke proporcionalna s dobrotom, negativna vrijednost dobrote nema smisla. Ovaj problem već smo prije riješili transformacijom funkcije f(x) u g(x) = f(x) + M, gdje je M velika pozitivna konstanta npr. M = 1000. Međutim funkcija g(x) će tada za sve x biti veliki broj zbog čega će funkcija dobrote za sve kromosome tada biti približno jednaka i iznosit će otprilike 1000. Općenito, neka f(x) poprima velike vrijednosti za svaki x. To znači da će prilikom selekcije svi kromosomi imati približno jednaku vjerojatnost ponavljanja u sljedećoj populaciji. Drugim riječima, sve su jedinke podjednako dobre i loše, odnosno sve je skupa loše.
Dan problem se barem na prvi pogled rješava jednostavno. Funkciji cilja f(x) se oduzme konstanta koja je jednaka minimumu zadane funkcije u zadanom intervalu:
dobrota(v(x)) = f(x) - min{f(x)}
Iako je dano rješenje na prvi pogled jednostavno, problem pronalaska minimuma funkcije f(x) je ekvivalentan polaznom problemu - pronalasku optimuma zadane funkcije. Međutim sama ideja je u redu i potrebno ju je samo iskoristiti na drugačiji način. Nije potrebno oduzeti minimum funkcije f(x) za svaki x ∊ [dg,gg]. Dovoljno je znati najmanju vrijednost funkcije cilja za sve trenutne kromosome.
dobrota(v(x)) = f(x) - min{f(xi)}
Vrijednost min({f(xi)}) nije ista za svaku generaciju budući da je jednaka najmanjoj vrijednosti dobrote svih kromosoma u populaciji. Zbog toga je potrebno u svakom koraku iznova računati vrijednost najlošije jedinke. Međutim, to ne znači usporavanje algoritma jer se ionako provodi pretraga za najboljom jedinkom. Dakle, identifikacija najbolje i najlošije jedinke obavlja se u jednom koraku pretrage. Opisan postupak naziva se translacija ili pomak funkcije cilja (windowing). Na taj način funkcija dobrote ne može poprimiti niti negativne vrijednosti, niti se translacijom dobivaju približno iste vrijednosti.
Pojavljivanje duplikata kromosoma u sljedećim populacijama također se pokazalo kao velik nedostatak selekcije. Eksperimenti su pokazali da čak do 50% od ukupnog broja kromosoma mogu biti duplikati, što samo usporava algoritam.
Turnirska selekcija
Turnirska selekcija u svakom koraku generira novu populaciju iz stare tako da VEL_POP puta odabire s jednakom vjerojatnošću k broj jedinki iz stare populacije, zatim ih uspoređuje i najbolju jedinku kopira u bazen za reprodukciju. U sljedećem koraku nad ovim će bazenom djelovati genetski operatori. Eliminacijska turnirska selekcija također odabire nasumice k jedinki, ali umjesto odabira najbolje eliminira najlošiju i nadomješta je s djetetom dviju slučajno odabranih preživjelih jedinki.
2.4.2 Eliminacijski genetski algoritam Eliminacijska selekcija
Za razliku od jednostavne selekcije, eliminacijska selekcija ne bira dobre jedinke iz kojih generira novu populaciju, već iz stare populacije eliminira loše jedinke i reprodukcijom ih zamjenjuje novim. Postoji mogućnost da se prilikom reprodukcije pojavi dijete koje je identično nekoj već postojećoj jedinki. Kao što smo prije naveli duplikati samo usporavaju genetski algoritam pa neki autori predlažu genetski algoritam bez duplikata. Poslije svake reprodukcije valja provjeriti da li novonastala jedinka već postoji ili ne. Ako postoji, ponavlja se postupak reprodukcije sve dok se ne generira jedinka koja nema duplikata. Takva selekcija naziva se eliminacijska selekcija bez duplikata kojom se eliminira prije naveden nedostatak.
Algoritam selekcije loših kromosoma sličan je jednostavnoj selekcije uz dvije bitne razlike. Budući da biramo loše jedinke vjerojatnost odabira mora biti obrnuto proporcionalna dobroti jedinke. Čim je dobrota jedinke manja, vjerojatnost selekcije je veća. Danu funkciju nazivamo funkcija kazne. pk = kazna(vk) pk - vjerojatnost odabira; vk - jedinka, k = 1,2,...,VEL_POP kazna(vk) = max{dobrota(vi)} - dobrota(vk) max{dobrota(vi)} - maksimalna dobrota u trenutnoj populaciji Kod jednostavne selekcije jedan kromosom smo više puta mogli izabrati. Ovdje to naravno ne možemo, jednom odabrani kromosom za eliminaciju se više ne može odabrati.
Tijekom svake selekcije i mutacije javlja opasnost gubljenja najbolje jedinke u populaciji. Međutim, korisno je osigurati da najbolja jedinka u novoj populaciji u najgorem slučaju bude barem jednaka kao u prošloj populaciji, ako ne i bolja. Stoga se javlja potreba zaštite najbolje jedinke od bilo kakve izmjene ili eliminacije tijekom evolucijskog procesa. Takav mehanizam se naziva elitizam. Genetski algoritam s ugrađenim elitizmom iz generacije u generaciju asimptotski teži ka globalnom optimumu.
Reprodukcija je razmnožavanje jedinki s pomoću genetskog operatora križanja ali tijekom reprodukcije dolazi i do slučajnih promjena nekih gena ili mutacije te zamjene gena ili inverzije. U svakom procesu reprodukcije sudjeluju jedinke koje su preživjele proces selekcije.
Križanje ili crossover je binarni operator koji djeluje nad dvije jedinke koje nazivamo roditelji. Križanjem nastaje jedna ili dvije nove jedinke koje se nazivaju djeca. Najvažnija karakteristika križanja je da djeca nasljeđuju svojstva svojih roditelja. Tako ako su roditelji dobri i djeca će najvjerojatnije biti dobra, ako ne i bolja od roditelja.
Kao što smo prije rekli svi podaci koji obilježavaju jednu jedinku zapisani su u jednom kromosomu. Kromosom je niz bitova duljine n. Križanje je definirano proizvoljnim brojem prekidnih točaka koje dijele kromosom na više dijelova. Svaki dio se zatim promatra odvojeno. Na slici 2.3 možemo vidjeti primjer križanja s jednom točkom prekida.
Slika 2.3 Križanje s jednom točkom prekida
Uniformno križanje je križanje s n-1 prekidnih točaka. Tada se pri križanju svaki bit kromosoma promatra odvojeno. Vjerojatnost da dijete naslijedi jedan bit jednog roditelja je 0.5, jednaka za oba roditelja. Ako se ta vjerojatnost razlikuje za pojedine gene tada se takvo uniformno križanje naziva p-uniformno križanje. Na primjer ako je p = 0.3 tada je vjerojatnost odabira jednog bita prvog roditelja 30%, a odabira jednog bita drugog roditelja 70%. Ako se vjerojatnost nasljeđivanja razlikuje za pojedine gene, tada se zadaje maska koja definira vjerojatnost za svaki gen posebno.
Uniformno križanje se može izvesti na više načina. Najlakše i najjednostavnije je uniformno križanje implementirati kao logičku operaciju. Potrebno je izdvojiti sve bitove koji su jednaki i prepisati ih, a ostale postaviti na 0. To se postiže logičkom operacijom I. Za sljedeći dio potreban nam je R kromosom dobiven slučajnim procesom. Pomoću njega slučajnim izborom postavljamo one bitove djeteta koji se razlikuju kod roditelja operacijom R I (A XILI B). Logičkom operacijom ILI spojimo dva dobivena dijela u novi kromosom djeteta.
DIJETE = AB + R(A⊕B)
DIJETE = AB + RA + RB
Broj točaka prekida odabire se ovisno o veličini populacije. Manji broj točaka očuvava shemu odnosno djeca zadržavaju veću sličnost s roditeljima. Međutim manjim brojem točaka prekida ograničava se prostor pretraživanja algoritma zbog čega se takvo križanje koristi pri velikim populacijama koje već imaju veliku raznolikost shema. S druge strane, uniformno križanje pretražuje velik prostor pa se stoga koristi pri manjim populacijama.
Pokazalo se korisnim provjeriti jesu li roditelji jednaki prije križanja. Ako jesu nema smisla provoditi križanje. Umjesto da se mehanizam otklanjanja duplikata implementira posebno, može se izvesti u sklopu križanja. Dakle, ako su roditelji jednaki, mutira se jedan od roditelja a dijete se dobiva slučajnim odabirom kromosoma.
Drugi operator karakterističan za genetski algoritam je mutacija. Slučajna promjena jednog ili više gena. Mutacija je unarni operator jer djeluje nad jednom jedinkom, a njezin rezultat je izmijenjena jedinka.
Parametar koji određuje vjerojatnost mutacije pm jednog bita je vjerojatnost promjene svakog pojedinog bita jedinke. Ako vjerojatnost mutacije teži k jedinici, tada se algoritam pretvara u algoritam slučajne pretrage prostora rješenja. S druge strane, ako vjerojatnost mutacije teži k nuli, postupak će najvjerojatnije već u početku procesa optimiranja stati u nekom lokalom optimumu.
Jednostavna mutacija svaki bit kromosoma mijenja s jednakom vjerojatnošću pm.
Potpuna mutacija sličnim postupkom odabire kromosom, a ne gen za mutaciju, kom se zatim ispremiješaju svi bitovi. Potpuna mutacija je specijalni oblik miješajuće mutacije čija je prva granica početak kromosoma, a druga granica kraj kromosoma. Miješajuća mutacija je vrsta mutacije koja slučajnim postupkom odabire kromosom za mutaciju te prvu i drugu granicu promjene i tada ili izmiješa gene ili ih slučajno generira (potpuna miješajuća mutacija) ili ih invertira (invertirajuća miješajuća mutacija).
Slika 2.4 Različite vrste mutacija
Evolucijski programi najčešće ne koriste binarni prikaz. U tom slučaju umjesto parametra pm koristimo vjerojatnost mutacije kromosoma pM.
Mutacijom se pretražuje prostor rješenja i upravo je mutacija mehanizam za izbjegavanje lokalnih minimuma. Ako populacija završi u nekom od lokalnih optimuma, jedino se slučajnim pretraživanjem prostora rješenja pronalazi bolje rješenje. Dovoljno je da samo jedna jedinka koja nastaje mutacijom bude bolja od ostalih pa da se u nekoliko sljedećih generacije sve jedinke presele u prostor gdje se nalazi bolje rješenje. Samo križanjem se to ne bi moglo ostvariti. Uloga mutacije je i obnavljanje izgubljenog genetskog materijala. Dogodi li se, na primjer, da sve jedinke imaju isti gen na određenom mjestu u kromosomu, samo križanjem se taj gen nikad ne bi mogao promijeniti.
Svaki genetski algoritam sadrži nekoliko parametara koji određuju karakteristike optimiziranja. Neke od njih kao veličina populacije, broj generacije prije zaustavljanja algoritma i vjerojatnost mutacije, smo već spomenuli. Isto tako smo vidjeli da različiti tipovi selekcije zahtijevaju različiti parametre. Dok generacijski genetski algoritam zahtjeva vjerojatnost križanja, eliminacijski genetski algoritma zahtjeva broj jedinki za eliminaciju. Uobičajne vrijednosti parametara za algoritme s “malim” i “velikim” brojem jedinki u jednoj populaciji dane su u tablici.
Slika 2.5 Popis parametara genetskog algoritma
Za različite vrijednosti parametara algoritma, algoritam daje različite rezultate. Brže ili sporije dolazi do boljeg ili lošijeg rješenja. Očigledno je da se sad pojavljuje novi problem postavljanja djelotvornih vrijednosti parametara. Optimiranje parametara genetskog algoritma je složen postupak i zahtjeva izvođenje velikog broja eksperimenata. Pokazalo se daje dovoljno optimizirati sljedeće parametre: veličina populacije, vjerojatnost mutacije, vjerojatnost križanja i broj jedinki za eliminaciju. Kako bi se riješio ovaj problem optimiziranja moguće je definirati takozvani genetski algoritam nad genetskim algoritmom. Grefenstette je predložio da za izbor vjerojatnosti križanja i mutacije upotrebljava posebni genetski algoritam čije bi izvršavanje teklo paralelno s glavnim genetskim algoritmom koji radi na rješavanju problema. Jedinka predstavlja skup vrijednosti parametara algoritma.
Tak je ukupno vrijeme trajanja optimiranja uz pomoć genetskog algoritma, a S je srednje odstupanje od točnog rješenja. a i b su parametri koji se zadaju i koji će ovisiti o teme da li je potrebno da algoritam radi brže ili da daje bolje rezultate. Veliki nedostatak tog pristupa je nezgrapna provedba na računalu.
3. Pregled ostalih evolucijskih algoritama
3.1 Genetsko programiranje
Sljedeći u nizu evolucijskih algoritama je genetsko programiranje (GP). Ono nasljeđuje većinu karakteristika genetskog algoritma međutim svoju optimizaciju ne provodi nad jedinkama predstavljenim nekom strukturom podataka, već nad cijelim računalnim programima. Svako rješenje genetskog programiranja je jedan računalni program koji bolje ili lošije rješava zadani problem.
Uzmimo za primjer problema mrav koji se kreće po 2D polju i skuplja hranu. Cilj programa je skupiti čim više hrane koja je nasumice razbacana po polju, uz jednu pretpostavku. Mrav vidi samo polje neposredno ispred sebe. Rješenje ovog problema je program koji upravlja mravom. Međutim, pronaći program koji to obavlja najbolje je vrlo teško. Pokušajmo ovaj problem riješiti pomoću genetskog programiranja.
Jedinku genetskog programiranja je najjednostavnije prikazati pomoću stabla. Definirajmo moguće akcije u našem primjeru. Mov: pomak naprijed, lef: rotacija 90° u lijevo, rig: rotacija 90° u desni. Početnu jedinku mogli bi definirati ovako: Slika 3.1 Struktura osnovnog stabla Ako je hrana ispred mrava program izvodi lijevo podstablo, inače izvodi desno. PR2 izvodi sva podstabla s lijeva na desno, odnosno simulira niz naredbi. Ako je hrana ispred mrava, on će se pomaknuti naprijed da je pokupi i zatim okrenuti jednom u lijevo. Ako hrana nije ispred mrava on će se okrenuti u desno. Brzom provjerom programa pronalazimo nekoliko nedostataka, na primjer ako mrav oko sebe nema hrane on će se beskonačno vrtjeti u desno.
Međutim nema veze, jer smo napravili ono što smo htjeli. Generirali smo početnu populaciju. Sada je dovoljno “osloboditi” procese mutacije, križanja i selekcije koji će samostalno optimirati polazni program.
Dakle, genetsko programiranje je evolucijski algoritam koji oponašanjem evolucije optimizira programska rješenja zadanih problema. Tijek obavljanja optimiranja genetskog programiranja prikazana je na slici 3.2.
Vidimo da je struktura genetskog programiranja vrlo slična genetskom algoritmu. Razlog tome je što je genetsko programiranje zapravo samo specijalizirani oblik genetskog algoritma koji je našao široku uporabu u rješavanju različitih problema.
Slika 3.2: Tijek genetskog programiranja
Evolucijske strategije (ES) su sljedeća tehnika optimizacije iz područja evolucijskih algoritama koju ovdje obrađujemo. Najveća razlika evolucijske strategije, u odnosu na ostale evolucijske algoritme, je u načinu kreiranja nove generacije. Dok većina evolucijskih algoritama podjednako upotrebljava križanje i mutaciju, evolucijske strategije prednost daju mutaciji dok se križanje koristi samo u pojedinim slučajevima. Tako se kod evolucijske strategije potomak stvara direktno mutacijom roditelja. Selekcija se kao i kod većine evolucijskih algoritama bazira na dobroti jedinke.
Razlog intenzivne primjene mutacije kod evolucijske strategije počiva u karakteristikama problema koji se tom tehnikom rješavaju. Pogledajmo problem trgovačkog putnika. Problem se očituje u traženju najkraćeg puta koji putnik mora prijeći tako da, krenuvši od početnog grada, obiđe sve zadane gradove točno jednom i ponovno se vrati u početni grad. Problem se matematički zadaje matricom n x n gdje Cij poprima vrijednosti udaljenosti između grada i i grada j.
Kroz godine ovaj problem je okupirao umove mnogih istraživatelja zbog mnogih razloga. Problem trgovačkog putnika je vrlo lako za opisati, ali predstavlja veliki problem prilikom rješavanja. Nije poznat niti jedan vremenski polinomni algoritam kojim se on može riješiti. Nedostatak tih polinomnih algoritama je karakteristika klase NP - teških algoritama. Drugo, problem je široko primjenjiv na različite probleme usmjeravanja i raspoređivanja. Na kraju, kako je poznato mnogo informacija o ovom problemu, postao je neka vrsta testnog problema za sve nove kombinatoričke metode optimizacije.
Važno je uvidjeti da križanje dobrih jedinki populacije ne dovodi do napretka algoritma. Kombinacija dobrih jedinki najčešće rezultira lošom jedinkom udaljavajući algoritam od traženog optimuma. Međutim mutacija samo pojedinog dijela jedinke često uzrokuje poboljšanje jedinke i napredovanje cijele populacije. Pokazalo se korisnim zato, kod ovakvih tipova problema gotovo u potpunosti eliminirati križanje i zadržati samo mutaciju.
Evolucijske strategije dijele se s obzirom na način generiranja novih potomaka i selekcije sljedeće populacije. Krenimo od najjednostavnijeg primjera.
(1+1)ES - U populaciji nad kojom se obavlja reprodukcija i selekcija sadrži samo dvije jedinke. Prva je roditelj iz koje procesom mutacije nastaje potomak. Selekcija bira bolju od te dvije koja zatim ulazi u sljedeću generaciju.
(p+1)ES - U populaciji postoji p roditelja. Međutim mutacija se odvija samo nad jednom jedinkom, a potomak koji nastaje se konstantno reproducira. Iz cijelog seta potomaka izabire se najbolja jedinka koja se ubacuje u trenutnu populaciju na mjesto jedinke koja je imala najmanji faktor dobrote.
(p+c)ES - U populaciji ponovno postoji p roditelja međutim procesom mutacije nastaje c potomaka uz uvjet da je nastalo više djece nego roditelja c>p. Prilikom procesa mutacije koristi se samo jedna jedinka iz populacije roditelja. Selekcija ravnopravno izabire p jedinki najveće dobrote iz skupa roditelja i potomaka.
(p,c)ES - Proces generacije jednak je (p+c)ES. Ponovno nastaje c potomaka uz uvjet da je c>p. Međutim, u ovom slučaju u novu generaciju ulaze isključivo potomci. Od c potomaka izabire se p najboljih jedinki koje prelaze u novu generaciju.
(c/z+p)ES - Ova strategija slična je (c+p)ES uz dodatni parametar z koji označava koliko jedinki roditelja sudjeluje u reprodukciji. Dok u (c+p)ES u procesu reprodukcije sudjeluje samo jedan roditelj, kod ovog tipa strategije taj je broj varijabilan.
(c/z,p)ES - Strategija identična (c/z+p)ES uz uvjet da se nova generacija bira isključivo iz potomaka.
(c’, p’((c, p)y)ES - Ovaj tip strategije je nešto složeniji. Prvo se iz populacije roditelja c’ kreira p’ potomaka koji se izoliraju na y generaciju. U svakoj od y generacije se zatim stvara p potomaka od kojih samo c najboljih prelazi u sljedeću generaciju. Nakon y generacija izabiru se najbolje jedinke od y izoliranih populacija koje zatim postaju roditelji nove c’ generacije potomaka.
Algoritam evolucijskih strategija gotovo je identičan genetskim algoritmima uz navedene promjene kod operatora križanja, mutacije i selekcije.
Evolucijsko programiranje dodatno naglašava uporabu mutacije potpunom eliminacijom genetskog operatora križanja. Slično kao i kod ostalih evolucijskih algoritama mutacija mijenja vrijednost pojedinih gena. Međutim kod evolucijskog programiranja definira se i intenzitet mutacije koji predstavlja “snagu”, odnosno broj gena pojedine jedinke koji se mutiraju. Intenzitet mutacije se za ovaj algoritam odvija prema gaussovoj jediničnoj normalnoj razdiobi, što znači da algoritam favorizira više manjih promjena u odnosu na nekoliko velikih.
Algoritam evolucijskog programiranja odvija se u tri koraka te je vrlo sličan genetskom algoritmu uz eliminaciju križanja:
1. Generiranje početne populacije.
2. Svaka jedinka kopira se u novu populaciju, gdje se mutira prema zadanoj distribuciji mutacije. Jačina mutacije ovisi o funkcionalnim promjenama nametnutim od strane roditelja.
3. Stare jedinke i novi potomci se evaluiraju te postupkom selekcije izdvajaju u novu generaciju jedinki.
Evolucijsko programiranje je vrlo slično evolucijskoj strategiji, te se problemi koji se njima rješavaju gotovo uopće ne razlikuju. Dok evolucijsko programiranje nove jedinke generira isključivo mutacijom, evolucijske strategije mogu i ne moraju koristiti križanje. Manje razlike postoje i kod uobičajne metode selekcije koju koriste ova dva algoritma.
Klasifikatorski sustavi (CS) su kognitivni sustavi koji imaju mogućnost spoznaje događaja iz svoje okoline i reakcije na te događaje. Povećanje kompleksnosti mnogih problemskih domena dovelo je do potrebe za rješenjima koji se mogu prilagoditi pojedinom zadatku. Tako se korištenjem evolucijskih algoritama i učenja s potkrjepljenjem modeliraju klasifikatorski sustavi koji imaju mogućnost prilagođavanja i učenja.
Klasifikatorski sustavi, uz metode evolucijskih algoritama, koriste i brojne metode drugih grana računalne znanosti. Zbog toga se neki stručnjaci protive uvrštavanju klasifikatorskih sustava među evolucijske algoritme. U ovom seminaru ih ipak obrađujemo jer koriste mnoge metode evolucijskog algoritma.
Klasifikatorske sustave dijelimo na klasifikatorske sustave koji nemaju sposobnost učenja (non-learning classifier systems, nLCS) i klasifikatorske sustave koji imaju sposobnost učenja (learning classifier systems, LCS). Opišimo prvo nLCS sustav. Kao što smo rekli, klasifikatorski sustavi nastoje prilagoditi svoje ponašanje prema okolini koja se neprestano mijenja. Da bi mogli spoznati stanje okoline potrebni su im alati koji to omogućavaju, koje kod klasifikatorskih sustava nazivamo detektori. Pomoću detektora se stanje okoline očitava i prenosi u listu poruka. Sustav zatim reagira na ulaz pomoću pravila koja odgovaraju uvjetu u listi poruka. Akcija koja je određena pravilom se zapisuje u listu poruka. U zadnjem se koraku, pomoću efektora, izvodi akcija smještena na listi poruka. Proširi li se sustav komponentom za raspodjelu nagrada primljenih od okoline i komponentom za istraživanje prostora mogućih pravila, dobivamo LCS.
LCS se uglavnom upotrebljava za rješavanje jednog od četiri tipa problema: klasifikacijski problemi, problemi učenja potkrjepljenjem, problemi aproksimacije funkcija i problemi predviđanja. Klasifikacijski problemi predstavljaju probleme čiji je cilj raspoređivanje skupine objekata u podskupine i određivanje samih pravila po kojima se objekti raspoređuju. LCS nastoji pronaći takav skup pravila po kojima se klasificiranje obavlja što preciznije. Klasifikacijski problemi tipični su za područja dubinske analize podataka. Učenje s potkrepljenjem svodi se na pronalaženje optimalne funkcije ponašanja koja je u LCS predstavljena skupom pravila. Primjer problema učenja s potkrjepljenjem možemo naći u problemu labirinta. Cilj LCS-a koji se primjenjuje na problemima aproksimacije funkcija je upravo što točnija aproksimacija funkcije skupom pravila koja se djelomično preklapaju. LCS se može primijeniti i u rješavanju gotovo svih problema predviđanja.
Evolucijski algoritmi predstavljaju jednostavan pristup vrlo složenim problemima. Korištenjem mehanizama zasnovanih na biološkoj evoluciji, kao što su križanje, mutacija i selekcija, evolucijski algoritam pretražuje velik prostor potencijalnih rješenje tražeći optimum. Za razliku od determinističkih optimizacijskih metoda, evolucijskih algoritmi ne postavljaju nikakva predviđanja na prostor rješenja što omogućuje široku primjenu i dobre rezultate u velikom broju polja kao što su strojarstvo, fizika, kemija, biologija, genetika pa i umjetnost, ekonomija i marketing.
Brojne primjene evolucijskih algoritama rezultirale su velikom raznolikošću sustava koji ih koriste. Samim time se i način implementacije razlikuje od slučaja do slučaja. FER-ov tim predvođen profesorom Domagojem Jakobovićem izgradio sustav koji podržava aplikacije svih tipova evolucijskih algoritama pod nazivom Evolutionary Computation Framework. Sustav podržava brojne algoritme optimiziranja, različite načine unosa podataka kao i mnogo složenije metode optimiranja od onih ovdje opisanih. Više informacija možete pronaći na http://gp.zemris.fer.hr/ecf.
Najveći nedostatak evolucijskih algoritama je izostanak teorijske podrške. U velikoj većini slučajeva nemoguće je unaprijed odrediti hoće li primjena evolucijskih algoritama na dan problem uroditi plodom. Zbog tog se mnoge firme odlučuju za determinističke metode optimiziranja izbjegavajući prije naveden rizik. Međutim, potencijal evolucijskih algoritama je velik te će oni nastaviti zauzimati vrlo važno mjesto u metodama optimiranja.
1) Golub, M. Genetski algoritam, prvi dio, 05.04.2007. http://www.zemris.fer.hr/~golub/ga/ga_skripta1.pdf
2) Evolucijski algoritmi http://www.zemris.fer.hr/~golub/ga/studenti/projekt2007/index.html
3) Uvod u genetsko programiranje http://www.zemris.fer.hr/~yeti/studenti/Uvod_u_genetsko_programiranje.pdf
4) Marko Pielić, Pregled evolucijskih algoritama, Seminar http://www.zemris.fer.hr/~golub/ga/studenti/seminari/2007_pielic/Pregled%20evolucijskih%20algoritama%5B2007%5DPielic_Marko.htm
5) Wikipedia, Evolucijski algoritmi http://en.wikipedia.org/wiki/Evolutionary_algorithm
6) Monika Čeri i Iva Malović, Evolucijske strategije, Projekt http://www.zemris.fer.hr/~golub/ga/studenti/projekt2007/es.html
7) Ivica Pađen, Evolucijsko Programiranje, Projekt http://www.zemris.fer.hr/~golub/ga/studenti/projekt2007/ep.html
8) Mario Lučić i Goran Radanović, Klasifikatorski Sustavi, Projekt http://www.zemris.fer.hr/~golub/ga/studenti/projekt2007/lcs.html
9) Evolutionary Computation Framework, ECF http://gp.zemris.fer.hr/ecf/