Algorithm Research On Constrained Project Scheduling Problem Baced On Improved Quantum Genetic Algorithm

Quantum genetic algorithm is a combination of quantum computing and genetic algorithm,a probabilistic search optimization method.Compared with the traditional genetic algorithm,this algorithm has better computing parallelism and population diversity,so it has faster convergence speed,stronger searching ability and higher searching efficiency.As a new evolutionary computation method,quantum genetic algorithm has been applied to solve some complex optimization problems,and has achieved very good results.In the implementation of the project between each different projects in the process of sharing resources often conflict,so under the condition of resource constrained project scheduling and how to meet project demand for resources and shorten the duration of each project is an important problem.This paper first introduces the research status of quantum genetic algorithm,expounds some basic concepts of quantum genetic algorithm such as quantum computation,quantum bit encoding,quantum gate operation and disaster etc..The realization process of the basic quantum genetic algorithm is given.For resource constrained project scheduling algorithm(RCPSP),a resource constrained project scheduling optimization algorithm based on quantum genetic algorithm is proposed.This method takes the quantum encoding scheme based on priority activities,combined with the adjacency matrix storage project,effectively solves the problem of scheduling activities violations,using resource allocation priority preemption mode to arrange the project resources,so as to avoid the conflict of the project resource allocation.The optimization performance of the improved quantum genetic algorithm is tested by four typical complex functions.The performance of the improved quantum genetic algorithm by numerical experiments are carried out to test,get the following conclusions: compared with general quantum genetic algorithm,quantum crossover operator in quantum genetic algorithm,can increase the diversity of population and improve the global search capability of the algorithm;quantum mutation operation can improve the local search ability of the algorithm;using H door instead of quantum rotation gate,can effectively avoid the premature convergence,which makes the algorithm more suitable for solving the multiple local optimal solution.This paper focuses on the application of the improved quantum genetic algorithm in resource constrained project scheduling problem.Based on the quantum phase encoding is proposed.The improved quantum genetic algorithm with quantum crossover and quantum mutation and catastrophe for solving project scheduling problems.The results of the experiment show that the problem of resource constrained project scheduling can be solved effectively by using the parallel computation of the computer.The optimization method of resource constrained project scheduling problem based on improved quantum genetic algorithm is better than the traditional quantum genetic algorithm,which takes advantage of the small storage space,strong searching ability and fast convergence speed.