The Course Scheduling System Based On Genetic Algorithm

Since the computer technology develops extremely rapidly and its application is not only being used in all aspects of social life,but also playing an important role,the informationalization turns into an irreversible development tendency.The implementation of teaching plan serves as an important part among a series of supervisory work in teaching activities.Courses scheduling, which is a routine work in high school education administration,will not only take lots of time and energy manually,but be prone to make errors as well. Therefore,the automatic courses scheduling by using computer rises gradually and continues to develop.Genetic Algorithm(GA)develops on the basis of biological evolution and natural selection mechanism with highly parallel,randomized,adaptive characteristics,which is a very effective solution to all the fields of NP problems.Different from traditional search algorithms,GA not only has the nature of the parallelizability,self-organizing,adaptive learning and self-identity,etc,but also has no special requirements for the objective function of micro,convexity, and so on.Thus,it shows a strong researching advantage in the solution to NP hard problems.This article,which applies genetic algorithms to solve the problem of course scheduling,fully discussed the issues of course scheduling factors,the main constraints,objectives and difficulties of solution,and describes the problem of arranging scheduling completely with a mathematical model.Since course scheduling is an issue belonging to the multi-objective decision-making standard optimization problems,this paper has made a deep exploration from the perspectives of encoding,select the operation, cross-choice,variation,etc.Although variation has the least probability of occurrence,it can guarantee the diversity;prevent the search from being into the local sub-optimal solution;inhibit the earlier occurrence of GA effectively. GA happens under the guidance of the established formula.It establishes a formula as a genetic algorithm fitness function.A better solution has been put forward based on the university course scheduling problems. Our main task is to make a reasonable arrangement for classes,teachers, curricula and classrooms for a week to solve the timetable problem.According to the condition,we amend the encoding method,which must be able to include the genetic information.Because of the special nature of timetable,the traditional genetic algorithm cannot work appropriately in binary code which is difficult to express timetable information.We give a natural expression based on the information-coding.At the same time,we visit the initialized object and determine the address of the image of teachers,curricula and classes,which are P-schedule classes in a number of combinations L collection.Considering the actual characteristics of the school timetable in our tests, we make an n-dimensional array as a gene,and then each curriculum is the map f:C×Pâ†'(L,T,C).The specific genetic manipulation is as follows:â… .InitializationThis part aims to provide the initial population for the following evolutionary operation.Its fitness may be very low,but it does not matter.In our algorithm, an initial schedule is worked out by using free space in a random search.For each class to retain a free-idle hour(c) and an not searching space nosearchhour(c),of Lc(c∈C) make nosearchhour(c)=idlehour(c),have a random time p∈nosearchhour(c).If the conflict nosearchhour(c)= nosearchhour(c)-1,and then continue to search.Otherwise,timetable(c,p)= Lc(c∈C),idlehour(c)=idlehour(c)-1.We can repeat the process until the formation of the curricula needs.2.SelectionComputing,known as reproductive choice,is used to simulate the natural selection of biology,that is,always leave the better ones.A certain chromosome with great adaptability will be chosen from the old population to put into the match focus to prepare the exchange of chromosomal variation and operations for a new population.The higher the fitness of the chromosome is, the greater the likelihood that it may be chosen,the more widely the next generation of its genes in the population distributes,the more their children and grandchildren in the emergence of the next generation.3 ExchangeAlthough this operation selects the good from the old population,it cannot create a new chromosome.The pioneers of genetic algorithm proposed exchange operation,which simulates the process of reproduction in biological evolution,that is,a new variety was born by the combination and the exchange of the two chromosomes.In the timetable system,because of the legality of the issue,we cannot adopt a simple single-point or multi-point exchange which make cause illegal solution.This algorithm will spend lots of time in each determination of the legality of solution.As only one of the class curricula can be exchanged,the exchange set up to focus on every one of the conflict.It saves more time than non-use of direct cross-time exchange.We have adopted an intelligent correction in the exchange of each school timetable to address automatically,making it a legitimate school timetable.In addition,a random number r(0＜r＜1) will be produced in the exchange when defining a probability px.Only when r＜px,the implementation of the exchange will operate,or not to implement.4 VariationComputing used to simulate the biological variability in the natural environment due to a variety of genetic accident caused by gene mutations,it's a very small probability of random genetic change(that chromosome to one of a string of symbols) of the value.Mutation ensures the genetic diversity in the population,makes the search carry out in a large space as much as possible, avoids a partial solution by the loss of useful genetic information in search and obtains a higher quality answer of the optimization. Due to the illegal school timetable in the timetable system,if we adopt a simple random variation,there may be a lot of conflict which will cost too much time in the above correction.Therefore,we expect to mutate the original gene without error correction and we consider the use of the exchange column,so that we do not have to error correction after the exchange of the school timetable.Following the exchange operation,a mutation probability py is also defined, then comes a random number r(0＜r＜1).when r＜py,the implementation of the mutation,or not to implement.Finally,based on the study and research of genetic algorithm,I take the school(with a four-year,every-grade A,B,C 3 classes) where I work as the research object.The course scheduling is modeled based on the actual curricula provided by teachers,classrooms,related information and the model I figured out.