Optimizacija kolonijom mrava

1.    Uvod
U ovom radu obrađuje se optimizacija kolonijom mrava (ant colony optimization – ACO u daljnjem dijelu teksta). ACO je algoritam koji po svojem načinu rada spada u kategoriju evolucijskih algoritama. Uže ga možemo svrstati među swarm intelligence, jer ne koristi tipične rutine genetskih algoritama, već se zasniva na kolektivnom znanju i dijeljenju informacija među mnogim jedinkama.
Nakon objašnjenja optimizacijskih problema koji se rješavaju ACO algoritmima slijedi biološka osnova ACO algoritma. Način rada mrava pri pronalaženju hrane, kao dio velike kolonije, pokušava se imitirati računalnim algoritmom.
U sklopu projekta demonstrirani su jedan slobodno dostupan program koji koristi ACO algoritam, te jedan novi program napisan za ovaj projekt.

2.    Optimizacijski problem
2.1    Optimizacijski problemi
Vrsta optimizacijskih problema ima mnogo. Za sve jednostavne zadatke postoje deterministički algoritmi koji brzo mogu pronaći savršeno rješenje, no za veće i složenije probleme deterministički pristup susreće se sa svojim granicama. Pod pojmom ”složeni optimizacijski problemi” mislimo na zadatke koji se ne mogu riješiti determinističkim metodama u kratkom vremenu, iz jednostavnog razloga što postoji prevelik broj mogućih kombinacija. Vrijeme potrebno da računalo prođe kroz sve postojeće moguće kombinacije rješenja je često neprihvatljivo dugo, stoga se koriste evolucijski algoritmi koji ne daju uvijek optimalno rješenje, ali dođu prihvatljivo blizu optimalnom rješenju u prihvatljivo kratkom vremenu.

2.2    Travelling salesman problem
Problem putnika, odnosno putujućeg prodavača, je naziv za specifičnu vrstu optimizacijskog problema. Problem je zadan na sljedeći način:
Jedan prodavač mora obići sve gradove koji su mu zadani, no u svaki grad smije ući samo jednom. Kojim putem, odnosno redoslijedom je najbolje obilaziti gradove, ako su udaljenosti među gradovima različite?
Prikazano formulom (formula 2.1) ovaj se zadatak može postaviti kao traženje minimuma ukupnog puta, pri čemu je n broj gradova u problemu, a i redni brojevi grada kojeg je putnik obišao.

Formula 2.1 – definicija TSP
Gradovi su zadani kao točke u ravnini, međusobno udaljene neki konstantan iznos (primjer Slika 2.1). Naravno genetski algoritmi se neće primjenjivati na ovako bizarno jednostavne zadatke kada su samo četiri grada u pitanju, već za probleme kada je u pitanju više stotina ili tisuća gradova.

Složenost ovog problema je  . To znači da će za ova četiri grada postojati svega tri moguća rješenja, od kojih je lako izabrati najbolje, no već za pet gradova tu je 12 mogućih rješenja. Broj mogućnosti raste strahovito brzo i tako nadilazi sposobnosti determinističkih algoritama za velike brojeve gradova. Primjerice za 50 gradova bi broj mogućnosti koje deterministički stroj mora proći bio 3×1064.

 
2.3    Vehicle routing problem
Problem usmjeravanja vozila sličnog je porijekla kao problem putujućeg prodavača. Radi se o skupu vozila koja moraju poslužiti klijente. Problem usmjeravanja vozila poznat je diljem svijeta i često se mora rješavati, primjerice službe isporuke i dostave kao što su pošta, picerije, ispunjavanje popisa stanovništva. Potrebno je organizirati isporuke više dostavljača kako bi se povećala ušteda goriva i vremena. Bez dodatnih uvjeta, i uz broj vozila 1, vehicle routing problem odgovara travelling salesman problemu. Postoje mnoge varijacije problema usmjeravanja vozila koje lagano mijenjaju problem, a većina ih potječe iz konkretnih primjera u svijetu. Osnovni VRP se može prikazati formulom 2.2, pri čemu V označava broj vozila, v redni broj vozila, n broj gradova, i redni broj grada obiđen, a (n/V) broj gradova koje obilazi svako vozilo.