An Improved Quantum Evolutionary Algorithm And Its Application Research On Tsp Problem

The traveling salesman problem is one of the well-known problem in mathematics field, the large-scale TSP is a typical easy-to-describe but difficult to deal with NP-hard problem, and how to effectively solve the TSP has important theoretical significance and application value. Because those who can abstract all nodes in the traversal of a graph once and only once, the problem of seeking the least costly Hamilton path, can be used as a TSP problem to solve.Quantum-inspired evolutionary algorithm is the effective integration of quantum computing and evolutionary algorithms, It uses evolutionary algorithms with simple operation, do not need to determine the rules, probability-based optimization method that can automatically access and optimization of the search space, the adaptive search direction, implicit parallelism, the ability of global optimization, robustness and other properties. Combined with powerful parallel computing power and can effectively simulate the quantum behavior of the quantum computing, to overcome the traditional evolutionary algorithm to solve the larger, more complex problems, need a huge computation and storage, easy to fall into local convergence and other defects. Quantum evolutionary algorithm into many of the basic features of quantum mechanics, and combine it with the evolutionary algorithm will greatly improve the efficiency of the algorithm. At the same time, this paper proposes an improved quantum-inspired evolutionary algorithmfor the TSP problem solving research, And experiments show that the algorithm is compared with the traditional evolutionary algorithm has a better advantage.the main work and innovation is as follows:1, In the improved Quantum-inspired Evolutionary Algorithm for the introduction of the qubit. make the quantum chromosome coding built on the basis of the quantum state vector representation, use qubit and the city serial quantum chromosome encoding, make the quantum chromosome have parallelism and superposition, to effectively reduce the size of the population, the coding of the algorithm chromosome and decoding simple, easy implementation of the encoding and decoding.2, Using an improved quantum rotation gate--Dynamic Hε door Adaptive Dynamic quantum rotation gate. The use of improved quantum rotation gate to update the population, the algorithm automatically adjusts to different evolutionary status and stage the size of the quantum rotation angle, change the speed of the population towards the outstanding individual evolution, set the probability of the trigger, the use of the quantum NOT gate quantum mutation operation, accelerate the convergence rate and it is not easy to fall into local optimal solution.3, This paper presents an improved quantum-inspired evolutionary algorithm method for solving the TSP problem. Use the qubit combine with city code for quantum chromosome coding, make the chromosome coding built on the basis of the quantum state vector representation; Using the improved quantum rotation gate--Dynamic Hε quantum gates for dynamic adaptive quantum update, Algorithm automatically adjusts the size of the quantum rotation angle at different evolution stages and status, using the quantum NOT gate of quantum variation operating. The simulation results show that its search to the optimal solution of a high success rate, the search results; in performance superior to the traditional evolutionary algorithm..