Applied Research Of Hybrid Genetic Algorithm And Simulated Annealing Algorithm In Traveling Salesman Problem

This paper introduces the main ideas of the several common algorithms of solving TravelingSalesman Problem. It is shown that the Genetic Algorithm and Simulated AnnealingAlgorithm had certain advantages in the process of solving TSP. And these two algorithmshave been widely used in solving practical problems. This paper makes a deep research andprogramming with these two algorithms and then has found some defects of GeneticAlgorithm which based on global search and Simulated Annealing Algorithm which based onlocal search. On the basis of these two algorithms, this paper presents the improved algorithmrespectively and verifies the effectiveness of the improved algorithm. At the same time, basedon two kinds of improved algorithm, this paper proposes a hybrid genetic and simulatedannealing algorithm, which used to solve the TSP. First of all, the hybrid algorithm producesthe initial population through a hybrid method, which improving the quality of the initialpopulation and increasing the probability of the search to the optimal solution. Second, thehybrid algorithm on a selective basis which can give full play to the characteristics of theexcellent genes and greatly reducing the genetic algebra improves the convergence speed andeffectively prevent precocious phenomenon to avoid falling into local optimal solution.Finally, the hybrid algorithm using simulated annealing process improves the probability ofgetting a more optimal solution and then optimize the path one more in order to make thebetter solution as soon as possible. Compared to the single genetic algorithm or simulatedannealing algorithm, the hybrid algorithm shows the superior feasibility and superioreffectiveness by instances.