The Study On University Timetabling Problem Based On The Improved Hybrid Genetic Algorithm

The university timetabling problem (UTP) is a combinatorial optimization problem with many constraints and objectives, and whether it can be solved effectively determines the utilization of the resources and the quality of teaching. UTP is NP-complete and solving it manually is extremely inefficient. Therefore, the help of computers and artificial intelligence algorithms is needed. Among many algorithms, the genetic algorithm (GA) is a random searching algorithm that borrows from the thought of biological evolution and natural selection. GA applies well to solving the NP-complete problems because it is capable of self-organization, self-adaption, self-learning, and parallel global search.First of all, this paper analyzes the relevant constraints involved, designs the function of the objectives expected to be achieved, and establishes the corresponding mathematical model. Then GA and simulated annealing (SA) are applied to construct an artificial intelligence algorithm based on the characteristics of the problem. In the process of solving the problem, random processing is adopted when generating the initial population, the best individual is kept during the selection operation, competitive mechanism is introduced during the crossover operation, and SA is applied during the mutation operation. The efficiency of the algorithm is significantly improved, and the algorithm is able to jump out of the local optimum to search the global optimum. Besides, this paper uses hybrid programming of Matlab and Access, which significantly improves the efficiency of dealing with a massive amount of data. Finally, the proposed hybrid algorithm is used to solve a practical university timetabling problem containing many combining classes. Satisfactory results are achieved, which proves the practicality and the validity of the proposed model and algorithm.