Mechanical Engineering, JSS Academy of Technical Education, Bangalore, Karnataka, India
Received date: February 16, 2015; Accepted date: October 21, 2015; Published date: October24, 2015
Citation: Raghavendra BV (2015) Solving Traveling Salesmen Problem using Ant Colony Optimization Algorithm. J Appl Computat Math 4:260. doi:10.4172/2168-9679.1000260
Copyright: © 2015 Raghavendra BV. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at Journal of Applied & Computational Mathematics
Ant Colony Optimization is a new meta-heuristic technique used for solving different combinatorial optimization problems. ACO is based on the behaviors of ant colony and this method has strong robustness as well as good distributed calculative mechanism. ACO has very good search capability for optimization problems. Travelling salesman problem is one of the most famous combinatorial optimization problems. In this paper we applied the ant colony optimization technique for symmetric travelling salesperson problem. Analysis are shown that the ant select the rich pheromone distribution edge for finding out the best path.
Ant colony optimization; Travelling salesman problems; Algorithm models
Ant Colony Optimization (ACO) is a relatively new meta-heuristic and successful technique in the field of swarm intelligence. This technique was first introduced by Dorigo and his colleagues [1,2]. This technique is used for many applications especially problems that belong to the combinatorial optimization. ACO algorithm models represent the behavior of real ant colonies in establishing the shortest path between food sources and nests. The ants release pheromone on the ground while walking from their nest to food and then go back to the nest. The ants move according to the richer amount of pheromones on their path and other ants would be followed and will tend to choose a shorter path which would have a higher amount of pheromone. Artificial ants imitate the behavior of real ants, but can solve much more complicated problem than real ants can.
ACO has been widely applied to solving various combinatorial optimization problems such as traveling salesman problem (TSP), job-shop scheduling problem (JSP), vehicle routing problem (VRP), quadratic assignment problem (QAP), etc. . Although ACO has a powerful capacity to find out solutions to combinatorial optimization problems, it has the problems of stagnation, premature convergence and the convergence speed of ACO is always slow. These problems will be more obvious when the problem size increases (Figure 1).
The traveling salesman problem (TSP) is the problem of finding a shortest closed tour which visits all the cities in a given set. In a symmetric TSP the distance between two cities is the same regardless of the direction of travel whereas in the asymmetric TSP the distance is different with regards to the direction of travel . This paper restricts attention to symmetric TSPs in which cities are on a plane and a path (edge) exists between each pair of cities. The definition of a TSP is: given N cities, if a salesman starting from his home city is to visit each city exactly once and then return home, find the order of a tour such that the total distances (cost/time/money/energy etc) traveled should be minimum. A complete weighted graph G= (N, E) can be used to represent a TSP, where N is the set of n cities and E is the set of edges (paths) fully connecting all cities. Each edge (i,j)∈E is assigned a cost dij, which is the distance between cities i and j [5-7].
The Ant System was first introduced and applied to TSP by Marcodorigo et al. Initially, each ant is placed on some randomly chosen city. An ant k currently at city i choose to move to city j by applying the following probabilistic transition rule:
where nij is the heuristic visibility of edge (i, j), generally it is a value of 1/dij, where dij is the distance between city i and city j. City J is a set of cities which remain to be visited when the ant is at city i. α and β are two adjustable positive parameters that control the relative weights of the pheromone trail and of the heuristic visibility. If α=0, the closed vertex i more likely to be selected. This is responding to a classical stochastic greedy algorithm. If β=0, only pheromone amplification is at work: This method will lead the system to a stagnation situation, i.e. a situation in which all the ants generate a sub-optimal tour. So the trade-off between edge length and pheromone intensity is necessary. After each ant completes its tour, the pheromone amount on each path will be adjusted according to equation (1-ρ) is the pheromone decay parameter (0< ρ <1) where it represents the trail evaporation when the ant chooses a city and decides to move. Number of ants represented by m, Lk is the length of the tour performed by ant k and Q is an arbitrary constant [8,9]. After all the ants complete their tour the pheromone is required to be updated using
In this paper a symmetric travelling salesman problem is presented for five cities. The distance of each city is given in the Table 1 and their visibility for each edge is shown in Table 2 and 3.
Table 1: Distance (dij) of cities.
Table 2: Visibility of edge = 1/dij.
Table 3: Randomly select the first City by each ant.
No of Ants=5
α =0.7, β=0.7, Q=1, Number of iteration=5
Initially pheromone (τ) distribution for each edge=1
Ant colony optimization methodology is presented for symmetric cities of travelling salesmen problem in this paper. A detailed procedure for city selection for respective ant is presented in the Tables 4-8 for iteration 1 to 5. The selection of next city is based on the maximum probability within the set of possible selection of the cities for next move. This is marked as ‘*’ in the respective iteration. In the Table 4, ant 2, 3 and 5 gives the minimum distance with the initially assumed pheromone which is one for each edge. The minimum distance remain same for the ant 2, 3 and 5 for iteration 2, however the pheromone (τ) distribution is different because of updating the pheromone in the iteration 2 for each edge based on the updating rule. In the iteration 4, the ant 1, 2, 3 and 5 are selected the best path with minimum distance. However in the iteration 5, all the ants are converged to the minimum distance. The pheromone (τ) distribution for iteration, 2, 3, 4 and 5 are updated for each iteration. The distribution of the pheromone (τ) for each edge is shown in the beginning of the respective table.
Table 4: Iteration-1.
Table 5: Iteration-2.
Table 6: Iteration-3.
Table 7: Iteration-4.
Table 8: Iteration-5.
It is shown in the iteration number 5 that all the ants converge to the best path which gives minimum distance. The pheromone distribution for iteration and the next city selection based on maximum probability is determined in the iteration. It is evident from the analysis that the rich pheromone edge is converges the best path for the travelling salesmen problems.
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals