Study On Genetic Algorithm For Travel Salesman Problem

Genetic algorithm(GA) which has the characteristic of latent parallelism, non-differentiability of objective function and so on, as a optimization method of simulating the process of natural biotic inherit and evolution, is used to solve some problems which are difficult to solve by the traditional optimization method. Travel salesman problem(TSP) is a typical NF's combination and optimization problem, and is widely used in many fields. So the research of GA solving TSP has the important theoretical significance and value of application. Quantum-inspired genetic algorithm(QGA) which has many characteristic of quantum computation, such as highly parallelism, as a new probability evolutionary algorithm, improves greatly computation efficency when it is used to solve the practical problems. Consequently QGA solving TSP has the important value of exploration. Moreover, it is a new thought to solve the complex combination and optimization problem by QGA importing chaos which has ergodicity and randomness.Firstly, a method of improved GA solving TSP is proposed in the thesis: the initial population is produced by priori knowledge and randomness method. Crossover operator that the combiantion of heuristic crossover and edge-recombination crossover and different sufficiency fuction in the early stage and anaphase of GA is used. Secondly, a method of improved QGA solving TSP is focused on: a method of matrix encodement adapts to TSP and policy of restoration is suggested. Controllable revolution door based on QGA is proposed, using the fuzzy rules controlling rotatory angle which makes the algorithm converge faster. At the same time, quantum crossover and quantum variation can avoid algorithm trap in the local optimum solution and prevent from premature convergence. Finally, a method of chaos quantum-inspired genetic algorithm solving TSP is proposed: chaos sequence function is used in updating quantum revolution door in order to avoid premature convergence. All in all, the results tested on the computer indicate that the three algorithm proposed in the thesis have the merit of smaller scale of population, less iterative times, easier to avoid local optimum solution, and easier to get the optimum solution than that of traditional GA...