Research Of Genetic-Ant Colony Hybrid Algorithm Based On Traveling Salesman Problem

Traveling Salesman Problem is a representative and the most study NP-Hard problem in the field of combinatorial optimization.It is the concentrated generalization and simplified form of variety complex problem. It is widely used in industry, agriculture, national defense, architecture, business, especially railway transportation, etc. So effectively resolve TSP problem will directly drive the combinatorial optimization field new development, and it has the extensive practical value. In addition, because of the TSP's representative, it has become the indirect compare standards of heuristic search and optimization algorithm.Therefore, the study of TSP has important theoretical value.With the development of the computer, the researchers suggest many intelligent algorithms for solving TSP. The genetic algorithm is a kind of searching method which is the most widely used and has the long research history. Ant colony algorithm is a relatively new algorithm which has the positive feedback mechanism and good at combinatorial optimization problem.Therefore, using genetic algorithm and ant colony algorithm solving TSP are representative.But with the problems of the scale and complexity is more and more big, the single genetic algorithm and the ant colony algorithm already cannot satisfy the requirements,so a hybrid algorithm integrated genetic algorithm with ant colony optimization for solving TSP was studied,and it also is representative.This paper has done some work in hybrid algorithm of solving TSP:1. In order to play better performance of genetic algorithm in hybrid algorithm, this paper discussed the best combination of crossover operator and mutation operator. Several TSP were used as simulation tests to find the best combination operators.2. Due to the ant colony algorithm of ant colony operation parameters have important influence in hybrid algorithm. Therefore, this paper makes a detailed analysis on various parameters on the influence of ant colony algorithm. We present using genetic algorithm to optimize three parameters to find out optimal parameter values. Several TSP were used as simulation tests to test successful and available. It provides methods for find out parameter combination of solving specific problems.3. This paper studies two key points of the hybrid algorithm integrated genetic algorithm with ant colony optimization. Two new strategies called dynamic combination and GSA was proposed aiming at convert genetic solution from genetic algorithm into information pheromone to distribute in ant colony algorithm. Several TSP were used as simulation tests to test successful and available.4. Finally the hybrid algorithm based on genetic algorithm and ant colony algorithm is applied to optimize holes machiningpath optimization and baiyang lake tourist route planning. It proved this method has wide application prospects in practical application.