Neuro-evolucija sa menjajućim topologijama (Neuro-evolution with augmenting topologies, NEAT) je tehnika koju su 2002. razvili Kenet Stenli Oven I Risto Mikulainen sa Univerziteta Teksas. Ova tehnika koristi genetske algoritme da istrenira strukturu mreže i težine veza, i ima zgodan način izbegavanja nazivanja istog neurona različitim imenima koristeći istorijske podatke generisane pri stvaranju novih neurona i veza. NEAT pokušava da proizvede mrežu minimalne veličine, tako što počinje evoluciju koristeći inicijalnu populaciju mreža sa minimalnom topologijom i dodavanjem neurona i veza za vreme evolucije. Ovo je zanimljivo rešenje zato što i priroda radi na sličan način – povećavajući složenost organizama vremenom.
Prvo, pogledajmo kako NEAT predstavlja neuralnu mrežu genima.
Genotip
U ovom genetskom algoritmu jedna jedinka je jedna neuralna mreža. Genotip se sastoji od liste gena neurona i liste gena veza.
Gen neurona
Gen neurona opisuju njegova uloga u mreži (ulaz, bias, skriveni, izlaz), i jedinstveni identifikacioni broj. Gen može sadržati i vrednost koja određuje oštrinu aktivacionog odgovora sigma funkcije, koja bi takođe mogla da evoluira vremenom (ali ovo nećemo koristiti).
Takođe, gen sadrži x i y poziciju neurona na mreži. Za sada, razmotrimo samo y vrednost (x se određuje slično). Na početku, ulazi i bias neuroni imaju y vrednost 0, a izlazi y vrednost 1. Kada se napravi novi neuron na vezi između dva stara neurona, njegova y vrednost je prosek y vrednosti dva stara neurona. Ove vrednosti su korisne za iscrtavanje mreže, određivanje dubine mreže, ali najviše za određivanje da li je neka grana povratna ili ne.
Gen veze
Gen veze sadrži informacije o tome koja dva neurona povezuje, težinu veze, indikator da li je veza važeća, indikator da li je link povratan (ide iz većeg y u manji, ili su jednaki) i inovacioni broj (više o ovome uskoro).
Inovacije
Sada kada smo videli kako NEAT opisuje neuralne mreže genima, pogledajmo glavni deo NEAT-a – kako stvara nove neurone i veze, i kako pamti koji neuron i veza u jednoj jedinci odgovara kojem u drugoj jedinci.
U inicijalnoj populaciji postoje samo ulazni, bias i izlazni neuroni, gde su svi ulazni i bias neuroni povezani sa izlaznim neuronima. Ostali se dodaju mutacijama. Postoje tri različite mutacije u NEAT-u: dodavanje gena neurona, dodavanje gena veze i promena težina veza.
Inovacija se dešava kada je nov gen dodat u genotip, bilo dodajući vezu ili neuron, i ona je evidencija te promene. Postoji globalna baza svih inovacija, u kojoj svaka inovacija ima svoj identifikacioni broj. Na početku, dodaju se inovacije za sve početne neurone i veze. Svaki put kada se doda novi neuron ili veza, baza se proveri da se vidi da li je takva inovacija ranije stvorena. Ako jeste, novi gen uzima postojeći identifikacioni broj. Ako nije, nova inovacija sa novim identifikacionim brojem je dodata u bazu, i gen uzima taj identifikacioni broj.
Dodavanje veze
Ova mutacija dešava se tako što se izaberu dva nasumična neurona u mreži A i B, takvi da ne postoji veza od A do B i da B nije bias niti ulaz. Proverava se inovaciona baza da se vidi da li je neka jedinka već napravila ovu mutaciju, i ako jeste nova veza dobija taj inovacioni broj. Ako nije, pravi se novi inovacioni broj, inovacija se pamti u bazi, i nova veza uzima taj inovacioni broj. Veza uzima nasumičnu težinui ubacuje se u gene veza te jedinke. Ako je y pozicija neurona B veća ili jednaka od y pozicije neurona A, onda je to povratna veza.
Dodavanje neurona
Ova mutacija se dešava tako što se izabere jedna nasumična veza u jedinci koja ide od neurona A ka neuronu B (koja nije povratna i gde A nije bias). Ta veza se označi kao nevažeća. Kontaktira se baza inovacija da se vidi da li je već nekada neuron mutirao između A i B. Ako jeste, uzima se njegov inovacioni broj za novi neuron C, ako nije stvara se novi inovacioni broj koji se pamti u bazi inovacija i koji koristi neuron C. Neuron C se dodaje u gene neurona jedinke, i onda stvaraju veze A-C i C-B i veze između bias neurona i neurona C, naravno sa proverom u bazi inovacija da li te inovacije već postoje. Veza C-B uzima težinu veze A-B, veza A-C težinu 1, veza bias-C težinu 0. Na taj način se pokušava da promena prođe što glatkije, tj. da ne pokvari već naučeno ponašanje.
Na primer, evoluiramo mrežu koja ima dva ulaza i jedan izlaz. Levo vidimo kako izgleda mreža pre dodavanja novog neurona, desno posle. Kada je neuron 4 dodat tri inovacije su stvorene, jedna za neuron 4 i dve za veze 1-4 I 4-3 (stara 3-1 veza i dalje postoji u genotipu ali je proglašena nevažećom, takođe na slici je ignorisan bias neuron i njegova dodatna inovacija veze). Ta promena je dodata u inovacionu bazu. Ako bilo kada u budućnosti neka jedinka bude napravila istu mutaciju (dodavanje neurona između neurona 1 i 3), taj neuron će imati inovacioni broj 4, i veze 1-4 i 4-3 imaće isti inovacione brojeve kao u ovoj jedinci.
U ranoj fazi razvoja mreža, problem može nastati ako je početna mreža mala i ista veza podeljena nekoliko puta, izazivajući lančani efekat, kao na slici ispod.
Taj problem se rešava tako što se, ako je broj skrivenih neurona ispod određene date granice, biraju starije veze za deljenje, pre nego mlađe.
Ukrštanje
Pri ukrštanju ukrštaju se samo geni veza (potrebni geni neurona, koji su na krajevima veza, se samo preuzmu jer su isti u oba roditelja). Pošto svaka inovacija ima jedinstven inovacioni broj geni se mogu upariti pre ukrštanja, tj. možemo znati koji gen iz jedne jedinke odgovara kojem iz druge. Da pojasnimo ovo, pogledajmo sledeću sliku:
Kao što se vidi, jedinke su različitih topologija, ali tačno se zna koji gen jedne jedinke odgovara kojem genu druge jedinke, a koji ostaje neuparen jer postoji u jednoj ali ne u drugoj jedinci. Geni koji ostaju neupareni u sredini zovu se rasparni geni, a geni koji ostaju neupareni na kraju pretekli geni. Gene koji postoje u oba roditelja dete nasleđuje nasumično, od jednog ili drugog roditelja. Rasparne i pretekle gene nasleđuje od prilagođenijeg roditelja. Ovim procesom NEAT obezbeđuje ne samo da je fenotip nove jedinke neuralna mreža koja funkcioniše, već i da je u najvećoj mogućoj meri poprimila osobine od oba roditelja.
Podela na vrste
Kada se struktura mreže promeni, bilo dodavanjem neurona ili veze, velika je verovatnoća da će nova jedinka biti loše prilagođena dok ne dobije šansu da evoluira i utvrdi sebe među populacijom. Na žalost, ovo znači da postoji velika verovatnoća da jedinka izumre pre nego što ima šanse da evoluira neko potencijalno interesantno ponašanje. Ovo je očigledno nepoželjno – mora postojati neki način da pomognemo nove inovacije u počecima njihove evolucije. Podela na vrste nam tu može pomoći.
Vrsta je grupa jedinki sa sličnim karakteristikama koje su sposobne za uspešno međusobno razmnožavanje koje proizvodi zdravo potomstvo, a nisu sposobne za razmnožavanje sa drugim vrstama.
U prirodi, uobičajan mehanizam podele na vrste je geografska udaljenost. Zamislimo populaciju neke vrste koja je vremenom postala geografski podeljena zbog rasta planinskog venca, recimo. Vremenom, ove dve populacije će postati različite zbog različitih pritisaka okruženja i različitih mutacija njihovih genotipa. Sa jedne strane venca populacija može razviti deblju kožu zbog hladnijeg vremena, a sa druge strane prilagoditi da izbegava razne predatore koji tamo žive. Na kraju, dve populacije će se toliko promeniti da njihove jedinke, čak i kad bi se srele, ne bi mogle međusobno da se razmnožavaju.
NEAT simulira podelu na vrste da stvori prirodne niše za nove topološke promene u mreži. Na ovaj način, slične jedinke mogu da se takmiče između njih a ne sa ostatkom populacije. Na taj način oni su sačuvani od prebrzog izumiranja.
Da bismo podelili jedinke u vrste, moramo da napravimo neku ocenu koliko su različite date dve jedinke. Broj gena veze jedinke koja ima više veza je n. Nađemo prosečnu razliku težina u genima veza koje se poklapaju (
), broj rasparnihGena (
) i broj preteklih gena (
). Kompatibilnost dve jedinke data je sledećom formulom:
Na početku postoji samo jedna vrsta. Jedinke se dele u vrste tako što se upoređuju sa najprilagođenijim jedinkama u svakoj vrsti, i nalaze onu kojoj su najbliži. Ako su od najbliže vrste udaljeni manje od određenog praga udaljenosti, ubacuju se u tu vrstu, ali ako nisu kreiraju novu vrstu u koju ulaze.
Kada je jedinci dodeljena vrsta može da se razmnožava samo sa drugim članovima vrste. Međutim, sama podela na vrste ne štiti nove inovacije. Da bismo to uradili, moramo da nađemo način da promenimo prilagođenje jedinki tako da pomaže mlađim vrstama da ostanu aktivne razuman vremenski period. To se radi tako što se jedinkama u mlađim vrstama (recimo mlađim od 15 generacija) množi vrednost prilagođenja sa koeficijentom većim od 1, a starim (recimo starijim od 80) sa pozitivnim koeficijentom manjim od 1. Ako vrste ne pokažu napredak u nekoliko poslednjih generacija (najbolje prilagođenje se ne poveća, recimo 15 generacija), te vrste ubijamo. Izuzetak za ovo pravilo je vrsta koja poseduje najbolju jedinku u celoj populaciji.
Kada se promeni prilagođenje jedinkama, izračuna se prosečno prilagođenje svake vrste. Vrsta koja ima veće prosečno prilagođenje u sledećoj generaciji daće više potomaka, i obrnuto.
Neuralna mreža
Primetili smo da neuralna mreža kakvu smo smo ovde opisali može imati i povratne veze (one koje ide od neurona bližeg izlazu ka neuronu bližem ulazu). Time omogućavamo povratne informacije, koje mogu biti korisne.
Izlaz neuron računa se tako što se saberu otežali ulazi sa čije druge strane su aktivirani neuroni. Neuron je aktiviran ako su aktivirani svi neuroni sa njegovih ulaza koji nisu povratni. U jednom potezu aktivacije svi neuroni paralelno ažuriraju svoj izlaz i indikator aktivacije. Ulaz je proizveo izlaz kada su svi izlazi neuroni aktivirani.
Postoji dva načina korišćenja ovakve mreže. Prvi je trenutni, u kojem se u mrežu u kojoj nijedan neuron nije aktiviran dovode ulazi, i proces aktivacije ponavlja dok svi izlazi nisu aktivirani. Ovaj način se koristi kada prethodni prolaz kroz mrežu nema nikakve veze sa sledećim prolazom, na primer, da li na jednoj slici ima lice nema nikakve veze da li će biti na sledećoj slici. Međutim, u nekim slučajevima prethodni impulsi kroz mrežu možda imaju značaja za trenutne odluke. Na primer, ako vozimo kola i na određeni broj milisekundi pitamo mrežu za odluke. Takva mreža može iskoristiti i prethodne informacije koje su putovale mrežom i, napraviti neke povratne sprege u odnosu na njih. To se zove aktivni način korišćenja. Kada se na mrežu dovedu ulazi neuroni ostaju aktivirani od prethodnog puta, i vrši se samo jedan potez aktivacije.Takva mreža može, na primer, izračunati izvod nekog ulaza, što može biti korisno.
Sada kada smo objasnili kako NEAT funkcioniše pogledajmo eksperimentalne rezultate njegovog korišćenja.