Convergence Analysis And Improvement Methods Research Of The Double Chain Quantum Genetic Algorithm

The quantum genetic algorithm is a hybrid genetic algorithm combining quantumcomputing with the genetic algorithm, which makes up for some shortcomings of thetraditional genetic algorithm, especially suitable for the optimization solution ofcomplicated engineering problems. In this algorithm, the gene of quantumchromosomes is encoded with quantum bits, and the population is updated withquantum revolving gate, the quantum bit genes of chromosome can approach thequantum bit genes of contemporary optimal chromosome, then this can produce the bestindividual and accelerate convergence speed. The existing problems in quantum geneticalgorithm as follows:(1)The probability amplitude is more close to0or1by traditionalquantum coding, and the algorithm results are at the local extreme value frequently, andpremature convergence phenomenon is produced.(2) The size and the direction of therotation angle of traditional quantum revolving gate is determined by the adjustmentstrategy designed, and the solution convergence speed and the accuracy is influenced bythe probability amplitude of the rotation angle.(3) The theory research of the complexityand convergence of the algorithm is of weak.In view of the defects of the quantum genetic algorithm, this paper carries out thefollowing researches:(1) The obvious shortcomings of the existing double chain quantum geneticalgorithm are easy to fall into the local extreme value, slow convergence speed and thelow accuracy of convergence. Many algorithms are improved, but it’s difficult to haveessential breakthrough, in addition the efficiency, stability and convergence of thealgorithm are usually verified with experimental results in the literature, and there hasno particular reports about theory proof of the algorithm convergence. In this paperconvergence problem of the double chain quantum genetic algorithm is studiedtheoretically, the convergence of the algorithm is proved in accordance with the theoryof Markov chain, and the algorithm convergence and the influence of optimizationefficiency are analyzed and discussed by the simulation.(2) There are many good properties in the double chain quantum genetic algorithm, such as population diversity, the global search ability and calculation parallelism, but ithas not completely solve premature convergence phenomenon in solving thecombinatorial optimization problem, at the same time there is no guarantee about theglobal convergence of the algorithm. For this reason, in this paper a double chainquantum genetic algorithm of improved rotating gate is proposed, the chromosomes ofpopulation are updated with a kind of improved quantum rotating gate in the algorithm,it effectively improves the convergence speed of the algorithm, avoid algorithm into thelocal optimal solution, and the algorithm is more suitable for solving the problem ofmany local optimal solution and realizes the global convergence of the algorithm.