2.3 Algoritmi bazirani na populaciji rješenja


Osnovna karakteristika algoritama baziranih na populaciji rješenja je da se u svakom iterativnom koraku koriste skupom rješenja. Oni pretražuju rješenja opisujući evoluciju skupa točaka u prostoru pretrage [1]. Ovdje se opisuju algoritmi: stohastičko difuzno pretraživanje, optimizacija mravljom kolonijom, optimizacija rojem čestica i  evolucijski algoritmi.

2.3.1       Stohastičko difuzno pretraživanje

Stohastičko difuzno pretraživanje (Stohastic Diffusion Search, SDS) je prvi put opisano 1989. kao algoritam koji se bazira na populaciji rješenja sa ciljem pronalaženja najboljeg odgovarajućeg uzorka [3]. SDS kao metaheuristički algoritam spada u grupu inteligencije roja, a  glavna mu je karakteristika da koristi direktnu komunikaciju između agenata, oponašajući mehanizam komunikacije mravlje vrste poznate kao Leptothorax Acervorum. Zbog toga spada i u multiagentne sustave. SDS se uglavnom koristi u problemima kada se funkcija cilja može rastaviti na komponente koje se mogu zasebno procijeniti. To mogu, primjerice, biti funkcije koje pronalaze određeni uzorak (najbolji odgovarajući) u znakovnom nizu. Kako bi se pronašlo optimalno rješenje, upošljava se roj od nekoliko agenata od kojih svaki ima pretpostavku o globalnom optimumu [4]. Rastav funkcije cilja na komponente koje se mogu zasebno procijeniti, omogućuje da agenti u SDS-u mogu dati ocjenu trenutne pretpostavke na temelju procjene komponente rješenja. Time će se brzo, bez iscrpnog pretraživanja, procijeniti trenutna pretpostavka. Pri traženju rješenja roj agenata obavlja posao paralelno i istodobno (i sinkronizirano). Kostur algoritma je dan na Slici 2.15.

Inicijaliziraj(Agente);

Čini {

 Ispitaj(Agente);

       Difundiraj(Agente);

} dok(Kriterij_zaustavljanja != zadovoljen);

Slika 2.15 Kostur SDS-a

Inicijaliziraj je funkcija (metoda) koja postavlja  pretpostavke pojedinim agentima. Uglavnom se hipoteze postavljaju slučajnim odabirom, ali postoje i drugi načini na koje se postavljaju pretpostavke, pogotovo ako su poznate neke istine o mogućem rješenju.

U funkciji Ispitaj svaki agent uzima jednu komponentu rješenja i na temelju toga radi procjenu svoje pretpostavke. Funkcija ocijeni vraća vrijednost procjene. Na temelju te vrijednosti, agenti se dijele u dvije grupe: u pasivne, čija hipoteza nije zadovoljavajuća, i aktivne čija je hipoteza zadovoljavajuća.

za (i = 1 do broja_agenata) {

j = nasumice_odaberi() % broj_komponenata;

ako (ocijeni(agent[i],j) == dobro)

      agent.aktivnost = aktivan;

inače

      agent.aktivnost = pasivan;

}

Slika 2.16 Pseudokod funkcije ispitaj

Nakon faze ispitivanje slijedi faza difuzije pri čemu svaki pasivni agent (u realizaciji danoj na Slici 2.12) nasumice odabire drugog agenta za komunikaciju. Ako je odabrani agent aktivan, agent koji je birao preuzima njegovu pretpostavku (difuzija informacija [14]). Ukoliko je odabrani agent pasivan, tada nema protoka informacija

između agenata, već agent koji je birao nasumice odabire novu pretpostavku. Time je opisan pasivni regrutacijski mehanizam u kojem pasivni agent pronalazeći aktivnog može i sam postati aktivan. Druga mogućnost je da aktivni agent nasumice bira agenta i ako je taj agent  pasivan, on ga regrutira. Ovaj postupak naziva se aktivna regrutacija. Bitno je uočiti, da se u svakoj iteraciji difuzne faze aktivne regrutacije broj agenata može najviše dvostruko povećati u odnosu na stanje prije difuzne faze.

za (i = 1 do broj_agenata) {

ako (agent.aktivnost == pasivan){

      pom_agent = nasumice_odaberi_agenta();

      ako (pom_agent.aktivnost == aktivan)

           agent.pretpostavka=pom_agent.pretpostavka;

      inače

           agent.pretpostavka=nasumice_odaberi_pretpostavku();

}

}

Slika 2.17 Pseudokod funkcije difundiraj

Pasivna regrutacija nema takvo ograničenje. Treća vrsta regrutacije je dualna (mješovita) regrutacija, u kojoj i pasivni i aktivni agenti biraju druge agente potrebne za aktiviranje pasivnih agenata. Budući da ovakav postupak regrutacije najbolje opisuje ponašanje biološkog modela na kojem je zasnovan SDS, on se danas smatra i najučinkovitijim postupkom. Na Slici 2.17 je dan opis difuzne faze s pasivnom regrutacijom.

img14

Slika 2.18 Faza inicijalizacije, ispitivanja i difuzije

Kriterij_zaustavljanja određuje kada će SDS završiti sa radom. Kao što je opisano, tijekom rada algoritma agenti postaju aktivni i grupiraju se u skupine koje imaju iste pretpostavke. Dva su osnovna kriterija koja se primjenjuju u zaustavljanju algoritma:

  1. Slabi kriterij zaustavljanja koji je funkcija ukupnog broja aktivnih agenata
  2. Jaki kriterij zaustavljanja koji je funkcija ukupnog broja aktivnih agenata s istom hipotezom [15].

Jasno je da najveća skupina aktivnih agenata određuje optimalno rješenje, pa nam jaki kriterij zaustavljanja daje točnije rješenje, ali trajanje algoritma je zbog toga duže.

SDS, kao metaheuristički algoritam, traži globalni optimum. Zbog toga treba zadovoljiti uvjet da algoritam ne zapne u lokalnom optimumu, kao i uvjet da se algoritam stabilizira kada pronađe globalni optimum (ne pobjegne iz njega). Kako je prvi zahtjev u suprotnosti s činjenicom da algoritam tijekom vremena stvara sve veće i veće skupine aktivnih agenata s istim pretpostavkama, algoritam se može neznatno izmijeniti u cilju izbjegavanja lokalnog optimuma. Naime, u difuznoj fazi možemo koristiti aktivnu regrutaciju i ako je izabrani agent aktivan i pripada istoj skupini (ima istu hipotezu), on postaje pasivan s nasumično izabranom pretpostavkom. Time se razbijaju velike skupine aktivnih agenata s istom hipotezom i smanjena je mogućnost zaglavljivanja u lokalnom optimumu, tj. istražuje se veći prostor rješenja. Izmijenjeni algoritam se zove konteksno-senzitivan SDS [4]. Ovako izmijenjen algoritam pokazuje znatne prednosti kada je optimalno rješenje promjenjivo, tj. kada se nalazimo u dinamičkom sustavu. Uvjet stabilnosti SDS-a je zadovoljen: pokazuje se da je SDS eksponencijalno stabilan [15].  Sam algoritam brzo konvergira k rješenju i nema veliku složenost.

Primjer 2.4 Igra restorana

Zamislimo grupu studenata FER-a koji su otišli na konferenciju o SDS-u u grad koji nikad prije nisu posjetili. Da bi se ugodno proveli, oni pokušavaju pronaći restoran u kojem su njima najbolja jela. Domišljati FER-ovci koriste SDS kako bi u što kraćem roku pronašli odgovarajući restoran. Svaki od njih napravi pretpostavku o dobrom restoranu u gradu, ode u njega i izabere jelo slučajnim odabirom. Sljedećeg jutra, nakon ludo provedene noći, svaki student koji je bio nezadovoljan pita slučajno odabranog kolegu studenta za procjenu restorana koji je on pohodio. Ukoliko je  procjena dobra, student koji je pitao pamti ime restorana kojeg mu je dao kolega student i uzima taj restoran za svoj izbor. Inače se koristi internet pretraživačem da bi slučajno odabrao restoran u kojem će večerati. Nakon nekoliko dana, stvori se značajna skupina FER-ovaca koji večeraju u najboljem restoranu [3, 4, 14, 15].

2.3.2        Optimizacija mravljom kolonijom

Optimizaciju mravljom kolonijom (Ant Colony Optimization , ACO) je prvi predložio Marco Dorigo u svojim radovima. Inspiraciju vuče iz ponašanja argentinske vrste mrava Iridomyrmex humilis [17].  Provedeni su pokusi u kojima je mravlje gnijezdo spojeno sa izvorom hranom pomoću dva mosta čija se relativna duljina mijenjala. Pokazalo se da će nakon nekog vremena većina mrava prolaziti kraćim putem, a razlog tomu je posredan način komunikacije mrava pomoću feromona kojeg mravi ostavljaju za sobom. Naime, mrav donosi odluku na temelju količine feromona kojeg osjeća da postoji na određenom putu. Kako se feromoni više osjećaju na kraćem putu (zbog njihove veće gustoće), većina mrava će nakon nekog vremena  prolaziti kraćim putem. Također treba uzeti u obzir i učinak isparavanje feromona, koji je bitna karika algoritma koji oponaša mrave.

Zbog analogije na kojem je izgrađen, ACO se uglavnom koristi u problemima koji se mogu svesti na pronalaženje najkraćeg puta u grafu, posebice u problemima vezanim uz pronalaženje najkraćeg Hamiltonovskog ciklusa (ciklusa koji prolazi svim vrhovima grafa) u potpunom jednostavnom grafu (grafu čija su svaka dva vrha spojena). Problem trgovačkog putnika (Travelling salesman problem, TSP), kada se formalno definira, nije ništa drugo nego potraga za najkraćim hamiltonovskim ciklusom u potpunom jednostavnom grafu. Zbog toga je ACO prikladno objasniti na na tom problemu. Valja naglasiti da je TSP NP-težak problem i egzaktne metode rješavanja imaju u najboljem slučaju eksponencijalnu složenost.

Neka je definiran potpun jednostavan graf G(V,E) sa skupom vrhova V i skupom bridova E. Uzmimo da je broj vrhova n, a broj mrava m. Algoritam nastoji odrediti najkraći hamiltonovski ciklus tako da oponaša mrave koji se kreću iz jednog vrha do drugog i ostavljaju tragove feromona za sobom. Pri tome se obilaze svi vrhovi i to samo jednom, a u početni vrh se dolazi kada se obiđu svi ostali. Zbog toga mrav mora imati pamćenje (memoriju) o gradovima koje je obišao. Na Slici 2.19 dan je pseudokod kostura ACO-a.

Inicijlizacija_parametara_i_tragova_feromona;

Dok (uvjet_zaustavljanja != zadovoljen){

   Rasporedi_aktivnosti();

}

Rasporedi_aktinosti(){

   KonstruirajMravljeRješenje();

   DaemonAktivnosti(); //opcionalno

   ObnoviTragoveFeromona();

}

Slika 2.19 Kostur ACO-a

Glavni dio ACO-a su Rasporedi_aktinosti. Aktivnosti se sastoje od KonstruirajMravljeRješenje, ObnoviTragoveFeromona, DaemonAkcije, pri čemu  nije izričito rečeno kako su tri aktivnosti raspoređene, izvedene i sinkronizirane [4].

img16

Slika 2.20 KonstruirajMravljeRješenje i ObnoviTragoveFeromona

U KonstruirajMravljeRješenje svaki mrav (zasebno) konstruira konstrukcijski graf Gc(V,C)  gdje je C skup bridova grafa koji zajedno sa vrhovima V tvore ciklus duljine n. C sadrže komponente rješenja (i, j) kojima pridružujemo tragove feromona τij , kao funkciju vremena, i varijablu heuristike hij, koja posjeduje apriorna saznanja o komponenti rješenja. Varijabla heuristike je najčešće recipročna vrijednost duljine komponente, tj. ηij=1/dij, gdje je dij duljina komponente. Konstrukcija započinje u slučajno odabranom vrhu grafa. Koristi se varijabla djelomičnog rješenja sp kojoj se u svakom koraku konstrukcije pridružuje jedna komponenta iz skupa mogućih komponenata N(sp). sp je inicijalno prazni skup, a N(sp) predstavlja skup komponenti pomoću kojih možemo doći iz zadnjeg odabranog vrha u njemu susjedni neodabrani vrh. Odabir komponente temelji se na vjerojatnosnom modelu u kojem je vjerojatnost odabira najčešće dana formulom (2.2).


formula2
(2.2)

U formuli (2.2) α i β su parametri relativnog odnosa feromonskog traga i heurističke informacije(varijable), tj. odnosi njihovih važnosti.
DaemonAktivnosti su aktivnosti koje ne može provesti svaki mrav zasebno, a poboljšavaju svojstva algoritma. Primjerice, nad skupinom rješenja možemo provesti lokalno traženje i izdvojiti dobra rješenja po nekom kriteriju. To nam olakšava obnavljanje feromona u fazi ObnoviTragoveFeromona zakazanih aktivnosti. Također, možemo bridovima koji su elementi dobrog rješenja pridijeliti dodatne tragove feromona.

ObnoviTragoveFeromona možemo razložiti na dvije zasebne aktivnosti. Prvo tragovi feromona na svim bridovima potpunog grafa G isparavaju (opadaju). Isparavanje se provodi po eksponencijalnom zakonu, tj. u novom koraku broj feromona je reduciran za parametar isparavanja ρ (0<ρ<1). Njime se smanjuje brzina konvergencije, tj. smanjena je mogućnost zapinjanja u lokalnom optimumu. U drugoj fazi se poveća broj feromona na onim bridovima potpunog grafa koji su dijelovi onog konstrukcijskog grafa Gck koji zadovoljava kriterij dobrog rješenja. Obnavljanje feromona može biti zadano formulama (2.3).

formula3
(2.3)

U formulama (2.3) Lk je ukupna duljina puta dobrog rješenja Ck.
ACO se pokazao uspješnim u rješavanju NP-teških problema, ali i u područijima obrade podataka i usmjeravanja u telekomunikacijskim mrežama [4, 17, 18, 19].

2.3.3       Optimizacija rojem čestica

Optimizacija rojem čestica (Particle swarm optimization,PSO) spada u algoritme inteligencije roja i algoritme bazirane na populaciji rješenja. Algoritam su razvili Eberhart i Kennedy 1995. inspirirani ponašanjem jata ptica i roja insekata pa se osnovne ideje algoritma mogu opisati na takvom ponašanju[20]. Primjerice, jato galebova svakodnevno traga za hranom. Ukoliko jedan galeb osjeti dobar izvor hrane  vrlo je vjerojatno da će ga ostali članovi jata slijediti. Ipak, da bi se omogućila potraga i za boljim hranilištem, svaki galeb u sebi ima i instinkt za bolje hranilište. Time je omogućeno kratkotrajno odvajanje od jata u potrazi za boljim hranilištem.

PSO opisuje ovakav model, tj. model čestica koje lete nad prostorom rješenja u potrazi za globalnim optimumom. Za vjeran opis ovakvog modela, svakoj čestici je potrebno pridružiti vektor brzine i vektor položaja u hiperprostoru Rn (ponekad su potrebne dimenzije prostora veće od tri da bi se problem efikasno riješio). Također, svaka čestica pamti dvije vrste rješenja: svoje najbolje i globalno najbolje rješenje (najbolje rješenje svih čestica). Često se, umjesto globalno najboljeg rješenja, pamti najbolje rješenje susjedne okoline. U tu svrhu se u roju odrede međusobni susjedi, i svaka čestica pamti najbolje rješenje iz svog susjedstva. Pamćenje najboljeg rješenja iz susjedstva bolje istražuje prostor rješenja, manja je vjerojatnost upadanja u lokalni optimum, ali je konvergencija sporija. Isto tako,  lako je uočiti da je globalno najbolje rješenje poseban slučaj najboljeg rješenja iz susjedstva u kojoj su sve čestice međusobno susjedi. Detaljnije opišimo algoritam.

img22

Slika 2.21 Promjena vektora brzine k boljem rješenju

Svaka čestica na temelju svog trenutnog položaja i svoje trenutne brzine bira sljedeći položaj. Brzina je promjenjiva i mijenja se uglavnom u ovisnosti o dva relativna odnosa: najboljeg rješenja čestice i trenutnog rješenja čestice, najboljeg globalnog rješenja i trenutnog rješenja čestice. Tu vidimo dva utjecaja na promjenu položaja i brzine: utjecaj najboljeg rješenja čestice (kognitivni utjecaj) i najboljeg općenitog rješenja (društveni utjecaj). Zbog toga će se nakon nekog vremena većina čestica kretati u smjeru najboljeg rješenja. Također, algoritam u sebi treba uključiti i nasumičnost (intuiciju čestice o najboljem rješenju). Nasumičnost nam omogućava bijeg iz lokalnog optimuma i uglavnom je dana kroz slučajno odabrani broj iz intervala [0,1] kojim su pomnoženi kognitivni i društveni utjecaji. Slijedi formalniji opis PSO-a. 

parametri c1,c2;

brojevi r1,r2;

inercijska_varijabla w;

vrijeme t=0; // broj iteracija

vektori_polozaja x[m][n],xnaj[m][n];

//2*m vektora za m čestica, svi dimenzije n

vektori_polozaja xglob[n];

vektori_brzine v[m][n];

Inicijaliziraj(&w,&c1,&c2,x,v,xnaj,xglob);

čini{

     za(i = 0 do i < m){

           za(j = 0 do j < n){

                 r1=slučajno_odaberi([0,1]);

                 r2=slučajno_odaberi([0,1]);

                 x[i][j]=x[i][j]+v[i][j];

                 v[i][j]=w*v[i][j]+c1*r1*(xnaj[i][j]-x[i][j])

                         +c2*r2*(xglob[i][j]-x[i][j]);

           }

           //:= kopira redak matrice

           ako(f(&x[i][0]) > f(&xnaj[i][0])) xnaj[i]:=x[i];

           ako(f(&x[i][0]) > f(xglob)) xglob:=x[i];

     }

     t=t+1;

     w=promjeni(w,t);

} dok(zaustavni_kriterij != zadovoljen);

    

Slika 2.22 Pseudokod PSO-a

Neka je f funkcija kojoj se traži optimum i neka ima za varijablu vektor dimenzije n, a vrijednost koju vraća neka je skalar. Neka se optimizira pomoću m čestica. Tada vektor položaja i-te čestice xi i vektor brzine i-te čestice vi opisuju izrazi (2.4).

formula4

(2.4)

U izrazu (2.4), ω je inercijska varijabla, c1 je kognitivni parametar, c2 je društveni parametar, r1 i r2 su slučajni brojevi iz intervala [0,1], xinaj je najbolje rješenje i-te čestice, xglob je globalno najbolje rješenje, a t je broj iteracija koje oponaša vrijeme. Inercijska varijabla ω je iz intervala [0.9,1.2] i veća vrijednost omogućuje globalnu pretragu, dok manja lokalnu [22]. Stoga se najčešće inercijska varijabla postavi na vrijednost 1.2 i smanjuje tijekom vremena do vrijednosti 0.9, premda ju se može postaviti i kao konstantnu. Kognitivni parametar c1 predstavlja  važnost samospoznaje čestice, tj. važnost najboljeg rješenja kojeg je ona pronašla. Društveni parametar c2 predstavlja utjecaj društva, tj. važnost najbolje pronađenog rješenja uopće. Uglavnom se uzima 1.8< c1 = c2 < 2.2 . Slučajni brojevi r1 i r2 nam unose slučajnost u algoritam, a glavna im je  karakteristika da omogućavaju bijeg iz lokalnog optimuma.

Način rješavanja prikazan pseudokodom na Slici 2.22 je asinkroni, tj. jednoprocesni [22]. Uobičajno se koristi višeprocesni sinkroni  PSO, u kojem su čestice predstavljene pomoću paralelnih procesa i koriste komunikaciju među procesima za razmjenu informacija o globalno najboljem rješenju.

PSO se uglavnom koristi za optimizaciju funkcija kontinuiranih varijabli, ali može se koristiti i za optimiziranje funkcija diskretne varijable. Sljedeći primjer dočarava kako prilagoditi algoritam u svrhu optimiziranja funkcije diskretne varijable.

Primjer 2.5. Mali Ivica i pola-pola primjer

Malom osnovnoškolcu Ivici je uzor Gauss, a rješavanje problemskih zadataka mu je drugo ime za odmor. U knjizi je naišao na problem pola-pola u kojem treba iz šest listi (n1,...,n6), koje sadrže konačno mnogo različitih cjelobrojnih vrijednosti, izabrati šest brojeva (iz svake po jedan), tako da brojevi budu različiti i da zbroj izabranih brojeva iz prve tri liste bude jednak zbroju izabranih brojeva iz ostale tri liste. Primjerice liste mogu biti definirane kao n1=(0,1,2,3,4), n2=(0,1,2,3,4), n3=(0,1,2,3), n4=(0,1,2,3,4,5,6), n5=(0,1,2), n6=(0,1,2,3,4), a rješenje bi bilo (3,4,1,6,0,2). Ivica uočava da je dovoljno minimizirati funkciju prikazanu u izrazu (2.5).

formula5

(2.5)

formula6

(2.6)

U izrazu (2.5), ni(ki) je ki-ti element liste, pri čemu je ki slučajno izabran. Sada se njegovo razmišljanje može opisati diskretnim PSO-om. Vektori xi i vi će imati  šest komponenata oblika (b1,...,b6) i (b2->b5,...,b4->b3). Formule definirane za izračunavanje vektora u sljedećoj iteraciji se modificiraju kako je to prikazano u izrazu (2.6).

Operatori korišteni u izrazu (2.6) su definiranu u izrazu (2.7).

formula7

(2.7)

U izrazu (2.7) brz predstavlja brzinu, poz poziciju, a br predstavlja skalar. Alea je funkcija koja vraća slučajno odabran broj iz intervala [0,1].

Nakon ovakve preinake, dovoljno je upotrijebiti već objašnjen PSO i Ivica će (možda) dobiti tražene rezultate i tako se, poput Gaussa, (možda) proslaviti.

PSO se „udomaćio” u mnogim aplikacijama i pokazuje prednosti nad mnogim algoritmima. Njegova snaga je u tome što se uz male preinake osnovnog modela algoritma može napraviti algoritam koji učinkovito rješava različite vrste problema. Primjenu PSO možemo naći u različitim područjima poput neuronskih mreža i umjetne inteligencije [3, 20, 21, 22, 23].

2.3.4       Evolucijski algoritmi

Evolucijski algoritmi (Evolutionary algorithms, EA) su posebna skupina metaheuristika za rješavanja optimizacijskih problema. Svoju inspiraciju vuku iz Darwinove evolucijske teorije koja tumači da u prirodi vlada neprestana borba za opstanak. Drugim riječima, u prirodi neprestano teče proces prilagođavanja vrsta okolini u kojoj žive, a sve sa ciljem da se uspije u toj okolini opstati. Pri tome se u određenoj populaciji neke vrste, dobra svojstva nastoje očuvati, a loša svojstva nastoje zamijeniti boljima. Uvjeti u prirodi određuju koje će jedinke opstati i to razabiranje nazivamo procesom selekcije. Vrste se razmnožavanjem spašavaju od izumiranja. Jedinke koje nastaju razmnožavanjem u pravilu nasljeđuju svojstva roditelja, ali zbog mutacija neka od tih svojstava mogu biti promijenjena. Mutacije omogućavaju promjenu svojstava i nastajanje novih svojstava i ključ su prilagodbe vrsta novim uvjetima u prirodi.

EA obuhvaćaju široku klasu metaheurističkih algoritama. EA prate proces evolucije, pa uglavnom svi EA sadrže:

·        operator promjene koji oponaša razmnožavanje i mutaciju, a cilj mu je unošenje raznolikosti u skup rješenja

·        operator selekcije čija je namjena navođenje skupa rješenja k globalnom optimumu.

Da bi se optimizirala funkcija, potrebno je varijable funkcije koje optimiziramo prikazati u pogodnom obliku, tj. kodirati ih. Varijable predstavljaju fenotipove jedinki i njihovim kodiranjem dobivamo kromosome koji predstavljaju genotipove jedinki. Kromosomi se sastoje od gena. Funkcija dobrote (funkcija procjene) nam određuje kvalitetu pojedinog rješenja. EA je algoritam zasnovan na populaciji rješenja, a populaciju čine jedinke koje se mogu križati i mutirati.

Na početku rada algoritma se odabire populacija (inicijalizacija) i procjeni se svaka jedinka u populaciji. Inicijalizacija populacije se uglavnom obavlja slučajnim odabirom, no bilo kakve apriorne spoznaje o optimalnom rješenju se mogu uzeti u obzir prilikom inicijalizacije. Nakon inicijalizacije  ulazi se u iterativni postupak, koji traje dok nije zadovoljen zaustavni kriterij. Zaustavni kriterij može biti zadovoljen ukoliko je zadovoljena optimalna razina (razina koju unaprijed znamo zbog poznavanja optimuma) ili ukoliko istekne evolucijsko vrijeme (općenitiji slučaj). U svakom ciklusu se najprije odabiru parovi roditelja sa dobrim svojstvima. Roditelji sa dobrim svojstvima se križaju u nadi da će rekombinacijom gena stvoriti dijete s boljim svojstvima. Procesom križanja nastaju djeca koja ulaze u proces mutacije.

Inicijaliziraj populaciju;

Procjeni svakog kandidata;

Dok (zaustavni_kriterij != zadovoljen){

      Odaberi roditelje;

      Križaj parove odabranih roditelja;//razmnožavanje

      Mutiraj dobivenu djecu;

      Procjeni nove kandidate;

      Izaberi jedinke za sljedeću generaciju;

}

Slika 2.23 Pseudokod EA-a

Mutacija omogućava širu pretragu prostora rješenja i bijeg iz lokalnog optimuma. Zadnja faza je izbor jedinki za sljedeću generaciju i predstavlja prirodnu selekciju: jedinke dobrih svojstava ulaze u sljedeću generaciju, dok jedinke loših svojstava izumiru.

Četiri su osnovne skupine EA: evolucijske strategije, evolucijsko programiranje, genetski algoritmi i genetsko programiranje. Navedeni algoritmi prate pseudokod prikazan na Slici 2.23, dok su im razlike uglavnom u tehničkim detaljima izvedbe [24].

Evolucijske strategije (Evolutionary Strategies, ES) koriste realni vektor za prikaz jedinke, a mutacija i selekcija su glavne tehnike pretrage prostora. Mutacijom se svakoj komponenti vektora dodaje slučajna vrijednost distribuirana po Gaussovoj razdiobi, pri čemu algoritam posjeduje svojstvo samo-adaptacije standardne devijacije u svakoj iteraciji. Odabir roditelja je slučajan, tj. po uniformnoj razdiobi. Selekcija je deterministička i mogu se razabrati dvije osnovne strategije. (λ, μ)-ES strategija izabire za sljedeću generaciju μ najboljih jedinki od λ stvorene djece. (μ+λ)-ES strategija izabire za sljedeću generaciju μ najboljih jedinki iz λ stvorene djece i μ najboljih jedinki roditelja. Algoritam se uglavnom koristi pri manjim populacijama, a prednost mu je brzina i činjenica da dobro optimizira probleme koji se svode na funkcije realnih varijabli.

Evolucijsko programiranje (Evolutionary Programing, EP) je nastalo na ideji da se simulirajući evoluciju kao proces učenja pokuša stvoriti umjetnu inteligenciju. Pri tome su se koristili konačni automati stanja. Danas se evolucijsko programiranje uglavnom koristi za numeričku optimizaciju. EP nema točno utvrđen standard, a današnje inačice jako slične evolucijskim strategijama. Osnovna karakteristika EP-a je da nema križanja među jedinkama, pa je mutacija glavni operator promjene. Kod EP-a se mogu koristiti različiti načini prikaza jedinke i različiti načini ostvarivanja mutacije. U današnjim inačicama su načini prikaza i načini ostvarenja mutacije istovjetni s onima iz ES-a. Selekcija se vrši po (μ+ μ)-strategiji.

Genetski algoritmi (Genetic Algorithms, GA) se uglavnom koriste prilikom diskretnih optimizacijskih problema i onih koji se na to mogu svesti. Ne karakterizira ga brzina izvođenja, ali se uz manje izmjene može primijeniti na širok skup problema.

Osnovni GA koristi binarni vektor (niz bitova)  za prikaz jedinke i uniformno križanje. Mutacija se svodi na promjenu bitova na nekim pozicijama, pri čemu je vjerojatnost promjene pojedinog bita konstantna. U selekciji se jednostavno svi roditelji zamjene sa djecom.

Složeniji verzije GA imaju izmijenjene načine križanja, mutacije i selekcije. Ipak, većina funkcija u algoritmu i dalje ostaje stohastička što održava populaciju raznolikom i sprječava prebrzu konvergenciju k suboptimalnom rješenju.

Genetsko programiranje (Genetic Programing, GP) je karakteristično po tome što rješenje nekog problema pokušava pronaći tako da stvara program koji će ga riješiti. Da bi se to postiglo potrebna je velika populacija, a rješavanje problema je relativno sporo. Za prikaz jedinki je pogodno upotrijebiti strukturu graf. Mutacije su moguće, ali nisu potrebne. Mutacijama se mijenja struktura grafa (promjena čvorova), dok se križanjem izmjenjuju podstabla. Zbog načina rješavanja problema, GP se primjenjuje u područjima strojnog učenja.

Primjer 2.6  Problem 8 kraljica

U zemlji Kvadrat izbili su veliki nemiri jer kralj nije uspio primiriti svojih 8 kraljica. Stoga je on odlučio podijeliti zemlju na 64 jednaka polja. Zloj vještici naredio je da začara kraljice tako da vide samo polja koja su ispred, iza , lijevo, desno i dijagonalno od polja u kojem obitavaju. Kralj je shvatio da se kraljice neće napadati i izazivati nerede ako jedna drugu ne vide. Stoga je naredio dvorskoj ludi da rasporedi kraljice po poljima tako da se međusobno ne vide. Zbog svog dobrog poznanstva sa Darwinom, dvorska luda je pokušala pronaći rješenje pomoću EA-a. Kraljice je poredala u poredak i tom je poretku odlučila pridijeliti populaciju uređenih osmorki prvih osam prirodnih brojeva sa sljedećim značenjem: m-ta kraljica se smješta u m-tu kolonu u red zadan m-tim članom najbolje uređene osmorke. Dakle, fenotip je konfiguraciju ploče i kraljica, dok je genotip permutacije uređene osmorke (jedinka je pojedina osmorka). Luda dobiva onoliko kaznenih bodova od kralja koliko se kraljica međusobno vidi. Više kaznenih bodova znači manju mirovinu, pa je ludi cilj minimizirati te kaznene bodove. Funkcija dobrote će očito biti negativna vrijednost broja kaznenih bodova (jer želi minimizirati kaznene bodove). Luda izabire roditelje tako da nasumično izabere osam jedinki, a iz njih izvuče par najboljih roditelja koji će se križati. Način na koji luda obavlja križanje luda je prikazano na Slici 2.24. Ukoliko

img32

Slika 2.24 Mutacija i rekombinacija

se prilikom križanja neki broj ponavlja u uređenoj osmorci, luda ga zamjeni s onim kojeg nema u uređenoj osmorci. Križanjem dvaju roditelja nastaju dva djeteta. Mutacije radi tako da obavi zamjenu mjesta dvaju brojeva u osmoci. Selekciju vrši dodavanjem dva djeteta umjesto dva roditelja koji imaju manju funkciju dobrote u odnosu na sve roditelje i oba djeteta.

Nakon obavljenog posla dvorska luda se prestaje „ludirati” i odlazi u zasluženu mirovinu [24, 25, 26, 27]..