Research And Application Of Quantum Genetic Algorithm

With the help of quantum theory,the quantum genetic algorithm makes up for the shortcomings of the lack of population diversity of the classical genetic algorithm,promotes the improvement of the search speed and accuracy of the genetic algorithm,and embodies the powerful solving ability in the optimization problem.However,when the naive quantum genetic algorithm solves complex problems,there are still shortcomings such as insufficient convergence speed and easy to fall into local optimal solutions.The LPN(learning parity with noise)problem is a basic problem in modern cryptography,coding theory and machine learning.It is closely related to the decoding problem of random linear codes.In solving LPN problems with traditional algorithms,the number of equations with errors is the largest.The solution of is a relatively complex problem,and it has important theoretical significance to study the optimization algorithm for solving LPN problem.In this context,in order to speed up the algorithm's convergence speed and improve the algorithm's global convergence,as well as to solve the LPN problem,this thesis proposes an improved quantum genetic algorithm and applies it to the solution of the LPN problem.The main work is as follows:1.An adaptive quantum genetic algorithm based on niche is proposed.The traditional quantum genetic algorithm is easy to fall into the local optimal solution,usually adopts a fixed rotation angle strategy and the rotation direction needs to be determined by looking up the table,which affects the efficiency of the algorithm.This thesis proposes a niche-based adaptive quantum genetic algorithm to improve the algorithm mainly from encoding methods,niche co-evolution,determining the rotation direction of quantum gates,adaptive rotation angles,quantum convergence gates and quantum catastrophes.The Rosenbrocks function and the Schaffer function are tested to verify that the improved quantum genetic algorithm has improved both in convergence speed and accuracy.2.A higher-order quantum genetic algorithm scheme suitable for function optimization is designed.Traditional quantum genetic algorithms use independent qubits to construct quantum chromosome representations.In order to further improve the performance of the algorithm,high-order quantum genetic algorithms use quantum registers composed of multiple qubits to construct quantum chromosome representations.This thesis analyzes the chromosome structure and measurement methods of the high-order quantum genetic algorithm,and constructs a quantum operator that does not involve a lookup table to complete the evolutionary update;analyzes the advantages and influencing factors of the high-order quantum genetic algorithm from the perspective of principle.Four different types of test functions are selected in the standard test function set,and the convergence speed and accuracy are considered comprehensively.Through the analysis of the performance of the high-order quantum genetic algorithm with different register sizes(r =1,2,(43),6),it is verified that the high-order quantum genetic algorithm is relatively The traditional quantum genetic algorithm has improved the convergence speed and accuracy,and experiments have verified that the optimal scale of the register is 2-5.3.Designed and realized the application scheme of high-order quantum genetic algorithm in LPN problem.This thesis analyzes the LPN problem and the intuitive meaning of its solution,constructs a fitness evaluation function,transforms it into an optimization problem suitable for genetic algorithm,and explains the possibility of genetic algorithm to solve LPN problem in principle.In this thesis,several examples of LPN problems are randomly generated to verify that it is a feasible and effective solution to use quantum genetic algorithm to solve the error equations in the LPN problem.