Study On Quantum Genetic Algorithm Based On Low Discrepancy Monte Carlo Sequences

Conventional genetic algorithms combine with principles of quantum computing to form quantum genetic algorithm. Quantum genetic algorithm uses the ability of handling huge amounts of data to improve search performance of genetic algorithm. Quantum genetic algorithm usually adopts quantum rotation gate to realize evolutionary operation. Because of small quantum rotation angle, the efficiency of algorithm search is often low. And this can be easier to lead to extra iterations, long compute time and fall into local extremum. To solve above problems, this paper makes improvement on quantum genetic algorithm, the main work are as follows:(1) This paper proposes a Low Discrepancy Monte Carlo Sequence Quantum Genetic Algorithm (LDQGA). Using good uniform distribution characteristic of the low discrepancy Monte Carlo sequence improves balance of exploration and utilization of genetic algorithm. The main methods are as follows. One is to design a new quantum rotation gate. The rotation gate adopts uniform low discrepancy sequence sample quantum superposition state. The algorithm's ability of exploring solution space is improved. So that the proposed algorithm is not easy to fall into local optimal. Second is to design a new Pareto neighborhood search. The method uses low deviation sequence to search solution locally in the current solution and improves algorithm's ability of using the current solution to find a better solution. The experimental results of five complex continuous function optimization problem show that the global search capability, convergence speed, the number of iterations and computation time of proposed algorithm are better than the conventional quantum genetic algorithm.(2) To figure out the problem such as difficult optimization problems of discrete variable when LDQGA algorithm solves 0-1 combinatorial optimization problem, reverse method is introduced to improve LDQGA algorithm of neighborhood search process. The method selects two reversal point in the sequence of 0 and 1 of the current solution and put the 0/1 negative value of two reversal points in the original position antithetically. Finally, the validity of the algorithm is verified on optimal loading problem of multi-model and multi-cargo. The obtained optimization results are better than the contrast algorithms.