Ant Colony Optimization

صفحه 1:
+1 اا كلا ۸ ۷6 ۳ ۷ 11 ۸ UNIVERSITY OF TECHNOLOGY Ant Colony Optimization By: Dr. Behrooz Karimi Email: B.Karimi@aut.ac.ir AUT- Department of Industrial Engineering 1:۳ ۳ 

صفحه 2:


صفحه 3:
Ant Colony Optimization Travelling Salesant Problem ‘ok clace licten up, This problem might seem second nature to you but in some inferior species it is called o "hard" problem AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 4:
Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications +Conclusions) HOE: QAP Conclusions, limitations AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 5:
Section I Introduction AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 6:
Section I Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications AUT- Department of Industrial Benrooz Karimi Engineering 

صفحه 7:
Swarm intelligence * Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination. * Achieving a collective performance which could not normally be achieved by an individual acting alone. * Constituting a natural model particularly suited to distributed problem solving. AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 8:
مت و یبود و ‎Engineering ‘Benrooz Karimi‏ 

صفحه 9:


صفحه 10:
AUT- Department ¢ 

صفحه 11:


صفحه 12:


صفحه 13:
Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature AUT- Department of Industrial Benrooz Karimi Engineering 

صفحه 14:
Natural behavior of an ant Foraging modes * Wander mode * Search mode * Return mode * Attracted mode * Trace mode * Carry mode AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 15:
Natural behavior of ant AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 16:
Work to date Problem name ‘Authors Algorithm name Year “Traveling salesman Darigo, Manieaze & Colom 25 1 Gamberdella & Dorigo Ant 1995, Dorigo & Gamberdella ACS GACS 3 opt 1996 Stutale & Hoos Mas 1997 Bullnheimer, Hartl & Strauss AS, 1997 Cordon, et al BWAS 2000 ‏هه‎ ‘Maniezzo, Colorni & Darigo ASOAP 1۳ Gamberdella, Taillard & Dorigo ‏قدو كما‎ 1907 Stutzle & Hoos MMAS-QaP 1998 Maniezzo ANTS.QaP 1999 Manivezo & Colorni AS-QAP 1994 ‘Scheduling problems Colerni, Doriga & Manieaze ASSP 17 Stutzle AS-SMTTP, 1999 Barker etal ACS-SMTTP 1999 don Besten, Stutzle & Dorigo ACS-SMTWTP 2000 Merkle, Middendert & Schmeck ACO-RCRS 1997 10116 ‏سس صسسسس‎ ‘AS-VAP 1307 Gamberdella, Taillard & Agazzi HAS-VRP 1999 16 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 17:
Year 1596 1998 1998 1998 1997 1997 1998 1998 1997 1997 1908 1908 1998 1999 1999 1999 2000 1 Work to date Algorithm name ABC SGA AntNetFS. smart ants ani AntNet & AntNetFA Regular ants car ABC:backward HAS-SOP ANTCOL as SCS ANTS-FAP ‏هه(‎ ‏ملعم‎ ‎00 ‎60 ها Benrooz Karimi Problem name Authors Connection-oriented ‘Schoonderwood et al network routing White, Pagurek & Oppacher Di Care & Doriga Bonabau etal Connection less i Garo & Dorigo network routing Subramanian, Druschel & Chen Heusse et al van der Put & Rethlrante Sequential ordering Gamberdella& Doriga Graph coloring Costa & Hertz ‘Shortest common Supersequence Michel & Middendort Frequency assignment Maniozzo & Carbonaro Generalized assignment Ramalhinho Lourenco & Serra ‘Multiple knapsack Loguizamon & Michalewicz Optical networks routing Navarro Varela & Sinclair Redundancy allocation Liang & Sith Constraint satisfaction Solna AUT- Department of Industrial Engineering 

صفحه 18:
How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the neighborhood Pheromone: 2 Memory: M,or Tabu, Next move: Use probability to move ant AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 19:
@ A simple TSP example 260 © 60 ©0160 ورك:... 60 > ويك 200 مود ‎AUT- Department of Industrial‏ ‎Engineering‏ 

صفحه 20:
Iteration 1 0 0 [e) ۹ | © 20 AUT- Department of Industrial Engineering 1:۳ ۳ 

صفحه 21:
How to build next sub-solution? fe] 6 8 = 1 61 نج ل ا 1622107 تشد ‎Ingle 1 NOWSR‏ 7 زو ‎otherwise‏ 0 AUT- Department of Industrial Engineering Behrooz Karim 

صفحه 22:
Iteration 2 0.0 6.01 ]0,۵[ 22 AUT- Department of Industrial Engineering ‏و‎ 

صفحه 23:
Iteration 3 oo) 0:۵: ۳ 3 [0,0,0] (oo) - 0 ‏نوا‎ © e 23 AUT- Department of Industrial Benrooz Karimi Engineering 

صفحه 24:
Iteration 4 [0,0,0,0] © أ 6 24 AUT- Department of Industrial Engineering ‏و‎ 

صفحه 25:
Iteration 5 [2,0,0,0,0) ]۵,0,۵,۵,۵[ اين © ‎Gal‏ م AUT- Department of Industrial Engineering ‏و‎ 

صفحه 26:
Path and Pheromone Evaluation ]0,0,6,0,®[ = ‎Arf,‏ ©ههد ,نا 5 a [2,0,.0,0,) Ga, = if, j)€ tour eo 0 otherwise ‏موم ينا‎ 9=Theobjectivealuef theestolutio in theuureriteration loo) ‏بر‎ =Theobjectivealuef thay, ant ]۵,۵,۵,۵,0[ 20 مر [2,0,0,0,0) 20 وا fol 26 AUT- Department of Industrial Engineering 1:۳ ۳ 

صفحه 27:
End of First Run ‎Beret Tents (Greenacres cod eed)‏ ب ‎Ol acts che ‎QOew wits ae bora ‎27 ‎AUT- Department of Industrial ‎Engineering Benrooz Karimi 

صفحه 28:
Ant System (Ant Cycle) Dorigo [1] 1991 Initializ [x(t Ing IP B=) ‏یر‎ Ele OF Mal? 0 otherwise if jeallowed tH ‏باس‎ ‎1, (t+ n)=pr,(t)+ At, pi (i,j € tounlescribéay tabu 0 otherwise 28 Engineerin ig End ‘Behrooz Karimi Au = LJ AUT- J 

صفحه 29:
Stopping Criteria Stagnation Max Iterations 

صفحه 30:
General ACO * A stochastic construction procedure * Probabilistically build a solution * Iteratively adding solution components to partial solutions: - Heuristic information - Pheromone trail * Reinforcement learning reminiscence * Modify the problem representation at each iteration 30 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 31:
General ACO ¢ Ants work concurrently and independently * Collective interaction via indirect communication leads to good solutions 31 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 32:
Versatility Application to ATSP is straightforward No modification of the basic algorithm 32 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 33:
Some inherent advantages * Positive Feedback accounts for rapid discovery of good solutions * Distributed computation avoids premature convergence * The greedy heuristic helps find acceptable solution in the early solution in the early stages of the search process. + The collective interaction of a population of agents. 33 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 34:
Disadvantages in Ant Systems * Slower convergence than other Heuristics * Performed poorly for TSP problems larger than 75 cities. ٠ No centralized processor to guide the AS towards good solutions AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 35:
Improvements to AS Daemon actions are used to apply centralized actions = Local optimization procedure ™ Bias the search process from global information AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 36:
Improvements to AS Elitist strategy e/ L(t) if arc(ij)e T” ۸ )( 0 otherwise AS rank 1, (t+ =(1- p ry (t)+ Saw. rar) (t)+ wir g(t) AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 37:
Improvements to AS ACS * Strong elitist strategy = Pseudo-random proportional rule With Probability q,: 20 ‏ام‎ ‎J =argmax.y,\t (thf With Probability (1- q,): [x,(OF [ny PP oo ———__, if jeallowed P= ‏کر کر‎ 0 otherwise 37 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 38:
Improvements to AS ACS (Pheromone update) t,(t+ D=(1- p ke, (t)+ parC) ™ Update pheromone trail while building the solution ™ Ants eat pheromone on the trail ™ Local search added before pheromone update 38 AUT- Department of Industrial Engineering 1:۳ ۳ 

صفحه 39:
Improvements to AS T min Tey SU as = High exploration at the beginning = Only best ant can add pheromone =" Sometimes uses local search to improve its performance 39 AUT- Department of Industrial Engineering 1:۳ ۳ 

صفحه 40:
Section IT Applications +Conclusions AUT- Department of En 

صفحه 41:
Travelling Salesman Problem (TSP) TOP PROGLEO : Cred O otter, gad « dstoare Pucrton d betwern cites, Prod a tour teat! (. Gore took every oly owe od voy oe ©. Ontcrtzer he totd dotooce. AUT- Department of Industrial Engineering 

صفحه 42:
ACO for the Traveling Salesman Problem he POOP ‏بت‎ a very ‏منود‎ probew ihe voctent oP 60۵ ‏توق‎ ‎he orkid @O ue ae‏ نت ماما تا مسا هی ین ‎Tl‏ ست تسسات ست لمت سيا سحا ‎Poteet athe ke‏ ‎‘ie‏ و موه اجه ما رو و ‎he MEO wos choseo Por ‏وی روم‎ ‎۶ hs a probles te whick the ‏موی روت من‎ 8 his woe oP he cost sted OP-hadd problews a the ovebiciorial opiceization ‎8 tte very evel to exphin. Go thot the okprthy behavior te ‏موجه مسا نوا مهبم‎ techuirahies. ‎42 ‎AUT- Department of Industrial ‎Engineering Benrooz Karimi 

صفحه 43:
Search Space 5 5 بو ومیل a 8 De wok ree w erovoktedl o ata ver ‏مخ مایا نی نوا تخاس‎ 1) (2) LS brand ou bor kere ‏م7‎ 7 ook ede oP he rk annoecied ‏سح جام و لانن‎ 0 T (42) deported by wie. Phervere & dose ord tp bated dt niet AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 44:
Ant Systems (AS) et Gystews Por DEP @rak (0,6): where ۵ < ‏اوه‎ (6 = eke d, < tor rest Proce ‏رو‎ tie ot (eck werd) ct wove Prow coe oly te the vent j wih soxe tenes probobiy. 44 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 45:
Ant Systems Algorithm for TSP AUT- Department of Industrial Engineering 1:۳ ۳ 

صفحه 46:
Rules for Transition Probability 1. Okoker or cet y vay hus been voted 4052 ‏بحل )رصح د خاد‎ le): [fet oP domes trator be visted 4سا لقح ات 6 كه 3002 اسر یر ‎eo. Nz‏ مسقم طلم ‎oP‏ سر هس96 ‎route.‏ جا را انز رو | ‎probably Por oct fs tc Pro vity‏ ملع سا ار ا let a = 0: closest cities are selected 46 AUT- Department of Industrial Benrooz Karimi Engineering 

صفحه 47:
Pheromone trail and heuristic function: are they useful? g bee — ACS standard ‎ACSno heuristic‏ لا ‎@ 450 = —— ACS no pheromone 2 ‏عم‎ ‎5 a2 —— ‏وبر تب‎ 8 5 435 = B 430 5 425 3 ‎4204 ‎40 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 Problem size ‎Comparison between ACS standard, ACS with no heuristic (i.e., we set B=0), and ACS in which ants er sense nor deposit pheromone. Problem: Oliver30. Averaged over 30 trials, 10,000/m iterations per ‎47 ‎AUT- Department of Industrial Benrooz Karim, ‎Engineering ‎ 

صفحه 48:
Trail pheromone in AS ORter the coxepteica oP a tour, cacy oot hae soe ‏جمومصمصحام‎ Atk; (8) Por euck edhe thot they wed. depeuds pa how wel he wot ‏اس سا‎ Joma ۵6 AT (n= ۲ bs ) 0 if ET (A) Trail pheromone 7, (7) <— (1- p)T,(t-) + AT, () decay = 48 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 49:
Ant Colony Optimization (ACO) Qorte & Cawbardels troduced Pour ‏و تالم‎ 6908 : 4. ‏فصو ال‎ rude, 8 ‏لها عون ارام لا‎ updaies, 9 ‏مسا اه مس‎ updates oP ‏ممصا او و( ۰ اما ام‎ ] vondidate bet to restrict the choice oP the oext oly to visit. 49 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 50:
ACS : Ant Colony System for TSP Loop Randomly position m artificial ants on n cities For city=1 ton For ant=1 tom {Each ant builds a solution by adding one city after the other} Select probabilistically the next city according to exploration and exploitation mechanism Apply the local trail updating rule End for End for Apply the global trail updating rule using the best ant Until End_condition AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 51:
ACO State Transition Rule probabilistic rule Oext ay 6 chose betwee he wot usted cites orcordiay too probubitetic nue (Cxplotoica: the best edee is choses (Cxploroiod: cack of te edges iv proportion to tis yoke AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 52:
ACS State Transition Rule : Formulae ۳ mar foro ie oy} ifq<qy (Exploitation) 1 ۱ Jk(t) is the set of cities still to be visited by ant k positioned on city r Band qo are parameters wed (ry | 5 otherwise (Exploration) where 0 $ is a stochastic variable distributed as follows: 1 0 2)([ ]:۸( : if seJ,(r) 0 ‏سوير‎ ‎ao ‎Lo otherwise 3 vis the trail ۰ ‏و‎ 15 the inverse of the distance AUT- Department of Industrial Engineering Behrooz Karim 

صفحه 53:
ACS State Transition Rule : example t(A B) =150 n(A B =1/10 2)4 0( 235 n(A CO =1/7 t(A D) =90 (A D) =1/15 sui probably == Afploitation (Edue PB = dS) swik probably ((- —-)@kploration ®® wih probubiliy ISG/CO 60 ‏اس‎ probubili, 26/26 ®O wit probubiliy 0/26 AUT- Department of Industrial Engineering 

صفحه 54:
ACS Local Trail Updating ... Sivlor ty evoporaios If an edge (r,s) is visited by an ant a0,8)=(l-p} ,5)+ Ads) with Az(r,s) = % 54 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 55:
ACS Global Trail Updating tthe ead oP cack iteroiva the best oot is dhowed to reiPorce its tour by depositiog oddiicod pherowour versely proportiocd to the feath oP the tour 11,5) <11-a): (7,8) +a Adtr, NGloba where 470: Global = LL... ‘best AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 56:
ACO vs AS Pheromone trail update Ocpost pherowour oer powwplettag a tour it BG ere m CO only fre oot ‏ای مد‎ the best tour Brow the bec bP thre ‏مهن تا و ای ام‎ thre ‏توا ار مهو‎ ‏ما و‎ (sats seer of far artes or bret tsar sre Bear) ‎BG pheno ral urdate oppied to ol edges‏ و ‎ALere 1 ®CO the dba pheroxrzar tral update toppled valy to the best tour ‎56 ‎AUT- Department of Industrial Engineering ‎Benrooz Karim, 

صفحه 57:
ACO : Candidate List اعلا للجم و ‎Ose oP‏ جر ام ‎tet oP prePerred ties to viet!‏ © ابا لو ‎fies ane‏ لجو و ,تهت لك دسي سوه اوه اس 8 مد رود بو توا بو جوز * Oboe oP cent city ‏یی عا و ما مت‎ bist. * Otker cites: oly Pool the cities to the tet hove bee visited. AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 58:
Performance * @kworithe Pourd best svluivas a sual problews (“PS rity) * Og loner problews cowerged to youd schutivcs — but at the best * On “static” problews the MS ‏سوه باه مها الم‎ * Oats are “dyoawic” opicoizers — skould we eves expert wood perPorwoure ‏وه‎ ptaiz probes * Couptiog cat with lod opicvizers yave work AUT- Department of Industrial Benrooz Karimi Engineering 

صفحه 59:
Quadratic Assignment Problem(QAP) Problem is: Assign n activities to n locations (campus and mall layout). ‏مارفا‎ 4) aes avs) p= ۳ , distance from location i ‏حصفجححها میا‎ : F= {fila Lu _flow from activity h to activ .—- Assignment is permutatldn Minimize: Cn) = Yq Ly Ena ija « It’s NP hard AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 60:
QAP Example I Location 9 ١ ‎Facilities‏ ع 5 ‎ ‎ ‎ ‎biggest flow: A - es des How to assign facilities to ‎| 7 Ss ocak ns eo ‎ ‎\ ‎\ ‎\ ‎| | ° Higher ‎Lower cost AUT- Department of ngs! = Engineering ‎Benrooz Karimi 

صفحه 61:
Simplified CRAFT (QAP) ‎depurtieuts have ened sta‏ مت ما8 ۱ سر حالما عمط مسا رو اس بر ‎ip locaton |‏ لو ۰ ۲ وود ۳ ] ‎۷ ‎PESO) ohare ‎ae‏ 2 7 @ 1 مه رسمه 6 © 0 ‎ ‎ ‎ ‎ ‎ ‎Craewy” fn‏ زر تسه ‎Boob‏ ۱۲۰۱ 141 ۱1 زا ‎rato‏ قر ‎Bir 1 11۸۱۰1‏ ‎VOT. ۱‏ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎61 ‎AUT- Department of Industrial ‎Engineering Benrooz Karimi ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 62:
Ant System (AS-QAP) ناساس سصصصوه زاو وا دا و ‎a lovato t‏ ما موجه :© مصاع ‏6/۳ ‏تي اام رس ل ‎easter’ (eta‏ ی بای 3۳ ‏و له اس وان ام مخ ‎een pened departs em ee percha‏ = لمعم كار ‎= deed) coupled lcatives ond Pasties ore thibied (Tabu list) ‎62 ‎AUT- Department of Industrial ‎Engineering Benrooz Karimi 

صفحه 63:
AS-QAP Heuristic information Opkxee ond Pw Poteutals 0123 6 0 60 50 10 120 ‏بر ر 9 0 0 وى 0 م باه 4 0 ال‎ 0 1 ۱2 4 0 6 00 * 5۵0 30 0 50 ۰ ۱130 3560 1 10 20 50 0 80 | The coupling Matrix: 720 1200 1440 1680) | 260 1100 1320 1540 s, = fe d =720 ~|780 1300 1560 1820 s,,=£+d, =960 480 800 960 1120) ‏رای وا با مس‎ bee beacon debe Biman eae AL ‏رت‎ ‎2 63 AUT- Department of Industrial Engineering Benrooz Karim, 

صفحه 64:
AS-QAP Constructing the Solution > he Panties ore racked ia deorrastoy order of the Blew pote > atk wets the ‏ما سا رد(‎ | wil the probabiy, «ive by: 1 “رجا “اهارجا = ‎Ho‏ ‏رای where Nie the Pestle Deichbor bord oP cde 1 if jeN تاسلج و ما ‎٩‏ ۱ ما از تمه" مایت وا ‎IOkeu Out k chovses‏ ‎poled rove “pherowow” oa he ooupkay (1)‏ اج موه و و لو او 64 AUT- Department of Industrial Engineering Behrooz Karim 

صفحه 65:
AS-QAP Pheromone Update > Pherowoue tral update to oll couplers! tT, (t+) =px,(O+ 2S AG kA ۸ ‏ون و موه بح‎ oat k puts oo the oouphery (1) Q ۸ 31 1 0 otherwise if facilityi isassigned to location jin the solution of ant k @ J} the objectivefunctionvalue 9 he eth bors Sey 65 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 66:
Hybrid Ant System For The QAP اوه رین موه ور و ‎cyphers pea nerd ki‏ مرو 0 ماه امن ساوح موه وه امس موی بو ام (لمسم) بو اوه دوه ماه حول لوا مه امس 86 AUT- Department of Industrial Engineering Behrooz Karim 

صفحه 67:
Hybrid Ant System For The QAP (HAS-QAP) ‎way.‏ ولو و هط ‎wes oF the pheno‏ )راخ رنه ‎ved ip ody oa ext‏ ‎> eoprove the o's scktion veto ‏اوه اما سل‎ ‏ای حتاف لمه ماس ذا ‎67 ‎AUT- Department of Industrial ‎Engineering Benrooz Karimi 

صفحه 68:
Hybrid Ant System For The QAP (HAS-QAP) Generate m initial solutions, each one associated to one ant Initialise the pheromone trail For Imax iterations repeat For each ant k=1 m do Modify ant k;s solution using the pheromone trail Apply a local search to the modified solution new starting solution to ant & using an intensification mechanism End For Update the pheromone trail Apply a diversification mechanism End For 68 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 69:
HAS-QAP algorithms Performance lOnwparsoxe wih sve of the best heurstes Por he QO have shows that 06-0 f exo the best os Par os red world, ood structured problews ore ‏وی‎ OD ke poly ooerpetion wos show i cpeutiohybrid dkprike. [Oe reso, ued uostructured problews the perPormce of L0G-Q0P war kes powpetive ond tabu searches ore stil the best wehods. ‎opiotraiza were kted to trovelboy‏ بوصامت مد تاه ماوت مه امه سا ,نوت وچ ارام ات ی لو اراس ملد ‎89 ‎AUT- Department of Industrial ‎Engineering Behrooz Karim 

صفحه 70:
Similarities with other Opt. Technique Populations, Elitism ~ GA Probabilistic, Random~ GRASP Constructive = GRASP Heuristic info, Memory ~ TS AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 71:
Design Choices ٠ Number of ants * Balance of exploration and exploitation ٠ Combination with other heuristics techniques * When are pheromones updated? * Which ants should update the pheromone? * Termination Criteria 71 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 72:
Conclusions ACO is a recently proposed metaheuristic approach for solving hard combinatorial optimization problems. Artificial ants implement a randomized construction heuristic which makes probabilistic decisions. The acumulated search experience is taken into account by the adaptation of the pheromone trail. ACO Shows great performance with the “ill-structured” problems like network routing. In ACO Local search is extremely important to obtain good results. 72 AUT- Department of Industrial Engineering Benrooz Karimi 

صفحه 73:
References Dorigo M. and G. Di Caro (1999). The Ant Colony Optimization Meta-Heuristic. In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 11-32. M. Dorigo and L. M. Gambardella. Ant colonies for the traveling salesman problem. BioSystems, 43:73-81, 1997. M., Dorigo and L. M. Gambardella. Ant Colony System: A cooperative learning approach to the traveling salesman problem. /EEE Transactions on Evolutionary Computation, 1(1):53-66, 1997. G. Di Caro and M. Dorigo. Mobile agents for adaptive routing. In H. El-Rewini, editor, Proceedings of the 31st International Conference on System Sciences (HICSS-31), pages 74-83. IEEE Computer Society Press, Los Alamitos, CA, 1998. M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: An autocatalytic optimizing process. Technical Report 91-016 Revised, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991 L, M. Gambardella, ۱ E. D. Taillard, and G. Agazzi. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 63-76. McGraw Hill, London, UK, 1999. L. M. Gambardella, * E. D. Taillard, and M. Dorigo. Ant colonies for the quadratic assignment problem, Journal of the Operational Research Society,50(2):167-176, 1999. V. Maniezzo and A. Colorni, The Ant System applied to the quadratic assignment problem. IEEE Transactions on Data and Knowledge Engineering, 11(5):769-778, 1999. Gambardella L. M., E. Taillard and M. Dorigo (1999). Ant Colonies for the Quadratic Assignment Problem. Journal of the Operational Research Society, 50:167-176. 73 AUT- Department of Industrial Engineering Behrooz Karim