Ponukan (zabrinutim) komentarima na BOL vijestima vezanim uz temu umjetne inteligencije, odlucio sam napisati ovaj pomalo duzi tutorial da bacim malo svjetla na "misticnu" temu umjetne inteligencije. Tutorial je prvenstveno namijenjen programerima jer se bavi konkretnom implementacijom odredenog podrucja umjetne inteligencije, ali vrlo lako moze posluziti kao stivo i onima koji nisu u toj bransi jer ima dosta price "na suho" da se tako izrazim. Imajte na umu da je ovo samo djelic velikog i aktivnog podrucja umjetne inteligencije.
Krenimo s jednim naizgled jednostavnim, pomalo filozofskim pitanjem: sto je to svijest? Ovo pitanje na prvi pogled nema veze s racunalima i racunarstvom, no ako pogledamo malo dublje u tematiku dolazimo do potpuno suprotnog zakljucka. Naime, povecanjem racunalne moci danas imamo sve "pametnije" programe, algoritme, robote, drugim rijecima, imamo sve "pametniju" umjetnu inteligenciju. Probleme koji se danas postavljaju pred racunarsku znanost vise nije moguce rijesiti konvencionalnim metodama i algoritmima, rjesenje moramo traziti u drugim smjerovima. Raspoznavanje uzoraka na slici, raspoznavanje govora, kombinatorijalni problemi, izvlacenje znanja iz gomile podataka (big data), predvidanje trendova, klasifikacija i dr., pa u krajnjem slucaju i proucavanje ljudskog mozga na temelju umjetnih modela, sve su to problemi koje je nemoguce rijesiti uobicajenim algoritmima i tu se okrecemo tzv. umjetnoj inteligenciji.
Vratimo se malo na pocetno pitanje o tome sto je svijest. Na njega bas i ne mozemo odgovoriti (jos). Idemo se onda pitati jedno drugo pitanje. Da li npr. glista ima svijest? Opet, mozda malo zeznuto, ali mogli bi se sloziti da nema. No sto je sa psom? Psi su svjesni okruzenja, osjecaju bol, strah, ali recimo, ne prepoznaju se pred ogledalom. Tu je jos teze odgovoriti, pa bi se mogli sloziti da su psi do neke mjere svjesni. Svjesniji od gliste, ali ne kao covjek. Sto mozemo zakljuciti iz ovoga? Sto konkretno cini razliku? Pa, ocito je to velicina mozga. Sigurni smo da svijest ima veze s mozgom (kao i emocije npr.), ali ne i kako, a i ne znamo definirati.
Danas znamo da je glavni element za obradu u mozgu neuron. Pojednostavljeno, neuron se sastoji od dendrita, tijela neurona i aksona. Prosjecno, svaki je neuron povezan s jos 10^4 drugih neurona preko dendrita. Svaki neuron se moze "upaliti" i pritom salje elektricne impulse drugim neuronima preko svog izlaza, aksona. Drugi neuroni akumuliraju ulaze, obraduju ih pa pale ili ne pale i tako u krug. Neurona u ljudskom mozgu ima oko 100 milijardi koji su medusobno povezani s oko 10^15 veza. Iz svih ovih brojki jasno je da se obrada podataka u mozgu odvija masivno, ali MASIVNO paralelno. Dodatni argument ovome jest cinjenica da su neuroni jako spori, vrijeme paljenja im je cca 1 ms. S obzirom da covjek moze izrazito kompleksnu obradu podataka obraditi u vrlo kratkom roku (npr. mozemo prepoznati poznatu osobu sa slike za cca 0.1 s) ocito je da se obrada ne vrsi slijedno. Za usporedbu danas najdublju neuronsku mrezu ima Microsoft (koliko dugo, to cemo jos vidjeti) sa 152 sloja ako se ne varam (zanimljivost je da je 2012. ako se ne varam, najdublja mreza imala 8 slojeva). Cak i ako svaki sloj ima po 10000 neurona, to je i dalje puno manje od ljudskog mozga.
No, da li je svijest posljedica tih ogromih brojki? Vrlo vjerojatno ne. Ako bi napravili racunalo sa sirovom procesnom moci mozga, vrlo vjerojatno za posljedicu ne bi dobili svijest. Takoder, istrazivanja pokazuju da u mozgu nema posebnog mjesta (centra) za svijest, tako da smo u slijepoj ulici po tom pitanju. Ne znamo odgovor na njega, a mozda nikad niti necemo znati. Postoji vise hipoteza, da je svijest posljedica kompleksnih procesa u mozgu, da mozda samo imamo dojam svijesti, a ustvari smo samo zrtve uzroka i posljedice. Ustvari, cak ne mozemo niti reci da li su drugi oko nas svjesni. Sto se nas tice, moze biti da svi samo reagiraju na podrazaje. S tim na umu, ako bi i stvorili svjesnog robota, ne bi mogli ni reci da li je svjestan ili samo reagira na podrazaje pa izgleda da je svjestan. Ovo je samo povrsina ovo pitanja, koga zanima vise moze traziti po internetu.
Jos je jedna stvar kod umjetne inteligencije. Dosta cesto razlikujemo tzv. "jaku" i "slabu" (ili primjenjenu) umjetnu inteligenciju. Jaka umjetna inteligencija je ustvari opca umjetna inteligencija koja bi imala sve znacajke ljudske inteligencije. Stvaranje ovakog tipa inteligencije zahtijeva jos nepoznata i fundamentalno nepredvidiva znanstvena otkrica te duboko znanstveno poznavanje i shvacanje svijesti. A to jos nemamo i dok ti uvjeti ne budu zadovoljeni, tesko da ce se cak u ovom stoljecu nesto na ovom polju postici. Gdje smo trenutno kod opce umjetne inteligencije? U principu, jaz izmedu danasnjeg racunarstva i opce umjetne inteligencije istovjetne ljudskoj je otprilike kao i jaz izmedu danasnjeg svemirskog leta i prakticnog svemirskog leta nadsvjetlosnom brzinom. Slaba umjetna inteligencija je ono cime se ustvari danas najvise bavimo i na sto cu se ja kroz ovaj tutorial (a mozda i jos koji) osvrnuti, tocnije, osvrnut cu se samo na dijelic jer je to podrucje stvarno ogromno. Sad se postavlja pitanje cemu ovoliki uvod? Pa, kao prvo, volim puno pricati. :P Kao drugo, ovime sam se htio osvrnuti na ceste komentare u BOL vijestima o umjetnoj inteligenciji, a koji redovito glase "skynet", "we're doomed", "propali smo", "naj* smo" i sl. Ne, nismo, moramo jos puno zgancov pojesti da bismo bili u stanju nesto takvo napraviti. S druge strane, tko zna, mozda se potrefe neki od potrebnih (navedenih) uvjeta i nesto napravimo, ali kako to obicno biva, malo je vjerojatno. Einstein je prije 100 godina predstavio teoriju relativnosti, pa i dan danas jos ne putujemo kroz crvotocine ili koristimo energiju crne rupe, ili sto vec. Tako da, jos smo jako daleko od "skyneta". Ubuduce kad govorim o umjetnoj inteligenciji, mislim upravo na tu primjenjenu umjetnu inteligenciju.
Sad nakon malo poduzeg uvoda, krenimo na konkretnije stvari. Za pocetak cemo obraditi jedno od podrucja unutar umjetne inteligencije za koje smatram da ga je relativno lagano shvatiti (i prakticki nema matematike sto se ne moze reci za neka druga podrucja koja se temelje na dosta netrivijalnoj matematici) i nakon sto shvatite nacin rada vrlo lako mozete sami implementirati slicne stvari. Rijec je o tzv. evolucijskom racunarstvu, tj. evolucijskom racunanju. Sto to konkretno znaci? Pa, nije bas lagano definirati taj pojam, ali mozemo reci da je to podrucje racunarske znanosti koje proucava algoritme koji simuliraju evolucijski razvoj vrsta, ponasanje jedinke u drustvu ili pak simuliraju neke aspekte umjetnog zivota. Svi ti algoritmi su tzv. populacijski algoritmi (jer operiraju nad nekom populacijom) iako se moze dogoditi da populacija padne na samo jednu jedinku. Uz to, velik dio ovih algoritama inspiraciju vuce iz prirode i procesa u prirodi, no postoje i oni koji nemaju nikakvu motivaciju iz prirode. Razvoj ovog podrucja je zapoceo negdje sezdesetih godina proslog stoljeca. Onako kako danas znamo to podrucje, ono se dijeli na ugrubo tri dijela: evolucijske algoritme (evolucijske strategije, evolucijsko programiranje, genetsko programiranje, genetske algoritme...), algoritme rojeva (algoritam roja cestica, algoritam kolonije mrava, algoritam kolonije pcela, umjetni imunoloski sustav...) te ostale algoritme (algoritam diferencijske evolucije...). Konkretno, u ovom tutorialu obradit cemo jednog od najpoznatijih predstavnika evolucijskih algoritama, genetski algoritam.
Sto je genetski algoritam? GA je heuristicka metoda (vrlo vazno, sve u umjetnoj se vrti oko nekakve heuristike) slucajnog i usmjerenog pretrazivanja prostora rjesenja koja imitira prirodni evolucijski proces. GA (kao i svi algoritmi evolucijskog racunanja) sluzi za rjesavanje tezih optimizacijskih problema za koje ne postoji egzaktna matematicka metoda rjesavanja ili NP-teskih problema. Sad bude jasno zasto sam za pocetak odabrao GA. Nacin rada GA moze se sazeti prakticki u jednu recenicu: imamo pocetnu populaciju, iz nje se odabiru bolje jedinke, one sudjeluju u reprodukciji i tako ukrug dok se ne zadovolji uvjet zavrsetka procesa. Pa ovo je zaista lagano! Pa i jest, ali postoji kvaka. S obzirom da je u svojoj sustini GA ovako "lagan", ono sto je tesko jest konkretno definirati te korake. Kako prikazati populaciju? Kako generirati pocetnu populaciju? Kako evaluirati populaciju? Kako izabrati jedinke iz populacije? Kako ih krizati? Sve ovo treba definirati za svaki problem posebno i upravo taj nedostatak univerzalne i konkretne kuharice GA cini u odredenoj mjeri teskim.
Stoga, u sljedecim retcima osvrnut cemo se na sljedeci problem te na njemu objasniti konkretne korake u nadi da steknete odredeni osjecaj za GA. Problem je ovaj: imamo neku crnu kutiju koja za odredeni ulaz generira nekakav izlaz. Jedino sto znamo je priblizan oblik prijenosne funkcije. Nas ce zadatak biti dokuciti pravi oblik prijenosne funkcije, a u tome ce nam pomoci GA. No, prvo idemo definirati pseudokod genetskog algoritma. Konkretno, postoje dva tipa GA: eliminacijski i generacijski. Sto to znaci i koja je razlika izmedu njih? Kao sto smo vec rekli GA radi nad nekom populacijom iz koje se izabiru jedinke za daljnju reprodukciju. Uvjet eliminacijskog genetskog algoritma jest da se uvijek radi nad jednom populacijom, drugim rijecima, iz populacije se uzmu potencijalni roditelji te se krizaju cime se stvara novo dijete koje se ubacuje u populaciju. Medutim, da bi se dijete moglo ubaciti u populaciju, neka jedinka se mora eliminirati iz populacije (da se odrzi konstantan broj jedinki unutar populacije). Na taj nacin u populaciji postoje i roditelji i djeca. To je eliminacijski genetski algoritam. Generacijski GA iz koraka u korak iz populacije roditelja stvara novu populaciju djece (dakle, ovo je vazno, sad imamo dvije populacije u memoriji), a nakon toga stara populacija odumire i ostaje samo nova te se proces ponavlja. Iz mog iskustva, eliminacijski GA je nesto brzi i trosi manje memorije jer operira nad samo jednom populacijom, no sporije konvergira k rjesenju (u vise generacija). S druge strane generacijski je nesto sporiji i trosi vise memorije (zbog dvije populacije u isto vrijeme), ali nesto brze konvergira k rjesenju (u manje generacija). Idemo sada vidjeti konkretan pseudokod oba tipa GA.
Pseudokod eliminacijskog GA:
populacija = stvori_pocetnu_populaciju(velicina)
evaluiraj(populacija)
ponavljaj_dok_nije_zadovoljen_uvjet_zavrsetka:
odaberi roditelj1 i roditelj2 iz populacija
dijete = krizaj(roditelj1, roditelj2)
mutiraj dijete
evaluiraj dijete
odaberi jedinku iz populacije -> ako losija zamijeni s djetetom
kraj
Kao sto vidimo, u principu vrlo jednostavno.
Generacijski GA:
populacija = stvori_pocetnu_populaciju(velicina)
evaluiraj(populacija)
ponavljaj_dok_nije_zadovoljen_uvjet_zavrsetka:
nova_populacija = 0 // ova razlika je bitna!
ponavljaj_dok_je velicina(nova_populacija) < populacija:
odaberi roditelj1 i roditelj2 iz populacija
dijete = krizaj(roditelj1, roditelj2)
mutiraj dijete
dodaj_u(nova_populacija, dijete)
kraj
populacija = nova_populacija
kraj
Mozemo vidjeti, ovdje baratamo s dvije populacije.
Postoji jos jedna vrsta generacijskog GA koja podrzava tzv. elitizam (zadrzavanje najbolje/ih jedinke/i u generaciji):
populacija = stvori_pocetnu_populaciju(velicina)
evaluiraj(populacija)
ponavljaj_dok_nije_zadovoljen_uvjet_zavrsetka:
nova_populacija = 0
ubaci_u_nova_populacija(dvije_najbolje_jedinke_iz_populacija) // elitizam!
ponavljaj_dok_je velicina(nova_populacija) < populacija:
odaberi roditelj1 i roditelj2 iz populacija
dijete = krizaj(roditelj1, roditelj2)
mutiraj dijete
dodaj_u(nova_populacija, dijete)
kraj
populacija = nova_populacija
kraj
Ovdje dakle vidimo da imamo jedan dodatan korak koji u ovom slucaju uzima dvije najbolje jedinke i cuva njihov genetski materijal u sljedecoj generaciji. To se naziva elitizam.
Sad prakticki znamo kako napraviti GA, trebamo jos dodatno pojasniti neke pojmove koji su se do sad pojavili. Krenimo redom:
Jedinka ili kromosom - jedinka je neko konkretno rjesenje.
Populacija - populacija je (ocito) skup jedinki.
Gen - gen je dio nekog kromosoma, tj. dio nekog rjesenja, ako sad nije jasno, bude kad krenemo raditi GA
Nad navedenim pojmovima djeluju nekakvi genetski operatori koje smo sreli u pseudokodu:
Operator selekcije - ovaj operator bira jedinke iz populacije
Operator krizanja - ovaj operator kriza izabrane jedinke i stvara novu koja nosi karakteristike roditelja
Operator mutacije - ovaj operator je izrazito bitan jer mutira pojedinu jedinku te tako omogucava genetsku raznolikost, drugim rijecima, sprijecava da zapnemo u lokalnim optimumima (mi se nadamo globalnom).
Jos moramo obratiti paznju na par stvari. Prvo, prikaz rjesenja, tj. kako cemo definirati prikaz jedinke (kromosoma) i gena. Drugo, na koji nacin evaluirati jedinku, tj. kako prikazati i izracunati njezinu dobrotu (engl. fitness). Sad vec imamo osjecaj da iako je u principu GA lagan, nije bas trivijalan kad se krene u samu implementaciju.
Prikaz jedinke:
Jedinku se moze prikazati prakticki na proizvoljan nacin i to ovisi o konkretnom problemu. Ovdje cemo razmotriti samo prikaz brojevima s pomicnim zarezom, ali spomenut cemo i binarni prikaz. Dakle, prikaz rjesenja brojevima s pomicnim zarezom je u principu najjednostavniji i najprirodniji nacin prikaza rjesenja. Npr., ako trazimo minimum funkcije dviju varijabli, tocku T(x, y) za koju je iznos funkcije najmanji, tj. f(z) = (x, y) gdje f(z) moze biti bilo kakvog oblika, recimo f(z) = x^2 + y, jedna jedinka, tj. kromosom izgledao bi ovako:
jedinka = [0.4, 2.3]
Ja sam to ovdje napisao kao Python listu, ali to moze biti i obicno polje u C++-u/Javi/C#-u, svejedno. Dakle, vrlo jednostavno, jedan gen je varijabla x, a drugi gen je varijabla y.
Binarni prikaz je takoder jednostavan za razumijeti, ali zahtjeva dodatno kodiranje/dekodiranje kromosoma. Tu opet imamo proizvoljan nacin kodiranja/dekodiranja pojedinih gena. Npr., neka pojedini gen moze poprimiti vrijednost od 0 do 15 i neka jedinka ima istu strukturu kao i ova maloprije. Jedno moguce rjesenje neka bude 3 i 10. Tada ce jedinka izgledati ovako:
jedinka = 00111010
Ovdje sam pretpostavio da smo brojeve 0 do 15 kodirali direktno u njihove ekvivalente u binarnom sustavu tako da je 3 = 0011, a 10 = 1010. Rjesenja smo mogli kodirati i Grayevim kodom. Ili na vec neki drugi nacin, samo je bitno da je konzistentan i da znamo dekodirati vrijednosti. Sto je bolje od ovoga dvoje? Grayev kod ili prirodni binarni kod? Opet, ovisi o konkretnom problemu, implementaciji operatora, parametrima, prakticki o svemu. Tu lezi ta tezina implementacije GA. Imate nevjerojatno puno varijacija i izbora, a sve je meduovisno i nema najboljeg.
Kako bi u prethodnom primjeru kodirali rjesenje koje je prikazano brojevima s pomicnim zarezom u rjesenje koje je prikazano binarno? Tu postoje neke formule koje rade pretvorbu, tj. linearnu interpolaciju (odnosno uniformno uzorkovanje intervala). Necu ih izvoditi vec cu samo dati gotove formule. Zelimo preciznost na odredenu decimalu i trebamo izracunati koliko nam je potrebno bitova za prikaz nekog broja tom preciznoscu. To se racuna sljedecom formulom:
M = ld(((x_max - x_min) / preciznost) + 1)
gdje je ld dualni logaritam (logaritam po bazi 2), x_max i x_min je raspon intervala, a preciznost je zeljena preciznost. Npr., zelimo preciznost 10^-1 iz intervala [-50, 50]. Po formuli slijedi:
M = ld(((50 - (-50)) / 0.1) + 1) = ld(10^3 + 1) ~ 9.967
sto znaci da nam je za prikaz jednog broja iz intervala [-50, 50] treba 10 bitova. Iz toga slijedi da bi jedinka sa zadanom preciznoscu imala ukupno 20 bitova (jer se sastoji od dva broja s pomicnim zarezom).
Kako izracunati te brojeve? To nam kaze sljedeca formula:
x = (m / (2^M - 1)) * (x_max - x_min) + x_min
gdje je m = {0, 1, ..., 2^M - 1}. Drugim rijecima nulti x je upravo x_min jer cijeli umnozak s nulom postaje nula i ostaje jedino x_min, a (2^M - 1)-i x je upravo x_max jer se prva zagrada krati i ostaje x_max - x_min + x_min sto je x_max. Evo primjer: pretpostavimo da brojeve kodiramo s 4 bita, to je jako mala preciznost. To znaci da na raspolaganju imamo samo 16 brojeva uniformno rasporedenih po cijelom intervalu [-50, 50]. Dva otpadaju na granice i jos 14 ih je uniformno rasporedeno izmedu. Neka nam je jedinka sljedeca:
jedinka = 00111010
Znamo da je jedan gen kodiran s 4 bita (M = 4), dakle m1 = 0011, m2 = 1010:
x1 = (m1 / (2^M - 1)) * (x_max - x_min) + x_min = (3 / 15) * (50 - (-50)) + (-50) = -30
x2 = (m1 / (2^M - 1)) * (x_max - x_min) + x_min = (10 / 15) * (50 - (-50)) + (-50) = 16.667
Drugim rijecima, jedinka nam je jednaka [-30, 16.667] kad ju dekodiramo.
Eto, sad smo vidjeli dva od mnogo mogucih nacina prikaza rjesenja. Ostaje jos pitanje kako izracunati dobrotu pojedinog rjesenja, odnosno jedinke. Eh, to je opet jedna od onih stvari kod GA koje ovise o konkretnom problemu. U ovom konkretnom slucaju koji cemo mi raditi, koristit cemo srednju kvadratnu pogresku kao funkciju lošoće ili funkciju kazne (u kodu sam ju nazvao badness). Dakle, jos jedna od stvari koje se u GA mogu proizvoljno definirati. Opcenito se gleda da jedinke imaju cim vecu dobrotu, no u nasem slucaju mi cemo gledati obrnuto, cim jedinke imaju manju lošoću tim su bolje.
Jos nam ostaje pogledati operatore. Operatore cu objasniti za brojeve s pomicnim zarezom, kod binarnog prikaza se ne razlikuju puno.
Operatori:
Prvo cu objasniti operator krizanja. Najjednostavniji operator krizanja radi na sljedeci nacin: uzme dvije jedinke, odabere neku poziciju gdje ce "rezati" kromosom te napravi trecu jedinku koja je kombinacija prve i druge od razrezanih dijelova. Evo primjer:
roditelj1 = [1, 3, 4, 10, 2, 7, 9]
roditelj2 = [3, 7, 2, 1, 5, 6, 11]
Recimo da smo slucajno odabrali prekid kod treceg gena, dijete izgleda ovako:
dijete = [1, 3, 4, 1, 5, 6, 11] -> vidimo da je dijete kombinacija dvaju roditelja.
Ovo je bio samo primjer, postoji mnostvo operatora krizanja, svaki prikladan za drugaciji prikaz rjesenja. Cak stovise, za jedan nacin prikaza rjesenja postoji vise razlicitih operatora krizanja. Npr., za binarni prikaz rjesenja postoji krizanje s jednom tockom prekida (to je u principu ovaj primjer), krizanje s vise tocaka prekida gdje se malo uzme od jednog roditelja, malo od drugog, pa opet od prvog i tako redom koliko god tocaka prekida imamo. Takoder postoji i uniformno krizanje gdje svaki bit (gen) ima vjerojatnost 50% da ce biti nasljeden od prvog, odnosno od drugog roditelja. Kod prikaza brojevima s pomicnim zarezom imamo diskretnu (uniformnu) rekombinaciju sto je ekvivalentno uniformnom krizanju kod binarnog prikaza, svaki realni broj (gen) ima 50% vjerojatnost da ce biti nasljeden od prvog, odnosnog drugog roditelja. Imamo jednostavnu aritmeticku rekombinaciju gdje se odredi jedna tocka prekida, te se djetetu do te tocke daju geni jednog roditelja, a od te tocke nadalje uzima se aritmeticka sredina gena. Postoji i jednostruka aritmeticka rekombinacija kod koje se uzima aritmeticka sredina samo jednog gena. Postoji potpuna aritmeticka rekombinacija gdje se dijete stvara na nacin da se napravi aritmeticka sredina svih gena oba roditelja. Zatim, umjesto aritmeticke sredine moze se raditi zbrajanje/oduzimanje s vrijednoscu koju da normalna razdioba. Ima nevjerojatno puno izbora i kombinacija i niti jedno nije najbolje u opcem slucaju, tek za konkretne slucajeve su neke varijante bolje od drugih. Mi cemo u nasem primjeru raditi jednostavnu aritmeticku rekombinaciju i to umjesto jednog djeteta stvorit cemo odmah dva (eto, vec neka varijacija) tako da cu sad pokazati primjer toga:
roditelj1 = [0.1, 0.5, 0.3, 0.7, 0.2]
roditelj2 = [0.9, 0.9, 0.1, 0.5, 0.3]
Recimo da je tocka prekida kod drugog gena. Prvo dijete ce uzeti gene prvog roditelja, drugo dijete ce uzeti aritmeticku sredinu tih gena:
dijete1 = [0.1, 0.5 ...
dijete2 = [0.5, 0.7 ... -> jer (0.1 + 0.9) / 2 = 0.5 i (0.5 + 0.9) / 2 = 0.7
Sad ce prvo dijete dobiti aritmeticku sredinu ostalih gena, (0.3 + 0.1) / 2 = 0.2, (0.7 + 0.5) / 2 = 0.6, (0.2 + 0.3) / 2 = 0.25, a drugo ce dobiti gene drugog roditelja:
dijete1 = [0.1, 0.5, 0.2, 0.6, 0.25]
dijete2 = [0.5, 0.7, 0.1, 0.5, 0.3]
Jasno je da ovdje moze biti jos svakakvih varijacija na temu.
Sljedeci operator koji nam treba je operator mutacije. Operator mutacije djeluje nad jednom jedinkom i mutira ju. Opet, za razlicite prikaze postoje razliciti operatori mutacije. Tako za binarni imamo npr., jednostavnu mutaciju koja izabere neki nasumicni bit (gen) i okrene ga iz 0 u 1 ili iz 1 u 0. Postoji i potpuna mijesajuca mutacija kod koje broj jedinica i nula ostaje isti, ali im se redoslijed izmjeni. Kod prikaza brojevima s pomicnim zarezom imamo takoder jednostavnu mutaciju koja izabere nasumican broj (gen) i zamijeni ga nekim drugim nasumicnim brojem. Moguca je i varijacija gdje se izabere nasumican gen pa se zbroji/oduzme s brojem koji vucemo iz normalne (Gaussove) razdiobe. Mutacija je u principu najjednostavniji operator.
Sad kad imamo operator krizanja i operator mutacije, fali nam jos operator selekcije. Njega sam ostavio za kraj jer je on najkompliciraniji i najbitniji za optimalan rad GA. Selekcije se dijele na generacijske gdje se direktno biraju bolje jedinke ciji genetski materijal ulazi u sljedecu generaciju te eliminacijske gdje se biraju lose jedinke za eliminaciju, dok bolje prezivljavaju postupak selekcije (postoje i neke druge podjele). Selekcija ima mnogo, no ja cu ovdje spomenuti samo dvije: k-turnirsku selekciju te proporcionalnu selekciju.
Proporcionalna selekcija poznata je i pod nazivom engl. roulette-wheel selection. Kod ove selekcije vjerojatnost odabira i-te jedinke definirana je izrazom:
p_i = f_i / suma_od_1_do_n(f_j)
Dakle, vjerojatnost odabira i-te jedinke je njezina dobrota podjeljena sa sumom dobrota svih jedinki. Zove se roulette-wheel selekcija jer si ovu selekciju mozemo zamisliti na sljedeci nacin. Svaka jedinka dobije krisku odredene velicine na nekom kolu. Tada zavrtimo to kolo i jedinke s vecim kriskama imaju vecu vjerojatnost da budu izabrane, tj. da ce prenijeti svoj genetski materijal u sljedecu generaciju od jedinki s manjom kriskom. To je bitna stvar! Ne biramo eksplicitno jedinke s vecom dobrotom, nego upravo suprotno, biramo ih slucajno, ali one s boljom dobrotom imaju bolju sansu da budu izabrane. Na ovaj nacin smo osigurali da i one slabije jedinke imaju ipak nekakvu vjerojatnost da ih se odabere te smo tako smanjili mogucnost da algoritam zaglavi u lokalnom optimumu. Ova selekcija nije najsretnije rjesenje (inace, kad su GA prvi put predlozeni, ova selekcija je orignalno bila predlozena za operator) iz dva razloga. Prvo, sve dobrote moraju biti nenegativne (znaci vece ili jednake nuli) dok srednja vrijednost mora biti strogo veca od nule (jer se nulom ne moze dijeliti). Drugo, podlozna je problemu skaliranja. Sto to znaci? Zamislimo dvije populacije od po tri jedinke. U prvoj populaciji dobrote su redom 1, 2 i 3, a u drugoj 100001, 100002, 100003. Vjerojatnost odabira trece jedinke u prvoj populaciji je: 3/(1 + 2 + 3) = 0.5. Vj. odabira trece jedinke u drugoj populaciji je: 100003 / (100001 + 100002 + 100003) = 0.333336667. U obje populacije trece jedinke su najbolje, no u drugoj populaciji vjerojatnost odabira najbolje jedinke je gotovo pa ista vjerojatnosti odabira najgore koja iznosi 0.33333 (uvjerite se sami). No, u nasem primjeru ovakva ce selekcija biti relativno dobra.
Druga selekcija koju sam spomenuo je k-turnirska selekcija. Vrlo je jednostavna i najcesce se koristi kod eliminacijskih GA, ali nije nuzno, moze se koristiti i kod generacijskih (sto cemo i koristiti). Kod k-turnirske selekcije iz populacije se izvlaci nasumicno k jedinki i zatim se odabire najbolja jedinka. Postoje dvije varijante: jedna s ponavljanjima gdje je moguce istu jedinku izvuci vise puta iz populacije i druga bez ponavljanja gdje se jednom izvucena jedinka vise ne moze izvuci. Konkretna turnirska selekcija koju cemo mi implementirati biti ce 3-turnirska selekcija i koristit cemo ju kod eliminacijskog GA na sljedeci nacin: izabrat cemo nasumicno tri jedinke, dvije bolje ce biti roditelji, a nastalo dijete ce u populaciji zamijeniti trecu, najlosiju jedinku. Kod generacijskog GA k-turnirskom selekcijom uzet cemo samo najbolju jedinku iz turnira za roditelja.
Jos jedna stvar koja je ostala, a koju sam vec spomenuo, ali usputno su parametri. Koji su to parametri? Velicina populacije, vjerojatnost krizanja, vjerojatnost mutacije, velicina turnira (ukoliko se koristi k-turnirska selekcija), elitizam, itd. Svi su parametri medusobno ovisni, no u principu tri najbitnija su velicina populacije, vj. krizanja i vj. mutacije i oni najvise odreduju hoce li GA naci optimalna rjesenja ili ce negdje zaglaviti te koliko brzo ce ih pronaci. Fino podesavanje parametara je pak umjetnost za sebe.
Eto, to je vise manje to sto se tice potrebnih znanja za uspjesnu implementaciju GA. Sada cemo konacno malo zaprljati ruke i implementirati konkretan GA.
Koristimo domaće donje rublje (Galeb d.d.)
