用遗传算法进行智能排课，相信老师会很喜欢

关注

发布于: 2 小时前

摘要：遗传算法（Genetic Algorithm）是一种基于自然选择过程，模拟生物进化的 AI 模型，它可以在模拟的生物进化过程中逐代搜索到最优解的一种方法。本文利用遗传算法实现了一个简单的程序来对课程进行排程。

本文分享自华为云社区《如何用遗传算法进行智能排课》，作者：jackwangcumt。

根据百度百科的定义，遗传算法（GeneticAlgorithm）是一种基于自然选择过程，模拟生物进化的 AI 模型，它可以在模拟的生物进化过程中逐代搜索到最优解的一种方法。遗传算法不能直接对问题进行求解，而是需要借助编码规则，将问题中的核心要素抽象为染色体上的基因，并通过基因的交叉、变异等过程，迭代选择优良基因进行繁殖，生成下一代，直到求得最优解或者满意的优化解。目前遗传算法的使用范围非常广泛，常应用于运筹、机器学习、人工智能等领域。

1、遗传算法过程图解

遗传算法核心的任务是要通过编码体系，给出解决方案的染色体表现规则，首先需要随机初始化一定数量的种群（population），而种群则由一定数目的个体(individual)构成。每个个体实际上是染色体(chromosome)，可以通过规则计算出适应度（fitness）。初代种群产生之后，按照优胜劣汰的进化原理，逐代进化产生出优秀的后代。

在每代进化过程中，根据个体的适应度大小来选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行交叉（crossover）和变异（mutation），产生新的种群。末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。退出条件一般为达到最大的迭代次数，比如 10000 次，另外，就是适应度满足要去，比如达到 0.99。基本的流程示意图如下所示：

2、课程编排要求

实际的课程编排，由于涉及到大量的老师、班级、教室和课程等要素，因此非常的复杂，借助遗传算法也可能求不出最优解，而只是求出局部最优解，但是利用遗传算法辅助课程编排仍然是一个非常好的手段。一般来说，课程编排过程中，必须满足几个限制条件，否则，给出的课程安排是无效的，具体说明如下：

1. 同一时刻，一个教室只能开设一门课程；

2. 一个教室是有座位个数限制的，上课的学生总数不能超过教室座位数；

3. 同一个时刻，同一个老师或班级学生只能参与一门课程，而不能参与多个课程；

4. 教室分多媒体教室和普通教室，有的课程需要多媒体教室，因此，教室配置必须满足课程要求；

以上 4 条限制，都满足的情况下，给出的课程安排才是有效的，但请注意，不一定是最优的，它并未考虑优化条件，比如同一个老师，如果在一天按照多门课程，那么显然有点超负荷工作，或者同一门课程，在同一天，连续开设多次，这样对于老师和学生来说，都有点吃不消。

3、课程编排中要素数据结构

前面提到，课程编排过程中，涉及到老师、班级（学生组），教室和课程等要素，下面给出各要素的数据结构说明：

课程 : 课程对象的实现类名为 Course ，其中包含课程 ID 和课程名称 2 个字段。

教室 : 教室对象的实现类名为 Room ，其中包含教室 ID、教室名称、座位数、是否是多媒体教室这 4 个字段。

教师 : 教师对象的实现类名为 Professor，其中包含教师 ID、教师名称和该教室需要教授的所有课程班（CourseClass）这 3 个字段。

课程班 : 课程班对象的实现类名为 CourseClass，其中包含课程授课老师、教授的课程、上课的班级、需要的座位数（多个班级人数求和）、是否需要多媒体教室和上课时长这 6 个字段。此类还提供方法 GroupsOverlap(CourseClassc)来判断自己和参数 c 是否有班级的重叠，同理，方法 ProfessorOverlaps(CourseClassc)可判断自己和参数 c 是否有老师的重叠。

班级 : 班级对象的实现类名为 StudentGroup，其中包含班级 ID、班级名称、班级人数和该班级需要上的所有课程班（CourseClass）这 4 个字段。

染色体表现（ChromosomeRepresentation）: 为了应用遗传算法，需要重点考虑如何用基因序列的方式来表示问题的解，一般来说，基因序列是一长串有序的序列，这里可以将多维的课程安排要素通过降维方式，压缩到一维数组上，而数组（后续称为插槽 Slots）的长度就是：

一周上课天数 * 每天的上课时长数 * 教室数

举例来说，一周上课天数假设为 5，表示周一到周五，每日上课时长为 12 小时，比如早上从 8 点开始上课，晚上到 20 点结束。而教室数为了简单起见，假设是 2 个，因此总数组长度为 5 * 12 * 2= 120 ，这个一维数组中的每个元素，可以放置课程班 CourseClass，而不同的课程班组合就代表了不同的课程排课方案。排课方案可以用如下示意图进行表示：

注意：上述一个插槽 Slot 代表一个小时单位，也可以表示课程的位置索引，其中可指向具体的课程班 CourseClass 实例，表示该插槽位有对应的课程安排。

4、适应度 Fitness

基于上述的染色体表现，我们需要计算某一个个体的适应度，计算的方法如下：

1. 遍历代表染色体表现的一维数组中的每个课程班信息，如果同一时刻教室不存在多个课程的重叠，那么增加适应度分值。

2. 遍历代表染色体表现的一维数组中的每个课程班信息，如果课程对于多媒体的要求和教室匹配，那么增加适应度分值。

3. 遍历代表染色体表现的一维数组中的每个课程班信息，如果课程参与的班级总人数小于等于教室的座位数，那么增加适应度分值。

4. 遍历代表染色体表现的一维数组中的每个课程班信息，如果老师同一时刻不会再多个教室进行授课，那么增加适应度分值。

5. 遍历代表染色体表现的一维数组中的每个课程班信息，如果班级同一时刻不会在多个课程班进行学习，那么增加适应度分值。

而这上述 5 个增加适应度分值的指标，是否满足，可以通过额外的数据结构进行表示，即一个检验规则数组表示，索引为 0 到 4，共 5 个值。课程重叠，用红色 R 表示，不重叠，用绿色 R 表示。教室是否有足够的座位，不足用红色 S 表示，否则用绿色 S 表示。教室是否和课程的多媒体要求匹配，不匹配用红色 L 表示，否则用绿色 L 表示。课程班中的教师是否有重叠，重叠用红色 P 表示，否则用绿色 P 表示。课程班中的班级是否有重叠，重叠用红色 G 表示，否则用绿色 G 表示。而个体的适应度值为一个 float 类型的值，等于：

score/ (number_of_classes * 5)

范围为 0 到 1。而对于课程排课场景来说，适应度分值越高，给出的解决方案越好。因此，进化过程中的个体选择要优选适应度分值的个体。

5、遗传算法模拟实现

而对于课程排课场景来说，适应度分值越高，给出的解决方案越好。因此，进化过程中的个体选择要优选适应度分值的个体。下面给出算法模拟的进化过程（选择、交叉和变异）的核心代码片段，示例如下：

List<Schedule> offspring = new List<Schedule>();offspring.resize(_replaceByGeneration);for (int j = 0; j < _replaceByGeneration; j++){    //随机选择    Schedule p1 = _chromosomes[RandomNumbers.NextNumber() % _chromosomes.Count];    Schedule p2 = _chromosomes[RandomNumbers.NextNumber() % _chromosomes.Count];    //交叉    offspring[j] = p1.Crossover(p2);    //变异    offspring[j].Mutation();}

复制代码

从上述代码可知，后代 offspring 根据参数_replaceByGeneration 来确定需要进化的个体大小，针对每一个进化的后代，首先通过随机方法选择两个父代 p1 和 p2，首先通过 p1.Crossover(p2)获取到交叉操作后的后代，然后在对其进行变异处理 offspring[j].Mutation()。其中交叉操作核心代码如下：

public Schedule Crossover(Schedule parent2){    // 根据概率确定是否需要交叉操作    if (RandomNumbers.NextNumber() % 100 > _crossoverProbability)        //直接返回        return new Schedule(this, false);    //拷贝生成新的chromosome object    Schedule 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();    //交替用父个体组合交叉生产新的个体    bool first = RandomNumbers.NextNumber() % 2 == 0;    for (int i = 0; i < size; i++)    {        it1.MoveNext();        it2.MoveNext();        if (first)        {            //添加新的课程            n._classes.Add(it1.Current.Key, it1.Current.Value);            for (int j = it1.Current.Key.GetDuration() - 1; j >= 0; j--)                n._slots[it1.Current.Value + j].AddLast(it1.Current.Key);        }        else        {            //添加新的课程            n._classes.Add(it2.Current.Key, it2.Current.Value);            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;    }    //计算适应度    n.CalculateFitness();    //返回更好的后代    return n;}

复制代码

由上述代码可知，其中的_crossoverProbability 表示一个交叉的概率，并不是每次调用交叉操作都要执行具体的交叉操作，当随机生成的数大于设定的概率后，才进行交叉具体的操作。其中的交叉点位置也是随机生成的，交叉点的个数通过参数_numberOfCrossoverPoints 给定。交叉操作的本质是将两个父类中所指向的课程集合进行随机的组合交换，也就是说，交换的是课程信息以及课程的索引位置。而变异过程相对简单，就是对需要实行变异操作的个体，当满足变异概率时，随机选定一个课程并将其移动到另一个随机选择的插槽（Slots）中。变异过程核心代码如下：

public void Mutation(){    //按照概率决定是否需要突变    if (RandomNumbers.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;        // 随机确定课程的索引位置        int nr = Configuration.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--)        {            //移除不需要的课程            LinkedList<CourseClass> cl = _slots[pos1 + k];            for (LinkedList<CourseClass>.Enumerator it3 = cl.GetEnumerator(); it3.MoveNext(); )            {                if (it3.Current == cc1)                {                    cl.Remove(it3.Current);                    break;                }            }            //移动课程到新的插槽位置            _slots[pos2 + k].AddLast(cc1);        }        // 更新课程位置        _classes[cc1] = pos2;    }    CalculateFitness();}

复制代码

课程排程，需要提供一些基础的数据，比如教师资源情况、班级情况、课程情况、教室情况等。下面给出资源数据模板：

#prof	id = 1	name = 李老师#end
#prof	id = 2	name = 张老师#end
#prof	id = 3	name = 汪老师#end
...
#course	id = 1	name = Web编程#end
#course	id = 4	name = 电子商务#end
...
#course	id = 8	name = 数据库原理#end
#room	name = C101	lab = false	size = 80#end
#room	name = C102	lab = true	size = 90#end#group	id = 1	name = 电商1班	size = 22#end
...
#group	id = 4	name = 会计2班	size = 27#end
#class	professor = 1	course = 1	duration = 2	group = 1	group = 2#end...
#class	professor = 12	course = 8	duration = 2	group = 3	group = 4#end

复制代码

下面给出初始化种群中的个体染色体表现型，具体代码如下，种群大小可通过参数给定，通过循环调用 MakeNewFromPrototype()生成不同的个体，并添加到初代种群中。MakeNewFromPrototype 方法核心代码如下：

public Schedule MakeNewFromPrototype(){    //插槽个数    int size = (int)_slots.Count;    //生成新的个体 chromosome    Schedule newChromosome = new Schedule(this, true);    //随机获取CourseClass信息    LinkedList<CourseClass> c = Configuration.GetInstance().GetCourseClasses();    for (LinkedList<CourseClass>.Enumerator it = c.GetEnumerator(); it.MoveNext(); )    {        //随机获取课程位置        int nr = Configuration.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;        //将CourseClass信息放于随机的插槽位上        for (int i = dur - 1; i >= 0; i--)            newChromosome._slots[pos + i].AddLast(it.Current);        //添加课程class信息        newChromosome._classes.Add(it.Current, pos);    }    //计算适应度    newChromosome.CalculateFitness();    return newChromosome;}

复制代码

在 UI 上，采用 C# GDI+进行绘制，示例如下：

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);                }        }    }}

复制代码

执行后，遗传算法多次迭代后，显示的 UI 界面如下：

中间环节，还不能得到可行解的迭代过程，可能显示如下的界面：

由于周一的【8-10】和【9-11】有两个课程同时占用了同一个教室，因此，UI 上会显示红色的斜纹，同时 R（Room）为红色。至此，我们基本实现了一个用 C#语言实现的遗传算法，来进行简单的课程排程操作。最后，本博客参考https://www.codeproject.com/articles/23111/making-a-class-schedule-using-a-genetic-algorithm一文。

点击关注，第一时间了解华为云新鲜技术~

发布于: 2 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/af4a2254e9493b520b7810261】。文章转载请联系作者。

华为云开发者社区

关注

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区，提供全面深入的云计算前景分析、丰富的技术干货、程序样例，分享华为云前沿资讯动态，方便开发者快速成长与发展，欢迎提问、互动，多方位了解云计算！传送门：https://bbs.huaweicloud.com/

发布

暂无评论

创作场景

用遗传算法进行智能排课，相信老师会很喜欢

1、遗传算法过程图解

2、课程编排要求

3、课程编排中要素数据结构

4、适应度 Fitness

5、遗传算法模拟实现

华为云开发者社区

评论