Application Research Of Genetic Algorithm For The Travelling Salesman Problem

The traveling salesman problem (TSP, Travlling Salesman Problem) is a classic combinatorial optimization problems, and is NP-hard problem, too. Technical engineering problems in practice, such as circuit board drilling, urban planning, the postman messenger problems, network layout problems, can be seen as the traveling salesman problem model, and solved. Finding a fast and high quality solution algorithm to solve the traveling salesman problem is of great significance. Thus scholars have put forward a number of related algorithms, and done related experiments, such as the score limit method, insertion method, The ant colony algorithm, simulated annealing, genetic algorithms and so on.The genetic algorithm is one of the classic random search algorithm, and is first proposed by Holland. The genetic algorithm contains genetic operators,such as selection, crossover, mutation and it is a key step in the algorithm. The selection operator includes the fitness proportion selection, Boltzmann selection, ranking selection, tournament selection and elitist selection operator. For the crossover operator, this paper introduces two kinds of crossover operator, namely, the one-point crossover and multi-point crossover, and analyze their respective advantages and disadvantages. For the mutation operator, the paper introduces the point mutation reverse mutation, insertion mutation operator.and so on.In addition, research and research prospects of the genetic algorithm is proposed.In this paper, genetic algorithm is applied to the traveling salesman problem. A new genetic algorithm, ectopic cross-complement mutation genetic algorithm,is proposed. The paper gives the CCA algorithm flowchart. Systematic introduction to the ectopic crossover operator. Detailed analysis of the two ectopic crossover operator (single point crossover, Ectopic two crossover). For ectopic crossover operator problems, and propose a method to solve the duplicated genes in individuals after the cross. For the mutation operator, a complement mutation operator. This experiment uses Matlab programming language. Respectively, using the traditional genetic algorithm and CCA algorithm to solve the traveling salesman problem, has the obtained experimental data and convergence curves. The experimental results include the evolution of algebra, the route of the traveling salesman and the total distance. By comparing the experimental data, we can see the CCA genetic algorithm in the600generation can reach through the streets. The traditional genetic algorithm, you need800to achieve the optimal solution. CCA algorithm convergence rate is faster than traditional algorithms convergence. The experimental results show that the CCA algorithm convergence precision is higher than the traditional genetic algorithm.