Ant Colony Optimization Part 3: Algorithms Spring 2009 Instructor: Dr. MasoudYaghini Ant Colony Optimization: Part 3 Outline (cid:1) The Traveling Salesman Problem (cid:1) ACO Algorithms for TSP (cid:1) Ant System (cid:1) Elitist Ant System (cid:1)(cid:1) RRaannkk--bbaasseedd AAnntt SSyysstteemm (cid:1) MAX–MIN Ant System (cid:1) Ant Colony System (cid:1) Search Stagnation (cid:1) Experimental Evaluation (cid:1) ACO plus Local Search (cid:1) References The Traveling Salesman Problem Ant Colony Optimization: Part 3 The Traveling Salesman Problem (cid:1) The traveling salesman problem is an extensively studied problem in the literature. (cid:1) The TSP also plays an important role in ACO research: the first ACO algorithm, called Ant SSyysstteemm,, aass wweellll aass mmaannyy ooff tthhee AACCOO aallggoorriitthhmmss proposed subsequently, was first tested on the TSP. Ant Colony Optimization: Part 3 The Traveling Salesman Problem (cid:1) The reasons for the choice of the TSP: it is an important NP-hard optimization problem that – arises in several applications it is a problem to which ACO algorithms are easily – aapppplliieedd it is easily understandable, so that the algorithm behavior – is not obscured by too many technicalities it is a standard test bed for new algorithmic ideas—a – good performance on the TSP is often taken as a proof of their usefulness the most efficient ACO algorithms for the TSP were also – found to be among the most efficient ones for a wide variety of other problems Ant Colony Optimization: Part 3 The Traveling Salesman Problem (cid:1) The traveling salesman problem is the problem faced by: a salesman who, starting from his home town, – wants to find a shortest possible trip through a given set – ooff ccuussttoommeerr cciittiieess,, visiting each city once – finally returning home. – Ant Colony Optimization: Part 3 The Traveling Salesman Problem (cid:1) The TSP can be represented by a complete weighted graph G =(N, A) with: N : the set of n = |N| nodes (cities) – A : the set of arcs fully connecting the nodes. – (cid:1)(cid:1) EEaacchh aarrcc iiss aassssiiggnneedd aa wweeiigghhtt dd wwhhiicchh rreepprreesseennttss ij the distance between cities i and j. (cid:1) The TSP is the problem of finding a minimum length Hamiltonian circuit of the graph, where a Hamiltonian circuit is a closed walk (a tour) visiting each node of G exactly once. Ant Colony Optimization: Part 3 The Traveling Salesman Problem (cid:1) We may distinguish between: Symmetric TSPs, where the distances between the cities – are independent of the direction of traversing the arcs, that is, d = d for every pair of nodes, and ij ji AAssyymmmmeettrriicc TTSSPP ((AATTSSPP)),, wwhheerree aatt lleeaasstt ffoorr oonnee ppaaiirr ooff – nodes i, j we have d ≠ d ij ji Ant Colony Optimization: Part 3 The Traveling Salesman Problem (cid:1) A solution to an instance of the TSP can be represented as a permutation of the city indices (cid:1) This permutation is cyclic, that is, the absolute position of a city in a tour is not important at all but oonnllyy tthhee rreellaattiivvee oorrddeerr iiss iimmppoorrttaanntt Ant Colony Optimization: Part 3 Traveling Salesman Problem (cid:1) The only constraint in the TSP is that all cities have to be visited and that each city is visited at most once. (cid:1) This constraint is enforced if an ant at each ccoonnssttrruuccttiioonn sstteepp cchhoooosseess tthhee nneexxtt cciittyy oonnllyy aammoonngg those it has not visited yet (cid:1) The feasible neighborhood of an ant k in city i, where k is the ant’s identifier, comprises all cities that are still unvisited.