Analysis of Travelling Salesman Problem Using Ant Colony Optimization, Genetic Algorithm and Hybrid of Ant Colony Optimization and Genetic Algorithm

Analysis of Travelling Salesman Problem Using Ant Colony Optimization, Genetic Algorithm and Hybrid of Ant Colony Optimization and Genetic Algorithm

Analysis Of Travelling Salesman Problem Using Ant Colony Optimization, Genetic Algorithm And Hybrid Of Ant Colony Optimization And Genetic Algorithm

Anita Kumari1, Supreet Singp

1Electronics & Communication Engg, Punjab Technical University/ BBSBEC Fatehgarh Sahib, Punjab, India.

2Electronics & Communication Engg, Punjab Technical University/ BBSBEC Fatehgarh Sahib, Punjab, India.

Abstract

Traveling Salesman Problem (TSP) is a TSP problem where each customer has a given probability of requiring a visit. The goal is to nd a priori tour of minimal expected length over all customers, with the strategy of visiting a random subset of customers in the same order as they appear in the priori tour. Travelling salesman problem (TSP) is one of the optimization issues which it is not solvable with classical methods. There had been many attempts to address this problem using classical methods such as integer programming and graph theory algorithms with different success. In the proposed work a solution is offered which includes Ant Colony Optimization, Genetic Algorithm and hybrid of ACO and GA.In this paper Best route, Route length, jitter factor and Propagation delay is obtained for ACO, GA and Hybrid.

Keywords-TSP,Optimization, GA, ACO.

1. INTRODUCTION

   The Travelling problems of all time,A salesman visits N cities with given positions and returns finally to his city of origin. Each city is to be visited only once, and the problem is to find the shortest possible route. This problem belongs to a class known as NP-complete problems. TSP is one of the most studied optimization problem today. TSP is still a case for intensive studies in many fields; one of the reasons for this is that TSP is a NP-complete problem. In The field of algorithms there are manyclassifications of problems, two of the most important ones are the classes of P and NP. If a problem is in P, it is reckoned that the problem is possible to solve on regular computers within reasonable time. If it is classified as NP as a rule of tomb it is notpossible to do so. NP can be solved in such a way, that the two classes P and NP is equal to each other. In NP there exists a set of problems which is called NP- Complete. These problems have the property that if one of those problems can be classified to be in P, all other problems in NP are also in P. Since the TSP is NP-Complete, it is therefore interesting in both the field oftheoretical studies of the problem P=NP VS P NP, and in the field of approximation heuristics.

   The general problem of travelling salesman can be stated as the

   following: If we are given a set of cities {c1, c2, c N} and for each pair {ci, cj} of distinct cities the distance between them is d(ci, cj). If a line is drawn through all the cities visiting each city only once, and end up where it started. The goal is to find an ordering of the cities that minimizes the total length of that line. This creates a Hamiltonian cycle in the graph of cities.

   In the past two decades, new computational methods such as refrigeration algorithms, multilevel approach, ACO, GAs and Artificial Neural Networks to solve the problem of TSP have been suggested for average length. Of these methods, which both GAs and ACO is based on repetitive, in finding solutions close to the optimal solution for problems, hybrid optimization has been considered mostly.In the proposed work three optimization techniques are presented such as ACO, GA, Hybrid of ACO and GA. In later section, we will discuss theliterature survey with the techniques used to tackle the above discussed problem.

   1. LITERATURE SURVEY

• Kang[2]et.al proposed An Improved Genetic & Ant ColonyOptimization Algorithm for Travelling Salesman Problem. ACA and GA are two bionic optimization algorithm, they are also twopowerful andeffectivealgorithms for solving the combination optimization problems, moreover they all were successfully used in traveling salesman problem(TSP). The proposed work syncretizes two algorithms; meanwhile, a new syncretic method is put forward. The simulation results show that the newalgorithm of ACA and GA is better at improvingglobal convergence and quickening the speed of convergence.Ant Colony Algorithm (ACA) and Genetic Algorithm (GA) enlightened by biologic evolutionism are put forward as a kind of bionic algorithms.

• Gharehchopogh[3] et.al proposed Genetic Algorithm (GA) and Ant Colony Optimization (ACO) as Hybrid Algorithm to solve DTSP. In this,suitability of algorithm and travelled distance for DTSP has been considered. Obtained results suggest that Hybrid algorithm does not establish easily in the local

  optimum andpossesses a good speed in convergence for comprehensive answer.The objective function is intended to minimize the travelled distance. Therefore, it is possible to choose the suitability according to travelled, in such a way that for shorter distances more amount of suitability is considered.

• Sadiq[4] et.al proposed optimizing delivery routes usingGeneticAlgorithms.The proposed methodology of optimizing delivery route scheduling using GA to solve the Multiple Traveling Salesman Problem (mTSP). The traveling salesman problem(TSP)isa combinatorial optimization problem where a salesman must find the shortest route to n cities and return to a home base.With robust clustering and genetic algorithm procedures provides an ideal environment to solve this type of problem.

• Dwivedi[5] et.al proposed flexible method for solving the travelling salesman problem using genetic algorithm. The proposed work offers a solution which includes a genetic algorithm implementation in order to give a maximal approximation of the problem with the reduction of cost. In genetic algorithmcrossoveris as a main operator for TSP. There were lot of attempts to discover an appropriate crossover operator. The efficiency of the crossover operator is compared as against some existing crossover operators. The work proposed here intends to compare the efficiency of the new crossover operator with some existing crossover operators.

• Hlaing[1] et.al proposed Solving Traveling Salesman ProblembyUsingImproved Ant Colony Optimization Algorithm.. TSP is one of the most famous combinatorial optimization problems and which has wide application background. ACO has very good search capabilityfor optimization problems,but it still remains a computational bottleneck that the ACO algorithm costs too much time to convergence.

1. TECHNIQUES USED

   ACO: ACO presented for the first time by Dorigoas a Multi- Agent Solution for difficult problems of TSP. ACO is one of collective intelligence algorithms. The main idea of collective intelligence algorithms is to use the real life of creatures that without using complex mechanisms run their social life in all its aspects as best as possible. ACO is one of the optimization algorithms which are inspired from observations and studies on the ACO. ACO for the Traveling Salesman Problem, a set of cities is given.The goal is to find the shortest tour that allows each city to be visited once and only once. In more formal terms, the goal is to find a Hamiltonian tour of minimal length on a fully connected graph. In ant colony optimization, the problem is tackled by

   simulating a number of artificial ants moving on a graph that encodes the problem itself.Ant colony optimization is an iterativealgorithm. At the end of an iteration, on the basis of the quality of the solutions constructed by the ants, the pheromone values are modified in order to bias ants in future iterations to construct solutions similar to the best ones previously constructed.

   Figure.1 Optimization by Ant Colony

   GA: GA is an iterative process that includes a population of individuals or chromosomes which are randomly or heuristic that each one by a string of symbols as a gene in possible solution on the issue has been coded. GA usually are used in search spaces which are very large. People can select an operation, integration and mutation to obtain a higher fitness values to search for the best solution to the problem.The process involves generating random solutions and applying genetic operators in hopes that the solutionwill evolve to find the optimal solution. This process can be characterized by four stages: During initialization, a random set of solutions is generated to form an initial population. These random solutions are generated from the entire range of possible solutions (the search space).Once an initial population has been formed, the solutions are evaluated based on the fitness function (equivalent to an objective function).The best solutions are then selected to breed a new population. During the reproduction phase, genetic operators are applied to the solutions in order to breed new characteristics.The most commonly used operators are mutation andcrossover: Crossover operations involve combining two solutions (parents) to produce more solutions (children). Genetic material from the previous generation is given to the subsequent generation maintaining fitness strength. Mutation operations involve randomly changing some characteristics of a solution.Thisintroduces a certain amount of randomness into the search and

   Fig.2Four Stages of Genetic Algorithms

   prevents premature convergence to a sub-optimal solution.

   Hybrid: Hybrid of ACO and GA is a third technique proposed in this paper. The objective function is intended to minimize the travelled distance.To minimize the route, the travelled distance by ants as a suitability value is used. Therefore, it is possible to choose the suitability according to travelled, in such a way that for shorter distances more amount of suitability is considered. In recent decades, many efforts to improve the quality of the answer – obtained by this algorithm are applied. Hybrid algorithms are part of these activities. Due to the similar structure of ACO and GA there is idea to combine and proposed a new algorithm. In the hybrid algorithms, initial answers of ACO among the obtained data from routes for the mutations are selected by GA. GA answers have been used for a wide range of ants search. In the GA there are optimal solutions to achieve a better answer in every generation. Consequently, the GA using efficient routes of ACO, explores the most efficient way in search space till in a new searching point moves towards the better solutions. GA as a computational algorithm for optimization with regards to a set of answer points in each iteration computation searches effectively the different parts of answer. In hybrid method unlike ACO all the all-round solution space is searched, therefore there will be less possibility for convergence to local optimum. You see the overall view of the hybrid algorithm in Fig.3 As the figure implies the algorithm has three basic concepts: ACO, GA and hybrid, comparing answers part which is explained in the following.

   242

   242

   100

   0

   100

   0

   1

   1

   1.3

   1.3

   20 2.2

   20 2.2

   12.5

   12.6

   12.5

   12.6

   Jitter

   Jitter

   Fig..3The Proposed Hybrid ACO and GA Algorithm for TSP

   Algorithm

   Begin:

   Initialize Pheromone matrix

   Read and initialize distance matrix n :=1 (number of ants)

   Do while n<Max Iteration

   If current node is not the last node, choose next feasible node on the basis of pheromone density, at equal

   Situation, choose it randomly. n :=n + 1

   Calculate Fitness

   g:= 0; (number of generation) Calculate Fitness

   While (not Terminate-Condition)

   {

   g ++;

   GA- Fitness ;

   }

   End

   4 RESULT

   In order to show that the proposed paper has good performance for Travelling salesman problem. ACO, GA and Hybrid are used to calculate parameters: best distance, best route, jitter factor and propagation delay as shown in table for 30 cities and 50 cities and comparing the results.In this paper the parameters of improved hybrid algorithm are as follows: m=20,=1.5, =2, =0.9, Pc=0.8, Pm=0.8,Q=100000.

   Best Distance

   Best Distance

   TABLE: 1

   S.No.	No. of Cities.30	Hybrid	ACO	GA
   1	Jitter	1.3	20	12.6
   2	Propagation Delay	1	2.2	12.5
   3	Best Distance	242	315	543

   543

   543

   600

   500

   400

   300

   200

   315

   600

   500

   400

   300

   200

   315

   Hybrid ACO

   GA

   Hybrid ACO

   GA

   Jitter

   Propagation Delay

   Best Distance

   Jitter

   Propagation Delay

   Best Distance

   Fig..4

   Best route for 30 cities is represented by graph for TSP:

   TABLE: 2

   S.No.	No. of Cities.50	Hybrid	ACO	GA
   1	Jitter Factor	15.2	20.2	21.6
   2	Propagation Delay	1	2.5	15.1
   3	Best Distance	321.8	404	1015

   Fig.5 Best route is represented by GA for TSP

   2000

   1000

   0

   1015

   321.8 404

   1 2.5 15.1

   15.2 20.2 21.6

   Hybrid ACO GA

   Fig.6 Best route is represented by ACO for TSP

   Fig.7 Best route is represented by Hybrid for TSP

   Jitter Factor Propagation Delay Best Distance

   Fig.8

   Best route for 50 cities is represented by graph for TSP:

   Fig.9 Best route is represented by GA for TSP

   Fig.10 Best route is represented by ACO for TSP

   Fig.11 Best route is represented by Hybrid for TSP

   S.N o	Paramet ers	Hybrid		ACO		GA
   1	No. of Cities	30	50	30	50	30	50
   2	Jitter	1.3	15	20	20	13	21.6
   3	Propagat ion Delay	1	1	2.2	2.5	13	15.1
   4	Best Distance	242	322	315	404	543	1015

   S.N o	Paramet ers	Hybrid		ACO		GA
   1	No. of Cities	30	50	30	50	30	50
   2	Jitter	1.3	15	20	20	13	21.6
   p>3	Propagat ion Delay	1	1	2.2	2.5	13	15.1
   4	Best Distance	242	322	315	404	543	1015

   TABLE: 3

   No. of Cities Jitter Propagation Delay Best Distance

   1015

   242 321.8 315 404 543

   1 2.2 2.5

   1 2.2 2.5

   1

   1.3 15.2

   Fig.12

   1. CONCLUSION AND FUTURE SCOPE

      As shows in tables and graphs best route, best distance, jitter factor and propagation delay parameters are calculated for 30 and 50 cities. As observed Hybrid algorithm shows better result in case of all parameters. Hybrid algorithm was developed to assist the user to obtain optimal tour to visit n cities. In the future,hybrid algorithm can be designed to further improve performance, parameters , to be adaptive adjust or other improvement strategy will be introduced and also apply on wirless networks. Performance of improved hybrid algorithm need be further tested and verified in other typical combinatorial optimization problem and continuous space optimization problem in order to broaden applied research field practical problem.

   2. REFERENCES

      1. Hlaing Zand Khine. M An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem 2011 International Conference on Information Communication and Management vol.16 ,2011, Singapore

      2. Kang.L and Cao.W An Improved Genetic & Ant Colony Optimization Algorithm for Travelling Salesman Problem,ThirdInternational Symposium on Information Science and Engineering, 2010 IEEE.

      3. Gharehchopogh.F,Maleki.I and Farahmandian.M New Approach for Solving Dynamic Travelling Salesman Problem with Hybrid Genetic Algorithms and Ant Colony OptimizationInternational Journal of Computer Applications, Volume 53 No.1, September 2012.

      4. Sadiq.S, The Traveling Salesman Problem: Optimizing Delivery Routes Using Genetic Algorithms,SAS Global Forum 2012.

      5. Dwivedi.V, Chauhan.T, Saxena.S and Agrawal.P Travelling Salesman Problem using Genetic Algorithm National Conference on Development of Reliable Information Systems, Techniques and Related Issues (DRISTI) 2012.

      6. Afaq H. and Saini S. On the Solutions to the Travelling Salesman Problem using Nature Inspired Computing Techniques IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011 ISSN (Online): 1694-0814.

30 50

20 20.2

30

30

50

12.5 15.1

12.6 21.6

30 50

Hybrid ACO

GA