| Curriculum scheduling problem 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 GA, GA is often used to solve comlicated NPC Problem.In this paper Genetic Algorithm (GA) is applied to solve curriculum scheduling for a university. The main works as follows:Firstly, all kinds of potential factors, multi-restrictions of curriculum scheduling problem are discussed. What's more, the difficulties to resolve the curriculum scheduling problem and the optimal object are represented, and the mathematic model about curriculum scheduling problem is designed. Secondly, some classic GA coding schemes, as well as their applications in curriculum scheduling system are analyzed and compared in details. Based on the studies about all coding schemes' strengths and weaknesses, an improved genetic algorithm for solving curriculum scheduling problems is proposed. Compared to traditional coding schemes, this scheme is simpler, more effective and easier to understand. Meanwhile, the cross and mutation genetic operations are all comprehensibly redesigned to correspond to this code scheme.Thirdly, combined with the mathematic model about curriculum schedule, an automatic curriculum scheduling system based on this multi-dimension coding scheme and the corresponding genetic operations is realized on the windows platform using Vsiaul C++ 6.0.Finally, real course data is used to test this multi-dimension coding scheme and the corresponding genetic operations in the application of real curriculum scheduling problem, and the result is satisfying in the way of the time complexity and curriculum scheduling result.
|
PDF Full Text Request