The Research And Implementation On Course Timetabling System Base On Imporved Virus Evolutionary Genetic Algorithm

In1976, S. Even and Cooper proved that course timetabling problem is an NP-hard problem. As a result, there is not polynomial time algorithm could accurately solve the course timetabling. Therefore, we need to develop Intelligent Algorithm for approximate optional solution. Genetic Algorithm, by simulating the natural genetic principle that the fittest survives, can effectively avoid the occasion of being trapped into local solution so as to rapidly search the most approximate solution or second most approximate solution. Therefore, this algorithm is widely adopted in function optimization and combination optimization field. It’s among the most profound evolutionary algorithms. However, it suffers the defects of local premature convergence and rapid researching speed drop in later period of evolution.The virus evolutionary genetic algorithm, by integrating virus infecting, copying and deleting operation to realize the diversity of same group of virus while maintaining genetic algorithm feature of delivering genetic information within the same generation to effectively to achieve the vertical genetic information delivery between different generations and horizontal evolutionary information delivery among different groups within the same generation, offers the satisfied algorithm convergence performance and overcomes the defects of premature and poor convergence performance in traditional genetic algorithm. This paper adopts virus evolutionary genetic algorithm to research into course timetabling. The main tasks are as below:1. This paper systematically researches into course timetabling and analyzes course timetabling problem basic elements, soft restriction, hard restriction and solution target based on the actual need of the course timetabling problem before establishing course timetabling system’s math optimization model.2. After reviewing the applications in the researches of course timetabling, based on the own features of course timetabling, this paper puts forward an improved virus evolutionary genetic algorithm (IVEGA) for solving this issue. The major improvements are as below:(1) it designs an effective gene encoding method to make the original algorithm more target-oriented.(2)The comparative analysis between the test result of this algorithm and other algorithms based on typical testing function shows that this algorithm is effective. 3. Based on IVEGA, by taking Visual Studio2008as tool, using C#as develop language to implements an algorithm model for course timetabling. The test result based on reality data shows that this algorithm model could effective solving the course timetabling problem.