The Case-injection-based Genetic Algorithm And Its Application In University Timetable Problem

University Timetable Problem is a multi-objective combination optimization issue about education resource, which have puzzled many universities for a long time. Solving the issue is not only conducive to the research of the multi-objective optimization issue in the operational research, but also more significant to overcome the status quo of the inconsistency between the rarity of education resource and the abundance of students in our country.The timetable problem in general is known to be NP-complete. Genetic Algorithms are powerful general-purpose optimization means that are often capable of finding globally optimal solutions even in the most complex of search spaces. To get more first-rank individuals and to avoid the so-called local optimal solution, most of these algorithms initialize all the population in random way. This makes genetic algorithms more complicated, and debases their performance. The case-based reasoning has a good learning ability and can efficiently get a solution by learning former experience. Therefore, an improved algorithm, named case-injected genetic algorithm, is proposed to solve University Timetable Problem in this thesis. The algorithm utilizes case-based reasoning to initialize all the population in random way and replaces all of the worst individuals in evolutionary natural selection stage, so it can speed up convergence and carry out the course timetable better and faster.The university timetable problem is modeled, the influencing factors and main constraints are described formally. The operators of genetic algorithm are designed, the case-injected initialization the splitting and combining class and the avoiding conflict is implemented. Finally, we use Visual C ++ 6.0 as development tool and Access 2000 as background database to design the automatic course timetabling system based on case-injected genetic algorithm, and compare the test result of this system with that of the system based on the random genetic algorithm. The final result shows that the performance of case-injected genetic algorithm is better than that of the random genetic algorithm.