An appropriate representation of the Genetic Algorithm for the travelling alesmen problem

Abstract

In artificial intelligence, a Genetic Algorithm (GA) is a search that mimics the process of natural selection. It is routinely used to generate useful solutions to optimization problems. In a GA, we simulate the survival of the fittest among individuals over consecutive generation for solving problems. Choosing a representation in the design of a GA is the major problem. The Travelling Salesmen Problem (TSP) is an NP-Hard problem in Computational Optimization. Computation of the exact solution of the TSP requires an amount of computation time which is exponential in the size of the problem. In this research, TSP is solved by a new representation of GA. An encoding mechanism is developed and selection, crossover and mutation operators are defined. We have presented a GA variant for solving the TSP that uses the novel cross over method. In the crossover it uses one of the parent’s position of the gene structure to mate with other parent’s chromosomes. Our GA representation is tested with 17, 26 and 42 cities and found that our algorithm performs accordingly and generates expected near optimal results within acceptable levels. Using Brute force search for 17 cities problem, TSP would have needed checking 2.092279 x 10 to the power 2 possibilities, however GA within 1000 iterations gives the optimal solution. The actual answer for 17 cities TSP is 2085. We also ran GA for 26 cities and 42 cities TSP’s with average results of 1034 (actual 937) and 944 (actual 699) respectively for 5 runs when the population size, number of generations, max_crossover_gene parameter are increased to 500, 2000 and to 8 respectively, we got average of 994 and 837 for 26 cities and 42 cities TSP’s respectively. So, we could see that tuning of the GA parameters optimizes the result.