Based On Immune Algorithm For Solving TSP Problems

The TSP question is a typical NP(Non-deterministic Polynomial) question, solves the TSP problem in to be possible effectively to calculate theoretically has the important theory value. At present, the existing problems of various algorithms for solving TSP, based on human immunology and the new model of artificial immune - immune algorithm (Immune Algorithm, IA), with its strong convergence and better solution results and so become the focus of academic research. Artificial immune algorithm is immune to the concepts and the combination of theory and genetic algorithms, which not only preserves the good characteristics of the genetic algorithm itself, but also by increasing the immune operator to repress its iterative process of degradation occurs, and to improve the algorithm convergence speed. Immune algorithm is based on the immune system, learning algorithm, in solving the given optimization task (called antigens), the algorithm is beginning to collect some estimates of parameters (called antibodies), the fitness of each antibody and the concentration of its performance to assess. In each generation, the fitness is good, low concentration of antibodies to allow crossover and mutation to produce the next generation of new antibody formation. The biological immune system inspired by the algorithm can quickly export the complex issues of effective solutions. Immune algorithm is an important step in the cross. Solving the TSP is part of the traditional cross-match the cross, this approach requires a larger cross-population size, the algorithm less efficient, and easy to fall into local optimal solution.In this paper, the immune algorithm have been analyzed, and based on immune mechanisms of biological immune system made two improvements: (1) used in the algorithm is more similar to biological immune system, treatment of memory cells, by simply taking the best individual as the individual memory cells to generate memory cells in groups, to enhance the solution group in the evolution of diversity. (2) the introduction of "vaccine" concept, starting with the parent the information extracted by the vaccine, and vaccine-based crossover, the crossover effect has been significantly improved, that is introduced in the course of his cross-learning.First, the paper analyzes the performance of immune algorithm, several important parameters, and the simulation results select the appropriate parameter values. Secondly, in order to verify the effectiveness of ideas to improve the above two, with the vaccine based on immune algorithm cross-TSP problem is solved, the improved immune algorithm and basic immune algorithm and genetic algorithm were compared. Experimental results show the effectiveness of the improved method. Finally, the improved immune algorithm in the TSP tests internationally to find the library to find a best path than the library path and a better optimum path.