Research On University Timetabling Problem Based On Self-fertilization Memetic Algorithm

With the rapid development of higher education, the universities continue to expand the scale, which will bring more stress for teaching resources and new challenges to scheduling of teaching. Due to larger scale, constraints and more complex relationship between events, the problem of teaching schedule has attracted more and more interests in the field of optimization and artificial intelligence. Current researches show that evolutionary algorithms are most popular and successful methods on theoretical research and have good practical results for this problem. As the problem size increases, focusing only on the optimization problem of course arrangement seems inadequate although it is the most important one in all stages of teaching scheduling because there are many interactions between the various stages. If we consider the whole problem including all stages with correlations, the algorithm also needs to change accordingly. On the other hand, most of the previous systems for specific problems have many limitations in universality. For these problems, after describing the stages as a whole process and analyzing the relations between the stages, we suppose a new comprehensive consideration of the optimization program. In this program, a new annealing Memetic algorithm based on self-crossover in a chromosome will be issued for achieving the optimal timetable and the fitness function is designed flexibly with the constraints. To verify the validity of the algorithm, we prove the convergence of the algorithm with Banach contraction mapping theorem. Main studies as follow:1. The various stages of the teaching schedule as a whole is discussed and the interactions between the various stages are analyzed as well as the data flow. The relationships between the various stages show that the schema of uniting class has a more significant impact on the timetable. And better uniting class schemas will facilitate the operation of course scheduling algorithm.2. Conducting a model for uniting classes and using annealing-Memetic algorithm for solving optimal schema. In the modeling, we firstly draw a fitness function by analyzing the characters which can achieve better timetable. Then depth-first search algorithm will be employed to calculate the fitness value of each individual. Finally, the annealing Memetic algorithm will be hired to obtain the optimal schema of uniting classes. 3. The problem of teaching schedule is studied in detail and a model of this problem is established. After analysis of the problem, we first issue a fitness function according to the constraints. The fitness function in this paper is only about soft constraints because those who do not meet the hard constraints will be removed directly in the calculation process. Such a definition approach has a certain degree of flexibility and scalability, nothing but fitness function in the algorithm will be modified when the constraints change. Then an annealing Memetic algorithm will be issued to obtain the optimal value of the problem with an iterative method. In the process, the paper defines specifically the individual form, crossover and mutation genetic operators, as well as local search methods respectively for this problem. Meanwhile, in order to improve the efficiency of algorithm and reduce the latent pressure of repair, a new self crossover operator is replaced the one that crossover between individuals previously.4. A real data set of one semester in Tianjin University is employed to verify the uniting classes and timetabling algorithm respectively with various parameters. The experimental results show the effectiveness of the algorithms. The comparation between the results and previous ones show that the satisfactions and efficiency of the new algorithm has some improvement. Finally, the Banach contraction mapping theorem will be hired to prove the convergence of the algorithm.