Improvement And Application In Routing Problem Of Quantum Genetic Algorithm

Quantum genetic algorithm is a hybrid evolutionary algorithm mixed by quantum computing and evolutionary computing, which avoid the defaults of classical evolutionary algorithm. Quantum genetic algorithm adopts some concepts and theory of quantum computing, such as qubit and superposed state, and use qubit to encode chromosome. The quantum chromosome which presented by probability can express many states information. The quantum gate was adopted as evolutionary operation to act on superposed state. It can hold diversity and avoid selection stress. Further more, the current best individual can lead mutation easily, which make the population evolve to good pattern with great probability and get the solution.Since it was proposed, Quantum genetic algorithm has been used in many fields successfully for its inherent parallelization. And there are many improved algorithm. In this paper, we extend the Quantum genetic algorithm application field based on these researches. The main research contents are summarized as follow:1,Proposes an improved quantum genetic algorithm performance further ,and proposes an Improved Hybrid Quantum Genetic Algorithm (IHQGA), the quantum crossover is used which can maintain the relative good gene blocks , the strategies of updating quantum gate using qubit phase approach and adjusting search grid adaptively are introduced,The Similar Newton method is introduced as a local searching scheme ,which is characterized by rapid convergence ,good global search capability and short computing time ;Test results of complex functions and application example demonstrate is superior to conventional genetic algorithms and quantum genetic algorithm in quality and efficiency.2,Proposes a QoS multicast routing algorithm based on Quantum Genetic Algorithm (QGA) , the quantum mutation is used which can prevent premature convergence and improve the capacity of global search algorithms, the strategies of updating quantum gate using qubit phase approach is introduced,which causes the population multiple ; The KMB is introduced as a scheme to form restrained Steiner tree , which is characterized by good global search capability and short computing time ;The experiments show that the proposed algorithm can find the global optimal solution with less computation and evolving time ; This method is superior to conventional genetic algorithms and quantum genetic algorithm in quality and efficiency.Quantum genetic algorithm, combined with quantum computing and evolutionary computing, is a novel optimization algorithm in which quantum mechanism is introduced. Quantum genetic algorithm could be used widely for its fast convergence speed and global optimization ability. The work in this thesis improves the performance of the algorithm and expands its application, and would promote the study on the Quantum genetic algorithm.