Umjetna inteligencija

Evolucijsko racunarstvo

doc. dr. sc. Marko Cupic

Copyright c© 2019. Marko Cupic, v0.2

IZDAVAC

JAVNO DOSTUPNO NA WEB STRANICI JAVA.ZEMRIS.FER.HR/NASTAVA/UI

Ovaj materijal nastao je na temelju knjige "Prirodom inspirirani optimizacijski algoritmi" (autor:Marko Cupic), kao popratni materijal na kolegiju Umjetna inteligencija.

Licensed under the Creative Commons Attribution-NonCommercial 3.0 Unported License (the“License”). You may not use this file except in compliance with the License. You may obtain acopy of the License at http://creativecommons.org/licenses/by-nc/3.0. Unless requiredby applicable law or agreed to in writing, software distributed under the License is distributed on an“AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.See the License for the specific language governing permissions and limitations under the License.

Prvo izdanje, lipanj 2016.

Sadržaj

1 Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1 Pregled algoritama evolucijskog racunanja 81.2 Najbolji optimizacijski algoritam 91.3 Optimizacija 10

2 Genetski algoritam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1 Motivacijski primjer 132.1.1 Evolucija Robbyjevog mozga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Primjena na numericku optimizaciju 192.3 Dvije vrste genetskih algoritama 222.4 Utjecaj operatora 232.4.1 k-turnirska selekcija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4.2 Proporcionalna selekcija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.5 Binarna reprezentacija 27

3 Mravlji algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1 Pojednostavljeni matematicki model 333.2 Algoritam Ant System 36

4 Kamo dalje? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Bibliografija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Knjige 41

Clanci 41

Konferencijski radovi i ostalo 42

Indeks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

1. Uvod

Razvojem racunarstva i povecanjem procesne moci racunala, ljudi su poceli rješavati izuzetnokompleksne probleme koji su do tada bili nerješivi – i to naprosto tehnikom grube sile (engl. brute-force, koristi se još i termin iscrpna pretraga), tj. pretraživanjem cjelokupnog prostora rješenja.Uobicajeni algoritmi koji se koriste u tu svrhu su algoritam pretraživanja u širinu, algoritampretraživanja u dubinu te algoritam iterativnog pretraživanja u dubinu (sve smo ih obradili naovom kolegiju). Svi navedeni algoritmi spadaju u algoritme slijepog pretraživanja s obzirom dane uzimaju u obzir nikakve informacije vezane uz problem koji rješavaju. Kako bi se pretragaubrzala, razvijena je i porodica algoritama usmjerenog pretraživanja, u koju spadaju algoritmi kojisu prilikom pretraživanja vodeni informacijama o problemu koji rješavaju i procjeni udaljenostiod trenutnog pa do ciljnog rješenja koje se traži. Ove se informacije uzimaju u obzir kako bi sepretraga usmjerila i time prije završila. Primjer ovakvog algoritma je algoritam A∗ koji smo takoderobradili.

S obzirom da su danas racunala ekstremno brza, nije rijetka situacija da se njihovom uporabomu jednoj sekundi mogu istražiti milijuni ili cak milijarde potencijalnih rješenja, i time vrlo brzopronaci ono najbolje. Ovo, dakako, vrijedi samo ako smo jako sretni, pa rješavamo problem koji segrubom silom, odnosno uporabom upravo spomenutih algoritama, dade riješiti. Nažalost, postojicitav niz problema koji ne spadaju u ovu kategoriju; spomenimo samo neke od njih.

Problem trgovackog putnika (engleski termin je Traveling sales-person problem, odnosno kraceTSP) definiran je ovako: potrebno je pronaci redoslijed kojim trgovacki putnik mora obici svegradove, a da pri tome niti jedan ne posjeti više puta, te da ukupno prevali najmanje kilometara. Nakraju, trgovacki se putnik mora vratiti u onaj grad iz kojeg je krenuo. Danas je poznato da ovajnaoko trivijalan problem pripada razredu N P-teških problema. N P-teški problemi pripadajuu vrstu problema za koje danas još uvijek nemamo efikasnih algoritama kojima bismo ih mogliriješiti. Uzrok tome je, dakako, ekstremna složenost ove vrste problema. Kako bismo ilustriralisloženost problema trgovackog putnika, napisan je jednostavan program u programskom jezikuJava koji ga rješava tehnikom grube sile, i potom je napravljeno mjerenje za probleme od 3 do 13gradova. Rezultate prikazuju slike 1.1 i 1.2.

Eksperiment je napravljen na racunalu s AMD Turion 64 procesorom na 1.8 GHz i s 1 GB

6 Poglavlje 1. Uvod

Slika 1.1: Ovisnost vremena pretraživanja kod iscrpne pretrage o broju gradova kod TSP-a

Slika 1.2: Ovisnost vremena pretraživanja kod iscrpne pretrage o broju gradova kod TSP-a uzlogaritamsku skalu po ordinati

7

radne memorije. Vrijeme potrebno za rješavanje problema s 12 gradova iznosilo je približno 12.3sekunde, dok je za 13 gradova bilo potrebno poprilici 2.5 minute. Ocekivano vrijeme rješavanjaproblema s 14 gradova je oko pola sata, za 15 gradova oko 7.6 sati, dok bi za 16 gradova trebalooko 4.7 dana.

Detaljnijom analizom ovog problema te samih podataka eksperimenta lako je utvrditi da jesloženost problema faktorijelna, pa je jasno da je problem koji se sastoji od primjerice 150 gradovaprimjenom tehnike grube sile prakticki nerješiv. Faktorijelna složenost naivnog nacina rješavanjaovog problema proizlazi iz cinjenice da se jedno rješenje problema može predstaviti kao jednapermutacija redosljeda obilaska gradova. Problem koji tada rješavamo jest pronalazak optimalnepermutacije, koji, ako ga rješavamo tako da ispitamo svaku mogucu permutaciju pa potom odabe-remo optimalnu, ima faktorijelnu složenost (jer toliko ima permutacija). Medutim, za ovaj konkretanproblem pokazano je da nema potrebe ispitivati baš svaku permutaciju rješenja; algoritmom koji setemelji na dinamickom programiranju ovaj problem moguce je rješiti u eksponencijalnoj složenosti(konkretno, u složenosti O(n2 ·2n)). Iako je ovo bitno prihvatljivije od faktorijelne složenosti, jasnoje da su takvi pristupi i dalje neupotrebljivi za vece primjerke problema. U teoriji grafova, problemtrgovackog putnika odgovara pronalasku Hamiltonovog ciklusa u grafu, za koji je pokazano da jeN P-potpun problem.

Probleme slicnog tipa u svakodnevnom životu neprestano susrecemo. Evo još dva problemavezanih uz akademski život.

� Primjer 1.1 — Rasporedivanje nerasporedenih studenata u grupe za predavanja. Razmo-trimo problem koji se javlja naknadnim upisom studenata na predmete, nakon što je vec napravljenraspored (redovno upisanih) studenata po grupama. Velicina grupe za predavanje ogranicena jedodijeljenom prostorijom u kojima se izvode predavanja. Nerasporedene studente potrebno je takorazmjestiti da grupe ne narastu iznad maksimalnog broja studenata (odredenog prostorijom), te dase istovremeno osigura da student nema preklapanja s drugim dodijeljenim obavezama. Primjerice:neka imamo 50 studenata koji su ostali nerasporedeni na 5 kolegija, i neka u prosjeku svaki kolegijima 4 grupe u kojima se održavaju predavanja. Potrebno je za prvog studenta i njegov prvi kolegijprovjeriti 4 grupe, pa za njegov drugi kolegij 4 grupa, itd. Za sve studente to ukupno daje:

(4 ·4 ·4 ·4 ·4) · (4 ·4 ·4 ·4 ·4) · · · · · (4 ·4 ·4 ·4 ·4) = 45 ·45 · · · · ·45 = 4550 ≈ 5 ·1034.

Kada bismo imali racunalo koje bi jednu kombinaciju moglo provjeriti u jednoj nanosekundi, zaprovjeru svih kombinacija trebali bismo 1.59 ·1018 godina! Kako bismo bolje shvatili koliko je ovovremena, spomenimo samo da je svemir star oko 1.37 ·1010 godina. �

� Primjer 1.2 — Izrada rasporeda meduispita. Razmotrimo problem u kojem je unaprijeddefiniran skup raspoloživih termina u kojima se mogu održati ispiti, kapaciteti termina, skupkolegija koji imaju ispite, te popis studenata po kolegijima. Jednostavnija varijanta problemazahtjeva pronalazak takvog rasporeda kolegija po terminima uz koji ce svi kolegiji održati svojeispite, i u kojem ne postoji student koji u istom terminu piše više od jednog ispita. Teža varijantaproblema dodatno traži da svaki student izmedu dva ispita ima što je moguce više slobodnogvremena. Uzmimo kao ilustraciju problem izrade rasporeda meduispita na Fakultetu elektrotehnikei racunarstva Sveucilišta u Zagrebu, u ljetnom semestru akademske godine 2008/2009. Broj terminabio je 40 a broj kolegija 130. Za prvi kolegij možemo uzeti jedan od 40 termina, za drugi kolegijjedan od 40 termina, ... Ukupno imamo 40130 kombinacija. Opisani problem je 10174 puta složenijiod prethodno opisanog problema rasporedivanja nerasporedenih studenata. Za jesenski ispitni rok uakademskoj godini 2011/2012 brojke su bile još vece: u rasporedivanje je ušlo gotovo 200 kolegija.�

Na srecu, optimalno rješenje nam cesto nije nužno; obicno smo zadovoljni i s rješenjem koje jedovoljno dobro.

8 Poglavlje 1. Uvod

Definicija 1.0.1 — Heuristika. Algoritme koji pronalaze rješenja koja su zadovoljavajucedobra, ali ne nude nikakve garancije da ce uspjeti pronaci optimalno rješenje, te koji imajurelativno nisku racunsku složenost (tipicno govorimo o polinomijalnoj složenosti) nazivamopribližni algoritmi, heuristicke metode, heuristicki algoritmi ili jednostavno heuristike. Dijelimoih na konstrukcijske algoritme te algoritme koji koriste lokalnu pretragu.

Konstrukcijski algoritmi rješenje problema grade dio po dio (cesto bez povratka unatrag) svedok ne izgrade kompletno rješenje. Tipican primjer je algoritam najbližeg susjeda (engl. nearest-neighbor procedure). Na problemu trgovackog putnika, ovaj algoritam zapocinje tako da nasumiceodabere pocetni grad, i potom u turu uvijek odabire sljedeci najbliži grad.

Algoritmi lokalne pretrage rješavanje problema zapocinju od nekog pocetnog rješenja kojepotom pokušavaju inkrementalno poboljšati. Ideja je da se definira skup jednostavnih izmjena kojeje moguce obaviti nad trenutnim rješenjem, cime se dobivaju susjedna rješenja. U najjednostavnijojverziji, algoritam za trenutno rješenje pretražuje skup svih susjednih rješenja i bira najboljeg susjedakao novo trenutno rješenje (tada govorimo o metodi uspona na vrh, ili engl. hill-climbing method).Ovo se ponavlja tako dugo dok kvaliteta rješenja raste.

U današnje doba posebno su nam zanimljive metaheuristike.

Definicija 1.0.2 — Metaheuristika. Metaheuristika je skup algoritamskih koncepata kojikoristimo za definiranje heuristickih metoda primjenjivih na širok skup problema. Možemo recida je metaheuristika heuristika opce namjene ciji je zadatak usmjeravanje problemski specificnihheuristika prema podrucju u prostoru rješenja u kojem se nalaze dobra rješenja.

Primjeri metaheuristika su simulirano kaljenje, tabu pretraživanje, algoritmi evolucijskog racunanjai slicni. Pri tome ih možemo podijeliti u dvije velike porodice algoritama: algoritmi koji radenad jednim rješenjem (gdje spadaju algoritam simuliranog kaljenja te algoritam tabu pretrage) tena populacijske algoritme koji rade sa skupovima rješenja (gdje spadaju algoritmi evolucijskogracunanja).

Osvrnimo se ovdje ukratko i na podskup algoritama evolucijskog racunanje poznat pod nazivomevolucijski algoritmi. Danas ga uobicajeno dijelimo na cetiri podpodrucja: genetske algoritme,genetsko programiranje, evolucijske strategije te evolucijsko programiranje. Zajednicka im je idejada rade s populacijom rješenja nad kojima se primjenjuju evolucijski operatori (selekcija, križanje,mutacija, zamjena) cime populacija iz generacije u generaciju postaje sve bolja i bolja.

Velika skupina algoritama koji se dobro nose s opisanim teškim problemima nastala je pro-ucavanjem procesa u prirodi. Priroda je oduvijek bila inspiracija covjeku u svemu što je radio. Ito ne bez razloga – prirodni procesi optimiraju život u svakom njegovom segmentu vec preko 4milijarde godina. Proucavanjem ovih procesa i nacina na koji živa bica danas rješavaju problemeznanost je došla do niza uspješnih tehnika kojima je moguce napasti prethodno opisane probleme.U nastavku cemo opisati dvije takve tehnike: genetski algoritam te optimizaciju temeljenu namravljem algoritmu.

1.1 Pregled algoritama evolucijskog racunanja

U prethodnom odjeljku kratko smo se osvrnuli na evolucijske algoritme. No kako izgleda širaslika?

Evolucijsko racunanje je grana umjetne inteligencije koja se, najvecim dijelom, bavi rješava-njem optimizacijskih problema. To je podrucje u razvoju vec više od pola stoljeca: zacetci sežu ukasne 50.-e. Evolucijsko racunanje danas obuhvaca bogat skup raznorodnih algoritama od kojihcemo se u ovom poglavlju osvrnuti na nekoliko. Evolucijsko racunanje može se podijeliti u trigrane: evolucijske algoritme, algoritme rojeva te ostale algoritme. Ova podjela kao i odabranialgoritmi prikazani su na slici 1.3.

1.2 Najbolji optimizacijski algoritam 9

Slika 1.3: Podjela evolucijskog racunanja na glavne grane. Uz svaku granu prikazani su i odabranialgoritmi.

Podrucje evolucijskog racunanja ujedno pripada i u podrucje metaheuristika – heuristikanamijenjenih vodenju problemski specificnijih heuristika u pokušaju da se pronade potprostor uprostoru pretraživanja koji sadrži dobra rješenja.

U evolucijske algoritme danas uobicajeno ubrajamo evolucijske strategije, evolucijsko progra-miranje, genetski algoritam te genetsko programiranje.

U algoritme rojeva ubrajamo mravlje algoritme, algoritam roja cestica, algoritme pcela i druge.Granu ostali algoritmi cini još niz drugih algoritama koji ne pripadaju u prethodne dvije

grane. Od znacajnijih algoritama tu svakako pripadaju umjetni imunološki algoritmi, algoritamdiferencijske evolucije te algoritam harmonijske pretrage.

1.2 Najbolji optimizacijski algoritamNakon ovog kraceg uvoda, evo i zanimljivog pitanja: koji je od spomenutih optimizacijskih algo-ritama najbolji?. Ovo je važno pitanje, jer ako ga odgovorimo, nadamo se da ce nam odgovoromoguciti da se fokusiramo na samo jedan – onaj najbolji, i zaboravimo na sve ostale. To bi svakakobila znacajna ušteda vremena. A evo i još jedno pitanje: mogu li se metaheuristicki algoritmi izporodice algoritama evolucijskog racunanja uspješno koristiti za rješavanje svih problema?

Dodatno, postavlja se i pitanje je li dobro koristiti nasumicnu pretragu, te da li, kada i u kojojmjeri uvesti dodatne informacije u algoritam? Uporaba dodatne informacije u postupku pretraživa-nja cini razliku izmedu slijepog i usmjerenog pretraživanja. U nedostatku bilo kakvih smjernica,algoritmi mogu samo nasumicno generirati moguca rješenja ili pak nasumicno modificirati trenutnarješenja. Uvodenjem dodatnih informacija mogli bismo pomisliti da ce algoritmi uvijek raditi bolje(ma što bolje znacilo). Medutim, uvodenjem dodatnih informacija pretraga se fokusira cime seefektivno smanjuje prostor pretraživanja; to u nekim slucajevima može djelovati nepovoljno napostupak pretraživanja (primjerice, u prisustvu velikog broja lokalnih ekstrema gdje ce algoritamostati trajno zarobljen u lokalnom optimumu jer je previše fokusiran). S druge pak strane, akoproblem nije takve vrste, fokusiranje pretrage može dovesti do znacajnog skracivanja vremenapotrebnog za pronalazak dovoljno dobrog (ili cak optimalnog) rješenja.

Razmišljajuci dalje u tom smjeru, vratimo se na pocetno pitanje: koji je algoritam pretraživanjaonda najbolji? Na našu srecu (ili ne), danas znamo odgovor na ovo pitanje. Wolpert i Macready suu svojim radovima dokazali da nema najboljeg algoritma, što je poznato kao teorem no-free-lunch.Dapace, dokazali su da su svi algoritmi pretraživanja – upravo prosjecno dobri:

All algorithms that search for an extremum of a cost function perform exactly the same,

10 Poglavlje 1. Uvod

according to any performance measure, when averaged over all possible cost functions.In particular, if algorithm A outperforms algorithm B on some cost functions, thenloosely speaking there must exist exactly as many other functions where B outperformsA.

No što to znaci odnosno kakve to ima posljedice? Poruka je jasna: za razlicite probleme razlicitice algoritmi biti "najbolji". Što više algoritama znamo, i što više razumijemo njihovo ponašanje inacin rada, vece su nam šanse da odaberemo pravi algoritam za problem koji pokušavamo riješiti.U ovom tekstu stoga cemo dati pregled dva algoritma; zainteresiranog se citatelja upucuje da daljesamostalno istraži druge pristupe, ili da iskoristi ponudu koju FER nudi kroz, primjerice, vještinuRješavanje optimizacijskih problema algoritmima evolucijskog racunanja u Javi.

1.3 OptimizacijaAlgoritme o kojima govorimo u ovom tekstu koristimo za rješavanje optimizacijskih problema.Prethodno opisani problemi rasporedivanja nerasporedenih studenata u grupe za predavanja teizrade rasporeda meduispita mogu se svesti na optimizacijske probleme na nacin da se definirafunkcija koja mjeri koliko je trenutno rješenje dobro. Potom puštamo algoritam da predlaže novarješenja odnosno da korigira i kombinira trenutna, a sve kako bi došao do rješenja koja su bolja.

Definicija 1.3.1 — Optimizacija. Optimizaciju cemo definirati kao postupak pronalaženjanajboljeg rješenja problema. Rješenje ce pri tome imati definiranu funkciju dobrote (engl.fitness-function) koju ce optimizacijski postupak maksimizirati, ili funkciju kazne (cijenu; engl.cost-function) koju ce optimizacijski postupak minimizirati.

Problemi koje optimiramo krecu se izmedu dvije krajnosti. Mogu biti:• kombinatoricki - koji su definirani nad diskretnom domenom koja može ali cak i ne mora

imati uredaj izmedu elemenata (usporedite primjerice domenu cijelih brojeva i cinjenicuda je 1 manje od 5 s domenom tropskog voca i cinjenicom da ne možemo reci je li bananamanja, veca ili jednaka ananasu);• kontinuirani - koji su definirani nad kontinuiranim domenama poput realnih brojeva, kom-

pleksnih brojeva i slicno, i gdje vec ta cinjenica povlaci beskonacan prostor pretraživanjakoji grubom silom nikada ne možemo pretražiti.

U praksi, cesto se susrecemo i s problemima koji su kombinacija ovih krajnosti - neki od elemenataproblema su diskretni a neki kontinuirani.

Optimizacijske probleme možemo promotriti i kroz prizmu problema pretraživanja prostorastanja o kojima smo vec ucili. Prisjetimo se: problem pretraživanja prostora stanja svodi se naproblem pronalaska puta od pocetnog stanja s0 do ciljnog stanja s f koristeci dozvoljene poteze(odnosno funkciju sljedbenika). Prisjetite se samo problema slagalice.

Jednu znacajnu podvrstu problema pretraživanja prostora stanja cine problemi zadovoljavanjaogranicenja.

Definicija 1.3.2 — Problem zadovoljavanja ogranicenja. Problem zadovoljavanja ograni-cenja (engl. Constraint Satisfaction Problem) je vrsta problema pretraživanja prostora stanjakod koje put od pocetnog do konacnog stanja nije bitan. Rješenje je iskljucivo konacno stanje.

Uobicajena je situacija da kod problema zadovoljavanja ogranicenja pocetna stanja generiramopotpuno slucajno i tijekom postupka pretraživanja ne pamtimo roditeljska stanja - radimo iskljucivos jednim ili populacijom "trenutnih" stanja koje mjerimo funkcijom dobrote ili kazne. Postojanjeciljnog stanja takoder je cesto nepoznato. Primjerice, vratimo se na problem izrade rasporedameduispita koji pripada u ovu vrstu problema. Definirajmo ispitni predikat tako da kao ciljno stanjeproglasi svaki raspored u kojem niti jedan student nije rasporeden na dva meduispita u isto vrijeme.

1.3 Optimizacija 11

Uzmemo li u obzir što je svaki od studenata upisao, koliko termina imamo na raspolaganju, kolikokolegija te koliki su raspoloživi kapaciteti dvorana, u opcem slucaju ne možemo znati postoji liuopce ciljno stanje (odnosno raspored bez preklapanja). Stoga je uobicajeno da tijekom provodenjaoptimizacijskog postupka pratimo kvalitetu rješenja i da isti prekinemo unatoc cinjenici da nijepronašao ciljno stanje (ali je neko za koje smo procijenili da je iskoristivo).

Problemi zadovoljavanja ogranicenja mogu definirati:• jedno ili više cvrstih ogranicenja (engl. hard constraints) te• jedno ili više mekih ogranicenja (engl. soft constraints).

Definicija 1.3.3 — Cvrsta ogranicenja. Cvrsta ogranicenja su ogranicenja koja nužno morajubiti ispunjena da bi rješenje bilo prihvatljivo.

Primjerice, kao cvrsto ogranicenje mogli bismo definirati da meduispiti dvaju predmeta s prvegodine preddiplomskog studija ne mogu ici u istom ili uzastopnim danima. U tam slucaju, svakipredloženi raspored koji ovo ne bi imao zadovoljeno automatski bi bio neprihvatljiv, neovisno osvim njegovim drugim karakteristikama.

Definicija 1.3.4 — Meka ogranicenja. Meka ogranicenja su ogranicenja koja definirajupoželjna (ili nepoželjna) svojstva rješenja.

Primjerice, bilo bi dobro da za svakog studenta vrijedi da mu je razmak izmedu uzastopnihmeduispita barem dva dana. Uzmemo li u obzir populaciju od 4000 studenata, meko ogranicenjenam omogucava da definiramo relativan odnos kvalitete dvaju rješenja: bolje je ono kod kojeg3900 studenata nema prekršeno navedeno meko ogranicenje od rješenja kod kojega to nema 3000studenata.

U slucaju da mekih ogranicenja ima više, u najjednostavnijem slucaju optimizacijski ce ihpostupak na odredeni nacin agregirati u jednu kumulativnu mjeru na temelju koje ce potom uspore-divati rješenja. Moguca su i druga rješenja koja vode na višekriterijsku odnosno mnogokriterijskuoptimizaciju (engl. multi-objective optimization vs. many-objective optimization).

2. Genetski algoritam

L. J. Fogel, A. J. Owens i M. J. Walsh stvorili su 1966. evolucijsko programiranje, I. Rechenberg1973. i H.-P. Schwefel 1975. evolucijske strategije, a H. J. Holland 1975. genetski algoritam.Paralelno tome, tekao je i razvoj genetskog programiranja koji je 1992. popularizirao J. R. Koza.Inspiracija za razvoj svih navedenih pristupa došla je proucavanjem Darwinove teorije o postankuvrsta.

Darwin teoriju razvoja vrsta temelji na 5 postavki:1. potomaka uvijek ima više no što je potrebno,2. velicina populacije je približno stalna,3. kolicina hrane je ogranicena,4. kod vrsta koje se seksualno razmnožavaju, nema identicnih jedinki vec postoje varijacije te5. najveci dio varijacija prenosi se nasljedem.

Iz navedenoga slijedi da ce u svakoj populaciji postojati borba za preživljavanje: ako potomaka imaviše no što je potrebno a kolicina hrane je ogranicena, sve jedinke nece preživjeti. Pri tome ce onebolje i jace imati vecu šansu da prežive i dobiju priliku stvarati potomke. Pri tome su djeca roditeljau velikoj mjeri odredena upravo genetskim materijalom svojih roditelja, no nisu ista roditeljima –postoji odredeno odstupanje.

Genetski algoritam jedan je od algoritama stvorenih za rješavanje optimizacijskih problema,a koji izravno utjelovljuje navedene postavke. Kroz tekst koji slijedi upoznat cemo se s idejomgenetskog algoritma te uvidjeti da ne postoji "jedan" genetski algoritam vec da je navedene postavkemoguce implementirati na niz razlicitih nacina cime dobivamo razlicite inacice genetskog algoritma.Kao motivacijski primjer poslužit ce nam zadatak razvoja upravljackog podsustava jednostavnogrobota.

2.1 Motivacijski primjerU svojoj knjizi Complexity: A Guided Tour, americka znanstvenica Melanie Mitchell daje vrlozgodan primjer koji cemo ovdje prikazati. Zamislimo zidovima ogradeni teren koji se sastoji odm×n ploca. Nakon održanog koncerta, na tom su terenu ostale porazbacane prazne boce vode.Pri tome se na svakoj ploci može zateci najviše jedna boca. Kako se koncerti redovno odvijaju,

14 Poglavlje 2. Genetski algoritam

0

1

2

3

4

5

6

7

8

9

0 1 2 3 4 5 6 7 8 9

Slika 2.1: Svijet robota Robbyja

umjesto da placamo covjeka za cišcenje terena, želimo razviti robota koji ce za nas obavljati tajposao. Primjer jednog takvog terena dimenzija 10×10 ploca prikazan je na slici 2.1. Robot senalazi u gornjem lijevom uglu (ploca 0,0) a popunjenost terena bocama je 30% (od 100 ploca, nanjih 30 se nalazi boca).

Robot kroz dostupne senzore od okoline može primiti sljedece informacije:• što se nalazi na ploci na kojoj je robot,• što se nalazi jednu plocu iznad ploce na kojoj je robot,• što se nalazi jednu plocu ispod ploce na kojoj je robot,• što se nalazi jednu plocu desno od ploce na kojoj je robot te• što se nalazi jednu plocu lijevo od ploce na kojoj je robot.

Senzor pri tome može dojaviti da je promatrana ploca prazna, da se na njoj nalazi boca ili pak dase radi o zidu. Stanje ploca koje su dijagonalne trenutnoj te stanje ploca koje nisu susjedne plocina kojoj je robot senzori ne percipiraju. Robot kojim raspolažemo takoder ne posjeduje nikakvumemoriju - robot ne može zapamtiti da je u nekom ranijem trenutku vec vidio na nekoj ploci bocu.U tom smislu, akcije koje robot poduzima u potpunosti su reaktivne: temeljem ulaza koje senzori uodredenom trenutku šalju, robot mora odluciti koju ce akciju poduzeti.

Upravljacki podsustav robota omogucava izvodenje sedam razlicitih akcija, kako slijedi.1. Ne radi ništa.2. Sagni se i pokupi bocu s ploce na kojoj stojiš.3. Otidi na susjednu plocu koja je iznad ploce na kojoj stojiš.4. Otidi na susjednu plocu koja je ispod ploce na kojoj stojiš.5. Otidi na susjednu plocu koja je desno od ploce na kojoj stojiš.6. Otidi na susjednu plocu koja je lijevo od ploce na kojoj stojiš.7. Otidi na slucajno odabranu susjednu plocu.

2.1 Motivacijski primjer 15

U slucaju da se robot odabranom akcijom sudari sa zidom, trenutna pozicija mu se ne mijenja (nemože se popesti na zid).

Zadatak koji želimo riješiti je sljedeci: za svaku mogucu percepciju koju robot prima potrebnoje odrediti akciju koju robot treba poduzeti kako bi u ogranicenom broju akcija pokupio što vecibroj boca. Naravno, idealno bi bilo da robot uspije pokupiti sve boce i tako ocisti teren. Za terendimenzija 10×10 broj akcija cemo ograniciti na 150.

S obzirom da je za svaku mogucu percepciju robota (odnosno razlicitu situaciju u kojoj serobot može zateci) potrebno odrediti akciju koju ce robot poduzeti, idemo najprije odrediti kolikorazlicitih percepcija može dobiti Robby? Kao pomoc razmotrimo sliku 2.2.

0 2 1 0 2

Trenutna

Iznad

Ispod

Desno

Lijevo

01

012

012

012

012

Ništa

Boca

Zid

Gledano kao ternarni broj:010 do 16110

Trenutna percepcija

0*34+2*33+1*32+0*31+2*30=6510

Slika 2.2: Percepcija robota Robbyja

Robby raspolaže s pet senzora koji mu govore što se nalazi na ploci na kojoj je i on sam te naizravno susjednim plocama. Stoga možemo razmišljati na sljedeci nacin. Na svakoj od tih pet plocamože biti ništa, boca ili zid. Broj mogucih kombinacija tada bi bio 3×3×3×3×3 = 35 = 243.Medutim, stvarni broj mogucih percepcija nešto je manji. Primjerice, nemoguce je da se Robbynalazi na zidu - stoga na trenutnoj ploci imamo samo dvije mogucnosti: ili je prazna ili sadrži bocu.Time je broj mogucih kombinacija 2× 3× 3× 3× 3 = 2 · 34 = 162. Mogli bismo iskljuciti jošnekoliko situacija koje se na pravokutnom terenu koji je barem dimenzija 2×2 ne mogu dogoditi:da je Robby okružen s tri ili cetiri zida. Medutim, necemo to uciniti jer uz 162 percepcije imamovrlo jednostavan nacin kako svakoj od tih percepcija pridijeliti jedan jedinstven redni broj. Slika 2.2prikazuje ideju: tri moguce situacije jedne ploce (ništa, boca, zid) kodirat cemo jednom ternarnomznamenkom. Citava Robbyjeva percepcija tada je zapisiva jednim 5-znamenkastim ternarnimbrojem cija vrijednost (u dekadskom sustavu) ide od 0 do 161.

Dodijelimo li i svakoj akciji redni broj (0: ne radi ništa, pa sve do 6: otidi na slucajno odabranususjednu plocu), postavljeni zadatak tada se svodi na odredivanje jednog 162-komponentnogvektora cijelih brojeva, ciji je element na poziciji i broj akcije koju robot treba poduzeti kada krozsenzore dobiva percepciju i. Ovo je ilustrirano na slici 2.3, gdje je akcija za svaku percepcijupostavljena na "Ne radi ništa" osim za percepciju 0 (prisjetimo se: situacija u kojoj robot stojina praznoj ploci i susjedne ploce su takoder prazne) za koju je podešena akcija 6 (pomakni se naslucajno odabranu susjednu plocu).

Pretpostavimo da problem želimo riješiti na sljedeci nacin: isprobat cemo kako se robot ponašaza svaku moguci konfiguraciju mozga i potom cemo odabrati najbolju (onu uz koju robot prikupljanajveci broj boca uz zadani ograniceni broj koraka). Koliko konfiguracija moramo isprobati? Jednakonfiguracija mozga je 162-komponentni vektor. Svaki njegov element može biti postavljen najednu od 7 vrijednosti (redni broj akcije). Stoga je broj razlicitih konfiguracija jednak:

7 ·7 ·7 ·7 · · ·7 ·7 ·7 = 7162.

16 Poglavlje 2. Genetski algoritam

0 0 0 0 6

4 3 2 1 0

0123456

0123456

0123456

0123456

0123456

Ne radi ništa

Sagni se i pokupi bocu

Otiđi iznad

"Mozak" robota Robby

0 0 0 0 0

161 160 159 158 157

0123456

0123456

0123456

0123456

0123456

Otiđi ispod

Otiđi desno

Otiđi lijevo

Otiđi u slučajnom smjeru

Slika 2.3: Jedna moguca konfiguracija "mozga" robota Robbyja

Ako je za provjeru "kvalitete" jednog mozga potrebna 1 µs, za provjeru kvalitete 7162 trebat cemo10123 godina odnosno 10113 starosti svemira. Ovo jednostavno razmatranje upucuje da cemo dorješenja morati nekim drugim putem.

2.1.1 Evolucija Robbyjevog mozga

Umjesto iscrpne pretrage, primjenit cemo Darwinovu ideju evolucije. Napisat cemo program koji cekrenuti od populacije slucajno generiranih mozgova (doista, generatorom slucajnih brojeva generiratcemo svih 162 komponente svakog od mozga iz populacije). Zatim cemo definirati funkcijudobrote koja ce vrednovati kvalitetu mozga. Tom cemo funkcijom vrednovati svaki od mozgovau populaciji. Potom cemo ponavljati jednostavan postupak: iz populacije cemo posredstvomslucajnog mehanizma odabrati tri mozga; kombiniranjem dva bolja (prema dogovorenoj funkcijidobrote) stvorit cemo novi mozak i taj cemo umetnuti u populaciju na mjesto treceg odabranog(najlošijeg od izabrana tri) mozga, i to samo ako novi mozak nije nekvalitetniji od tog treceg.Pseudokod ovog postupka dan je u nastavku.

Pseudokod 2.1.1 — Eliminacijski genetski algoritam.

• Generiramo slucajnu populaciju mozgova od VEL_POP jedinki; evaluiramo svaki.• Ponavljamo dok nije kraj:

– Biramo slucajno tri jedinke– Dijete = Križamo bolje dvije + Mutacija– Vrednujemo dijete i ubacimo ga na mjesto trece ako nije lošije od nje

Opisani postupak poznat je kao Troturnirski genetski algoritam a koristi se još i naziv Elimi-nacijski genetski algoritam odnosno potpunije Eliminacijski genetski algoritam s jednostavnomtroturnirskom selekcijom. U jednostavnijoj inacici, stvoreno dijete uvijek se ubacuje na mjestotrece-odabrane jedinke, neovisno o odnosu njihovih dobrota.

Križanjem dvaju roditelja nastaje dijete koje dio genetskog materijala preuzima od jednogroditelja a dio od drugog. Postoji niz nacina na koje se to može ostvariti, a tipicni primjeri suuniformno križanje te križanje s jednom tockom prijeloma. Kod uniformnog križanja za svaki segen (u našem slucaju to je akcija za pojedinu percepciju) posredstvom slucajnog mehanizma birahoce li biti preuzet od jednog ili od drugog roditelja. Slika 2.4 ilustrira ovu vrstu križanja.

Križanje s jednom tockom prijeloma bira poziciju gena na kojoj cijepa oba roditelja. Potomstvara dijete tako da od prvog roditelja uzme gene do tocke prijeloma a od drugog gene nakon tockeprijeloma. Drugo dijete moguce je izgraditi na analogni nacin: od drugog se roditelja uzimaju genido tocke prijeloma a od prvog nakon tocke prijeloma. Slika 2.5 ilustrira ovu vrstu križanja.

2.1 Motivacijski primjer 17

2 3 3 5 6

4 3 2 1 0

Roditelj 1: 2 0 3 5 1

161 160 159 158 157

4 1 4 6 5

4 3 2 1 0

Roditelj 2: 3 1 3 2 6

161 160 159 158 157

4 3 3 5 5

4 3 2 1 0

Dijete: 2 1 3 2 6

161 160 159 158 157

Slika 2.4: Provedba uniformnog križanja

2 3 3 5 6

4 3 2 1 0

Roditelj 1: 2 0 3 5 1

161 160 159 158 157

4 1 4 6 5

4 3 2 1 0

Roditelj 2: 3 1 3 2 6

161 160 159 158 157

4 1 4 6 5

4 3 2 1 0

Dijete 1: 2 0 3 2 6

161 160 159 158 157

2 3 3 5 6

4 3 2 1 0

Dijete 2: 3 1 3 5 1

161 160 159 158 157

Točka prijeloma: nakon trećeg gena

Slika 2.5: Provedba križanja s jednom tockom prijeloma

Mutaciju cemo provoditi na sljedeci nacin. Definirat cemo vjerojatnost mutacije gena kaovjerojatnost da cemo za neki konkretan gen napraviti mutaciju. Potom krecemo od prvog gena nadalje, i za svaki, sa zadanom vjerojatnošcu radimo njegovu mutaciju. Primjerice, ako je vjerojatnostmutacije gena jednaka 0.05, tada ce svaki od gena ima 5% šanse biti mutiran. Za gene za kojeutvrdimo da ih treba mutirati, njihovu vrijednost zamijenimo slucajno odabranom akcijom. Slika2.6 ilustrira ovako definiranu mutaciju, gdje je pod utjecajem mutacije došlo do promjene u trigena.

4 1 4 6 5

4 3 2 1 0

Jedinka: 3 1 3 2 6

161 160 159 158 157

4 1 1 6 5

4 3 2 1 0

Mutirana jedinka: 6 1 3 5 6

161 160 159 158 157

Slika 2.6: Provedba mutacije

Da bismo algoritam mogli isprobati, još je preostalo definirati funkciju dobrote. Postupit cemona sljedeci nacin.• Posredstvom slucajnog mehanizma stvorit cemo NS razlicitih terena, pri cemu ce svi imati

18 Poglavlje 2. Genetski algoritam

popunjenost bocama od pb.• Rad robota simulirat cemo u svakom od NS terena kroz zadani broj koraka NK i pri tome cemo

robotu davati nagradne ili kaznene bodove. Dobrotu ponašanja u jednom terenu definiratcemo kao ukupnu sumu bodova dobivenih na tom terenu. Konacnu dobrotu mozga postavitcemo na prosjecnu dobrotu ponašanja u svih NS terena.• Bodovanje radimo na sljedeci nacin.

– +10 bodova dodijelit cemo robotu svaki puta kada pokupi bocu.– −5 bodova dodijelit cemo robotu svaki puta kada se sagne da pokupi bocu na ploci na

kojoj nema boce.– −10 bodova dodijelit cemo robotu svaki puta kada se zabije u zid.

Ponašanje robota na više terena provjeravamo kako se ne bi dogodilo da se mozak robotaprilagodi jednoj specificnoj konfiguraciji terena. Medutim, kako je stvaranje novih terena dostaskupo, postupak možemo ubrzati tako da jednom stvoreni skup terena koristimo odreden brojiteracija (za ocjenu dobrote više od jednog mozga) pa ih tek tada nanovo generiramo.

Uvjet zaustavljanja algoritma može biti pronalazak dovoljno dobrog rješenja ili pak premašiva-nje zadanog broja iteracija.

Rad algoritma provjeren je uz sljedece parametre. Postotak popunjenosti bocama postavljenje na 0.35, dimenzije terena su 10×10, broj koraka (odnosno akcija) koje robot smije napravitije 150. Razvijamo mozak uporabom populacije od 50 jedinki, vjerojatnost mutacije gena je 0.02,vrednovanje robota provodimo na skupu od 20 svjetova i taj skup nanovo generiramo nakon svakih100 vrednovanih robota. Uvjet zaustavljanja je pronalazak mozga s kojim robot u prosjeku uspijedobiti 330 bodova (uz dane parametre, teorijski maksimum je 350).

Kretanje funkcije dobrote za jedno konkretno pokretanje algoritma prikazano je na slici 2.7.Šumovitost prikazane krivulje rezultat je periodicke promjene skupa terena na kojima se robotivrednuju. Uocite kako s vremenom dobrota rješenja postaje sve bolja i bolja.

-300

-200

-100

0

100

200

300

400

0 20000 40000 60000 80000 100000 120000

Dob

rota

Iteracija

Slika 2.7: Evolucija rješenja

Postupak je zaustavljen nakon iteracije 123826 u kojoj je pronaden mozak prosjecne dobrote334.5. Slika 2.8 detaljnije prikazuje zbivanja na samom pocetku evolucijskog procesa.

Na samom pocetku rada algoritma (iteracija 0), najbolje rješenje u populaciji imalo je prosjecnudobrotu −252.25. Slijedi da se radi o robotu koji se cesto zabija u zidove te se saginje da skupljaboce na poljima na kojima boca nema. U ranim trenutcima evolucije, taj se problem rješava pase preferiraju mozgovi koji to ne rade. Oko iteracije 50 dolazi se do konfiguracije mozga cija je

2.2 Primjena na numericku optimizaciju 19

-300

-250

-200

-150

-100

-50

0

50

0 50 100 150 200

Dob

rota

Iteracija

Slika 2.8: Evolucija rješenja - pocetak

prosjecna dobrota oko nule: radi se ili o mozgu koji je naucio akcije koje kažnjavamo kompenziratipovremenim prikupljanjem boca, ili pak o mozgu koji je naucio da je najbolje ne raditi ništa.

Kako vrijeme napreduje, mozak koji se razvija ipak postaje sve bolji i bolji. Jedan od trikovakoji evolucija relativno rano razvija jest ponašanje koje tjera robota da, ako oko njega nema boca,konzistentno krene u jednom smjeru do prvog zida i potom krene kružiti ili u smjeru kazaljke nasatu, ili u suprotnom smjeru (ali konzistentno). Zahvaljujuci takvom ponašanju, robot ce cestopronalaziti nove boce (a jednom kad ih nade, skuplja ih sve dok mu se ne dogodi situacija da okosebe više nema nicega, nakon cega ponavlja postupak - odlazi do zida i nastavlja kruženje).

Medutim, samo to nije još dovoljno da bismo postigli konacnu traženu dobrotu. S vremenom,evolucija pronalazi još jedno interesantno rješenje: ako se robot nade u situaciji da su oko njega sobje strane boce te ako je i on sam na polju na kojem je boca, tu bocu nije dobro pokupiti; umjestotoga, robot ce krenuti u jednom smjeru dok ne dode do kraja niza boca i potom se krenuti vracati itek ih tada sve redom skupljati. Razmislite zašto je ovakva strategija bitna!

Slika 2.9 prikazuje još jednu karakteristiku navedenog algoritma. Postupak optimizacijepokrenuli smo 20 puta te smo za svako od pokretanja vodili detaljni dnevnik iteracija u kojima supronadena nova bolja rješenja. Ova slika prikazuje kretanje prosjecne dobrote a crvena podrucjaoko krivulje oznacavaju pojas širine jednog standardnog odstupanja (engl. standard deviation)izracunatih na temelju dobrote svakog od 20 eksperimenata u promatranoj iteraciji.

2.2 Primjena na numericku optimizaciju

U prethodnom poglavlju razmotrili smo zadatak evolucije upravljackog podsustava robota, štoje primjer kombinatoricke optimizacije. Od mogucih 7162 razlicitih konfiguracija zadatak je biopronaci neku koja je dovoljno dobra za daljnju uporabu. Ista se nacela mogu primijeniti i na zadatkenumericke optimizacije. Numericke optimizacije tipicno su problemi pretraživanja n-dimenzijskogpodprostora kartezijevih produkata skupova realnih brojeva.

U nastavku cemo razmotriti dva od mnoštva slicnih primjera koje nije moguce jednostavno(ili uopce) rješavati analiticki. Razmotrit cemo i nacin na koji bismo iste mogli krenuli rješavatigenetskim algoritmom.

� Primjer 2.1 Zadana je funkcija f (x,y,z) = sin(z2 · 1|x|+0.02 · e

0.2·y) + cos(0.02 · x·z|y|+0.02 − 3 · x).

20 Poglavlje 2. Genetski algoritam

-300

-200

-100

0

100

200

300

400

0 50000 100000 150000 200000

Dob

rota

Iteracija

Slika 2.9: Evolucija rješenja - prosjecno ponašanje

Pronaci za koju vrijednost argumenata x, y i z ova funkcija poprima minimalnu vrijednost napodprostoru odredenom s x ∈ [−10,10], y ∈ [−10,10] i z ∈ [−10,10]. �

U ovom primjeru jedinka (odnosno sinonimi: rješenje, kromosom) bi predstavljala jednu tockuu trodimenzijskom prostoru realnih brojeva. U konkretnom programskom jeziku, mogli bismo je,primjerice, pamtiti kao polje od tri decimalna broja. Postavljeni zadatak ima prirodnu definicijufunkcije kazne: za svaku jedinku njezinu cemo kaznu definirati kao iznos funkcije u tocki kojupredstavlja jedinka.

Do funkcionalnog genetskog algoritma još nas dijeli samo zadaca definiranja operatora križanjai mutacije. Križanje dviju jedinki koje su prikazane kao polje decimalnih brojeva možemo ostvaritina mnoštvo nacina. Primjerice, u djetetu svaki od elemenata postavimo na aritmeticku sredinupripadnih elemenata iz oba roditelja. Primjer takvog križanja ilustriran je na slici 2.10. Postoji i nizdrugih mogucnosti; primjerice, križanje s jednom tockom prijeloma koje smo vec opisali.

Roditelj 1: 1.2 -3 6

0 1 2

Roditelj 2: 2.0 4.2 3.4

0 1 2

Dijete: 1.6 0.6 4.7

0 1 2

Slika 2.10: Definicija operatora križanja: aritmeticka sredina po komponentama

Mutaciju takoder možemo raditi na više nacina. Primjerice, možemo definirati vjerojatnostmutacije varijable pb, pa u skladu s tom vjerojatnošcu za svako od elemenata polja provjeritihocemo li ga mutirati ili ne. Ako je odgovor da, možemo mu dodati neki slucajno odabrani broj

2.2 Primjena na numericku optimizaciju 21

izvucen iz normalne distribucije centrirane oko 0 i prikladne standardne devijacije. Primjer ovakvemutacije prikazan je na slici 2.11. Pitali smo se želimo li mutirati prvi element, odgovor je bio ne;za drugi element odgovor je bio da; za treci element odgovor je bio ne. Za potrebe mutacije drugogelementa generirali smo slucajni broj iz normalne distribucije (u prikazanom primjeru na slici brojje bio -0.4) i dodali ga drugom elementu roditelja cime smo dobili vrijednost 4.2+(−0.4) = 3.8koju smo upisali kao drugi element polja djeteta. Uocite da ovako definirana mutacija dozvoljavada se ponekad mutira samo jedan element, ponekad dva elementa, ponekad tri, itd., ali u prosjeku,broj mutiranih elemenata bit ce proporcionalan zadanom vjerojatnocu pb.

Jedinka 1: 2.0 4.2 3.4

0 1 2

Mutirana jedinka: 2.0 3.8 3.4

0 1 2

Slika 2.11: Definicija operatora mutacije: nadodajemo broj iz normalne razdiobe oko nule

Uz ovaj dogovor imamo sve što je potrebno kako bismo upogonili prethodno opisani eliminacij-ski genetski algoritam. Pri provodenju turnira potrebno je samo obratiti pažnju da su sada dva boljaroditelja ona koja imaju manju dodijeljenu kaznu.

Želimo li raditi s funkcijom dobrote (za koju vrijedi: vece je bolje), istu bismo mogli definiratikao negativnu vrijednost iznosa funkcije u tocki koju predstavlja jedinka. u tom slucaju, od triizabrane jedinke, roditelji postaju dvije jedinke koje imaju vecu dobrotu. Slika 2.12 prikazujepostupak traženja minimuma ove funkcije pri cemu radimo s funkcijom dobrote. Uocite, kako seradi o zbroju sinusa i kosinusa, teorijski minimum je −2 (odnosno maksimalna dobrota je 2).

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

0 50 100 150 200

Dob

rota

Iteracija

Slika 2.12: Evolucija rješenja kod traženja minimuma funkcije

Prikazana evolucija rješenja ostvarena je populacijom od samo 5 jedinki, a pronadeno rješenjeje x = 9.113271967556997, y = 1.1167555646506055, z = −5.869755348529594. Opetovanimpokretanjem algoritma lako je utvrditi i da rješenje nije jedinstveno. Križanje i mutacija izvedeni

22 Poglavlje 2. Genetski algoritam

su u skladu s prethodno danim opisom i slikama 2.10 i 2.11. Mutacija je brojeve kojima korigiravrijednost zapisanu u roditelju dobivala izvlacenjem iz normalne distribucije s parametrima (0,0.2)pri cemu je prvi broj srednja vrijednost distribucije a drugi standardno odstupanje.

� Primjer 2.2 Kroz odredeno vrijeme promatran je rad nekog sustava. Sustav ima 3 ulaza (oznacimoih x, y i z) i jedan izlaz (oznacimo ga s P). Ulazima sustava upravljaju naponski. Na izlazu sustavgenerira laserski impuls odredene snage. Poznato je da je ovisnost snage tog impulsa o naponimakoji se dovode na ulaz oblika P(x,y,z) = α·eβ ·x

y + γ · z2. Medutim, konkretne vrijednosti parametaraα , β i γ nisu poznate. Tijekom pracenja rada sustava napravljen je i zabilježen niz mjerenja oblika:(x,y,z)→ P; primjerice, kada je x bio 0.1 V i y bio 0.3 V i z bio −0.2 V, snaga lasera na izlazuje bila 0.48 W. Uz pretpostavku da smo prikupili stotinjak takvih mjerenja, potrebno je odreditiparametre α , β i γ uz koje ce zadani model ovisnosti snage o ulaznim naponima najbolje odgovaratiopaženom ponašanju sustava. �

Kako bismo postupili u ovom slucaju? Kao prikaz rješenja opet možemo koristiti poljedecimalnih brojeva. Kako imamo tri parametra koji se traže (α , β i γ), polje ce imati tri elementa.Operatore križanja i mutacije možemo napraviti kao u prethodnom primjeru. Jedino pitanje kojepreostaje jest kako sada definirati funkciju dobrote ili funkciju kazne. No to nije problem. Uocimo:uz zadane vrijednosti parametara model ovisnosti je fiksiran: imamo funkciju koja uz zadane x, y iz može izracunati koju snagu model predvida. Ako su parametri dobro pogodeni, razlika izmedupredvidene snage i snage koja je stvarno bila izmjerena bit ce mala. Stoga cemo najprije definiratifunkciju pogreške kao srednje kvadratno odstupanje stvarno izmjerene snage i snage koju predvidamodel za svaki od izmjerenih podataka. Ta funkcija pogreške izravno ovisi o traženim parametrimaα , β i γ i nju cemo poistovjetiti s funkcijom kazne. Genetskim algoritmom potom cemo evoluiratiprijedloge ovih parametara uz zadacu minimizacije funkcije kazne.

2.3 Dvije vrste genetskih algoritamaKada razmatramo razlicite izvedbe genetskih algoritama, pronaci cemo dvije krajnosti. Prvu ciniimplementacija algoritma koju smo uveli kao eliminacijski genetski algoritam a koji je u engleskojterminologiji poznat kao Steady-state Genetic Algorithm. Radi se o izvedbi algoritma koja usvakom koraku radi minimalnu izmjenu u populaciji: mijenja se samo jedna jedinka. Isto tako, vecu sljedecem koraku, ta novododana jedinka može biti roditelj na temelju kojeg se stvara sljedecedijete.

Bitno drugaciju izvedbu cini takozvani Generacijski genetski algoritam ciji je pseudokodprikazan u nastavku. Radi se o izvedbi kod koje je na pocetku svake iteracije populacija roditeljafiksirana. Iz te populacije biraju se roditelji koji križanjem i mutacijom stvaraju djecu koja sepohranjuju u pomocnu privremenu populaciju. Postupak se radi sve do trenutka dok u populacijidjece nema jednak broj jedinki koliko ih je i u roditeljskoj populaciji. Kada se to dogodi, roditeljskase populacija briše a stvorena populacija djece promovira se u roditelje. Taj trenutak oznacavasmjenu generacije nakon cega se postupak ciklicki ponavlja.

Pseudokod 2.3.1 — Generacijski genetski algoritam.

• Generiraj slucajnu populaciju mozgova od VEL_POP jedinki; evaluiraj svaki.• Ponavljaj dok nije kraj:

– Inicijaliziraj pomocnu populaciju na praznu.– Ponavljaj dok velicina pomocne populacije ne postane jednaka velicini populacije

roditelja∗ Odaberi dva roditelja iz populacije roditelja

2.4 Utjecaj operatora 23

∗ Dijete = Križaj roditelje + Mutacija∗ Vrednuj dijete∗ Ubaci ga u pomocnu populaciju

– Obriši populaciju roditelja– Promoviraj pomocnu populaciju u populaciju roditelja

Kod generacijskog genetskog algoritma eventualno dobro dijete ne može se odmah iskoristiti;ono mora pricekati dok se ne završi citava generacija. Prikazani algoritam takoder nije elitis-ticki.

Definicija 2.3.1 — Elitizam. Elitizam je svojstvo algoritma da ne može izgubiti najbolje prona-deno rješenje.

Kod elitistickih algoritama graf koji prikazuje kretanje funkcije dobrote kroz evoluciju jemonoton; pogledajte ponovno sliku 2.12 koja to ilustrira. Kod algoritama koji nisu elitisticki taj cegraf biti nazubljen: prosjecne vrijednosti funkcije dobrote asimptotski ce rasti ali je sasvim moguceda u nekon koraku algoritma dobrota najbolje jedinke bude manja od dobrote najbolje jedinke kojuje algoritam imao u nekom prethodnom koraku.

Vježba 2.1 Generacijski genetski algoritam prikazan u prethodnom pseudokodu nije elitisticki.Možete li objasniti zašto? �

Vježba 2.2 Eliminacijski genetski algoritam kojim smo razvijali upravljacki podsustav Robbyjaje elitisticki. Možete li objasniti zašto? �

Generacijski genetski algoritam jednostavno se može pretvoriti u elitisticku inacicu. Primjerice,na pocetku svake generacije u pomocnu se populaciju djece može ubaciti kopija najbolje jedinke izroditeljske populacije.

2.4 Utjecaj operatora

Neovisno o tome koju inacicu genetskog algoritma koristimo, operatori križanja i mutacije imajuvažnu ulogu.

Operator križanja na temelju roditelja stvara djecu. Kako su ta djeca slicna roditeljima, ovajoperator ima ulogu fine pretrage prostora rješenja u okolici rješenja koja predstavljaju roditelji.Operator križanja na citavu populaciju cesto djeluje kontrakcijski. Uzmite za primjer križanjekoje smo prikazali za jedinke koje reprezentiramo poljem decimalnih brojeva i koje djecu stvaraizracunom aritmeticke sredine. Kada bismo koristili samo taj operator, svaka bi generacija bila svezgusnutija i zgusnutija. Ako zamislite populaciju kao skup tocaka u R-dimenzijskom prostoru kojezauzimaju odreden volumen, jasno je vidljivo da ce volumen populacije djece koja je dobivenaopisanim križanjem biti manji. Ponovimo li to kroz više iteracija, populacija postaje sve gušca igušca i gubi genetski materijal.

Operator mutacije ima suprotnu ulogu: on nad jedinkom radi jednu ili više slucajnih izmjenakoje jedinku mogu drasticno izmijeniti. Ovaj operator u postupku pretraživanja povecava volumenpopulacije. Njegova druga važna uloga jest izbacivanje populacije iz lokalnih optimuma.

Da bi evolucijski postupak pretraživanja bio djelotvoran, nužno je postici dobar balans izmedusila koje uvode ovi operatori. Ako je kontrakcijsko djelovanje križanja prejako, postupak ce sevrlo brzo zaglaviti u lokalnom optimumu. Ako je djelovanje mutacije prejako, ono ce konzistentnouništavati sve pozitivno što je postupak pretraživanja do tada pronašao i pretragu ce svesti naslucajnu. U idealnoj situaciji, ove su dvije sile medusobno u balansu cime se osigurava da postupakpretraživanja može napredovati prema kvalitetnijim rješenjima.

24 Poglavlje 2. Genetski algoritam

Opisana dinamika u stvarnosti je još malo kompliciranija: u obzir treba uzeti i selekcijski pritisakkoji je posljedica nacina na koji dobrota jedinke utjece na vjerojatnost njezinog razmnožavanja ipreživljavanja. Na ovom mjestu necemo se baviti formalnim definicijama ovog pojma vec cemorazmotriti dva primjera izvedbe operatora selekcije.

2.4.1 k-turnirska selekcijaSelekcija poznata pod nazivom k-turnirska selekcija omogucava kontroliranje selekcijskog pritiskajednostavnim podešavanjem jednog parametra: k iz naziva selekcije. Pseudokod ove selekcijeprikazan je u nastavku.

Pseudokod 2.4.1 — k-turnirska selekcija.Ulaz: populacija P jedinki velicine VEL_POP; k ≤VEL_POP. Izlaz: jedna jedinka• Inicijaliziraj pomocnu populaciju P′ na praznu• Ponavljaj k puta:

– Iz populacije P slucajnim postupkom uz jednoliku distribuciju vjerojatnosti odaberijednu jedinku koja još nije u populaciji P′

– Ubaci je u populaciju P′

• Vrati najbolju (ili najgoru - ovisno što tražimo) jedinku iz populacije P′

Opisani postupak iz populacije vadi uzorak od k jedinki i vraca onu koja je najpoželjnija. Akoovom selekcijom tražimo kandidata za roditelja, najpoželjnija ce jedinka biti ona koja od jedinki izuzorka ima najvecu dobrotu (ili najmanju kaznu). Tražimo li jedinku za eliminaciju, najpoželjnijace jedinka biti ona koja od jedinki iz uzorka ima najmanju dobrotu (ili najvecu kaznu). Trebamo lidva roditelja za križanje, uporabom ovakvog operatora selekcije, roditelje cemo dobiti tako da dvaputa pozovemo operator.

roditelj1 = k-turnir(P)

roditelj2 = k-turnir(P)

Što je parametar k veci, veci se naglasak daje na najbolja rješenja. Postavimo li da jek =VEL_POP, algoritam ce kao roditelja uvijek birati najbolju jedinku populacije, a to ce pakza posljedicu najcešce imati strelovitu konvergenciju algoritma u loš lokalni optimum. S drugepak strane, ako k postavimo na 1, roditelji se biraju potpuno slucajno i njihova dobrota uopce nijebitna; u ovom slucaju selekcijski pritisak uopce ne postoji i algoritam ce nasumice i neusmjerenogenerirati nova rješenja. U praksi se ovakva inacica operatora koristi uz manje vrijednosti k;primjerice, 2 ili 3, cime se osigurava da postoji barem minimalna kompeticija izmedu jedinki zaroditeljstvo.

Kod eliminacijske izvedbe genetskog algoritma, ovaj se operator može koristiti za odabir jedinkekoja ce biti zamijenjena (eliminirana) stvorenim djetetom. Evo primjera takvog jednostavnogalgoritma.

ponavljaj dok nije kraj

roditelj1 = k-turnir(P, biraj najbolju)

roditelj2 = k-turnir(P, biraj najbolju)

dijete = stvori(roditelj1, roditelj2)

vrednuj(dijete)

jedinka3 = k-turnir(P, biraj najlo²iju)

u populaciji P ukloni jedinku3 i zamijeni je sa stvorenim dijetetom

kraj

2.4 Utjecaj operatora 25

R U praksi cesto dolazi do konfuzije oko termina troturnirska selekcija. Ponekad se naprostomisli na operator koji turnirom uz k = 3 obavlja selekciju, a ponekad se misli na citaveliminacijski genetski algoritam kakav smo opisali u poglavlju s robotom Robby. Pogledajteprethodni primjer. Ako u njemu postavimo k = 3, radimo tri turnira (dva za izbor roditelja ijedan za izbor jedinke koju cemo eliminirati) odnosno biramo ukupno devet jedinki. Citav sepostupak može pojednostavniti tako da napravimo samo jedan turnir nad tri jedinke i dvijebolje odaberemo za roditelje a trecu (najlošiju) zamijenimo nastalim djetetom. Gdje godcemo govoriti o takvoj implementaciji algoritma, koristit cemo termin eliminacijski genetskialgoritam s jednostavnom troturnirskom selekcijom. Napomenimo i da dinamika takvogalgoritma u odnosu na prethodno opisani algoritam koji dobivamo uz k = 3 nije jednaka.

2.4.2 Proporcionalna selekcijaTermin Proporcionalna selekcija (engl. Roulette-Wheel Selection) koristi se za operator kojijedinke bira iz populacije na temelju vjerojatnosti koje su im dodijeljene proporcionalno njihovimdobrotama. Pretpostavimo da imamo populaciju od 4 jedinke, i neka su im dobrote redom 6, 4, 8 i2 (vidi sliku 2.13).

0

1

2

3

4

5

6

7

8

1 2 3 4

Dob

rota

Jedinke

Slika 2.13: Razdioba dobrota jedinki iz populacije

Svakoj jedinki htjeli bismo pridijeliti vjerojatnost odabira koja je proporcionalna njezinojdobroti. Oznacimo s f iti dobrotu jedinke i a s probi vjerojatnost da i-ta jedinka bude izabrana.Kako želimo da ta vjerojatnost bude proporcionalna dobroti, neka k predstavlja (za sada nepoznati)koeficijent proporcionalnosti, tako da možemo pisati:

probi = k ·fiti ∀i ∈ {1,2,3,4}.

Da bi probi bile vjerojatnosti, njihova suma mora biti 1. Slijedi da možemo pisati:

prob1 = k ·fit1

prob2 = k ·fit2

prob3 = k ·fit3

prob4 = k ·fit4

prob1 +prob2 +prob3 +prob4 = 1

26 Poglavlje 2. Genetski algoritam

što je sustav 5 jednadžbi s 5 nepoznanica. Uvrštavanjem prve cetiri u petu izravno dobivamorješenje za faktor proporcionalnosti k:

k =1

∑4i=1 fiti

.

Uvrštavanjem u prve cetiri jednadžbe dobivamo:

prob1 =fit1

∑4i=1 fiti

prob2 =fit2

∑4i=1 fiti

prob3 =fit3

∑4i=1 fiti

prob4 =fit4

∑4i=1 fiti

odnosno opci izraz:

probi =fiti

∑nj=1 fit j

. (2.1)

Pogledajmo to na našem konkretnom slucaju. Ukupna suma dobrota iznosi 6+4+8+2 = 20,pa cemo vjerojatnosti odabira jedinki redom postaviti na 6/20 = 0.3, 4/20 = 0.2, 8/20 = 0.4 i2/20 = 0.1. Uz ovakvu distribuciju vjerojatnosti vidimo da ce, primjerice, treca jedinka imati 40%šanse da postane roditelj. Ovo je lijepo prikazano i na slici 2.14 gdje su sve jedinke predstavljenekao kružni isjecci pri cemu je širina oboda isjecka proporcionalna dobroti jedinke koju isjecakpredstavlja.

jedinka 1dobrota = 6

jedinka 2dobrota = 4

jedinka 3dobrota = 8

jedinka 4dobrota = 2

Slika 2.14: Razdioba dobrota jedinki iz populacije prikazana kao kolo ruleta

Na slici je s desne strane prikazan i mali trokutic koji služi selekciji jedinki. Zamislimo da jeprikazani krug u centru fiksiran i da ga možemo potezom ruke zavrtiti. Uslijed trenja kolo ce ujednom trenutku stati, i jedinka koja se zatekne ispod trokutica bit ce odabrana. Uocite: vjerojatnost

2.5 Binarna reprezentacija 27

da to bude jedinka i proporcionalna je duljini oboda kružnog isjecka koji je predstavlja. Engleskinaziv ovakve selekcije (Roulette Wheel) upravo dolazi od ovakve konceptualne implementacije.

Programka implementacija ovakve selekcije prikazana je u pseudokodu u nastavku. Funkcijarandom(...) korištena u pseudokodu ovdje prima dva argumenta: donju granicu i gornju granicute prema uniformnoj distribuciji vraca slucajno generirani decimalni broj iz tog raspona.

Pseudokod 2.4.2 — Implementacija proporcionalne selekcije.

Ulaz: P - populacijaIzlaz: odabrana jedinka

suma = 0

za svaku jedinku J iz P: suma += J.dobrota

trokutic = random(0, suma)

podrucje = 0

za svaku jedinku J iz P:

podrucje += J.dobrota

ako je trokutic <= podrucje

vrati J

kraj ako

kraj za

Da bismo proporcionalnu selekciju mogli koristiti, uocite da jedinke moraju imati dobrote kojesu nenegativni brojevi. Ovo slijedi iz pocetne pretpostavke da želimo da je vjerojatnost odabirajedinke proporcionalna njezinoj dobroti. Ako je dobrota −5, što bi to znacilo za vjerojatnost?

U slucaju da želimo koristiti proporcionalnu selekciju a sve jedinke nemaju nenegativne dobrote,moguce je prije selekcije napraviti jednostavnu transformaciju: potrebno je pronaci jedinku cija jedobrota minimalna (oznacimo tu dobrotu s fitmin) i potom njoj i svim ostalim jedinkama u populacijidobrotu korigirati na dobrotu jedinke umanjenu za identificiranu minimalnu dobrotu:

fit′i← fiti−fitmin.

Dakako, necemo zbog selekcije mijenjati stvarne vrijednosti dobrote jedinkama: u prethodnomizrazu dobrote prema kojima se radi selekcija oznacili smo s fit′i i njih ce pripremiti sam operatorselekcije prije no što krene u vjerojatnosni odabir.

Ovaj operator podložan je još jednom problemu poznatom kao problem skale. Ako su vrijednostifunkcije dobrote jako visoke, vjerojatnosti odabira svih jedinki bit ce podjednake, neovisno o dobrotisamih jedinki. Primjerice, neka su dobrote triju jedinki koje cine populaciju redom 1000001,1000002 i 1000003. Iako je treca jedinka bolja od prethodne dvije, vjerojatnost odabira svih trijujedinki je 33.3% uz razliku na toliko dalekoj decimali da u praksi to nece imati nikakvog utjecaja.Jedno moguce rješenje ovog problema opet je translacija svih dobrota prema nuli za dobrotu najgorefunkcije, ili pak rangiranje jedinki po dobroti i dodjela vjerojatnosti proporcionalno rangu jedinke(najbolji rang, najveca vjerojatnost). Mana tog pristupa je povecana racunska složenost jer jejedinke potrebno sortirati.

2.5 Binarna reprezentacijaKratak osvrt na genetski algoritam koji ovdje dajemo ne bi bio potpun a da ne spomenemo kakoje jedan od koraka primjene genetskog algoritma na optimizacijski problem upravo odabir nacina

28 Poglavlje 2. Genetski algoritam

na koji ce rješenje ("kromosom") biti predstavljeno. Tek kada je dogovoren nacin predstavljanjarješenja, definiraju se operatori križanja i mutacije koji djeluju nad tom reprezentacijom. Uuvodnom dijelu ovog poglavlja vidjeli smo vec dvije reprezentacije: polje cijelih brojeva te poljedecimalnih brojeva.

Prakticki najranija reprezentacija rješenja u genetskom algoritmu bila je binarna reprezentacijakoja ima izravnu analogiju s genetikom: svaki bit je jedan gen, nakupina bitova cini kromosom.Križanje se provodi cijepanjem kromosoma i njihovom rekombinacijom dok mutacije invertirajuvrijednosti bitova.

Ovakav prikaz moguce je koristiti i kada se radi numericka optimizacija nad realnim podrucjem.Sve što je potrebno jest definirati postupak dekodiranja vrijednosti na temelju binarnog zapisa. Evokako to možemo napraviti.

Pretpostavimo da tražimo optimum funkcije f (x). Moguce vrijednosti varijable x kodirat cemobinarno uporabom k-bitova. Potrebno je definirati donju i gornju granicu za varijablu x unutarkoje radimo pretragu: xmin ≤ x ≤ xmax, cime je definirana i širina prostora pretrage: xmax− xmin.Primjetimo sada da k-bitni binarni vektor ima 2k razlicitih vrijednosti. Svaku od tih vrijednostiznamo pretvoriti u cijeli broj: binarni broj anan−1 . . .a1a0 pretvaramo oslanjajuci se na bazu:

a =n

∑i=0

ai ·2i.

Broj a bit ce minimalno 0 a maksimalno 2k−1. Te brojeve iskoristit cemo kako bismo jednolikouzorkovali prostor realnih brojeva iz intervala [xmin,xmax]. Broj 0 pri tome cemo preslikati u xmin,broj 2k−1 u xmax a sve brojeve izmedu linearno u taj interval. Izraz prema kojem to radimo je:

x =a

2k−1· (xmax− xmin)+ xmin. (2.2)

Pogledajmo to na primjeru.

� Primjer 2.3 3-bitnim binarnim kromosom želimo pretražiti podrucje [−30,+40]. Odredimo kojesu sve moguce vrijednosti realne varijable koje se mogu dobiti.

Trobitni kromosom (k = 3) može poprimiti vrijednosti od 000 do 111, što predstavlja cijelebrojeve od 0 do 7. Kako je u našem primjeru xmin =−30 a xmax =+40, širina podrucja je 70, pauporabom izraza (2.2) slijedi:

x =a7·70−30 = 10 ·a−30

što daje redom:

000→ a = 0→ x = 10 ·0−30 =−30

001→ a = 1→ x = 10 ·1−30 =−20

010→ a = 2→ x = 10 ·2−30 =−10

011→ a = 3→ x = 10 ·3−30 = 0

100→ a = 4→ x = 10 ·4−30 =+10

101→ a = 5→ x = 10 ·5−30 =+20

110→ a = 6→ x = 10 ·6−30 =+30

111→ a = 7→ x = 10 ·7−30 =+40

�

U prethodnom primjeru kromosom je imao samo 3 bita odnosno 8 mogucih vrijednosti. Kakoje širina prostora pretrage bila poprilicno velika, pretraga je morala raditi velike korake.

2.5 Binarna reprezentacija 29

Definicija 2.5.1 — Preciznost pretrage. Preciznost pretrage definirat cemo kao minimalnikorak (kvant) kojim se radi pretraga. Kod prethodno opisane binarne reprezentacije preciznost∆ odredena je izrazom:

∆ =1

2k−1· (xmax− xmin). (2.3)

U slucaju iz prethodnog primjera, preciznost pretraživanja bila je 123−1 · (40− (−30)) = 10.

Poznavanjem izraza (2.3) lako je uz zadane granice podrucja i zadanu preciznost doci do potrebnogbroja bitova.

Prokomentirajmo ovdje još jedno svojstvo reprezentacije rješenja: sama reprezentacija zaoptimizacijski algoritam može unijeti lokalni optimum koji u funkciji koja se optimira ne postoji.Primjerice, pretpostavimo da je genetski algoritam došao do sljedeceg rješenja koje je vrlo blizuoptimumu: 0111111. Stvarni optimum postiže se za 1000000. Da bi iz trenutnog rješenja postupakstigao u optimalno, morao bi doslovno promijeniti sve bitove što je vrlo malo vjerojatan scenarij- stoga ce na tom mjestu optimizacijski postupak najcešce zaglaviti. Ovakav problem moguce jeriješiti promjenom nacina dekodiranja rješenja (primjerice, uporabom Grayevog koda za pretvaranjebinarnog uzorka u cijeli broj).

Za kraj, spomenimo da binarna reprezentacija iskazuje još jedno zanimljivo svojstvo: pridjelovanju mutacije, promjena na razlicitim bitovima rješenje modificira u razlicitoj mjeri: promjenaprvog bita radi promjenu od cak pola širine prostora pretraživanja dok promjena zadnjeg bita radipromjenu od samo jednog kvanta. Kod ove reprezentacije jasno je zašto za mutaciju kažemo dajoj je uloga izbacivanje iz lokalnih optimuma - promjenom jednog jedinog bita ovdje mutacijamože napraviti dovoljno veliku izmjenu da se rješenje preseli u skroz novo podrucje i dalje nastavioptimizaciju.

U posljednjih desetak godina izravna uporaba decimalnih brojeva (ili polja decimalnih brojeva)pokazala se prakticnijom u odnosu na binarnu reprezentaciju.

3. Mravlji algoritmi

Mravi su izuzetno jednostavna bica – usporedimo li ih, primjerice, s covjekom. No i tako jednos-tavna bica zahvaljujuci socijalnim interakcijama postižu zadivljujuce rezultate. Sigurno ste punoputa u životu naišli na mravlju autocestu – niz mrava koji u koloni idu jedan za drugim prenosecihranu do mravinjaka. O ponašanju ovih stvorenja snimljen je citav niz dokumentarnih filmova:o njihovoj suradnji, o organizaciji mravinjaka, o nevjerojatnoj kompleksnosti i velicini njihovihkolonija. No kako jedno jednostavno bice poput mrava može ispoljavati takvo ponašanje?

Mnoštvo razlicitih znanstvenih disciplina iskazalo je interes za mrave. U okviru ovog kolegija,mravi su nam posebno zanimljivi iz vrlo prakticnog razloga: uspješno rješavaju optimizacijskeprobleme. Naime, uoceno je da ce mravi uvijek pronaci najkraci put izmedu izvora hrane i njihovekolonije, što ce im omoguciti da hranu dopremaju maksimalno ucinkovito. Kako to postižu? Da bimisterij bio još veci, spomenimo samo da mravlje vrste ili uopce nemaju razvijen vidni sustav, ili jeon ekstremno loš, pa je ocito da se za kretanje ne oslanjaju na osjet vida.

Kako bi istražili ponašanje mrava, Deneubourg i suradnici [6, 10] napravili su niz eksperimenatakoristeci dvokraki most postavljen izmedu mravinjaka i hrane (slika 3.1).

Mravi prilikom kretanja ne koriste osjet vida, vec je njihovo kretanje odredeno socijalniminterakcijama s drugim mravima [1, 2]. Na putu od mravinjaka do hrane, te na putu od hrane domravinjaka, svaki mrav ostavlja kemijski trag – feromone. Mravi imaju razvijen osjet feromona, teprilikom odlucivanja kojim putem krenuti tu odluku donose obzirom na jakost feromonskog tragakoji osjecaju. Tipicno, mrav ce se kretati smjerom jaceg feromonskog traga.

Deneubourg i suradnici prilikom eksperimenata varirali su duljine krakova mosta. U prvomeksperimentu oba su kraka jednako duga. Mravi su na pocetku u podjednakom broju krenuli prekooba kraka. Nakon nekog vremena, medutim, dominantni dio mrava kretao se je samo jednimkrakom (slucajno odabranim). Objašnjenje je sljedece. Na pocetku, mravi slucajno odabiru jedan ilidrugi krak, i krecuci se njima ostavljaju feromonski trag. U nekom trenutku dogodi se da nekolikomrava više krene jednim od krakova (uslijed slucajnosti) i tu nastane veca koncentracija feromona.Privuceni ovom vecom kolicinom feromona, još više mrava krene tim krakom što dodatno povecakolicinu feromona. S druge strane, kako drugim krakom krene manje mrava, kolicina feromonakoja se osvježava je manja, a feromoni s vremenom i isparavaju. Ovo u konacnici dovodi do

32 Poglavlje 3. Mravlji algoritmi

60°

15 cm

mravinjak hrana

Slika 3.1: Eksperiment dvokrakog mosta (prvi).

mravinjak hrana

Slika 3.2: Eksperiment dvokrakog mosta (drugi).

situacije da se stvori jaki feromonski trag na jednom kraku, i taj feromonski trag privuce najvecibroj mrava. Eksperiment je ponovljen više puta, i uoceno je da u prosjeku u 50% slucajeva mravibiraju jedan krak, a u 50% slucajeva biraju drugi krak.

Sljedeci eksperiment napravljen je s dvokrakim mostom kod kojeg je jedan krak dvostrukodulji od drugoga (slika 3.2). U svim pokušajima eksperimenta pokazalo se je da najveci broj mravanakon nekog vremena bira kraci krak.

Ovakvo ponašanje na makroskopskoj razini – pronalazak najkrace staze izmedu hrane i mravi-njaka – rezultat je interakcija na mikroskopskoj razini – interakcije izmedu pojedinih mrava kojizapravo nisu svjesni "šire slike" [4, 11, 12]. Takvo ponašanje temelj je onoga što danas znamo podnazivom izranjajuca inteligencija (engl. emerging intelligence).

Konacno, kako bi se provjerila dinamika odnosno sposobnost prilagodbe mrava na promjene,napravljen je treci eksperiment (slika 3.3).

Kod ovog eksperimenta mravinjak i izvor hrane najprije su spojeni jednokrakim mostom (cijije krak dugacak). Mravi su krenuli tim krakom do hrane i natrag. Nakon 30 minuta kada seje situacija stabilizirala, mostu je dodan drugi, dvostruko kraci krak. Medutim, eksperiment jepokazao da se je najveci dio mrava i dalje nastavio kretati duljim krakom, zahvaljujuci stvorenomjakom feromonskom tragu.

3.1 Pojednostavljeni matematicki model 33

mravinjak hrana mravinjak hrana

Kraći krak je odvojen

Nakon 30 minuta:

Slika 3.3: Eksperiment dvokrakog mosta (treci).

1

2

83

4 7

11

9

6

5

10

Mravinjak

Izvor hrane

Slika 3.4: Primjer pronalaska hrane.

3.1 Pojednostavljeni matematicki modelMatematicki model koji opisuje kretanje mrava dan je u [9]. Mravi prilikom kretanja u oba smjera(od mravinjaka pa do izvora hrane, te od izvora hrane pa do mravinjaka) neprestano ostavljajuferomonski trag. Štoviše, neke vrste mrava na povratku prema mravinjaku ostavljaju to jaciferomonski trag što je izvor pronadene hrane bogatiji. Simulacije ovakvih sustava, posebiceuzmemo li u obzir i dinamiku isparavanja feromona izuzetno su kompleksne. Medutim, idejei zakonitosti koje su ovdje uocene našle su primjenu u nizu mravljih algoritama – u doneklepojednostavljenom obliku.

Pogledajmo to na primjeru. Izmedu mravinjaka i izvora hrane nalazi se niz tunela (slika 3.4,tuneli su modelirani bridovima grafa).

Ideja algoritma je jednostavna. U fazi inicijalizacije, na sve se bridove postavi ista (fiksna)kolicina feromona. U prvom koraku, mrav iz mravinjaka (cvor 1) mora odluciti u koji ce cvorkrenuti. Ovu odluku donosi na temelju vjerojatnosti odabira brida pk

i j:

pki j =

τα

i j

∑l∈Nki

ταil, ako je j ∈ Nk

i

0, ako je j /∈ Nki

pri cemu τi j predstavlja vrijednost feromonskog traga na bridu izmedu cvorova i i j, a α predstavljakonstantu. Skup Nk

i predstavlja skup svih indeksa svih cvorova u koje je u koraku k moguce prijeci

34 Poglavlje 3. Mravlji algoritmi

iz cvora i. Konkretno, u našem slucaju N11 = 2,3,4. Ako iz cvora i nije moguce prijeci u cvor j,

vjerojatnost ce biti 0. Suma u nazivniku prethodnog izraza ide, dakle, po svim bridovima koji vodedo cvorova u koje se može stici iz cvora i.

Nakon što odabere sljedeci cvor, mrav ponavlja proceduru sve dok ne stigne do izvora hrane(cvor 11). Uocimo kako se rješenje problema ovom tehnikom gradi dio po dio – mravlji algoritmipripadaju porodici konstrukcijskih algoritama.

Jednom kada stigne do izvora hrane, mrav zna koliki je put prešao. Umjetni mravi feromonetipicno ostavljaju na povratku, i to na nacin da je kolicina feromona proporcionalna dobroti rješenja(odnosno ako tražimo najkraci put, obrnuto je proporcionalna duljini puta). Ažuriranje radimo zasve bridove kojima je mrav prošao, i to prema izrazu:

τi j← τi j +∆τk

gdje je:

∆τk =

1L,

pri cemu je L duljina pronadenog puta. Isparavanje feromona modelirano je izrazom:

τi j← τi j · (1−ρ)

gdje je ρ brzina isparavanja (iz intervala 0 do 1). Isparavanje se primjenjuje na sve bridove grafa.Ovaj pristup, dakako, ima svojih problema. Primjerice, kada mrav dinamicki gradi put, ako

se u svakom cvoru dopusti odabir bilo kojeg povezanog cvora, moguce je dobiti cikluse, što jenepoželjno. Takoder, ažuriranje feromonskog traga nakon svakog mrava pokazalo se kao loše.

Temeljeci se na opisanim principima moguce je napisati jednostavan optimizacijski algoritam,prikazan pseudokodom u nastavku.

Pseudokod 3.1.1 — Jednostavan mravlji algoritam.ponavljaj dok nije kraj

ponovi za svakog mrava

stvori rje²enje

vrednuj rje²enje

kraj ponovi

odaberi podskup mrava

ponovi za odabrane mrave

aºuriraj feromonske tragove

kraj ponovi

ispari feromonske tragove

kraj ponavljanja

Algoritam radi s populacijom od m mrava, pri cemu u petlji ponavlja sljedece. Svih m mravapusti se da stvore rješenja, i ta se rješenja vrednuju (izracunaju se duljine puteva). Pri tome, svakimrav prilikom izgradnje pamti do tada predeni put, i kada treba birati u koji ce sljedeci cvor krenuti,automatski odbacuje cvorove kroz koje je vec prošao (skupovi Nk

i ). Tek kada je svih m mravastvorilo prijedloge rješenja, odabire se n≤ m mrava koji ce obaviti ažuriranje feromonskih tragova.Pri tome n može biti jednak m, što znaci da ce svi mravi ažurirati feromonske tragove. Kako setakav pristup pokazao kao loša praksa, bolje je pustiti samo bolji podskup, ili cak samo najboljeg

3.1 Pojednostavljeni matematicki model 35

Slika 3.5: Rješenje TSP-a dobiveno jednostavnim mravljim algoritmom.

Slika 3.6: Napredak jednostavnog mravljeg algoritma.

mrava da obavi ažuriranje. Potom se primjenjuje postupak isparavanja feromona, i sve se ciklickiponavlja.

Kako bi se ilustrirao rad ovog algoritma, napisana je implementacija u Javi, i to na problemutrgovackog putnika s 30 gradova (podsjetimo se – radi se o NP teškom problemu; dobiveno rješenjekao i rješavani problem prikazani su na slici 3.5).

Rezultati su dobiveni uz sljedece parametre: m = 40, ρ = 0.2, α = 1, maksimalni broj iteracijaiznosi 500. Feromonski tragovi svih bridova izvorno su postavljeni na 1

5000 . Sa slike se može uocitida pronadeno rješenje nije idealno, ali je vrlo blizu optimalnog. Kvaliteta pronadenih rješenja krozepohe prikazana je na slici 3.6, gdje se može pratiti najbolje pronadeno rješenje kao i prosjecnopronadeno rješenje.

Nakon što smo opisali kako primijeniti prikazane ideje, pogledajmo stvarne algoritme koji sedanas koriste.

36 Poglavlje 3. Mravlji algoritmi

3.2 Algoritam Ant SystemAlgoritam Ant System predložili su Dorigo i suradnici [5, 7, 9]. Prilikom inicijalizacije grafa, na svese bridove deponira kolicina feromona koja je nešto veca od ocekivane kolicine koju ce u jednojiteraciji algoritma deponirati mravi. Koristi se izraz:

τ0 =m

Cnn

gdje je Cnn najkraca duljina puta pronadena nekim jednostavnim algoritmom (poput algoritmanajbližeg susjeda). Ideja je zapravo dobiti kakvu-takvu procjenu duljine puta od koje ce mravi daljetražiti bolja rješenja, te ponuditi optimalnu pocetnu tocku za rad algoritma. Prema [9], uz premaliτ0 pretraga ce brzo biti usmjerena prema podrucju koje su mravi slucajno odabrali u prvoj iteraciji,a uz preveliki τ0 kolicine feromona koje mravi ostavljaju u svakoj iteraciji bit ce premale da bimogle usmjeravati pretragu, pa ce se morati potrošiti puno iteracija kako bi mehanizam isparavanjauklonio višak feromona, i time omogucio da zapocne stvarna pretraga.

Rad algoritma zapocinje tako što m mrava stvara rješenja problema. U slucaju TSP-a, mravise slucajno rasporeduju po gradovima iz kojih tada zapocinju konstrukciju rješenja (nije dobro dasvi krecu iz istog grada). Prilikom odlucivanja u koji grad krenuti, umjesto prethodno prikazanogpravila, mravi koriste slucajno proporcionalno pravilo (engl. random proportional rule) koje uklju-cuje dvije komponente: jakost prethodno deponiranog feromonskog traga te vrijednost heuristickefunkcije. Vjerojatnost prelaska iz grada i u grad j odredena je izrazom:

pki j =

τα

i j ·ηβ

i j

∑l∈Nki

ταil ·η

β

il

, ako je j ∈ Nki

0, ako je j /∈ Nki

ηi j je pri tome heuristicka informacija koja govori koliko se cini da je dobro iz grada i otici u gradj. Ovo je tipicno informacija koja je poznata unaprijed, i u slucaju problema trgovackog putnikaracuna se kao ηi j =

1di j

, gdje je di j udaljenost grada i od grada j. Parametri α i β pri tome odredujuponašanje samog algoritma. Ako je α = 0, utjecaj feromonskog traga se poništava, i pretraživanjese vodi samo heuristickom informacijom. Ako je pak β = 0, utjecaj heuristicke informacije seponištava, i ostaje utjecaj iskljucivo feromonskog traga, što cesto dovodi do prebrze konvergencijesuboptimalnom rješenju (gdje mravi slijede jedan drugoga po relativno lošoj stazi). Dobri rezultatipostižu se uz α ≈ 1 i β izmedu 2 i 5.

Nakon što su svi mravi napravili rješenja, rješenja se vrednuju. Potom se pristupa isparavanjuferomona sa svih bridova, prema izrazu:

τi j← τi j · (1−ρ).

Nakon isparavanja, svi mravi deponiraju feromonski trag na bridove kojima su prošli, i toproporcionalno dobroti rješenja koje su pronašli:

τi j← τi j +m

∑k=1

∆τki j

pri cemu je:

∆τi j =

{ 1Ck , ako je brid i- j na stazi k-tog mrava0, inace

Implementacija ovog algoritma dana je pseudokodom u nastavku.

3.2 Algoritam Ant System 37

Slika 3.7: Rješenje TSP-a dobiveno algoritmom Ant System.

Slika 3.8: Napredak algoritma Ant System.

Pseudokod 3.2.1 — Algoritam Ant System.ponavljaj dok nije kraj

ponovi za svakog mrava

stvori rje²enje

vrednuj rje²enje

kraj ponovi

ispari feromonske tragove

ponovi za sve mrave

aºuriraj feromonske tragove

kraj ponovi

kraj ponavljanja

U svrhu ilustracije rada algoritma napravljen je program u programskom jeziku Java, i pokrenutnad problemom trgovackog putnika s 30 gradova. Parametri algoritma su redom: m = 30, α = 1,β = 2, ρ = 0.5. Algoritam je zaustavljen nakon 500 iteracija. Rezultati su prikazani na slikama 3.7i 3.8.

Uz opisane inacice algoritama, napravljen je i niz daljnjih poboljšanja poput elitisticka verzijaalgoritma (engl. Elitist Ant System – EAS) [7, 8], algoritma rangirajuceg sustava mrava (engl.Rank-based Ant System) [3], max-min mravljeg sustava (engl. Max-Min Ant System, MMAS) [13,

38 Poglavlje 3. Mravlji algoritmi

14, 15] te drugi. Zainteresiranog se citatelja upucuje na [9].

4. Kamo dalje?

Evolucijsko racunanje danas je našlo primjene u mnogim podrucjima ljudske djelatnosti. Fo-kusiramo li se na rješavanje optimizacijskih problema, mnogi su smjerovi u kojima možemokrenuti:• otkrivanje i izrada novih postupaka optimizacije,• teorijska analiza i razumijevanje postojecih postupaka te uvjeti pod kojima se postižu zado-

voljavajuci rezultati,• ubrzavanje postupaka optimiranja kroz paralelizaciju postupaka,• uporaba i razumijevanje hibridnih optimizacijskih postupaka koji istovremeno pretraživanje

rade kombinacijom raznih postupaka te• višekriterijska optimizacija kod koje se svakom rješenju pridjeljuje više mjera dobrote.

Kroz posljednjih tridesetak godina podrucje je dosta napredovalo, no još uvijek jest vrlo interesantnoi plodno za mnoga istraživanja.

Bibliografija

Knjige[Cam+01] S. Camazine i drugi, urednici. Self-organization in Biological Systems. Princeton, NJ:

Princeton University Press, 2001.

[DS04] M. Dorigo i T. Stützle. Ant Colony Optimization. Cambridge, MA: MIT Press, 2004.

[Hak83] H. Haken. Synergetics. Berlin: Springer-Verlag, 1983.

[NP77] G. Nicolis i I. Prigogine. Self-Organisation in Non-Equilibrium Systems. New York:John Wiley i Sons, 1977.

Clanci[Bon+97b] E. Bonabeau i drugi. “Self-organization in social insects”. Tree 12.5 (1997), stra-

nice 188–193.

[BHS99] B. Bullnheimer, R. F. Hartl i C. Strauss. “A new rank-based version of the Ant System:A computational study”. Central European Journal for Operations Research andEconomics 7.1 (1999), stranice 25–38.

[Den+90] J. L. Denebourg i drugi. “The self-organizing exploratory pattern of the Argentineant”. Journal of Insect Behaviour 3 (1990), stranice 159–168.

[DMC96] M. Dorigo, V. Maniezzo i A. Colorni. “Ant System: Optimization by a colony ofcooperating agents”. IEEE Transactions on Systems, Man, and Cybernetics – Part B26.1 (1996), stranice 29–41.

[Gos+89] S. Goss i drugi. “Self-organized shortcuts in the Argentine ant”. Naturwissenschaften76 (1989), stranice 579–581.

[SH00] T. Stützle i H.H. Hoos. “Max-Min Ant System”. Future Generation Computer Systems16.8 (2000), stranice 889–914.

42 Poglavlje 4. Kamo dalje?

Konferencijski radovi i ostalo[Bon+97a] E. Bonabeau i drugi. “Adaptive task allocation inspired by amodel of division of labor

in social insects”. Bio-Computation and Emergent Computing. Obrada: D. Lundha, B.Olsson i A. Narayanan. Singapore: World Scientific Publishing, 1997, stranice 36–45.

[CDM92] A. Colorni, M. Dorigo i V. Maniezzo. “Distributed optimization by ant colonies”.Proceedings of the First European Conference on Artificial Life. Obrada: F. J. Varela iP. Bourgine. Cambridge, MA: MIT Press, 1992, stranice 134–142.

[DMC91] M. Dorigo, V. Maniezzo i A. Colorni. Positive feedback as a search strategy. Tehnickoizvješce. Technical report 91-016. Milano: Dipartimento di Elettronica, Politecnico diMilano, 1991.

[SH97] T. Stützle i H.H. Hoos. “The Max-Min Ant System and local search for the travelingsalesman problem”. Proceedings of the 1997 IEEE International Conference onEvoultionary Computation (ICEC’97). Obrada: T. Bäck, Z. Michalewicz i X. Yao.Piscataway, NJ: IEEE Press, 1997, stranice 309–314.

[SH99] T. Stützle i H.H. Hoos. “Max-Min Ant System and local search for combinatorialoptimization problem.” Meta-Heuristics: Advances and Trend sin Local Search Pa-radigms for optimization. Obrada: S. Voss i drugi. Dordrecht, Netherlands: KluwerAcademic Publishers, 1999, stranice 137–154.

Kazalo

A

algoritam diferencijske evolucije . . . . . . . . . . . 9algoritam harmonijske pretrage . . . . . . . . . . . . 9algoritam roja cestica . . . . . . . . . . . . . . . . . . . . . 9algoritmi lokalne pretrage . . . . . . . . . . . . . . . . . 8algoritmi pcela . . . . . . . . . . . . . . . . . . . . . . . . . . . 9algoritmi rojeva . . . . . . . . . . . . . . . . . . . . . . . . . . 9

B

brute force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

E

evolucijske strategije . . . . . . . . . . . . . . . . . . . 8, 9evolucijski algoritmi . . . . . . . . . . . . . . . . . . . . . . 8evolucijsko programiranje . . . . . . . . . . . . . . 8, 9evolucijsko racunanje . . . . . . . . . . . . . . . . . . . . . 8

G

genetski algoritmi . . . . . . . . . . . . . . . . . . 8, 9, 13genetsko programiranje . . . . . . . . . . . . . . . . . 8, 9

H

heuristicke metodeseeheuristike . . . . . . . . . . . . . . . . . . . . . . . . 8

heuristicki algoritmiseeheuristike . . . . . . . . . . . . . . . . . . . . . . . . 8

heuristike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8algoritmi lokalne pretrage

seealgoritmi lokalne pretrage, 8konstrukcijski algoritmi . . . . . . . . . . Vidjeti

konstrukcijski algoritmimetaheuristike . . . . Vidjeti metaheuristikemetoda uspona na vrh . . . . . . . . . . . . . . . . 8

I

imunološki algoritmi . . . . . . . . . . . . . . . . . . . . . 9iscrpna pretraga . . . . . . . . . . . . . . . . . . . . . . . . . . 5

K

konstrukcijski algoritmi . . . . . . . . . . . . . . . 8, 34

M

metaheuristike . . . . . . . . . . . . . . . . . . . . . . . . . . . 8algoritam diferencijske evolucije . . . . . . 9algoritam harmonijske pretrage . . . . . . . . 9algoritam roja cestica . . . . . . . . . . . . . . . . . 9algoritmi pcela . . . . . . . . . . . . . . . . . . . . . . . 9algoritmi rojeva . . . . . . . . . . . . . . . . . . . . . . 9evolucijske strategije . . . . . . . . . . . . . . . 8, 9evolucijski algoritmi. . . . . . . . . . . . . . . . . .8evolucijsko programiranje . . . . . . . . . . 8, 9evolucijsko racunanje . . . . . . . . . . . . . . . . .8genetski algoritmi . . . . . . . . . . . . . . . . . .8, 9

44 KAZALO

genetsko programiranje . . . . . . . . . . . . .8, 9imunološki algoritmi . . . . . . . . . . . . . . . . . 9mravlji algoritmi . . . . . . . . . . . . . . . . . . . . . 9ostali algoritmi . . . . . . . . . . . . . . . . . . . . . . 9

mravlji algoritmi . . . . . . . . . . . . . . . . . . . . . . 9, 31Ant system . . . . . . . . . . . . . . . . . . . . . . . . . 36elitisticka verzija . . . . . . . . . . . . . . . . . . . . 37jednostavan mravlji algoritam . . . . . . . . 34Max-Min mravlji sustav . . . . . . . . . . . . . 37mravlji sustav . . . . . . . . . . . . . . . . . . . . . . 36pojednostavljeni model . . . . . . . . . . . . . . 33rangirajuci mravlji sustav . . . . . . . . . . . . 37

O

optimizacijski problemiizrada rasporeda meduispita . . . . . . . . . . . 7rasporedivanje nerasporedenih studenata u

grupe za predavanja . . . . . . . . . . . . . . 7

P

pretraživanjebrute force . . . . . . . . . . . . . . . . . . . . . . . . . . 5iscrpna pretraga . . . . . . . . . . . . . . . . . . . . . . 5slijepo pretraživanje . . . . . . . . . . . . . . . . . . 5tehnika grube sile . . . . . . . . . . . . . . . . . . . . 5usmjereno pretraživanje. . . . . . . . . . . . . . .5

približni algoritmiseeheuristike . . . . . . . . . . . . . . . . . . . . . . . . 8

problem trgovackog putnika . . . . . . . . . . . . . . . 5

S

slucajno proporcionalno pravilo . . . . . . . . . . 36

T

teorem no-free-lunch . . . . . . . . . . . . . . . . . . . . . 9TSP . . . . . . Vidjeti problem trgovackog putnika