Research On The Application Of Genetic Algorithm In Solving TTP

Timetable Problem (TTP) is a special problem of resource arrangement which is widely applied in making schedules for school curriculum and examination, all sorts of large conferences, sports games and operations of trains, flights and ships. This paper, targeting at the solution of TTP of college curriculum schedule, is directed to the analysis of the restricting factors and the establishment of a mathematic model. However, TTP of college curriculum schedule, as a difficult, restrictive and multi-objective problem of combination and optimization, has been indicated by experiments that it falls into the category of NP completeness, which poses challenges to the traditional search algorithm when the scale of seeking solutions enlarges.Genetic algorithm is an intelligent algorithm that simulates the process of biological evolution. As a new algorithm of overall optimized search, it has achieved broad applications in solving optimization problems due to such distinctive features as simplified process, universality, robustness and availability of parallel processing. Genetic algorithm has become an effective method to resolve NP completeness problem.According to the feature of TTP of college curriculum, we improve Genetic algorithm, bringing forward a primary chromosome on the basis of students' curriculum schedule and assisting chromosomes on the basis of classroom distribution schedule and teachers' schedule, which ease the solution of the problem. In addition, modification is made to the genetic algorithm as a result of its weaknesses in local search ability and convergence speed. Some universal traditional algorithms are introduced into and combined with genetic algorithm to produce a two-staged heuristic algorithm which turns out to be practical and effective in the virtual applications.