Exploring Travelling Salesman Problem using Genetic Algorithm

Exploring Travelling Salesman Problem using Genetic Algorithm

Alka Singh

1. ech. Scholars, Dept. of Computer Science & Engg. IEC- College of Engineering & Technology

   Greater Noida, U.P., INDIA

   Rajnesh Singh

   Associate Professor, Dept. of Computer Science & Engg.

   IEC-College of Engineering & Technology Greater Noida, U.P., INDIA

   Abstract – Genetic Algorithms (GAs) is an evolutionary search algorithm used to find out optimal solutions for various NP problems. An effective chromosome representation, a carefully designed crossover and mutation operators are needed in GAs to achieve an efficient search. Travelling salesman problem (TSP) is a combinatorial optimization problem. It is NP complete problem and is the most commonly studied problem in the area of optimization. But the complexity of the problem goes on increasing, as the number of cities increases. The objective of this study is to solve TSP using GAs approach. In the genetic algorithm system begins from a matrix of the calculated distance between the cities to be visited by the travelling salesman and randomly chosen city sequence as the initial population. Then new generations are formed repetitively until the suitable path is reached. Genetic algorithms use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover.

   Keywords–Genetic Algorithm, TSP, Selection, Crossover, Mutation, Enhanced Edge Recombination.

   1. INTRODUCTION

      Travelling salesman problem (TSP) is the most familiar combinatorial optimization problem. TSP is a permutation problem with the aim of searching the path of the shortest length (or the minimum cost). TSP can be represented as an undirected weighted graph, such that cities are the vertices, paths are the edges, and a paths distance is the edges length in the graph. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. TSP is used to find out the route for a salesman who begins from a home location, visits a given set of cities and returns to the original location.

      The route selected in such a manner that the total distance travelled is minimized and each city is visited exactly once. This problem is also known as NP-hard, and cannot be solved accurately in polynomial time. A lot of heuristic algorithms have been developed and proposed in the field of operations research to solve this problem. When there is less number of cities TSP is solved very easily, but as the number of cities grows it becomes very hard to solve, as huge amount of computation time is required. TSP can be used in numbers of fields very effectively such as military and traffic. Genetic algorithm is another approach to solve TSP because of its flexibility and robustness. Some distinctive applications of TSP comprise vehicle routing, computer wiring, cutting wallpaper and job sequencing etc.

   2. GENETIC ALGORITHM

      Genetic algorithm is pioneered by John Holland in the 1970s but it got popular in the late 1980s. Genetic Algorithms are search and optimization techniques based on Darwins Principle of Natural Selection. Darwins principle of Natural Selection can stated as select the best and discard the rest. For example assume a population of animals of a particular species in a jungle. Some animals in the population are stronger than the others and these characteristics help them to survive better in that environment as compared to the others. Suppose, the natural resources like water and food are limited in the jungle. So, these animals have to compete with each another for the resources. Finally, only the strongest or fittest individuals will survive and the rest will finish. GAs is used to solve a variety of problems that are not simple to solve using other

      Figure1. Flowchart of applied Gas

      The basic steps involved in genetic algorithm are-Evolution, Crossover and Mutation. Genetic algorithms implement optimization strategies by simulating evolution of species through natural selection. GA commences with various problem solution which are encoded into population. For evaluating the fitness of each individual a fitness function is applied, through the process of selection a new generation is created, after that crossover and mutation is applied on the created new generation. After the termination of genetic algorithm, an optimal solution is obtained. If the termination condition is not satisfied then with new population algorithm continues. The flowchart for applied GA is described in fig.1

   3. IMPLEMENTATION OF TSP USING GENETIC ALGORITHM

      To apply genetic algorithm for the TSP, the encoding solution is represented by chromosome. The chromosomes length is equal to number of nodes in the problem. Here we have explained the working of the GAs on a problem of 6 cities.

      1. Encoding

         We have considered six Indian cities such as- Delhi, Jaipur, Hyderabad, Pune, Haridwar and Surat and assign a number to each. Thus a path would be represented as a sequence of integers from 1 to 6. This is an example of Permutation Encoding as the position of the elements determines the fitness of the solution. The distances between different cities are represented as distance matrix .The distance matrix of the problem is given in table 1. The distance-matrix is symmetric; therefore, the part above the main diagonal contains all necessary information. The distance between the cities is measured to be symmetric that is if the salesman travels from city 1 to city 6 than the distance is same if he travels from city 6 to city 1. Due to this half of the matrix is empty. The first row and column denotes the city.

         Table 1.Distance matrix of 6 cities

         city	1	2	3	4	5	6
         1	0	261	1499	1417	203	1170
         2		0	1454	1207	939	922
         3			0	541	1679	890
         4				0	1806	362
         5					0	1552
         6						0

         *distance in km

         Here the initial population consists of six chromosome, where each chromosome represent the sequence through which cities have to be traversed and each gene represent the number assigned to a city.

         Chromosome 1 1 4 3 2 5 6

         Chromosome 2 1 4 2 6 5 3

         Chromosome 3 3 6 1 4 2 5

         Chromosome 4 6 3 1 5 2 4

         Chromosome 5 5 2 6 1 3 4

         Chromosome 6 2 6 3 1 5 4

      2. Fitness Function

         The main motive of fitness function is to choose if a chromosome is good. The criteria in the travelling salesman problem for good chromosome are its length. The fitness function will be the total cost of the tour represented by each chromosome. This can be calculated as the sum of the distances traversed in each travel segment. Lesser the sum, fitter is the solution.

      3. Selection

         Selection is used to pick the chromosome whose fitness value is less. Here we have used the tournament selection. As the name reflects tournaments are played between two solutions and the supeior solution is selected and placed in the mating pool. Two other solutions are chosen again and another slot in the mating pool is filled up with the better solution as shown in fig. 2

         Enhanced Edge Recombination Algorithm

         • Randomly choose the initial city from one of the two parents as a current city.

         • Remove all the occurrence of the current city from the edge table and add the current city in the edge list.

         • Select the cities in the edge-table which has the fewest entries in its own edge-list. The city with fewest entries now becomes the current city. Preference is given in case a negative integer is present.

         • If any tie occurs, it is broken randomly.

      4. Crossover

         Figure2. Selection Operator

      5. Mutation

         Mutation is useful to generate a new generation. The mutation induces a change in the solution, to maintain the diversity in the population and to prevent premature conversion. In this paper we have mutate the string by randomly selecting any two cities and interchanging their positions in the solution, thus giving rise to a new tour as shown in fig. 4.

         Single point crossover method randomly selects a crossover point in the string and swaps the substrings. But in TSP single crossover method is not used, as it may produce some invalid offspring. For solving TSP we have used the Enhanced Edge Recombination operator. This operator is different from other genetic sequencing operators as it emphasizes adjacency information rather than the order or position of items in the sequence. Edge-Recombination Operator algorithm involves constructing an Edge Table first. The Edge Table is an adjacency table that lists links into and out of a city found in the two parent sequences. If an item is already exists in the edge table and we are inserting it again, it shows that the particular element of a sequence must be a common edge and is represented by inverting its sign.Fig.3 shows the edge table of two selected parents.

         Figure3. Edge table of two parents

         Figure4. Interchange Mutation

      6. Termination and Result

      After the number of operators, such as selection, crossover and mutation have been applied to the problem, the best tour will be obtained and the process will be terminated. The tour between the six cities with minimum distance is 3968km as shown in figure 5.

      Figure5. Minimum Distance between 6 cities

   4. CONCLUSION

      Genetic Algorithms employ optimization strategies based on simulation of the natural law of evolution. By combining the knowledge of GAs for solving TSP is an optimistic approach. Depending on the manner the problem is encoded and which crossover and mutation methods are used, genetic algorithm find fine solutions for the travelling salesman problem. Through this paper our objective is to give a very effective process for solving TSP by using the genetic algorithm. In this paper we have solved the symmetric TSP but in future we would like to solve asymmetric TSP as well. Genetic algorithm is applicable in various artificial intelligence approaches as well as different fundamental approaches like object-oriented application and robotics etc.

   5. ACKNOWLEDGEMENT

We would like to thanks all the people who directly or indirectly helped us and we would also extend my sincere thanks to our Head of the Department, Computer Science and Engineering.

REFERENCES

1. Chetan Chudasama, S. M. Shah and Mahesh Panchal, Comparison of Parents Selection Methods of Genetic Algorithm for TSP, International Conference on Computer Communication and Networks (CSI- COMNET), 2011.

2. Dwivedi, TarunaChauhan,SanuSaxena and PrincieAgrawal, Travelling Salesman Problem using Genetic Algorithm, International Journal of Computer Applications(IJCA), 2012, pp. 25-30.

3. Naveen kumar, Karambir and Rajiv Kumar, A Genetic Algorithm Approach To Study Travelling Salesman Problem, Journal of Global Research in Computer Science, 2012, Vol. 3, No. (3).

4. Adewole Philip, AkinwaleAdioTaofiki and OtunbanowoKehinde, A Genetic Algorithm for Solving Travelling Salesman Problem, International Journal of Advanced Computer Science and Applications, 2011, Vol. (2), No. (1).

5. Ivan Brezina Jr.,ZuzanaCickova, Solving the Travelling Salesman Problem using the Ant colony Optimization, Management Information Systems, 2011, Vol. (6), No. (4).

6. ButhainahFahran, Al-Dulaimi, and Hamza A. Ali, Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA), World Academy of Science Engineering and Technology, 2008, Vol. (14).

7. Naef Taher Al Rahedi and Jalal Atoum, Solving TSP problem using New Operator in Genet ic Algorithms, American Journal of Applied Sciences 6(8):1586- 1590, 2009.

8. H. Braun, On Solving Travelling Salesman P roblem by Genet ic Algorithm, in P arallel P roblem-Solving from Nature, Lecture Notes in Computer Science 496, H.P. Schwefel and R. Manner Eds, Springer- Verlag, app. 129-133.

9. R. Poli and W. B. Langdon. Genetic Programming with One-point Crossover and Point Mutation. Technical Report CSRP-97-13, University of Birmingham, School of Computer Science, Birmingham, B15 2TT, UK, 15 Apr. 1997.

10. Alka Singh Bhagel and Ritesh Rastogi, Effective Approaches for Solving Large Travelling Salesman Problems with Small Populations, International Journal of Advances in Engineering Research (IJAER), 2011, Vol. (1), Issue (1).