| Production and Significance of the Research on Design-curriculum-scheduleWith the quick development of computer technology, it is anxiously needed to solve the problem that computers should substitute for manual work to make curriculum schedule in teaching management.In this background, the thesis intends to probe into how to arrange and optimize curriculum schedule by applying gene arithmetic. Current Status in Design-tableC. C. Gotlieb proposed the mathematical mode of Design-curriculum-schedule in 1963 which is difficult to put into practice, which resulted in suspicion that the problem of design-table can be worked out. While S. Even and Cooper approved that the problem of design-table is NP completed for the first time.Researchers all over the world actively studied the issue ranged from the simulating manmade Design-curriculum-schedule to the expert system constructed by artificial intelligence or the decision support system (DSS), only to find that these systems can only assist in making schedules while lack the ability of doing it intelligently.To make a comprehensive view on the previous studies on the issue, we can find that it is difficult to settle the problem of large-scale and constraint-considerations Design-curriculum-schedule because of various reasons.Constraints in Consideration of Design-curriculum-scheduleHard-collision Constraints: (1) A class cannot take two courses at the same time;(2) A teacher cannot appear in two classrooms at the same time.(3) Two courses cannot arranged in one classroom at the same time.(4) Classroom capacity >= class numbersSoft-collision Constraints: (1) Courses equally distributed within a week.(2) If have a course many time in a week, try to make it equally distributed within a week.Corresponding relation between Design-curriculum-schedule and GA. a) individual gene: a teacher gives a classb) individual gene weighting: individual gene represents all the classes a teacher is teaching at a time (the scope 1-4 in this thesis)c) gene pool: assembly of genes with the same weightingd) gene sequence: assembly of chromosome, individual gene and nulle) box: a position occupied by an individual gene, which represents for a classroom at a period of timef) weight of box: the box represents for the maximum classes that a classroom can accommodates (the scope 1-4 in this thesis)g) box group: all boxes are classified according to weighting number, the classified boxes fall into one grouph) illegal sequence: it is illegal for a sequence of chromosome not to satisfy the demands of hard-collision constraints.Essential Ideas of Design-curriculum-schedule by Using Gene Arithmetic Objects of curriculum schedule: teacher, curriculum, course-times, class, period, classroom, period-weightThe four objects——teacher, curriculum, course-times and classroom should be arranged beforehand according to resources in practice, and then form the four items into individual genes to present that a teacher gives a class.Composition of individual genesPeriod and classroom constitute a one-dimensional array that is regarded as a sequence of genes. Each element can be seen as a box.Each element( or each group of element) in genetic sequence represents for a period, the orders of which represents for scheduling.Classroom capacity can be seen as the weight of each element which shows a classroom's capacity at a period of time.Design-curriculum-schedule herewith has been transformed into a scheduling process of one-dimensional group elements with some constraints.To an individual gene, the entry into an empty box of a sequence of genes depends on whether the weighting of that individual gene is less than or equals to that of box..Strategy of Evaluating on the Degree of SatisfactionWe can make the genetic process develop in the direction to avoid hard-collision by designing an evaluation function for adaptation.Main criteria to evaluate curriculum schedule include: Whether to arrange courses at the utmost in the golden hours (degree MY1)Whether a course is equally distributed within a week (degree MY2) Whether a class is to be robbed by many individual genes (MY3)General degree (MY) can be designed as: MY =αMY1 +βMY2+γMY3 (αβγcan be regulated in practice)Once the sequence has been settled, for each hour has its weight, we can calculate MY1 for this sequence.For every individual gene carries the information that shows the total and ordinal class number a teacher gives, we only need to calculate the difference of periods of corresponding individual genes to a certain class and course, and multiply all the difference of periods, the result should be extracted by (n-1), n= times/week of this course in this class, the final result is the divergence of this course. We prescribe the divergence of the course that is given one times per week is 1. Add up the divergence of all courses, we get the divergence of the curriculum schedule which is MY2.Once an individual gene is put into a box, a corresponding class will be chosen. We will record 1 on the following table whenever a class is chosen. We can design the satisfaction function for adaptation MY= sum of the following table ( null is 0). The greater the number of MY3 is, the less competition will occur in a sequence.Initialization StrategyWe should optimize the process to put all individual genes into boxes with the same weights. If boxes with the same weights have been occupied, these individual genes should be put into the boxes whose weights are more than 1, and so on and so forth. If we want to put redundant genes of several genes pools into a box-collection, those with less weights should be given priority. Once the disposition strategy has been settled, for all the chromosomes, the amount and types of genes in each box-collection is fixed. Genetic ProcessReplication strategy takes uses of roulette wheel selection.Initialization StrategyCrossover falls into two groups: swap and adjust. Obviously, in order to ensure the completion of genetic sequence, adjustment is needed after the crossover, and the adjustment should keep to the following principles.1) To reserve exotic genetic segments and their positions.2) To ensure not to produce genetic absence and genetic repetition. 3) To ensure the stability of genetic types and total number. (As it is said before, once the disposition strategy has been assured, for all the chromosomes, the amount and types of genes in each box-collection is fixed.)4) Try to make the genetic orders in son-sequence are same with that of father-sequence. Therefore, after adjustment,Mutation StrategyRestricted by weight, mutation of reciprocal exchange and inversion will not be permitted, but position exchange and inversion within a box-collection will be allowed.Design-curriculum-schedule TestingAccording to academic plan of Changchun Finance College in the first semester of academic year 2007-2008, the program conducted a case study of testing design-curriculum-schedule. The following data have been used:◆Period: 20◆Classroom: 41◆Teacher: 81◆Course: 52◆Class: 102◆Group size: 50◆Probability of crossover (Pc) :0.8◆Probability of mutation(Pm):0.1◆Generation: 2000◆Evaluating function :MY =αMY1+βMY2+γMY3(α=0.8,β=2,γ=1.3) Fitting curve SummaryThe key to apply GA. is to design codes. The spark of this thesis is that transforms design-curriculum-schedule into Tsp with constraints and creates a unique code mode and genetic process which satisfy various constraints and not to hinder the extensive searching. |
PDF Full Text Request