Font Size: a A A

Study On University Course Scheduling Problem Based On Hybrid Genetic Algorithm

Posted on:2020-08-30Degree:MasterType:Thesis
Country:ChinaCandidate:C S ZhaoFull Text:PDF
GTID:2427330599953296Subject:Software engineering
Abstract/Summary:PDF Full Text Request
The course scheduling problem is a multi-objective combinatorial optimization problem with multiple constraints.As early as 1976,the course scheduling problem has proved to be an NPC problem.Combined with the actual situation of domestic universities,because each university's teaching plan,teaching requirements and teaching constraints are different,and there are many factors involved in the course scheduling,it is difficult to get the optimal solution to the course scheduling problem.The traditional manual course scheduling method not only takes a lot of time,but also the results of course scheduling can not meet the requirements of modern teaching activities.Nowadays,more and more scholars are beginning to study how to use the heuristic algorithm to get a satisfactory solution to the course scheduling problem in a short time,rather than the optimal solution.Genetic algorithm is a global optimization search algorithm.Which has good parallelism,versatility and stability,and is an effective algorithm to solve the NPC problem.Simulated annealing algorithm is a heuristic search algorithm,which is a random optimization algorithm based on Monte-Carlo iterative solution strategy.The algorithm can be used to deal with high complexity and high dimensional problems.The results of the solution are characterized by high quality and high efficiency.However,the algorithm is affected by parameters,has slow convergence speed,and does not have parallelism.Based on the analysis and modeling of university course scheduling problem,this paper proposes a university course scheduling algorithm based on the combination of genetic algorithm and simulated annealing-branch and boundary method.This paper first introduces the research background and significance of the course scheduling problem,and mainly introduce the research status and some existing problems of the course scheduling problem at home and abroad.Then this paper mainly introduces commonly used algorithms in the course scheduling problem: genetic algorithm and simulated annealing algorithm,and also introduce the branch and bound method.After that,this paper analyzes and models the course factors and constraints involved in the course scheduling problem in university,and transforms the practical problems of university course scheduling into mathematics problems.Aiming at the actual situation of university course scheduling,this paper proposes a university course scheduling algorithm based on the combination of genetic algorithm and simulated annealing-branch and boundary method.On the one hand,the algorithm improves the genetic operation process of genetic algorithm,and promotes the genetic evolution of the population in a better direction.On the other hand,the algorithm uses the idea of combining simulated annealing algorithm with branch and boundary method to optimize individuals.In the case of individual optimization,simulated annealing algorithm generates multiple individuals during the operation,thereby improving the disadvantage that the algorithm does not have parallelism.Then,this paper uses the idea of branch and boundary method to control the size of the individual produced so that the individual size is not too large.In this way,the algorithm not only improves the individual's fitness,but also makes the computing time not too large.Finally,the experimental results show that compared with the traditional simulated annealing algorithm,genetic algorithm and genetic simulated annealing algorithm,the algorithm in this paper takes more time for an average of 8730 to 10300 seconds.However,the optimal solution fitness of the proposed algorithm is higher than other algorithms between 0.0311 and 0.0411.The average fitness of the proposed algorithm is higher than other algorithms between 0.0313 and 0.0409.Although the algorithm needs more time,the algorithm in this paper can obtain individuals with better fitness,that is,the algorithm can get better course scheduling results.
Keywords/Search Tags:University Course Scheduling Problem, Genetic Algorithm, Simulated Annealing Algorithm, Branch and Bound Method, Multi-Objective Optimization
PDF Full Text Request
Related items