Genetic Algorithm with mixed crossover approach for Travelling Salesman Problem

Abstract

In the first part we are going to discuss about the Travelling Salesman Problem. As we are aware of that the Travelling Salesman Problem is an NP-hard problem thus it is impossible to solve it through the normal algorithm or say deterministic algorithm. If the number of cities in Travelling Salesman Problem is very small say 4-5 then we can think of solving it through brute force approach but the number of cities becomes 100-200 then it is impossible to comprehend as the number of possible solution or routes increases exponentially relative to the number of cities. Then we discuss about the benefits of Genetic Algorithm and how we can apply the study or use the benefit of Genetic Algorithm to solve Travelling Salesman Problem. Also we are going to go through every step of Genetic Algorithm and see very closely how all the work is done on every step. Then we are going to discuss about the background we have gone through like what kind of work or development has been done ever since in every other research papers. Then we are going to discuss about our methodology in a very detailed manner i.e. the actual method or process we have used or proposed in our paper. As we were going through it we realize as why we take some values of crossover or mutation rating as optimal for some problem not optimal for other, how do we decide it and why we do it, what difference does it make to our implementation. We have tried to answer this kind of question through our paper. And finally we go through the conclusive part of our work and talk about possibilities in future or possible work that can be done in the near future.