PROJEKT
Optimizacija kolonijom mrava
Zagreb
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.
0
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.
Slika 2.1 -
Travelling salesman problem sa 4 grada
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
1
3. Sustav Mrava
3.1 Mravi u prirodi
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 (
slika 3.1
),
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.
Slika 3.1 – nastanak prepreke na mravljem putu
Primjer odabira puta među dva različita puta do istog cilja može se brojčano prikazati u
vremenu na drugačiji način (
Slika 3.2: a) postojeće veze među ''gradovima'' i njihove duljine,
geometrijska interpretacija prepreke sa slike 3.1; b) prosječno polovica dolazećih mrava ide
duljim putem, a druga polovica kraćim; c) nakon što prvi mravi prođu kraćim putem i ostave
trag feromona iza sebe, slijedeći mravi će vjerojatnije ići kraćim putem.
). Ukoliko se ključni
dijelovi puta zamijene točkama brzo se dođe do slike koja podsjeća na
travelling salesman
problem
.
3
