Multiple Objective TSP based on ACO

Multiple Objective TSP based on ACO P. Cardoso1, M. Jesus2and A. M´arquez3 Abstract In this paper we present an Ant Colony Optimisation based algorithm to determine the Pareto set for the Multiple Objective Travelling Salesman Problem. Our results are then compared with the ones obtained with a genetic algorithm. 1 Introduction When developing a mathematical model, the majority of the real-world problems require several goals to be fulfilled at the same time, taking us in the area of Multiple Objective Optimisation (MOO). One of the most used approaches, simplifies the computational procedures by aggregating all the objectives in a function, followed by the application of known single objective optimisation techniques. Usually, that function is defined as a weighted linear combination of the multiple costs that, most of the times, produces an artificial value due to the different nature of the parcels. Furthermore, hardly ever exists a single solution that optimises simultaneously all the objectives and, therefore, a set of solutions that represents the best compromise between the conflicting objectives is most suitable. This paper describes a multiple pheromone trails Ant Colony Optimisation (ACO) with local search algorithm for the Multiple Objective Travelling Salesman Problem (MOTSP). Therefore, in the next section we will introduce some ideas related to MOO, MOTSP and ACO. In the third section, we present the optimisation procedure used to solve the MOTSP. Finally, we report on our experiments, present some succinct observation over the experimental results and some future work. 1Universidade do Algarve (EST). Dep. Eng. Electrot´ecnica. Email: p[email protected] 2Universidade do Algarve (EST). Dep. Eng. Civil. Email: [email protected] 3Universidad de Sevilla (FIE). Dep. de Matem´atica Aplicada I. Email: [email protected] 2 Preliminaries This section will be dedicated to introduce the problem as well as the basic heuristic used to solve it. Multiple objective optimisation The MOO can be mathematically defined as ”minimize” (f1(x), f2(x), . . . , fm(x)) subject to x∈S, where Sis the set of feasible solutions and ”minimize” requires the determination of a set of points from S, that optimises the costs over some defined order relation in IRm. A formal definition of optimality for the MOO, introduced by Vilfredo Pareto, says that: x∗∈Sis a Pareto optimum when there exists no other x∈Ssuch that fi(x)< fi(x∗), i = 1,2, . . . , m. The set of all points satisfying the above condition is named Pareto set. Therefore, the Pareto set is the best collection of solutions to the problem, i.e., one of the objective functions can only be improved at the expense of increasing at least one of the others. Multiple objective travelling salesman problem The single objective TSP is one of the best-known combinatorial optimisation problems. In this paper we consider the MOO variant that can be stated as follow: ”Given a network N= (V,C) where V={v1, v2, . . . , vn}is a set of nodes and C={ci:i∈ {1,2, . . . , m}} is a set of cost functions between nodes (ci:V × V → IR), determine the Pareto set for the minimum length Hamiltonian cycles”. Ant Colony Optimisation The ACO, introduced by Marco Dorigo, is one of the most recent meta heuristics. As the name suggests, the optimisation process mimics the colonies of ants, in particular their forager behaviour. The process is based in a set of artificial ants that communicate using artificial trails of pheromone. Those trails reflect the experience of the ants that have already solved the problem and favour the creation of new solution. The method comprises a set of iterations where collections of solutions are obtained. At the end of each iteration, the pheromone trails are updated considering the known solutions as well as a certain pheromone evaporation. The ACO as been applied to some of the most demanding combinatorial optimisation problems like, for example: the TSP, the Quadratic Assignment and the Vehicle Routing (a more extensive list of application and references can be found in [Dorigo, 2000]). Related to the MOO, in [Cardoso, 2003] an algorithm based on the ACO was used to optimise flows over a multiple objective network under a time window. 3 Multiple Objective TSP based on ACO In this section, we introduce the logic used to determine the Pareto set for the MOTSP based on ACO algorithm and a local search heuristic. Hamiltonian cycle construction Each ant, initially placed randomly in one of the nodes, creates a Hamiltonian cycle by the successive selection of nodes, from the ones not yet visited. The order in which the nodes are chosen, is made pseudo randomly according to the pheromone trails and a local greedy heuristic that gives preference to nearest nodes. Mathematically, the probability of moving from node uto node vis given by: puv =     Πm k=1τ(k) u,v αk(ck(u,v))−βk Pw∈U Πm k=1τ(k) u,wαk(ck(u,w))−βkif v∈ U 0 if v6∈ U ,(1) where τ(k) u,v is the quantity of k-pheromone in edge (u, v), ck(u, v) is the k cost of edge (u, v) and α1, α2, . . . , αmand β1, β2, . . . , βmare parameters that emphasis the costs and the local greedy heuristic importance, respectively. Pheromone update As referred, the process is based in a set of m pheromone trails, each one associated to a cost. Those trails, initially set equal, are updated after each iteration of the ACO according to τ(k) u,v = (1 −ρk)τ(k) u,v + ∆τ(k) u,v where ρk∈]0,1] is the evaporation factor and ∆τ(k) u,v is the quantity of pheromone layed in the edge (u, v) by the ants. More specifically, ∆τ(k) u,v =Pa∈P Q T(k) a where Qis an adjustable parameter related to the amount of pheromone that each ant leaves, Pis a set of Hamiltonian cycles such that (u, v)∈ P and T(k) ais the kcost of the acycle. Local search heuristic The local search used is based in a simple cycle modification that can be described as a node exchange heuristic. In essence, each pair of nodes is tested looking for switches that improve the cycle costs, i.e., a switch is performed if, by doing so, none of the costs are increased and at least one is diminished. 4 Results and conclusions Figure 1 compares the Pareto set ob- Figure 1: Pareto set obtained for the combination of kroa50 and kroa50 with our ACO based algorithm and MOGLS tained with our algorithm and the one determined with MOGLS (Multiple Objective Genetic Local Search) [Jaszkiewicz, 2000], for the combination of kroa50 and krob50 [TSPLIB, 2003]. Parameters α1, α2, β1, β2varied in {1, 5, 10},ρi= 0.1, i = 1,2, . . . ,m and only the elements in the Pareto set contributed to the variation of the pheromone trail at the end of each iteration. Conclusions As conclusion, the local search was used to face the fact that the pure ACO (with mpheromone trails) produced good initial approximations but had difficulties to improve those solutions. Therefore, as further work, the use of a more specific local search heuristic will probably reveal better performances. References [Cardoso, 2003] P. Cardoso, M. Jesus, A. M´arquez, MONACO - Multi-objective network optimisation based on ACO in Procedings of X EGC, Sevilla, 2003 [Dorigo, 2000] M. Dorigo, E. Bonabeau, G. Theraulaz, Ant algorithms and stigmergy in Future Generation Computer Systems 16 (2000) pp. 851−871, Elsevier [TSPLIB, 2003] www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95 (2003/07/28) [Merz, 2000] P. Merz, Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies, Doktor der Ingenieurwissenschaften genehmigte Dissertation [Jaszkiewicz, 2000] A. Jaszkiewicz, Genetic local search for multiple objective combinatorial optimization, European Journal of Operational Research, Vol. 137, No. 1, pp. 50–71, 2001