Ant Colony Optimization

Ant Colony Optimization

اسلاید 1: 1Ant Colony OptimizationBy: Dr. Behrooz KarimiEmail: B.Karimi@aut.ac.ir

اسلاید 2: 2Ant Colony Optimization

اسلاید 3: 3Ant Colony Optimization

اسلاید 4: 4Section I (Introduction)Historical BackgroundAnt SystemModified algorithmsSection II (Applications +Conclusions)TSPQAP Conclusions, limitationsPresentation Outline

اسلاید 5: 5IntroductionSection I

اسلاید 6: 6Introduction (Swarm intelligence)Natural behavior of antsFirst Algorithm: Ant SystemImprovements to Ant SystemApplicationsSection I

اسلاید 7: 7Collective 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.Swarm intelligence

اسلاید 8: 8

اسلاید 9: 9

اسلاید 10: 10

اسلاید 11: 11

اسلاید 12: 12

اسلاید 13: 13Inherent parallelismStochastic natureAdaptivityUse of positive feedbackAutocatalytic in natureInherent features

اسلاید 14: 14Wander modeSearch modeReturn modeAttracted modeTrace modeCarry modeNatural behavior of an ant Foraging modes

اسلاید 15: 15Natural behavior of ant

اسلاید 16: 16Work to date

اسلاید 17: 17Work to date

اسلاید 18: 18Ants:Simple computer agentsMove ant:Pick next component in the neighborhoodPheromone:Memory:MK or TabuKNext move:Use probability to move antHow to implement in a program

اسلاید 19: 19AEDCB1[]4[]3[]2[]5[]dAB =100;dBC = 60…;dDE =150A simple TSP example

اسلاید 20: 20AEDCB1[A]5[E]3[C]2[B]4[D]Iteration 1

اسلاید 21: 21AEDCB1[A]1[A]1[A]1[A]1[A,D]How to build next sub-solution?

اسلاید 22: 22AEDCB3[C,B]5[E,A]1[A,D]2[B,C]4[D,E]Iteration 2

اسلاید 23: 23AEDCB4[D,E,A]5[E,A,B]3[C,B,E]2[B,C,D]1[A,D,C]Iteration 3

اسلاید 24: 24AEDCB4[D,E,A,B]2[B,C,D,A]5[E,A,B,C]1[A,DCE]3[C,B,E,D]Iteration 4

اسلاید 25: 25AEDCB1[A,D,C,E,B]3[C,B,E,D,A]4[D,E,A,B,C]2[B,C,D,A,E]5[E,A,B,C,D]Iteration 5

اسلاید 26: 261[A,D,C,E,B]5[E,A,B,C,D]L1 =300L2 =450L3 =260L4 =280L5 =4202[B,C,D,A,E]3[C,B,E,D,A]4[D,E,A,B,C]Path and Pheromone Evaluation

اسلاید 27: 27All ants dieNew ants are bornSave Best Tour (Sequence and length) End of First Run

اسلاید 28: 28t = 0; NC = 0; τij(t)=c for ∆τij=0Place the m ants on the n nodesUpdate tabuk(s)Compute the length Lk of every antUpdate the shortest tour found=For every edge (i,j)Compute For k:=1 to m doInitializeChoose the city j to move to. Use probabilityTabu list managementMove k-th ant to town j. Insert town j in tabuk(s)Set t = t + n; NC=NC+1; ∆τij=0 NC<NCmax && not stagn.YesEndNoYesAnt System (Ant Cycle) Dorigo [1] 1991

اسلاید 29: 29StagnationMax IterationsStopping Criteria

اسلاید 30: 30A stochastic construction procedureProbabilistically build a solutionIteratively adding solution components to partial solutions:- Heuristic information- Pheromone trailReinforcement learning reminiscenceModify the problem representation at each iterationGeneral ACO

اسلاید 31: 31Ants work concurrently and independentlyCollective interaction via indirect communication leads to good solutionsGeneral ACO

اسلاید 32: 32Application to ATSP is straightforwardNo modification of the basic algorithmVersatility

اسلاید 33: 33Positive Feedback accounts for rapid discovery of good solutionsDistributed computation avoids premature convergenceThe 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.Some inherent advantages

اسلاید 34: 34Slower convergence than other HeuristicsPerformed poorly for TSP problems larger than 75 cities.No centralized processor to guide the AS towards good solutionsDisadvantages in Ant Systems

اسلاید 35: 35Daemon actions are used to apply centralized actionsLocal optimization procedureBias the search process from global informationImprovements to AS

اسلاید 36: 36Elitist strategyASrankImprovements to AS

اسلاید 37: 37ACSStrong elitist strategyPseudo-random proportional ruleWith Probability (1- q0):With Probability q0:Improvements to AS

اسلاید 38: 38ACS (Pheromone update)Update pheromone trail while building the solutionAnts eat pheromone on the trailLocal search added before pheromone updateImprovements to AS

اسلاید 39: 39High exploration at the beginningOnly best ant can add pheromoneSometimes uses local search to improve its performanceImprovements to AS

اسلاید 40: 40Applications +ConclusionsSection II

اسلاید 41: 41TSP PROBLEM : Given N cities, and a distance function d between cities, find a tour that: 1. Goes through every city once and only once 2. Minimizes the total distance. Problem is NP-hard Classical combinatorial optimization problem to test. Travelling Salesman Problem (TSP)

اسلاید 42: 42The TSP is a very important problem in the context of Ant Colony Optimization because it is the problem to which the original AS was first applied, and it has later often been used as a benchmark to test a new idea and algorithmic variants.The TSP was chosen for many reasons: It is a problem to which the ant colony metaphor It is one of the most studied NP-hard problems in the combinatorial optimization it is very easily to explain. So that the algorithm behavior is not obscured by too many technicalities. ACO for the Traveling Salesman Problem

اسلاید 43: 43Discrete GraphTo each edge is associated a static value returned by an heuristic function  (r,s) based on the edge-cost Each edge of the graph is augmented with a pheromone trail  (r,s) deposited by ants. Pheromone is dynamic and it is learned at run-imeSearch Space

اسلاید 44: 44Ant Systems for TSP Graph (N,E): where N = cities/nodes, E = edges = the tour cost from city i to city j (edge weight)Ant move from one city i to the next j with some transition probability. ADCBAnt Systems (AS)

اسلاید 45: 45InitializePlace each ant in a randomly chosen cityChoose NextCity(For Each Ant)more cities to visitFor Each AntReturn to the initial citiesUpdate pheromone level using the tour cost for each ant Print Best touryesNoStoppingcriteria yesNoAnt Systems Algorithm for TSP

اسلاید 46: 461. Whether or not a city has been visited Use of a memory(tabu list): : set of all cities that are to be visited = visibility: Heuristic desirability of choosing city j when in city i. 3.Pheromone trail: This is a global type of informationTransition probability for ant k to go from city i to city j while building its route.a = 0: closest cities are selectedRules for Transition Probability

اسلاید 47: 47 Comparison between ACS standard, ACS with no heuristic (i.e., we set B=0), and ACS in which antsneither sense nor deposit pheromone. Problem: Oliver30. Averaged over 30 trials, 10,000/m iterations per trial.Pheromone trail and heuristic function: are they useful?

اسلاید 48: 48After the completion of a tour, each ant lays some pheromone for each edge that it has used. depends on how well the ant has performed.Trail pheromone decay = Trail pheromone in AS

اسلاید 49: 49Dorigo & Gambardella introduced four modifications in AS :1.a different transition rule, 2.Local/global pheromone trail updates, 3.use of local updates of pheromone trail to favor exploration 4.a candidate list to restrict the choice of the next city to visit. Ant Colony Optimization (ACO)

اسلاید 50: 50ACS : Ant Colony System for TSP

اسلاید 51: 51Next city is chosen between the not visited cities according to a probabilistic rule Exploitation: the best edge is chosenExploration: each of the edges in proportion to its value ACO State Transition Rule

اسلاید 52: 52ACS State Transition Rule : Formulae

اسلاید 53: 53•with probability exploitation (Edge AB = 15) •with probability (1- )exploration AB with probability 15/26 AC with probability 5/26 AD with probability 6/26 ACS State Transition Rule : example

اسلاید 54: 54… similar to evaporation ACS Local Trail Updating

اسلاید 55: 55At the end of each iteration the best ant is allowed to reinforce its tour by depositing additional pheromone inversely proportional to the length of the tour ACS Global Trail Updating

اسلاید 56: 56Pheromone trail updateDeposit pheromone after completing a tour in ASHere in ACO only the ant that generated the best tour from the beginning of the trial is allowed to globally update the concentrations of pheromone on the branches (ants search at the vicinity of the best tour so far) In AS pheromone trail update applied to all edgesHere in ACO the global pheromone trail update is applied only to the best tour since trial began. ACO vs AS

اسلاید 57: 57Use of a candidate listA list of preferred cities to visit: instead of examining all cities, unvisited cities are examined first.Cities are ordered by increasing distance & list is scanned sequentially. Choice of next city from those in the candidate list. Other cities only if all the cities in the list have been visited. ACO : Candidate List

اسلاید 58: 58• Algorithm found best solutions on small problems (75 city)• On larger problems converged to good solutions – but not the best• On “static” problems like TSP hard to beat specialist algorithms• Ants are “dynamic” optimizers – should we evenexpect good performance on static problems• Coupling ant with local optimizers gave worldclass results….Performance

اسلاید 59: 59Problem is:Assign n activities to n locations (campus and mall layout).D= , , distance from location i to location jF= , ,flow from activity h to activity kAssignment is permutationMinimize:• It’s NP hardQuadratic Assignment Problem(QAP)

اسلاید 60: 60QAP Examplebiggest flow: A - BLower costHigher costLocationsFacilitiesHow to assign facilities to locations ?BC?ABCABCA

اسلاید 61: 61Simplification Assume all departments have equal sizeNotation distance between locations i and j travel frequency between departments k and h 1 if department k is assigned to location i 0 otherwiseExample2134LocationDepartment („Facility“)Distance*Frequency*1324Simplified CRAFT (QAP)

اسلاید 62: 62Constructive method:step 1: choose a facility jstep 2: assign it to a location iCharacteristics:– each ant leaves trace (pheromone) on the chosen couplings (i,j)– assignment depends on the probability (function of pheromone trail and a heuristic information)– already coupled locations and facilities are inhibited (Tabu list)Ant System (AS-QAP)

اسلاید 63: 63 Distance and Flow Potentials The coupling Matrix:Ants choose the location according to the heuristic desirability “Potential goodness” AS-QAP Heuristic information

اسلاید 64: 64 The facilities are ranked in decreasing order of the flow potentials Ant k assigns the facility i to location j with the probability given by:where is the feasible Neighborhood of node i Repeated until the entire assignment is foundWhen Ant k chooses to assign facility j to location i it leaves a substance, called trace “pheromone” on the coupling (i,j)AS-QAP Constructing the Solution

اسلاید 65: 65is the amount of pheromone ant k puts on the coupling (i,j) Pheromone trail update to all couplings: Q...the amount of pheromone deposited by ant kAS-QAP Pheromone Update

اسلاید 66: 66Hybrid algorithms combining solution constructed by (artificial) ant “probabilistic constructive” with local search algorithms yield significantly improved solution.Constructive algorithms often result in a poor solution quality compared to local search algorithms.Repeating local searches from randomly generated initial solution results for most problems in a considerable gap to optimal soultion.Hybrid Ant System For The QAP

اسلاید 67: 67 HAS-QAP uses of the pheromone trails in a non-standard way. used to modify an existing solution, Intensification and diversification mechanisms. improve the ant’s solution using the local search algorithm.Hybrid Ant System For The QAP (HAS-QAP)

اسلاید 68: 68Generate 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 k using an intensification mechanism End For Update the pheromone trail Apply a diversification mechanismEnd ForHybrid Ant System For The QAP (HAS-QAP)

اسلاید 69: 69Comparisons with some of the best heuristics for the QAP have shown that HAS-QAP is among the best as far as real world, and structured problems are concerned.The only competitor was shown to genetic-hybrid algorithm.On random, and unstructured problems the performance of HAS-QAP was less competitive and tabu searches are still the best methods.So far, the most interesting applications of ant colony optimization were limited to travelling salesman problems and quadratic assignment problems.HAS-QAP algorithms Performance

اسلاید 70: 70Populations, Elitism ~GAProbabilistic, Random~GRASPConstructive~GRASPHeuristic info, Memory~TSSimilarities with other Opt. Technique

اسلاید 71: 71Number of antsBalance of exploration and exploitationCombination with other heuristics techniquesWhen are pheromones updated?Which ants should update the pheromone? Termination CriteriaDesign Choices

اسلاید 72: 72ACO 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.Conclusions

اسلاید 73: 73Dorigo 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. IEEE 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.Reference