Timetabling Problem Research On Chaos Genetic Algorithm

In order to ensure the quality of tuition, a university must establish a set of normal teaching plans, while arranging courses is an important step of carrying out the teaching plan successfully. With the increasing quantity of college students, the scale of data are huge, and all kinds of constraints are complex, courses arrangement becomes more and more difficult in the limited teaching resources. Arranging courses by hand is impossible to finish the work. Therefore, it's urgent to solve the courses arrangement with computer. Timetabling problem (TP) is a typical problem about multi-restraints and combination optimization, and has been proved to be a Nondeterministic Polynomial Completed (NPC) problem in the 1970's.The genetic algorithm (GA), based on the biological mechanism of natural selection & heredity, is an adaptive and stochastic search algorithm. It can be highly implemented in parallel. For the stability and generality of genetic algorithm, the genetic algorithm is often used to solve complicated NPC Problem.At present, the timetabling problem has become a hot research spot. In view of the sole intelligent algorithm existing problems and insufficiency, the author designs the chaos genetic algorithm. And the paper has conducted more thorough research by using the chaos genetic algorithm to the university timetabling problem. The purpose of this paper is try to use chaos genetic algorithm in the timetabling problem, and proves the chaos genetic algorithm is an advanced algorithm adapting the problem.First of all, this paper summarizes timetabling problem and introduces the actuality and development of the timetabling problem in and out of China. Next, the paper summarizes the structure, the function and the characteristics of the genetic algorithms, and also analyzes the main characteristics and present situation of the chaos theory. It introduces the chaos to the genetic algorithms, using the chaos switch genetic algorithms could fully use the chaos sequence intrinsic regularity, effectively guiding the overlapping and the variation operation. After joining the chaos search strategy in the genetic algorithms, it has improved the algorithm search space greatly, at the same time avoiding the standard genetic algorithms being easy to fall into the partial minimum flaw.Finally, real course data is used to test the GA and the CGA in the application of real timetabling problem. The results prove that CGA is not only applicable to the timetabling problem, but also with higher efficiency.