Elektrotehniški vestnik 73(2-3): 93-98, 2006 Electrotechnical Review, Ljubljana, Slovenija
Optimizacija s pomočjo kolonije mravelj
Ivan Pešl, Viljem Žumer, Janez Brest
Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko, Smetanova ul. 17, 2000 Maribor, Slovenija
E-pošta: ivanpesl@hermes.si
Povzetek. V naravi so mravlje sposobne najti najkrajšo pot od vira hrane do gnezda brez uporabe vizualnih informacij. Poleg tega so se zmožne prilagoditi spremembam v okolju, na primer najti novo najkrajšo pot, ko trenutno pot preseka ovira. Pri tem nastane zamisel, da bi lahko bilo posnemanje takšnega obnašanja mravelj učinkovito tudi v diskretnem svetu. V članku bomo prikazali reševanje problema trgovskega potnika s pomočjo optimizacije s kolonijo mravelj.
Ključne besede: kolonija mravelj, umetna inteligenca, inteligenca roja, problem trgovskega potnika
ACO - Ant Colony Optimization
Extended abstract. Ant colony optimization is a relatively new approach to solving NP-Hard problems. It is based on the behavior of real ants, which always find the shortest path between their nest and a food source. Such behavior can be transferred into the discrete world, were real ants are replaced by simple agents. Such simple agents are placed into the environment where different combinatorial problems can be solved.
In this paper we describe an artificial ant colony capable of solving the travelling salesman problem (TSP). Artificial ants successively generate shorter feasible tours by using information accumulated in the form of a phermone trail deposited on edges of the TSP graph [1]. The basic ant behavior can be improved by adding heuristic information, e.g. local search.
We describe several different algorithms used in solving the TSP (and similar) problems. We start from the first algorithm that was first used in ant optimization named Ant System. This algorithm has been followed by many others approaches resulting in better performance of ant colony optimization. The main job is to test the ant behavior on different graphs, taken from the TSPLIB95 library. At the end we show a comparison of ant algorithms on several instances of TSP.
Key words: ant colony optimization, artificial intelligence, swarm intelligence, travelling salesman problem
1 Uvod
V naravi so mravlje sposobne poiskati najkrajšo pot od vira hrane do gnezda brez uporabe vizualnih informacij. Poleg tega so se zmožne prilagoditi spremembam v okolju, na primer poiskati novo najkrajšo pot, ko se sedanja prekine zaradi ovire. Na sliki 1A so prikazane mravlje, ki se gibljejo po poti, ki povezuje vir hrane z njihovim gnezdom. Za medsebojno komunikacijo mravlje uporabljajo feromon. Poti, ki so bolj obiskane, imajo
večjo količino feromona. Mravlje odlagajo feromon med hojo in vsaka mravlja daje prednost sledenju smerem, ki so bogatejše s feromonom. To elementarno obnašanje mravelj uporabimo za razlago, kako lahko poiščejo najkrajšo pot, ki ponovno poveže prekinjeno povezavo po tem, ko se je na začetni poti nenadoma znašla ovira (slika 1B). Ko nastane ovira, mravlje pred oviro ne morejo nadaljevati sledenja poti. V tem primeru lahko pričakujemo, da se bo polovica mravelj obrnila desno, druga polovica pa levo. Podoben položaj nastane tudi na drugi strani ovire (slika 1C). Zanimivo je, da bodo mravlje, ki po naključju izberejo krajšo pot okoli ovire, hitreje rekonstruirale prekinjeno pot kot mravlje, ki so izbrale daljšo pot. Zato bo krajša pot dobila večjo količino feromona na enoto časa in čez čas bo večje število mravelj izbralo krajšo pot (slika ID). Mravlje so prednostno nagnjene k potem z večjo vsebnostjo feromona, kar naredi nabiranje feromona še hitrejše na krajših poteh. Pokazali bomo, kako lahko naredimo podoben proces v simuliranem svetu, naseljenem z umetnimi mravljami, ki pa skušajo rešiti problem trgovskega potnika.
Optimizacija s pomočjo kolonije mravelj ACO (Ant Colony Optimization) [1] je del večjega območja, ki se ukvarja z raziskovanjem, temelječim na algoritmu mravelj oz. inteligentnosti roja, in se ukvarja z algoritmičnimi pristopi, ki so povzeti po obnašanju kolonij mravelj in drugih družabnih insektov. Posebnega pomena so kolektivne aktivnosti, kot so nabava hrane, skrb za zarod, gradnja gnezd itd., ki so mehanizmi samoorganizacije, komunikacije in razdelitev opravil. Optimizacija ACO je povzeta po obnašanju mravelj pri iskanju hrane. Mravlje uporabljajo posebne sledi feromona za označevanje poti do vira hrane.
Gnezdo a *

Hrana Gnezdo




_	Hrana
Ovira
Gnezdo


lil

Hrana Gnezdo
t
$ Ovira
«4lk ■

%
Uto JiL ^ <
•V0
Ovira
Hrana
Slika 1. Potovanje mravelj med virom hrane ter gnezdom nest
Figure 1. Ants travelling between the source of food and their
Optimizacija s pomočjo kolonije mravelj se uporablja za reševanje težkih kombinacijskih optimizacijskih procesov, kot so: problem trgovskega potnika, kvadratni do-delitveni problemi, problemi razvrščanja, dinamični usmerjevalni problemi v telekomunikacijskih omrežjih. Zal je težko teoretično analizirati algoritme ACO, glavni razlog za to je, da so zasnovani na zaporedjih naključnega odločanja, ki ponavadi ni neodvisno in pri katerem se verjetnosti porazdelitve spreminjajo od iteracije do iteracije.
V nadaljevanju bomo natančneje predstavili algoritme ACO. Pokazali bomo uspešnost reševanja na različnih primerih trgovskega potnika, tudi v kombinaciji z algoritmi za izboljšanje rešitev, kot je 2-opt.
2 Vrste algoritmov ACO 2.1 Sistem mravlje - AS
Sistem mravlje (Ant System) [3] je prednik vseh raziskav o algoritmih mravelj in je bil najprej uporabljen pri problemu trgovskega potnika.
Sistem mravlje uporablja predstavitev z grafom, ki je enak grafu trgovskega potnika, dopolnjen s stroškom S(r,s) in z zaželenostjo r(r,s), imenovano feromon. Feromon med izvajanjem posodabljajo mravlje. Če je AS uporabljen na simetričnih vrstah TSP, je r(r, s) = r(s,r), na asimetričnih vrstah pa je mogoče, da r(r, s) ^ t (s, r).
Sistem mravlje deluje tako, da vsaka mravlja zgene-rira celotno pot z izbiranjem mest glede na pravilo prehoda stanj (state transition rule) - mravlje se raje premikajo k mestom, ki so povezana s krajšimi povezavami (z nižjim stroškom) in z veliko količino feromona. Ko vse mravlje opravijo svojo pot, se uporabi pravilo globalne posodobitve feromona (global phermone updating rule) - na vseh povezavah del feromona izhlapi. Nato vsaka mravlja odloži količino feromona na povezave, ki pri-
padajo njeni poti v razmerju dolžine njene poti (povezave, ki pripadajo veliko kratkim potem, dobijo večjo količino feromona). Proces se potem ponavlja.
Pravilo prehoda stanj se imenuje naključno proporcij-sko pravilo (random-proportional rule) in je podano v (1). Pravilo prehoda stanj podaja verjetnost, s katero mravlja k v mestu r izbere mesto s, v katero se premakne:
[r(r,s)]-[r](r,s)f

če s G Jfc(r),
0, sicer
(D
kjer je r feromon, 77 = l/S je inverzna vrednost stroška, Jk(r) je množica mest, ki ostanejo, da jih obišče mravlja k in so povezane z r (da je rešitev mogoča), /3 je parameter, ki določi relativno pomembnost feromona proti strošku ((3 > 0).
Če v (1) pomnožimo količino feromona na povezavi (r, s) s pripadajočo hevristično vrednostjo 77(r, s), damo prednost izbiri povezav, ki so krajše in imajo večjo količino feromona.
Pravilo globalne posodobitve je implementirano kot: ko vse mravlje zgradijo svoje poti, je feromon posodobljen na vseh povezavah glede na:
m
r(r, s) (1 - a) • r(r, s) + ^ Ark(r, s), (2)
k=1
kjer je:
A Tfc(r,s) =
če(r, s) G poti od mravlje k 0, sicer
0 < a < 1 je parameter razpada feromona, L k je dolžina poti narejena od mravlje k in m je število mravelj.
Posodabljanje feromona je namenjeno dodeljevanju večje količine feromona krajšim potem. Formula posodabljanja feromona je namenjena posnemanju spreminjanja
količine feromona zaradi dodajanja novega feromona na povezavah, ki so jih obiskale mravlje, ter izhlapevanja feromona.
Feromon, postavljen na povezave, igra vlogo porazdeljenega dolgotrajajočega spomina; ta spomin ni lokalno shranjen znotraj posamezne mravlje, temveč je porazdeljen po povezavah grafa, kar dovoljuje indirekten način komunikacije.
Čeprav je sistem mravlje uporaben za iskanje dobrih rešitev za majhne TSP (do 30 mest), je potreben čas za reševanje večjih problemov neustrezen. Zato so bile predlagane tri glavne spremembe za izboljšanje algoritma, ki so pripeljale do definicije sistema kolonije mravelj (Ant Colony System - ACS).
2.2 Sistem kolonije mravelj - ACS
ACS [4] se od AS razlikuje v treh glavnih pogledih:
•	pravilo prehajanja stanj zagotovi direktni način za uravnovešanje med raziskovanjem novih povezav in izkoriščanjem danih in akumuliranih znanj o problemu,
•	pravilo globalne posodobitve je dodano samo povezavam, ki pripadajo samo najboljši poti mravlje, in
•	medtem ko mravlje gradijo rešitev, je uporabljeno pravilo lokalne posodobitve feromona.
Inicializacija do {
Vsaka mravlja je postavljena na začetno točko
do {
Vsaka mravlja doda pravilo prehajanja stanj, da naraščajoče zgradi rešitev, in pravilo lokalne posodobitve feromona
} while (Vse mravlje ne zgradijo kompletne rešitve)
Dodano je pravilo globalne posodobitve feromona } while (Zaključni pogoj)
Slika 2. Algoritem za ACS
Figure 2. Algorithm for ACS optimization
Algoritem ACS, ki je prikazan na sliki 2, lahko zapišemo: m mravelj je postavljenih na n mest izbranih glede na poljubno inicializacijsko pravilo. Vsaka mravlja zgradi pot (mogoča rešitev TSP) s ponavljajočim se dodajanjem stohastičnega požrešnega pravila (pravilo prehoda stanj). Med konstrukcijo svoje poti mravlja tudi spreminja količino feromona na obiskujočih povezavah z dodajanjem lokalnega posodobitvenega pravila. Ko vse mravlje končajo svojo pot, je količina feromona na povezavah spet posodobljena - z dodajanjem globalnega posodobitvenega pravila. Enako kot v AS tudi tu mravlje
uporabljajo za gradnjo svojih poti obe, hevristično informacijo (raje izbirajo krajše povezave) in informacijo o količini feromona.
2.2.1 Pravilo prehoda stanj
V ACS je pravilo prehoda stanj naslednje: mravlja postavljena v mesto r, izbere mesto s, kamor se bo premaknila s pravilom:
arg maxueMr){[r(r,u)] • [rj(r,u)]ß},
če q < qo (izkoriščanje) 5, sicer (pristransko raziskovanje),
(3)
kjer je q naključno število uniformno porazdeljeno v [0...1], qo je parameter (0 < qo < 1) in S je naključna spremenljivka, izbrana glede na verjetnost porazdelitve v d).
Pravilo prehajanja stanj, sestavljeno iz (3) in (1), se imenuje psevdonaključno proporcionalno pravilo (pseudo random proportional rule). To pravilo prehajanja stanj je prav tako kot prejšnje naključno proporcijsko pravilo naklonjeno prehodom k mestom, ki so povezana s krajšimi povezavami in z veliko količino feromona. Parameter qo določa relativno pomembnost izkoriščanja glede na raziskovanje: vsakič ko mora mravlja v mestu r izbrati mesto s za premik, naključno izbere število 0 < q < 1. Če je g < qo, potem je izbrana povezava glede na (3), sicer je izbrana povezava glede na (1).
2.2.2 Globalno posodobitveno pravilo
V ACS samo globalno najboljša mravlja (mravlja, ki je zgradila najkrajšo pot od začetka procesa) lahko položi feromon. Ta izbira skupaj z uporabo psevdonaključnega proporcionalnega pravila naredi iskanje bolj direktno: mravlje iščejo v soseščini trenutno najboljše najdene poti. Globalno posodabljanje je izvedeno, ko vse mravlje končajo svoje poti. Stopnja feromona je posodobljena z uporabo globalnega posodobitvenega pravila:
r(r, s) (1 — a) • r(r, s) + aAr(r, 5),
(4)
kjer je:
Ar(r, s) = <
(Lgb) , če (r, s) E globalno
najboljše poti
0, sicer
0 < a < 1 je parameter izhlapevanja feromona in Lgb je dolžina globalno najboljše poti od začetka procesa.
Namen globalnega posodabljanj a je zagotovitev večje količine feromona na kratkih poteh. Enačba (4) narekuje, da samo povezave, ki pripadajo globalno najboljši poti, dobijo ojačitev. Preizkušen je tudi drugi tip globalno posodobitvenega pravila, imenovan ponovitveno
najboljši, ki uporablja L^ (dolžina najboljše poti trenutne iteracije) v enačbi (4). Pri ponovitveno najboljšem pravilu povezave, ki dobijo ojačitev, pripadajo najboljši poti trenutne iteracije. Preizkusi so pokazali, daje razlika med tema dvema shemama minimalna, z manjšo prednostjo pri uporabi globalno najboljšega pravila.
2.2.3 Lokalno posodobitveno pravilo
Med gradnjo rešitve za TSP mravlje obiskujejo povezave in spreminjajo njihovo stopnjo feromona z uporabo lokalnega posodobitvenega pravila:
r(r,s) (l-p) + p.Ar(r,s),	(5)
kjerjeO<p<l parameter.
Vloga lokalnega posodabljanja v ACS je, da pomeša poti, tako da so zgodnja mesta v poti ene mravlje pozneje raziskana v poteh drugih mravelj. Z drugimi besedami, učinek lokalnega posodabljanja je, da se zaželenost povezav dinamično spreminja: vsakič ko mravlja uporabi povezavo, ta postane malo manj zaželena (ker izgubi nekaj svojega feromona). V tej smeri bodo mravlje bolje izkoristile informacijo o feromonu: brez lokalnega posodabljanja bi vse mravlje iskale v ozki soseščini najboljše prejšnje poti.
2.3 MAX-MIN sistem mravlje - MMAS
MAX-MIN sistem mravlje [5] je direktna izboljšava AS. Rešitve v MMAS so zgrajene natančno tako kot v AS, to pomeni, da so verjetnosti izbire izračunane enako kot v enačbi (1). Dodatno obstaja tudi vrsta MMAS, ki uporablja psevdonaključno proporcionalno izbirno pravilo povzeto po ACS. Z uporabo tega pravila so dobre rešitve najdene zelo hitro, medtem ko je kakovost končne rešitve slabša.
Glavne spremembe v MMAS glede na AS so naslednje:
•	za uporabo najboljše najdene rešitve lahko po vsaki iteraciji samo ena mravlja doda feromon (kot v ACS),
•	da se izognemo zastajanju iskanja, je dovoljeni obseg sledi feromona omejen z intervalom [Tmin,Tmax], kar pomeni, da za Vr^ velja rmin < Ti j ^ /Trnax, in
•	sledi feromona so inicializirane na zgornjo mejo, kar povzroči večje raziskovanje na začetku algoritma.
Ko vse mravlje zgradijo rešitev, se sledi feromona posodobijo glede na:
Tij(t+l) = (l-P)-Tij(t)+AT^t,	(6)
kjer Ar^st = 1 /Lbest. Mravlja, kateri je dovoljeno, da doda feromon, je lahko iteracijsko najboljša Tlb ali globalno najboljša Tgh. Ce so določene povezave pogosto uporabljene v najboljših rešitvah, bodo dobile večjo količino feromona.
Sledi feromona so v MMAS inicializirane na maksimalno vrednost feromona. Zato je raziskovanje poti na začetku algoritma povečano, ker je relativna razlika med količino feromona manj razločna.
2.4 Sistem mravelj z rangiranjem - ASrank
Naslednja izboljšava je sistem mravelj z rangiranjem Rank-Based Version of Ant System [7]. V ASrank je vedno uporabljena globalno najboljša pot za posodobitev sledi feromona, podobno kot v AS. Dodatno pa lahko še nekaj najboljših mravelj trenutne iteracije doda feromon. Da to dosežemo, so mravlje urejene po njihovi dolžini poti (L1(t) < L2(t) < ... < Lm(t)) in količina feromona, ki ga lahko mravlja položi, je določena z njenim položajem. Samo (w — 1) najboljšim mravljam je dovoljeno, da dodajo feromon. Globalno najboljši rešitvi, ki da najmočnejši odziv, je dana utež w. r-ta najboljša mravlja trenutne iteracije prispeva feromon z utežjo, dano glede na max{0,w — r}. Modificirano pravilo posodobitve feromona je naslednje:
Tij(t+l) = (l-p).Tij(t) +
w — 1
J2(w-r)-Ar^t)+wAr^b(t), (7)
r=1
kjer je A r^t) = 1 /Lr(t) in A <rf*(t) = 1 /L*b(t). 3 Stagnacija iskanja
Očitno je, da imajo predlagani algoritmi ACO veliko skupnih značilnosti. Sistem mravelj je lahko viden kot prva študija za demonstriranje sposobnosti algoritmov ACO za reševanje težkih kombinacijskih problemov, vendar je njegova učinkovitost slabša v primerjavi z drugimi pristopi. Zato je predlaganih nekaj algoritmov ACO, ki močno izboljšajo učinkovitost sistema mravelj. Glavna skupna značilnost med predlaganimi izboljšavami je, da bolj močno izkoriščajo najboljšo najdeno rešitev med raziskovanjem.
Problem, ki nastane pri močnejšem izkoriščanju najboljše rešitve, je stagnacija iskanja, to je situacija, kjer vse mravlje sledijo isti poti. Zato nekateri algoritmi ACO (ACS in MMAS) predstavijo dodatne značilnosti, da se izognejo stagnaciji. V ACS imamo lokalno posodabljanje, pri MMAS pa vpeljemo meje na dovoljeno količino feromona na povezavah.
Drugi zanimivi pristop za izboljšanje rešitev, dobljenih z algoritmi ACO, je uporaba lokalne optimizacije. Pravzaprav se že kar hitro pokaže, da je za
gradnjo dobrih rešitev optimizacija s pomočjo kolonije mravelj primeren pristop. Da pa takšno rešitev še popravimo, uporabimo na njej lokalne algoritme.
4	Lokalno iskanje
Ker se je pri preizkušanju pokazalo, da konstruktivni algoritmi pripeljejo do slabših rezultatov kot lokalni iskalni algoritmi, se poraja zamisel, da oba pristopa združimo. V našem primeru uporabimo ACO za iskanje rešitev, ki jih potem optimiramo z lokalnim iskanjem in dobljeno rešitev nadalje uporabimo v ACO (za posodabljanje feromona).
do {
for (vsako začetno točko i) { for (vsako končno točko j) {
if ((¿(M+D+čCjj+D) > (5(ij)+(j(i+ij+1))) { zamenjamo povezave, ter popravimo pripadajoče zaporedje } Hii }// for j } // for i } while (imamo izboljšavo)
Slika 3. Algoritem za optimizacijo 2-opt Figure 3. 2-opt optimization algorithm
Izbira lokalnega iskalnega algoritma je odvisna od problema, ki ga rešujemo. Za TSP se uporabljata algoritma 2-opt (slika 3) in 3-opt, ki iterativno zamenjujeta po dve ali tri povezave, dokler ne najdeta boljše rešitve. Lokalno iskanje, ki zamenjuje več kot tri povezave, se zaradi velike časovne zahtevnosti ne uporablja. V tem članku uporabljamo samo algoritem 2-opt.
5	Eksperimentalni rezultati
Primerne nastavitve parametrov za algoritme ACO je treba dobiti s preliminarnimi poskusi. Za preizkuse smo uporabljali naslednje nastavitve:
•	število mravelj m je enako številu mest, tako da pride ena mravlja na vsako mesto,
•	moč hevristične informacije /3 je nastavljena na 2,
•	mero izhlapevanja p smo nastavili na 0.2, kar se je izkazalo za dobro izbrano vrednost (ne prehitro in ne prepočasno izhlapevanje),
•	velikost seznama kandidatov smo nastavili na 10 odstotkov števila mest,
•	pomembna je nastavitev količine feromona na povezavah in njegovih mej (rm^n, rma;r). Količina feromona je odvisna od dolžine najdene rešitve in je nastavljena na rmax = l/(p • Tgb), kjer je Tgb
dolžina globalno najboljše najdene rešitve. Spodnja meja je izbrana glede na rmin = rrnax/(2 • n).
Za testni prostor smo iz knjižnice TSPLIB izbrali naslednje primere:
•	a280.tsp - Drilling problem (Ludwig),
•	att48.tsp - 48 capitals of the US (Padberg/Rinaldi),
•	lin318.tsp - 318 city problem (Lin/Kernighan),
•	eil51.tsp - 51 city problem (Christofides/Eliton),
•	kroAlOO.tsp - 100 city problem (Kro-lak/Felts/Nelson).
Knjižnica TSPLIB je na http://www.iwr.uni-heide lb erg. de/g ro ups/comopt/softwa re/TS P LIB 9 5/.
Cilj raziskave je poleg predstavitve algoritmov ACO tudi preverjanje delovanje algoritma ACS ter vpliv lokalnega iskanja na končni rezultat. Končni rezultat primerjamo tudi z optimalnim rezultatom za določeni testni primer. Prav tako primerjamo vpliv lokalnega iskanja ter razlike z naključnimi sprehodi po grafu. Hitrosti algoritma z drugimi algoritmi nismo primerjali, ker je težko zagotoviti enake pogoje, kot so bili izvedeni v drugih raziskavah.
V tabeli 1 so prikazani rezultati reševanja problemov trgovskega potnika. V prvem stolpcu so imena problemov. V drugem je njihova optimalna rešitev oz. najboljša najdena rešitev. Tretji stolpec vsebuje rešitev, dobljeno z algoritmom ACS brez lokalnega iskanja. Četrti stolpec vsebuje rešitev z uporabo algoritma ACS in dodanega lokalnega iskanja. Za lokalni iskalni algoritem smo uporabili 2-opt, ki je uporabljen na vsakih 25 ite-racij. V petem stolpcu prikazujemo rezultate, dobljene samo z algoritmom 2-opt, ki je dodan rešitvi, dobljeni z naključnim sprehajanjem po grafu. V zadnjem stolpcu so rešitve, dobljene z naključnim sprehajanjem po grafu. Pri naključnem sprehajanju po grafu izbiramo samo najbližja mesta s seznama kandidatov, kar pomeni, da je to naključno sprehajanje rahlo vodeno. Rezultati so dobljeni s tridesetimi ponovitvami vsakega algoritma in so podani kot najslabša (Max), najboljša (Min) in povprečna (Avg) vrednost.
Iz prikazanih rezultatov vidimo, da je reševanje optimizacij skih problemov z ACO učinkovito, še posebej kadar jih uporabimo skupaj z algoritmi za izboljšanje rešitev (primerjava ACS in ACS + 2-opt). Algoritem ACS gradi rešitev (konstrukcijski algoritem), 2-opt pa je po svoji naravi algoritem, ki izboljšuje rešitev. Rezultati algoritma ACS so primerljivi z rezultati algoritma 2-opt. Vidi se tudi razlika pri uporabi samo algoritmov ACS za gradnjo rešitev, kar potrjuje tezo, da se splača združiti algoritme, ki rešitev gradijo, z algoritmi, ki izboljšujejo
Problem	Optimalna
	rešitev
att48	33523
eil51	426
kroalOO	21282
a280	2579
lin318	42029
ACS
Max Min Avg
ACS + 2-opt Max Min Avg
2-opt Max Min Avg
Naključno Max Min Avg
36588 35116 35764 459 443 453
23245 22601 22968 3016 2940 2969 47829 45365 46671
33957 33523 33686 432 428 430 21390 21294 21343 2711 2625 2668 43325 42974 43202
37323 34604 35552 488 446 456 23762 22020 22871 2919 2821 2873 46916 44159 45488
77017 70614 74032 912 878 891 75580 72374 74232 13925 13286 13718 255012 243265 250330
Tabela 1. Rezultati algoritmov na TSPLIB testnih primerih
Table 1. Results of algorithms on the TSPLIB test examples
rešitev. To tezo nam dokazuje primerjava rezultatov algoritma ACS z uporabo algoritma 2-opt in samo z algoritmom 2-opt ali ACS. Dobljeni rezultati se ne razlikujejo veliko od optimalnih, včasih jih celo dosežejo. Prednost algoritmov ACO je tudi ta, da so primerni za vzporedno obdelavo [6] (vsaka mravlja lahko gradi pot na svojem procesorju, pomnilnik (feromon) pa je skupen).
6 Tehnike za pohitritev algoritma ACS
Časovna zahtevnost predstavljenega algoritma ACS je 0(n2), kjer je n število mest. Tudi zahtevnost lokalnega iskanja (2-opt) je 0(n2), kar da skupaj časovno zahtevnost 0(n4). Takšno časovno zahtevnost se da zmanjšati z uvedbo tehnike, imenovane seznam kandidatov [2]. Seznam kandidatov vsebuje mesta, ki so najbližje trenutnemu mestu (urejena po naraščajočem vrstnem redu) in ko izbiramo naslednje mesto za obisk, vzamemo mesto s tega seznama. Če smo obiskali že vsa mesta s seznama kandidatov, potem vzamemo prvo še ne obiskano mesto. Praktične izkušnje so pokazale, da lahko seznam kandidatov vsebuje sorazmerno malo mest za enako učinkovitost iskanja. Na primer za TSP s 500 mesti je dovolj od 6 do 10 mest. Enako tehniko lahko uporabimo tudi pri lokalnem iskanju [2].
Podoben primer imamo tudi pri posodabljanju feromona. Ker je feromon shranjen v matriki z 0(n2) elementi (eden za vsako povezavo), mora biti tudi feromon posodobljen za vsako povezavo v vsaki iteraciji. Ker je to draga operacija, posodobimo samo feromon, ki je na seznamu kandidatov vsakega mesta.
7 Sklep
V delu sta predstavljeni analiza algoritmov ACO in njihova uporaba za reševanje problema trgovskega potnika. Največji poudarek je na algoritmu ACS, ki je med predstavljenimi algoritmi najuspešnejši, posebej kadar ga združimo z algoritmi, ki izboljšujejo rešitev. Dobljeni rezultati potrjujejo uporabnost takšnega pristopa za reševanje težkih optimizacijskih problemov.
8 Literatura
[1] Marco Dorigo, Thomas Stutzle: tion, MIT Press, 2004.
Ant Colony Optimiza-
[2]	Thomas Stutzle, Marco Dorigo: ACO Algorithms for the Traveling Salesman Problem, Evolutionary Algorithms in Engineering and Computer Science: Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications, pp. 163-184, Belgium, 1999.
[3]	Marco Dorigo, Luca Maria Gambardella: Ant colonies for Traveling Salesman Problem, BioSystems, pp. 73-81, 1997.
[4]	Marco Dorigo, Luca Maria Gambardella: Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transaction on Evolutionary Computation, Vol. 1, pp. 53-66, 1997.
[5]	Thomas Stutzle, Holger Hoos: MAX-MIN Ant System and Local Search for Combinatorial Optimization Problems, Meta-Heuristic, Advances and Trends in Local Search Paradigma for Optimization, Kluwer Academic Publishers, pp. 313-329, 1998.
[6]	Bernd Bullnheimer, Gabriele Kotsis, Christine Strauss: Parallelization Strategies for the Ant System, SFB Adaptive Information Systems and Modelling in Economics and Management Science, Austria, 1997.
[7]	Bernd Bullnheimer, Richard F. Hartl, Christine Strauss: A New Rank Based Version of the Ant System, SFB Adaptive Information Systems and Modelling in Economics and Management Science, Austria, 1997.
Ivan Pešl je diplomiral leta 2002 na Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru. Trenutno je študent podiplomskega študija na omenjeni fakulteti. Njegovo področje raziskovanja so evolucijski algoritmi. Od leta 2000 je zaposlen v podjetju Hermes Softlab, d.d.
Viljem Zumer je redni profesor na Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru. Vodi Inštitut za računalništvo in Laboratorij za računalniške arhitekture in jezike. Področja, s katerimi se ukvarja, so programski jeziki, paralelno in porazdeljeno procesiranje ter računalniške arhitekture.
Janez Brest je diplomiral leta 1995, magistriral leta 1998 in doktoriral leta 2001 na Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru. Od leta 1994 je zaposlen v Laboratoriju za računalniške arhitekture in jezike, kjer se ukvarja s spletnim programiranjem, s paralelnim in porazdeljenim procesiranjem. Njegovo področje dela so tudi programski jeziki, ukvarja pa se tudi z optimizacijskimi raziskavami.