A Variety Of Group Adaptive Simulated Annealing Genetic Algorithm For Tsp

Traveling Salesman Problem, called TSP, has the widespread application background and the important theory value in combination optimizes, which is NP hard. The genetic algorithm is a kind of searching method which simulates the natural evolution. It is simple and easy to implement, especially it doesn't need the special field knowledge, so it has been used in every broad fields. Now the genetic algorithm has got a lot of fruits and more scholars begin to pay attention to it. In the genetic algorithm research, TSP question is widely adopted in appraising the different heredity operation and the performance to choose the mechanism. It is well known, the genetic algorithm has two serious shortcomings, namely easy premature restraining, as well as later period searching efficiency in the evolution to be low. Under this background, in view of above two shortcomings of the genetic algorithm, this article makes some improvement to the traditional genetic algorithm, proposed the multiple population Adaptive Simulated Annealing Genetic Algorithms to solve the Traveling Salesman Problem. This algorithm uses the adaptive crossover probability to carry on the roulette and most superior individual retention and the adaptive mutation probability carries on the mix mutation which use many kinds of mutation method unifies, introduces the partial search ability strong simulated annealing algorithm into the overall situation search ability strong genetic algorithm, and combines organically with the multi-population parallel heredity evolution thought. After some algebra of each sub population's evolution dependently, through the crossover and transfer, we can realize the population grading. The meaning of this grading lies here:it can makes the pieces of good gene in the good individual kept and optimization combined though crossover each other, and it also can makes the pieces of good gene in the bad individual kept through large probability crossover kept and combination, even improve. While processing, we can select and keep the good individual of each sub populations, and speed up the evolution speed while keeping the stability of the good individual evolution, and thus avoid the early constringency.By using the improved algorithm, to CH.N31, ATT48 and the EIL51 Traveling Salesman Problem, Simulation results show that this method not only avoids the premature convergence existed in genetic algorithms, but also enhances the globe convergence, thus improves the convergence velocity.