A new genetic algorithm based on graph edges, for solving TSP

Traveling salesman problem (TSP) is an optimization problem classified in NP-Hard problems. This problem has a wide use in practical applications like urban transportation system. There are two approaches for optimization problem. Exact methods and approximation methods. Exact methods are good choices for small-scale problems due to large time complexity related to them while approximation methods are suitable for large-scale problems. Genetic algorithm is an approximation method uses nature patterns to find the solution and its basis is making a generation by optimized characteristics inherited from previous populations. In incomplete graphs, most of the algorithms make edges with infinity weight between city pairs that there is no direct path between them. Because computers have limited memories, they use large numbers instead of infinity values and causes problem in full automated algorithms that use TSP solution in a part of their process. In this paper, we proposed a new genetic algorithm for TSP which is basically different with existed genetic algorithms. Our genetic algorithm is defined based on existed edges in reference graph; this property enables algorithm to be processed based on real answers and returning true solution in incomplete graphs and also the possibility of distinguishing if there is no tour available in the graph. This is a helpful characteristic for automated algorithms uses TSP solution in their process.

Keywords:

Traveling salesman problem , TSP , Genetic algorithm , approximation approach