Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation

In this work an alternative representation for permutations which is robust under ordinary crossover and mutation, is proposed. This method is used for solving the TSP. 1 Introduction A well known computational problem is the the Travelling Salesman Problem (TSP) which is known to be NP \Γ complete. Here is the wording of it: N points (`cities'), as well as the cost of travelling between every pair of them is given. Assume that a salesperson, starting from a given city, has to visit each city exactly once and hence make a round-trip. The aim is to find an optimal tour in which the total cost of the round-trip is minimized. More formally, the TSP can be formulated as a problem of graph theory: Given a graph G on a set of N vertices, a closed sequence of edges in G (i.e. a cycle) which passes through each vertex of G exactly once is called a Hamiltonian Cycle. Given a complete weighted graph G on a set of N vertices (cities) the TSP is then the problem of finding the shortest Ham...