Abstract: Genetic Algorithm (GA) is an AI model that simulates biological evolution based on the process of natural selection. It can search for the optimal solution in the process of simulated biological evolution generation by generation. This paper uses genetic algorithm to implement a simple program to schedule courses.
This article is shared by Jackwangcumt from Huawei Cloud community “How to Use Genetic Algorithm for Intelligent Course Scheduling”.
According to the definition of baidu baike, GeneticAlgorithm is an AI model that simulates biological evolution based on the process of natural selection. It can search for the optimal solution generation by generation in the process of simulated biological evolution. Genetic algorithm cannot solve the problem directly, but needs to abstract the core elements of the problem into the genes on the chromosome with the help of coding rules. Through the process of gene crossover and mutation, the excellent genes are selected iteratively for reproduction and generation of the next generation until the optimal solution or satisfactory optimization solution is obtained. At present, genetic algorithm is widely used in operation research, machine learning, artificial intelligence and other fields.
1. Genetic algorithm process diagram
The core task of genetic algorithm is to provide the chromosomal expression rules of the solution through the coding system, which first needs to randomly initialize a certain number of population, and the population is composed of a certain number of individuals. Each individual is actually a chromosome, and fitness can be calculated according to rules. After the generation of the first population, according to the principle of survival of the fittest evolution, generation by generation to produce excellent offspring.
In each generation of evolution, individuals are selected according to their fitness, and new populations are generated by crossover and mutation through genetic operators of natural genetics. The optimal individual in the last generation population can be approximated as the optimal solution of the problem through decoding. The exit condition is generally to reach the maximum number of iterations, such as 10000. In addition, the fitness should be satisfied, such as 0.99. The basic flow diagram is shown below:
2. Course arrangement requirements
The actual curriculum arrangement is very complicated because it involves a large number of elements such as teachers, classes, classrooms and courses. It may not be the optimal solution with the help of genetic algorithm, but only the local optimal solution. However, it is still a very good method to use genetic algorithm to assist curriculum arrangement. Generally speaking, there are several restrictions that must be met in the course arrangement process, otherwise, the course arrangement given is invalid, as follows:
1. Only one course can be taught in one classroom at a time.
2. The number of seats in a classroom is limited. The total number of students in class cannot exceed the number of seats in the classroom.
3. At the same time, a teacher or a class of students can only participate in one course, but not multiple courses;
4. Classrooms are divided into multimedia classrooms and ordinary classrooms. Some courses require multimedia classrooms, so the classroom configuration must meet the requirements of the course;
The above four restrictions, all meet the conditions, given course arrangement is effective, but please note that is not necessarily the best, it does not take into account optimal conditions, the same teacher, for example, if according to the courses in a day, so obviously a bit overworked, or the same course, on the same day, opening times in a row, so for the teachers and students, It’s all a bit overwhelming.
3. Data structure of elements in curriculum layout
As mentioned above, in the course arrangement process, elements such as teacher, class (student group), classroom and course are involved. The data structure of each element is explained as follows:
Course: The implementation class of the Course object is named Course, which contains the Course ID and Course name fields.
Classroom: The implementation class of the classroom object is named Room, which contains four fields: classroom ID, classroom name, seat number, and whether it is a multimedia classroom.
Teacher: The implementation class of the teacher object is called Professor, which contains three fields, the teacher ID, the teacher name, and all CourseClass required to be taught in the classroom.
Program classes: The implementation class of the program class object is called CourseClass, which contains six fields called the curriculum teacher, the courses taught, the classes to be taught, the number of seats required (summed over multiple classes), whether a multimedia room is required, and the length of the class. This class also provides a method called GroupsOverlap(CourseClassc) to judge whether there is a class-setting overlap between itself and parameter c, and in the same way, the method called ProfessorOverlaps(CourseClassc) to judge whether there is a teacher overlap between itself and parameter c.
Classes: The implementation class for a class object is called StudentGroup, which contains four fields called the class ID, the class name, the number of classes, and all coursecass required by the class.
ChromosomeRepresentation In order to apply genetic algorithm, it is necessary to focus on how to express the solution of the problem in the form of gene sequence. Generally speaking, gene sequence is a long and ordered sequence. Here, multi-dimensional course arrangement elements can be compressed into a one-dimensional array by dimensionality reduction, and the length of the array (later called slot Slots) is:
Number of school days per week * Number of school hours per day * Number of classrooms
For example, if the number of school days in a week is 5, the length of school is 12 hours from Monday to Friday. For example, school starts at 8:00 in the morning and ends at 20:00 in the evening. The number of classrooms, for simplicity, is assumed to be two, so that the total length is 5 * 12 * 2= 120. Each element in this one-dimensional array can be set with CourseClass, and different combinations of sets represent different curricular arrangements. The course arrangement scheme can be represented by the following schematic diagram:
Note: One of the above slots, which represents units of the hour, can also represent an index of the location of a curriculum, in which specific coursecass instances are pointed to, indicating that a corresponding curriculum is set in that Slot.
4
Based on the above chromosomal manifestations, we need to calculate the fitness of an individual, and the calculation method is as follows:
1. Traverse the information of each class in the one-dimensional array representing chromosome performance. If there is no overlap of multiple classes in the classroom at the same time, then increase the fitness score.
2. Traverse the information of each course in the one-dimensional array representing chromosome performance. If the multimedia requirements of the course match the classroom, then increase the fitness score.
3. Traverse the information of each class in the one-dimensional array representing chromosome performance. If the total number of classes participating in the course is less than or equal to the number of seats in the classroom, then increase the fitness score.
4. Traverse the information of each class in the one-dimensional array representing chromosome performance. If the teacher does not teach in more than one classroom at the same time, then increase the fitness score.
5. Traverse the information of each class in the one-dimensional array representing chromosome performance. If the class does not study in more than one class at the same time, then increase the fitness score.
Whether the above 5 indicators that increase the fitness score meet the requirements can be represented by an additional data structure, namely, an array of test rules, with indexes from 0 to 4, and a total of 5 values. Courses overlap, represented by red R, and non-overlap, represented by green R. Whether the classroom has enough seats is indicated by red S, otherwise green S. Whether the classroom matches the multimedia requirements of the course, if it does not, it is indicated by a red L, if it does not, it is indicated by a green L. Whether there are overlapping teachers in the class, the overlap is represented by red P, otherwise, it is represented by green P. Whether the classes in the class overlap, overlap is represented by red G, otherwise green G. The individual fitness value is a float value equal to:
score/ (number_of_classes * 5)
The range is 0 to 1. For the course scheduling scenario, the higher the fitness score, the better the solution. Therefore, individuals with fitness score should be selected in evolutionary process.
5. Genetic algorithm simulation
For the course scheduling scenario, the higher the fitness score, the better the solution. Therefore, individuals with fitness score should be selected in evolutionary process. The core code snippet for the evolutionary process (selection, crossover, and variation) simulated by the algorithm is shown below as an example:
List<Schedule> offspring = new List<Schedule>(); offspring.resize(_replaceByGeneration); for (int j = 0; j < _replaceByGeneration; R ++) {systemp1 = _yield [randomnumber.nextnumber () % _yield. Schedule p2 = _chromosomes[RandomNumbers.NextNumber() % _chromosomes.Count]; // Crossover offspring[J] = p1. / / the variation offspring [j]. Journal of Mutation (); }Copy the codeAs can be seen from the above code, offspring determine the size of the individual to be evolved according to parameter _replaceByGeneration. For each evolved offspring, two parents P1 and P2 are firstly selected by random method, and the offspring after Crossover operation is obtained through p1.Crossover(P2). After Mutation treatment with offspring[J].Mutation(). The core code of cross operation is as follows:
Public Schedule Crossover(Schedule parent2) {// If (randomnumber.nextNumber () % 100 > _crossoverProbability) // Return new Schedule(this, false); N = new Schedule(this, true); int size = (int)_classes.Count; List<bool> cp = new List<bool>(); for (int k = 0; k < size; k++) { cp.Add(false); } for (int I = _numberOfCrossoverPoints; i > 0; i--) { while (true) { int p = RandomNumbers.NextNumber() % size; if (! cp[p]) { cp[p] = true; break; } } } Dictionary<CourseClass, int>.Enumerator it1 = _classes.GetEnumerator(); Dictionary<CourseClass, int>.Enumerator it2 = parent2._classes.GetEnumerator(); NextNumber() % 2 == 0; bool first = randomnumber.nextNumber () % 2 == 0; for (int i = 0; i < size; i++) { it1.MoveNext(); it2.MoveNext(); If (first) {// Add new lessons n._classes.Add(it1.current.Key, it1.current. for (int j = it1.Current.Key.GetDuration() - 1; j >= 0; j--) n._slots[it1.Current.Value + j].AddLast(it1.Current.Key); } else {// Add new lessons n._classes.Add(it2.current.Key, it2.current. for (int j = it2.Current.Key.GetDuration() - 1; j >= 0; j--) n._slots[it2.Current.Value + j].AddLast(it2.Current.Key); If (cp[I]) first =! first; } // calculate fitness n.calculateFitness (); Return n; }Copy the codeIt can be seen from the above codes that _crossoverProbability represents the probability of a crossover. Not every time the crossover operation is called, a specific crossover operation will be performed. When the number randomly generated is greater than the set probability, the specific crossover operation will be carried out. The locations of the crossoverpoints are also randomly generated, and the number of crossoverpoints is given by the _numberOfCrossoverPoints parameter. The essence of crossover operation is to exchange randomly the set of courses pointed to in the two parent classes, that is to say, exchange course information and course index position. The mutation process is relatively simple, that is, when the mutation probability is met, a course is randomly selected and moved to another randomly selected slot. The core code of the mutation process is as follows:
Public void Mutation() {// If (randomnumber.nextNumber () % 100 > _mutationProbability) return; int numberOfClasses = (int)_classes.Count; int size = (int)_slots.Count; For (int I = _mutationSize; i > 0; i--) { int count = _classes.Count; int mpos = RandomNumbers.NextNumber() % numberOfClasses; int pos1 = 0; Dictionary<CourseClass, int>.Enumerator it = _classes.GetEnumerator(); if (mpos == 0) { it.MoveNext(); } for (; mpos > 0; it.MoveNext(), mpos--) ; pos1 = it.Current.Value; CourseClass cc1 = it.Current.Key; To determine the index of the course random location / / int nr = Configuration. The GetInstance (). GetNumberOfRooms (); int dur = cc1.GetDuration(); int day = RandomNumbers.NextNumber() % DefineConstantsSchedule.DAYS_NUM; int room = RandomNumbers.NextNumber() % nr; int time = RandomNumbers.NextNumber() % (DefineConstantsSchedule.DAY_HOURS + 1 - dur); int pos2 = day * nr * DefineConstantsSchedule.DAY_HOURS + room * DefineConstantsSchedule.DAY_HOURS + time; for (int k = dur - 1; k >= 0; K --) {// Remove unwanted classes LinkedList< coursecass > cl = _slots[pos1 + k]; for (LinkedList<CourseClass>.Enumerator it3 = cl.GetEnumerator(); it3.MoveNext(); ) { if (it3.Current == cc1) { cl.Remove(it3.Current); break; }} // Move the course to the new slot location _slots[pos2 + k].addLast (cc1); } // update class _classes[cc1] = pos2; } CalculateFitness(); }Copy the codeCurriculum schedule, need to provide some basic data, such as teacher resources, class situation, course situation, classroom situation, etc. The resource data template is shown below:
Name = # initial id = 1 # # end miss li initial id = 2 name = teacher zhang # # end initial id = 3 name = wang teacher # end... #course id = 1 name = Web programming #end #course id = 4 name = e-Commerce #end... #end #room name = C101 lab = false size = 80 #end #room name = C102 lab = true size = 90 #end #room name = C102 lab = true size = 90 #end #group id = 1 name = 1 class size = 22 #end... # group id = 4 name = 27 # end accounting class size = 2 # class professor = 1 course duration = = 1 group, 2 = 1 group = 2 # end... #class professor = 12 course = 8 duration = 2 group = 3 group = 4 #endCopy the codeThe following is the initial population of individual chromosome phenotypes, the specific code is as follows, population size can be given by parameter, through the loop call MakeNewFromPrototype() to generate different individuals, and added to the primary population. The MakeNewFromPrototype method core code is as follows:
Public Schedule MakeNewFromPrototype() {int size = (int) _slots.count; Newidea = new idea (this, true); // New idea (this, true); / / random CourseClass information LinkedList < CourseClass > c = Configuration. The GetInstance (). GetCourseClasses (); for (LinkedList<CourseClass>.Enumerator it = c.GetEnumerator(); it.MoveNext(); ) {/ / random access course position int nr = Configuration. The GetInstance (). GetNumberOfRooms (); int dur = (it.Current).GetDuration(); int day = RandomNumbers.NextNumber() % DefineConstantsSchedule.DAYS_NUM; int room = RandomNumbers.NextNumber() % nr; int time = RandomNumbers.NextNumber() % (DefineConstantsSchedule.DAY_HOURS + 1 - dur); int pos = day * nr * DefineConstantsSchedule.DAY_HOURS + room * DefineConstantsSchedule.DAY_HOURS + time; Set coursecass information on random slots in the set (int I = dur-1; i >= 0; i--) newChromosome._slots[pos + i].AddLast(it.Current); // Add(it.Current, pos); } / / calculate the fitness newChromosome CalculateFitness (); return newChromosome; }Copy the codeOn the UI, using C# GDI+ to draw, as shown in the following example:
protected void paint(PaintEventArgs e)
{
string baseFile = AppDomain.CurrentDomain.BaseDirectory;
string filename = baseFile + "GaSchedule.cfg";
Configuration.GetInstance().ParseFile(ref filename);
Graphics gac = e.Graphics;
Rectangle clientRect = e.ClipRectangle;
try
{
this.Invoke((MethodInvoker)delegate
{
sx = -GetScrollPos(this.Handle, SB_HORZ);
sy = -GetScrollPos(this.Handle, SB_VERT);
});
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
sx = 0;
sy = 0;
}
Color newColor = System.Drawing.Color.FromArgb(49, 147, 120);
Color bzColor = System.Drawing.Color.FromArgb(49, 147, 120);
Color errorColor = System.Drawing.Color.FromArgb(206, 0, 0);
Brush bgBrush = System.Drawing.Brushes.White;
gac.FillRectangle(bgBrush, clientRect);
Font tableHeadersFont = new Font("Microsoft YaHei", 12);
Font tableTextFont = new Font("Microsoft YaHei", 10);
Font roomDescFont = new Font("Microsoft YaHei", 10);
Font criteriaFont = new Font("Microsoft YaHei", 12);
SolidBrush classBrush = new SolidBrush(Color.DarkOrchid);
classBrush.Color = Color.FromArgb(255, 255, 245);
SolidBrush overlapBrush = new SolidBrush(Color.DarkOrchid);
overlapBrush.Color = Color.FromArgb(255, 0, 0);
HatchBrush myHatchBrush = new HatchBrush(HatchStyle.BackwardDiagonal, Color.Red,Color.Transparent);
int nr = Configuration.GetInstance().GetNumberOfRooms();
for (int k = 0; k < nr; k++)
{
for (int i = 0; i < ROOM_COLUMN_NUMBER; i++)
{
for (int j = 0; j < ROOM_ROW_NUMBER; j++)
{
int l = k % 2;
int m = k / 2;
if (i == 0 && j == 0)
{
Rectangle rect2 = new Rectangle(
sx+ROOM_MARGIN_WIDTH + ROOM_TABLE_WIDTH * l,
sy+ROOM_MARGIN_HEIGHT,
ROOM_CELL_WIDTH,
ROOM_CELL_HEIGHT);
gac.DrawRectangle(Pens.Black, rect2);
Rectangle rect3 = new Rectangle(rect2.X, rect2.Y + 8, rect2.Width, rect2.Height - 16);
string str;
str = string.Format("教室:{0}", Configuration.GetInstance().GetRoomById(k).GetName());
TextRenderer.DrawText(gac, str, roomDescFont, rect3, Color.FromArgb(0, 0, 0),
TextFormatFlags.VerticalCenter | TextFormatFlags.HorizontalCenter);
}
if (i == 0 && j > 0)
{
string str = string.Format("{0} - {1}", 8 + j - 1, 8 + j);
Rectangle rect3 = new Rectangle(
sx + ROOM_MARGIN_WIDTH + ROOM_TABLE_WIDTH * l ,
sy + ROOM_MARGIN_HEIGHT + ROOM_CELL_HEIGHT * (j),
ROOM_CELL_WIDTH,
ROOM_CELL_HEIGHT);
TextRenderer.DrawText(gac, str, tableHeadersFont, rect3, Color.FromArgb(0, 0, 0),
TextFormatFlags.VerticalCenter | TextFormatFlags.HorizontalCenter);
gac.DrawRectangle(Pens.Black, rect3);
}
if (j == 0 && i > 0)
{
string[] days = { "周一", "周二", "周三", "周四", "周五" };
Rectangle rect3 = new Rectangle(
sx + ROOM_MARGIN_WIDTH + ROOM_TABLE_WIDTH * l + ROOM_CELL_WIDTH * (i),
sy + ROOM_MARGIN_HEIGHT,
ROOM_CELL_WIDTH,
ROOM_CELL_HEIGHT);
TextRenderer.DrawText(gac, days[i - 1], tableHeadersFont, rect3, Color.FromArgb(0, 0, 0),
TextFormatFlags.VerticalCenter | TextFormatFlags.HorizontalCenter);
gac.DrawRectangle(Pens.Black, rect3);
}
}
}
}
if (_schedule != null)
{
Dictionary<CourseClass, int> classes = _schedule.GetClasses();
int ci = 0;
for (Dictionary<CourseClass, int>.Enumerator it = classes.GetEnumerator(); it.MoveNext(); ci += 5)
{
CourseClass c = it.Current.Key;
int p = it.Current.Value;
int t = p % (nr * DAY_HOURS);
int d = p / (nr * DAY_HOURS) + 1;
int r = t / DAY_HOURS;
t = t % DAY_HOURS + 1;
int l = r % 2;
int m = r / 2;
Rectangle rect = new Rectangle(
sx + ROOM_TABLE_WIDTH * l + ROOM_MARGIN_WIDTH + d * ROOM_CELL_WIDTH ,
sy + ROOM_TABLE_HEIGHT * m + ROOM_MARGIN_HEIGHT + t * ROOM_CELL_HEIGHT ,
ROOM_CELL_WIDTH ,
c.GetDuration() * ROOM_CELL_HEIGHT);
string str = string.Format("{0}\n({1})\n", c.GetCourse().GetName(), c.GetProfessor().GetName());
for (LinkedList<StudentsGroup>.Enumerator it2 = c.GetGroups().GetEnumerator(); it2.MoveNext(); )
{
str += (it2.Current).GetName();
str += "/";
}
str=str.TrimEnd('/');
if (c.IsLabRequired())
str += "[多媒体]";
gac.FillRectangle(classBrush, rect);
gac.DrawRectangle(Pens.Black, rect);
TextRenderer.DrawText(gac, str, tableTextFont, rect, Color.FromArgb(0, 0, 0), TextFormatFlags.WordBreak);
if (!_schedule.GetCriteria()[ci + 0])
{
bzColor = errorColor;
TextRenderer.DrawText(gac, "R", tableTextFont, new Point(rect.Left, rect.Bottom - 20), bzColor);
gac.FillRectangle(myHatchBrush, rect);
}
else
{
TextRenderer.DrawText(gac, "R", tableTextFont, new Point(rect.Left, rect.Bottom - 20), bzColor);
}
bzColor = newColor;
if (!_schedule.GetCriteria()[ci + 1])
{
bzColor = errorColor;
TextRenderer.DrawText(gac, "S", tableTextFont, new Point(rect.Left + 10, rect.Bottom - 20), bzColor);
}
else
{
TextRenderer.DrawText(gac, "S", tableTextFont, new Point(rect.Left + 10, rect.Bottom - 20), bzColor);
}
bzColor = newColor;
if (!_schedule.GetCriteria()[ci + 2])
{
bzColor = errorColor;
TextRenderer.DrawText(gac, "L", tableTextFont, new Point(rect.Left + 20, rect.Bottom -20), bzColor);
}
else
{
TextRenderer.DrawText(gac, "L", tableTextFont, new Point(rect.Left + 20, rect.Bottom - 20), bzColor);
}
bzColor = newColor;
if (!_schedule.GetCriteria()[ci + 3])
{
bzColor = errorColor;
TextRenderer.DrawText(gac, "P", tableTextFont, new Point(rect.Left + 30, rect.Bottom -20), bzColor);
}
else
{
TextRenderer.DrawText(gac, "P", tableTextFont, new Point(rect.Left + 30, rect.Bottom -20), bzColor);
}
bzColor = newColor;
if (!_schedule.GetCriteria()[ci + 4])
{
bzColor = errorColor;
TextRenderer.DrawText(gac, "G", tableTextFont, new Point(rect.Left + 40, rect.Bottom - 20), bzColor);
}
else
{
TextRenderer.DrawText(gac, "G", tableTextFont, new Point(rect.Left + 40, rect.Bottom - 20), bzColor);
}
}
}
}
Copy the codeAfter execution, the UI interface displayed after multiple iterations of the genetic algorithm is as follows:
In the intermediate stage, the iterative process in which a feasible solution cannot be obtained may display the following interface:
Since there are two courses [8-10] and [9-11] on Monday occupying the same classroom at the same time, the UI will display red twill and R (Room) is red. So far, we have basically realized a genetic algorithm in C# language to carry out simple course scheduling operations. Finally, this blog reference www.codeproject.com/articles/23… The article.
Click to follow, the first time to learn about Huawei cloud fresh technology ~