Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation
Göktürk Üçoluk · Intelligent Automation & Soft Computing · 2002
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 \\Gamma 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...