Reach Us
+44-7482-875032

Mechanical Engineering, JSS Academy of Technical Education, Bangalore, Karnataka, India

- *Corresponding Author:
- Raghavendra BV

Mechanical Engineering, JSSAcademy of Technical Education

Uttarhalli-Kengeri Road, Bangalore

Karnataka, 560060, India

**Tel:**01202400104

**E-mail:**[email protected]

**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. [3]. 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 [4]. 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 d_{ij}, 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 n_{ij} is the heuristic visibility of edge (i, j), generally it is a value of 1/d_{ij}, where d_{ij} 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, L_{k} 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

Where

Tour Length:

**Methodology**

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**.

Cities/ Cities |
A | B | C | D | E |

A | ∞ | 3 | 6 | 2 | 3 |

B | 3 | ∞ | 5 | 2 | 3 |

C | 6 | 5 | ∞ | 6 | 4 |

D | 2 | 2 | 6 | ∞ | 6 |

E | 3 | 3 | 4 | 6 | ∞ |

**Table 1:** Distance (d_{ij}) of cities.

Cities/ Cities |
A | B | C | D | E |

A | ∞ | 0.33 | 0.16 | 0.5 | 0.33 |

B | 0.33 | ∞ | 0.2 | 0.5 | 0.33 |

C | 0.16 | 0.2 | ∞ | 0.16 | 0.25 |

D | 0.5 | 0.5 | 0.16 | ∞ | 0.16 |

E | 0.33 | 0.33 | 0.25 | 0.16 | ∞ |

**Table 2:** Visibility of edge = 1/d_{ij}.

Ant | 1 | 2 | 3 | 4 | 5 |

City | A | B | C | D | E |

**Table 3:** Randomly select the first City by each ant.

**Parameter selection**

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**.

- Dorigo CM, Maniezzo V,Colorni A (1996)The ant system: Optimization by a colony of cooperating agents.IEEETransactions on System. Man and Cybernetics 26: 29-41.
- BlumC (2005) Ant Colony Optimization-Introduction and recent trends.Physics of LifeReviews 2(4): 353-373.
- SuHlaing ZCS, Khine MA (2011) Solving Traveling Salesman Problem by UsingImproved Ant Colony Optimization Algorithm. International Journal ofInformation and Education Technology 1(5): 404-409.
- JaiswalU, Aggarwal S (2011) Ant Colony Optimization. InternationalJournal of Scientific & Engineering Research 2(7): 1-7.
- HingrajiyaKH, GuptaRK, Chandel GS (2012) An Ant Colony Optimization Algorithm for SolvingTravelling Salesman Problem. International Journal of Scientific and ResearchPublications 2(8):1-6.
- DorigoM, Gambardella LM(1997) Ant colonies for the traveling salesman problem. BioSystemspp: 73-81.
- Dorigo M, Gambardella LM(1997) AntColony system -A cooperative learningapproach to the Travelling salesman problem. IEEE Transactions on EvolutionaryComputation1(1).
- Dorigo M,Stutzle T (2004) Ant ColonyOptimization.MIT Press.
- Rao SS (2009) EngineeringOptimization-Theory and Practice (4thEdn).John Wiley & Sons, Inc.

Select your language of interest to view the total content in your interested language

- Adomian Decomposition Method
- Algebraic Geometry
- Analytical Geometry
- Applied Mathematics
- Axioms
- Balance Law
- Behaviometrics
- Big Data Analytics
- Binary and Non-normal Continuous Data
- Binomial Regression
- Biometrics
- Biostatistics methods
- Clinical Trail
- Complex Analysis
- Computational Model
- Convection Diffusion Equations
- Cross-Covariance and Cross-Correlation
- Differential Equations
- Differential Transform Method
- Fourier Analysis
- Fuzzy Boundary Value
- Fuzzy Environments
- Fuzzy Quasi-Metric Space
- Genetic Linkage
- Hamilton Mechanics
- Hypothesis Testing
- Integrated Analysis
- Integration
- Large-scale Survey Data
- Matrix
- Microarray Studies
- Mixed Initial-boundary Value
- Molecular Modelling
- Multivariate-Normal Model
- Noether's theorem
- Non rigid Image Registration
- Nonlinear Differential Equations
- Number Theory
- Numerical Solutions
- Physical Mathematics
- Quantum Mechanics
- Quantum electrodynamics
- Quasilinear Hyperbolic Systems
- Regressions
- Relativity
- Riemannian Geometry
- Robust Method
- Semi Analytical-Solution
- Sensitivity Analysis
- Smooth Complexities
- Soft biometrics
- Spatial Gaussian Markov Random Fields
- Statistical Methods
- Theoretical Physics
- Theory of Mathematical Modeling
- Three Dimensional Steady State
- Topology
- mirror symmetry
- vector bundle

- Total views:
**15352** - [From(publication date):

December-2015 - Aug 19, 2019] - Breakdown by view type
- HTML page views :
**14633** - PDF downloads :
**719**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2019-20