Quantum Genetic Algorithm And Its Application In The Scheduling Problem

Quantum information theory is based on quantum mechanics and classical information science which use quantum states to load information and rules of quantum mechanics implementation to achieve information processing and transmission. The introduction of quantum information theory to traditional algorithm can effectively improve the performance of the traditional algorithm. Quantum information science combined with genetic algorithm can effectively avoid slow and premature convergence and ease to fall a local optimum and other defects. Production scheduling problems are typical combinatorial optimization problems and NP complete problems. With the expanding the scale of problems and the diversity of user requirements, the complexity will grow exponentially.For these reasons, the author chose the optimization of quantum genetic algorithm and its application in the scheduling problems as the research topic. Main tasks are as follows:(1)For the defects of quantum genetic algorithm in practical application, we proposed an improved quantum genetic algorithm. By improving the strategies of the revolving door and catastrophe and replacing history optimal solution with contemporary optimal solution as convergence objective to enhance the ability of the algorithm. The simulation of optimization of complex functions shows the computational efficiency of improved quantum genetic algorithm.(2) The improved quantum genetic algorithm (IQGA) applied to solve fuzzy due date scheduling problem on parallel machines. As the observations can't directly reflect the problem of solution, we used inversion decoding to expand the population size. The results of simulation show the feasibility and effectiveness of the algorithm. (3) When the Resource-constrained project scheduling problem size is large, the use of heuristic algorithm has slow convergence, easy to fall a local optimum and other defects. This article introduced the improved quantum genetic algorithm to solve such problems, and proposed a binary triangle matrix coding based on priority rule. The simulation of standard question bank confirmed that implied quantum genetic algorithm based on the new encoding method has a good convergence.