Research On Hybrid Genetic Algorithm For Solving The Traveling Salesman Problem

The traveling salesman problem is a classic NP-hard problem, has been a hot research scholars, the traveling salesman problem is also called the "traveling salesman problem", refers to a businessman traveled widely promoting their products, to find the city passing all plans once and go back to the origin of the shortest path. Traveling salesman problem in network routing, robot control, VLSI wiring has wide application background.Genetic algorithm for its excellent performance, good robustness and portability, has become a study combinatorial optimization problems commonly used algorithm.First this paper studies the development status of the traveling salesman problem and the current solution, discusses the classification and mechanisms of multi-objective evolutionary algorithm, and gives a detailed description of one of the most representative algorithms.Secondly, for use in traditional genetic algorithm crossover operator and does not handle the traveling salesman problem, easily disrupted gene fragment sequence, the loss of genetic information, this paper proposes a new crossover operator, Corresponding Connected Subgraph Crossover. And introducing niche operation, the new immigration algorithm and local search, fused into a new hybrid genetic algorithm. The experiments show that the algorithm fast convergence, high accuracy.Finally, we focus on hybrid genetic algorithm to solve multi-objective traveling salesman problem. The mixed genetic algorithm NSGA-II framework, the use of cross-connected subgraph adding local search algorithm on the relations of domination, to form a hybrid genetic algorithm for multi-objective traveling salesman problem. Initial population generation method for a dual objective traveling salesman problem. Experimental and comparison of several generic examples show that the algorithm has a good performance of finding Pareto optimal solution.