Improvement And Applications Of Quantum Evolutionary Algorithm

The quantum information science is a new cross-science of information science and quantum mechanics. Quantum mechanics is one of the greatest discoveries in the history of physics in the twentieth century. The singularity is that the concept of qubit state is introduced. The qubit state is adopted as information cell in the quantum information science. Quantum computing is an important application of quantum information science. Quantum computing adopts qubit to store the information, which is based on the concepts and principles of quantum theory, such as superposition of quantum states, entanglement and intervention. Quantum gate is used as an operator to realized the unitarily transform of superposed states. After got the output states, the result is got by measuring the quantum states. The parallelization of Quantum computing shows powerful computing ability. It is declared that quantum computing could solve many difficult problems in the field of classical computation, and due to its unique computational performance, the quantum computing has attracted extensive attention of researchers.Some problems with high computing complexity can not be effectively computed using traditional computers. Using quantum computer may reduce the complexity of the problems. But quantum algorithms are needed. There are many researches for quantum algorithms. As so far, the most important quantum algorithms are the quantum algorithm for solving the big number factoring problem proposed by Shor and the quantum algorithm for searching unstructured database proposed by Grover. The big number factoring algorithm can be performed in polynomial time on quantum computer, which can make NP-complete problem to P problem. The unstructured database can be searched with O( N ) speed by using the unstructured database searching algorithm. Since the appearance of big number factoring quantum algorithm, there is an upsurge in quantum computing research around all the world. But it is difficult to physically realize the quantum computer. Therefore, it becomes a focus that how to develop the computing efficiency by combining the quantum mechanisms with traditional computer. Compared to classical optimal algorithms, the evolutionary algorithm has many advantages such as robustness, global searching ability and not depends on the knowledge. But it also has many disadvantages. The population diversity and selection press can not be realized at the same time. The powerful selection press can lead premature and the weak press can lead to slow searching. Quantum evolutionary algorithm is a hybrid evolutionary algorithm mixed by quantum computing and evolutionary computing, which avoid the defaults of classical evolutionary algorithm. Quantum evolutionary 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 evolutionary 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 evolutionary algorithm application field based on these researches. The quantum evolutionary algorithm is used to solve the satisfiability problems. And a quantum combinatorial optimal algorithm is presented based on the quantum evolutionary algorithm and classical evolutionary algorithm. The main research contents are summarized as follow:(1) Quantum evolutionary algorithm is adopted to solve the satisfiability problems, and its application is expanded.Since it was proposed, the quantum evolutionary algorithm has been used in many fields successfully. But it has not been used for SAT problem by far. We adopt the quantum evolutionary algorithm to solve SAT problems. The SAT problems were converted to a optimization problem which can satisfy most clauses in clause set. We design a novel matrix description for SAT problem according to the characteristics of SAT problem. The description can simplify the expression of the problem and the computation of the fitness. The quantum evolutionary algorithm get better performance on convergence speed and solution quality compared with generic algorithm and binary particle swarm optimization in the same condition. The SAT problem is one representative problem in computation science and it is the basic problem for many theory and practice problems, such as symbolic logic,reasoning,machine learning. It has meaningful significance that the quantum evolutionary algorithm was adopt as a new algorithm for this problem.(2) The quantum evolutionary combinatorial algorithm is presented based on quantum-inspired evolutionary algorithm and conventional evolutionary algorithms.We proposed the quantum evolutionary combinatorial algorithm based on quantum-inspired evolutionary algorithm and concepts and theories of quantum computing. The population of the proposed algorithm is divided into quantum population and conventional evolutionary population. In the whole procedure, the evolutions of the two populations are cooperating. Quantum population will pass the individuals with good diversity to conventional evolutionary population. This will develop the diversity of the conventional evolutionary population. The conventional evolutionary will optimize these individuals to develop the quality of the solutions. The best solution which get by the conventional evolutionary will guide a parts of quantum individuals. The guidance will accelerate convergence speed of the quantum population. And ability of global optimization will be developed. There are two phases in the proposed algorithm. The quantum population and conventional evolutionary population are optimized by quantum-inspired evolutionary algorithm in the first-phase and by an evolutionary algorithm in the second-phase, respectively. According to different problems, different evolutionary algorithm is chosen to be combined with quantum evolutionary algorithm. To demonstrate the effectiveness and applicability of the proposed approach, we combine the quantum evolutionary algorithm with genetic algorithm and particle swarm optimization, separately. The genetic algorithm is suit to solve the discrete problems. So the knapsack problem is chosen to test the performance of the combination of the quantum evolutionary algorithm and genetic algorithm. Compared with quantum evolutionary algorithm, the combinational algorithm is better in the aspect of convergence speed and quality of the solutions. The particle swarm optimization suit to solve the continuous optimal problems. We combine the quantum evolutionary algorithm with particle swarm optimization to solve function optimal problems. The results show that the proposed algorithm can converge to the best solution every time. The combinational algorithm can exert the advantages of the two kinds of algorithm. It can accelerate the convergence speed and keep the diversity of the populations. Experimental results show that the proposed algorithm is feasible and effective for solving optimal problems.Quantum evolutionary algorithm, combined with quantum computing and evolutionary computing, is a novel optimization algorithm in which quantum mechanism is introduced. Quantum evolutionary 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 evolutionary algorithm.