1. Uvod

Način na koji mravi u prirodi pronalaze hranu je neko vrijeme bila nepoznanica, dok nije otkriveno da mravi kad pronađu hranu iza sebe ostavljaju trag feromona. Drugi mravi koji osjete feromone prate ih do hrane i vraćaju se do mravinjaka. Ukoliko negdje osjete jači trag feromona radije idu za njim nego za onim tragom koji je slabiji. To ima dva razloga, jedan je isparavanje feromona. Dakle što više vremena je prošlo od postavljanja feromona to je trag slabiji, što se dobro uklapa u logiku pronalaženja, jer ona hrana koja je više udaljena od mravinjaka na taj način ima manju šansu da bude praćena u odnosu na neku bližu. Drugi razlog razlike među tragovima feromona je broj mrava koji su ga postavili. Što više mrava se prethodno odlučilo za jedan put to je veća vjerojatnost da je put dobar te ga i ostali mravi prate. Ukoliko se na putu pojavi prepreka koja postojeći put dijeli na dva nejednaka puta, mravi na početku ne znaju koja strana je kraća. Stoga je vjerojatnost da će mravi krenuti na dulju i kraću stranu jednaka. Pošto je jedna strana kraća, na toj strani će trag feromona ubrzo postati jači, jer na kraćoj strani ne stigne ispariti koliko na duljoj strani. Pošto osjećaju da je trag feromona na jednoj strani jači više mrava se odlučuje za njega, te se ubrzo svi mravi odlučuju za kraći put.

2. Opis algoritma

Algoritam optimizacije kolonijom (Ant Colony Optimization – ACO) mrava zasniva se na imitaciji načina potrage za hranom prave kolonije mrava. Mravi u prirodi kad pronađu hranu iza sebe ostavljaju trag feromona. Drugi mravi koji osjete feromone prate ih do hrane i vraćaju se do mravinjaka. Ukoliko negdje osjete jači trag feromona radije idu za njim nego za onim tragom koji je slabiji. To ima dva razloga, jedan je isparavanje feromona. Dakle što više vremena je prošlo od postavljanja feromona to je trag slabiji, što se dobro uklapa u logiku pronalaženja, jer ona hrana koja je više udaljena od mravinjaka na taj način ima manju šansu da bude praćena u odnosu na neku bližu. Drugi razlog razlike među tragovima feromona je broj mrava koji su ga postavili. Što više mrava se prethodno odlučilo za jedan put to je veća vjerojtnost da je put dobar te ga i ostali mravi prate. ACO sustav stvara određeni broj mrava te ih pušta da traže optimum svaki za sebe. Trag feromona imitira se brojčanim vrijednostima na svakom dijelu puta, a mravi odlučuju kamo će ići prema formuli 2.1.

(2.1)

U formuli 2.1:
p je vjerojatnost
i lokacija mrava gdje se trenutno nalazi
j lokacija na kojoj bi mrav trebao biti u sljedećem koraku
k redni broj mrava o kojem je riječ
t redni broj koraka
τ je iznos traga feromona na putu (i,j)
h je vidljivost između gradova i i j
α je parametar važnosti traga
β parametar važnosti vidljivosti

Ukoliko je mrav već bio na lokaciji j, vjerojatnost je automatski 0, kako mrav ne bi dva puta u istom ciklusu išao na neko mjesto.

2.1 Pseudokod

Pseudo kod se može pojednostavljeno prikazati u dva dijela:

Slika 2.1 Pseudokod algoritma

Najsloženiji dio algoritma je funkcija Odradi_Ciklus() koja poziva n puta korak svakog pojedinog mrava. Složenost ove funkcije je n×m, složenost funkcije koraka pojedinog mrava je n, a funkcija Odradi_Ciklus se poziva NC puta (MAX_broj_ciklusa). Iz čega slijedi da je složenost algoritma NC×m×n². Dodavanje traga razlikuje se kod pojedinih izvedbi ACO sustava, koji uvelike ovisi o problemu nad kojim se primjenjuje.

3. Primjene algoritma

ACO se primjenjuje u dvjema kategorijama problema: statičkim i dinamičkim. Kod statičkih problema se karakteristike zadaju jednom, i to na početku i situacija se ne mijenja tijekom traženja rješenja. Klasičan primjer je problem putujućeg trgovca gdje se lokacije gradova i njihove relativne udaljenosti ne mijenjaju. S druge strane, kod dinamičkih se problema stvari mijenjaju u stvarnom vremenu, čemu se ACO uspješno prilagođuje. Standardni primjer u dinamičkoj kategoriji bilo bi mrežno usmjeravanje (network routing), jer se u mrežama čvorovi mogu dodavati i uklanjati

3.1 Problem putujućeg trgovca

Problem putujućeg putnika (Travelling Salesman Problem – TSP) zadan je pričom: Jedan prodavač mora obići sve gradove koji su mu zadani, no u svaki grad smije ući samo jednom, nakon što je obišao sve gradove vraća se u početni grad. Kojim putem, odnosno redoslijedom je najbolje obilaziti gradove kako bi ukupni pređeni put bio najkraći? Ukoliko sa n označimo broj gradova u problemu, složenost problema je . Matematički zapisano traži se minimum sume svih dijelova puta (formula 3.1; i je redni broj koraka kada je grad obiđen, n je broj gradova u problemu)

(3.1)

3.2 Problem usmjeravanja vozila

Problem usmjeravanja vozila (Vehicle Routing Problem – VRP) zadan je slično trgovačkom putniku, osim što nije jedan putnik koji treba obići sve gradove, već više njih surađuju (primjer poštari). Kao rješenje problema očekuje se redoslijed obilaženja gradova za svako vozilo (putnika), s uvjetom da ukupni put prijeđen (svih vozila zajedno) mora biti što manji.

3.3 Problem bojanja grafa

Problem bojanja grafa (Graph Coloring Problem) definiramo grafom G = (V, E) sa skupom čvorova V i skupom rubova E. Zadan je prirodni broj k, kako bismo predstavili k-bojanje kao funkciju boj : V → {1, 2, ... k}. Vrijednost boj(x) čvora x se zove boja čvora x. Čvorovi s jednakom bojom definiraju klasu boje. Ako dva susjedna čvora x i y imaju jednaku boju, tada x i y nazivamo konfliktnim čvorovima, dok je rub koji ih spaja konfliktni rub. Klasa boje bez konfliktnih rubova jest stabilan set, dok se k-bojanje bez konfliktnih rubova zove dozvoljeno rješenje i predstavlja pridruživanje čvorova u k stabilnih setova. Problem bojanja grafa traži minimalni broj k za koji postoji dozvoljeno rješenje nad zadanim grafom. Ukoliko zadamo prirodni broj k, tada rješavamo optimizacijski problem k-GCP s ciljem otkrivanja k-bojanja grafa G s minimalnim brojem konflikata (u idealnom slučaju tražimo nula konflikata).

4. Zaključak

Optimizacija kolonijom mrava je kvalitetan način optimiziranja mnogih teških optimizacijskih problema, statičkih i dinamičkih. U projektu napravljeni su, opisani i demonstrirani programi koji rješavaju 3 optimizacijska problema primjenom optimizacije kolonijom mrava.

5. Literatura

[1] Marco Dorigo, Vittorio Maniezzo, Alberto Colorni The Ant System: Optimization by a colony of cooperating agents IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, 1996
[2] Vittorio Maniezzo, Luca Maria Gambardella, Fabio de Luigi Ant Colony Optimization
[3] Marco Dorigo, Mauro Birattari, Thomas Stützle Artificial Ants as a Computational Intelligence Technique IRIDIA – Technical Report Series, September 2006
[4] wikipedia; grupa autora; http://en.wikipedia.org/wiki/Ant_colony_optimization
[5] Official ACO metaheuristic site; Prasanna Balaprakash, Marco A. Montes de Oca; http://www.aco-metaheuristic.org/about.html
[6] Genetic and Ant Colony Optimization Algorithms; autor: Peter Kohut; http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms.aspx