Genetic algorithm with neighbor solution approach for Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is an NP-Complete problem. Many techniques were developed to solve such problem, including Genetic Algorithms (GA's). The goal of this research is to enhance the performance of the Genetic Algorithm (GA) in solving the TSP. We achieve this goal by developing a local search algorithm called Search for Nearest Solution Algorithm (SNSA). This algorithm produces better solutions in acceptable periods of time. A new Crossover operator is proposed and used in the SNSA. Results for benchmark cases of the TSP show that the algorithm can find known optimum solutions. Comparisons between the proposed algorithm and other GA based methods with known crossover techniques show that SNSA has good quality solutions.
genetic algorithm traveling salesman problem nearest neighbor crossover least cost path