Travelling Salesman Problem Optimization Using Genetic Algorithm
Sahib Singh Juneja, Pavi Saraswat, Kshitij Kumar Singh, Jatin Sharma, Rana Majumdar, Sunil Kumar Chowdhary · 2019
Optimization problem is which mainly focuses on finding feasible solution out of all possible solutions. Travelling salesman problem belongs to this one. As it is not possible to find its solution in definite polynomial time that is why it is considered as one of the NP-hard problem. This paper utilizes the optimization capability of genetic algorithm to find the feasible solution for TSP. The algorithm starts with the calculation of Euclidean distance between the towns to be visited by the salesman. Initial chromosome pool is generated using value encoding. Then best fit chromosomes are selected by applying roulette wheel selection which then goes through m-point crossover. Now we apply interchange mutation on the offsprings generated before. Now this whole process is repeated until the convergence of genetic algorithm.