论文部分内容阅读
摘要：高校排课中待解决的主要问题就是合理的安排教师、教室、时间、班级等教学资源。大多数遗传算法对排课的应用考虑的是节次优先等问题，而对排课中的教学资源冲突采用消除的办法解决。针对排课中的冲突，该文以班级、时间、教室为三维坐标空间，以排课中存在的冲突数为适应度函数，采用平面交叉的方式，通过精英保留策略构造遗传种群进行选择进化。
关键词：遗传算法;三维编码;冲突函数;平面交叉;精英保留
中图分类号：TP301.6 文献标识码：A
文章编号：1009-3044（2019）32-0080-02
1概述
随着高校的不断扩招，对高校教学资源的合理分配显得越来越重要，其直接影响到高校的正常教学工作的开展。尤其是新学期开学时对高校内的课程安排问题最为突出。排课问题中，涉及了任课教师、教室、教学班、任课时间等多种因素，而我们首要解决的便是在存在大量教师、教室、教学班、认可时间等情况下找到一种合理的排课方案，例如：同一时间同一老师不能出任两门课程等。
排课问题是一个复杂的、多约束的组合问题。国外从20世纪50年代末开始对排课问题进行研究，并在S.Even和Cooper的论文中被证明这是一个NP完全问题。在意识到无法求出排课问题的精确解的情况下，科学家们致力于研究新的排课算法并应用于实际当中，例如Ferland等提出的将整数规划用于排课算法，然而由于该算法计算量大，只能运用于小型课表的编排。
2基于遗传算法的排课理论
遗传算法（Genetic Algorithm，简称GA）是一种模拟生物自然进化过程的优化算法，它由美国Michigan大学的Holland教授于1975年首先提出，并吸引了大批学者进行研究与推广。
高校排课的实质就是利用本校有限的资源，合理的安排教师和学生的授课任务。通常，在高校中都是以班为单位参与到教学计划的制定当中，因此排课当中涉及的因素有教室、教师、班级、时间、课程等因素。其次，在实际当中，教师与课程是对应的，即对一门固定的课程，其任课老师会提前确定下来。再有，对每一个班级，其所上课程是确定的。而不同班级之间又相互关联，即可能存在同一教师担任不同班级的某一门课程的授课任务或者不同班级可能存在占用同一间教室的情况。排课所对应的任务便是为不同班级合理的安排授课时间以及地点，以使其不产生冲突。一个合理的排课方案必须满足以下要求：
同一时间同一教师不能出任一门以上的课程;
同一时间同一教室不能安排一门以上的课程;
同一时间同一班级不能安排一门以上的课程。
2.1遗传算法的基本思想
遗传算法是从代表问题的可能潜在的解集的一个种群开始的，而一个种群是由经过基因编码的一定数目的个体组成。初始种群产生后，根据适者生存和优胜劣汰的原则，逐代演化产生越来越好的个体。而逐代演化的过程则是根据当代种群中个体适应度的优良挑选出父代，并根据遗传学中的遗传算子进行交叉与变异等产生子代，子代又组成新的种群。如此，使得每一代的个体越来越优秀，即所求问题的解越趋近真实解。
2.2排课问题的遗传算法模型
2.2.1编码
使用遗传算法首要考虑的便是如何编码，即怎样将问题与遗传算法对应起来。例如，求一个一元函数的极大值问题，可将自变量用二进制的方式编码，这样既利于计算机的计算又方便执行遗传算法中的交叉、变异等操作。排课问题中，课程与教师的关系为多对一、班级与课程的关系为一对多，而教室与班级、课程并无实际联系。由此，可采用三维网格的形式将一张课表完整的表示。
建立三维坐标系，以x轴表示班级，y轴表示时间段，z轴表示教室，如图1所示。
此时，若通过x轴上某一点，得到平行于yoz平面的切面，该平面上又有许多网格节點，如图2。
将x轴上对应班级下的课程按照一个网格节点至多填充一门课程一教师对的原则全部填人上述平面的网格节点中，即该班级的课程安排完成。对于剩下的班级以此类推，由此一个课表的编码完成。
2.2.2个体适应度函数
自然选择过程中，适者生存、优胜劣汰的法则普遍存在。而评判个体是否较其他个体优秀则是根据其对环境的适应来确定。在排课问题中，个体代表一张课表，其适应度越高则表示越趋近合理。因此，排课问题的适应度可由课表中存在的冲突数来反映，冲突越多则表明是适应度越低。故本问题的适应度函数可由如下公式计算：
其中，fllness为个体适应度，clashes为个体存在的冲突数量。当适应度为1时，说明该个体所表示的课表合理。
2.2.3选择
生物的进化时通过自然选择来完成的，在遗传算法理论中，搜索解通过选择操作来达成。常见的选择操作有赌轮盘选择以及锦标赛选择，而锦标赛选择更具通用性，且性能更优。锦标赛选择策略每次从种群中随机取出一定数量的个体（放回抽样），然后选择其中最好的一个个体进入子代种群。通常采用二元锦标赛选择，即每次随机取出2个个体。
2.2.4交叉
交叉操作在遗传算法起到核心作用，通过交叉使得遗传算法的搜索能力大大增加，同时使子代更容易出现优良的基因模式。排课问题中，不能在不同班级之间进行交叉操作，否则会破坏课表结构。遗传算法中，常见的交叉方式主要有单点交叉、两点交叉以及多点交叉等。其中，两点交叉的原理为随机选择染色体上的2个位置，将两者中间的基因片段互换。本文根据编码结构，结合两点交叉原理，设计了排课问题的面交叉方式。操作如下：
1）随机选择编码结构中的某一个班级;
2）将父代中该班级对应的平行于教室一时间平面的切面相互交换;
3）检测交换后生成的子代适应度;若适应度更低则返回1），否则交叉结束。
2.2.5变异
遗传算法中，变异操作保持了种群的多样性，同时防止遗传算法的过早收敛。在基于二进制编码的遗传算法中，变异操作一般是对0-1二进制串中的某一位进行求反操作。例如，将0变为1或将1变为0。在排课问题中，一个班级下的课程不能改变的原则不变，因此变异操作可用如下方法进行：
1）随机选择编码结构中的某一个班级;
2）随机选择该班级下某两个时间段;
3）交换步骤2）中选择的两个时间段中的教师一课程对，变异结束。
2.2.6精英保留策略
对遗传算法来讲，能否收敛到全局最优解是其首要解决的问题，而Rudoph已经采用有限马尔可夫链理论证明了仅采用交叉、变异和选择（比例选择法）三个标准遗传算子的遗传算法不能收敛到全局最优解。“精英保留”策略是De Jong针对遗传算法提出的，该策略保证了遗传算法的全局收敛性。在排课问题中，采用群体“精英保留”策略，即：将父代种群和子代种群合并后，选择其中最优的N个（种群大小）个体构成下一代种群。
2.2.7算法结束条件
算法本身不能无限制的执行下去，因此必须设置排课算法的结束条件。对于排课问题，算法结束标志着找到一个最优解或者没有找到，因此根据适应度值为1可判断算法结束，此时找到最优解;其次，设置算法的最大迭代次数，若算法执行完了最大迭代次数还没有找到最优解则强制结束。
在算法结束后，输出的原始结果为一条经过编码的染色体，即课表。通过解码的方式可找到任意班级、教室、教师的课表。
3结束语
本文通过分析高校排课问题中存在的主要问题，结合遗传算法理论，构造三维编码模式，极大地降低了排课问题中的冲突量。同时，在编码方案的基础上通过平面交叉的方式，结合“群体精英保留”策略实现排课算法理论。考虑的遗传算法的并行性，该算法在计算机上能快速稳定的进行排课求解。
关键词：遗传算法;三维编码;冲突函数;平面交叉;精英保留
中图分类号：TP301.6 文献标识码：A
文章编号：1009-3044（2019）32-0080-02
1概述
随着高校的不断扩招，对高校教学资源的合理分配显得越来越重要，其直接影响到高校的正常教学工作的开展。尤其是新学期开学时对高校内的课程安排问题最为突出。排课问题中，涉及了任课教师、教室、教学班、任课时间等多种因素，而我们首要解决的便是在存在大量教师、教室、教学班、认可时间等情况下找到一种合理的排课方案，例如：同一时间同一老师不能出任两门课程等。
排课问题是一个复杂的、多约束的组合问题。国外从20世纪50年代末开始对排课问题进行研究，并在S.Even和Cooper的论文中被证明这是一个NP完全问题。在意识到无法求出排课问题的精确解的情况下，科学家们致力于研究新的排课算法并应用于实际当中，例如Ferland等提出的将整数规划用于排课算法，然而由于该算法计算量大，只能运用于小型课表的编排。
2基于遗传算法的排课理论
遗传算法（Genetic Algorithm，简称GA）是一种模拟生物自然进化过程的优化算法，它由美国Michigan大学的Holland教授于1975年首先提出，并吸引了大批学者进行研究与推广。
高校排课的实质就是利用本校有限的资源，合理的安排教师和学生的授课任务。通常，在高校中都是以班为单位参与到教学计划的制定当中，因此排课当中涉及的因素有教室、教师、班级、时间、课程等因素。其次，在实际当中，教师与课程是对应的，即对一门固定的课程，其任课老师会提前确定下来。再有，对每一个班级，其所上课程是确定的。而不同班级之间又相互关联，即可能存在同一教师担任不同班级的某一门课程的授课任务或者不同班级可能存在占用同一间教室的情况。排课所对应的任务便是为不同班级合理的安排授课时间以及地点，以使其不产生冲突。一个合理的排课方案必须满足以下要求：
同一时间同一教师不能出任一门以上的课程;
同一时间同一教室不能安排一门以上的课程;
同一时间同一班级不能安排一门以上的课程。
2.1遗传算法的基本思想
遗传算法是从代表问题的可能潜在的解集的一个种群开始的，而一个种群是由经过基因编码的一定数目的个体组成。初始种群产生后，根据适者生存和优胜劣汰的原则，逐代演化产生越来越好的个体。而逐代演化的过程则是根据当代种群中个体适应度的优良挑选出父代，并根据遗传学中的遗传算子进行交叉与变异等产生子代，子代又组成新的种群。如此，使得每一代的个体越来越优秀，即所求问题的解越趋近真实解。
2.2排课问题的遗传算法模型
2.2.1编码
使用遗传算法首要考虑的便是如何编码，即怎样将问题与遗传算法对应起来。例如，求一个一元函数的极大值问题，可将自变量用二进制的方式编码，这样既利于计算机的计算又方便执行遗传算法中的交叉、变异等操作。排课问题中，课程与教师的关系为多对一、班级与课程的关系为一对多，而教室与班级、课程并无实际联系。由此，可采用三维网格的形式将一张课表完整的表示。
建立三维坐标系，以x轴表示班级，y轴表示时间段，z轴表示教室，如图1所示。
此时，若通过x轴上某一点，得到平行于yoz平面的切面，该平面上又有许多网格节點，如图2。
将x轴上对应班级下的课程按照一个网格节点至多填充一门课程一教师对的原则全部填人上述平面的网格节点中，即该班级的课程安排完成。对于剩下的班级以此类推，由此一个课表的编码完成。
2.2.2个体适应度函数
自然选择过程中，适者生存、优胜劣汰的法则普遍存在。而评判个体是否较其他个体优秀则是根据其对环境的适应来确定。在排课问题中，个体代表一张课表，其适应度越高则表示越趋近合理。因此，排课问题的适应度可由课表中存在的冲突数来反映，冲突越多则表明是适应度越低。故本问题的适应度函数可由如下公式计算：
其中，fllness为个体适应度，clashes为个体存在的冲突数量。当适应度为1时，说明该个体所表示的课表合理。
2.2.3选择
生物的进化时通过自然选择来完成的，在遗传算法理论中，搜索解通过选择操作来达成。常见的选择操作有赌轮盘选择以及锦标赛选择，而锦标赛选择更具通用性，且性能更优。锦标赛选择策略每次从种群中随机取出一定数量的个体（放回抽样），然后选择其中最好的一个个体进入子代种群。通常采用二元锦标赛选择，即每次随机取出2个个体。
2.2.4交叉
交叉操作在遗传算法起到核心作用，通过交叉使得遗传算法的搜索能力大大增加，同时使子代更容易出现优良的基因模式。排课问题中，不能在不同班级之间进行交叉操作，否则会破坏课表结构。遗传算法中，常见的交叉方式主要有单点交叉、两点交叉以及多点交叉等。其中，两点交叉的原理为随机选择染色体上的2个位置，将两者中间的基因片段互换。本文根据编码结构，结合两点交叉原理，设计了排课问题的面交叉方式。操作如下：
1）随机选择编码结构中的某一个班级;
2）将父代中该班级对应的平行于教室一时间平面的切面相互交换;
3）检测交换后生成的子代适应度;若适应度更低则返回1），否则交叉结束。
2.2.5变异
遗传算法中，变异操作保持了种群的多样性，同时防止遗传算法的过早收敛。在基于二进制编码的遗传算法中，变异操作一般是对0-1二进制串中的某一位进行求反操作。例如，将0变为1或将1变为0。在排课问题中，一个班级下的课程不能改变的原则不变，因此变异操作可用如下方法进行：
1）随机选择编码结构中的某一个班级;
2）随机选择该班级下某两个时间段;
3）交换步骤2）中选择的两个时间段中的教师一课程对，变异结束。
2.2.6精英保留策略
对遗传算法来讲，能否收敛到全局最优解是其首要解决的问题，而Rudoph已经采用有限马尔可夫链理论证明了仅采用交叉、变异和选择（比例选择法）三个标准遗传算子的遗传算法不能收敛到全局最优解。“精英保留”策略是De Jong针对遗传算法提出的，该策略保证了遗传算法的全局收敛性。在排课问题中，采用群体“精英保留”策略，即：将父代种群和子代种群合并后，选择其中最优的N个（种群大小）个体构成下一代种群。
2.2.7算法结束条件
算法本身不能无限制的执行下去，因此必须设置排课算法的结束条件。对于排课问题，算法结束标志着找到一个最优解或者没有找到，因此根据适应度值为1可判断算法结束，此时找到最优解;其次，设置算法的最大迭代次数，若算法执行完了最大迭代次数还没有找到最优解则强制结束。
在算法结束后，输出的原始结果为一条经过编码的染色体，即课表。通过解码的方式可找到任意班级、教室、教师的课表。
3结束语
本文通过分析高校排课问题中存在的主要问题，结合遗传算法理论，构造三维编码模式，极大地降低了排课问题中的冲突量。同时，在编码方案的基础上通过平面交叉的方式，结合“群体精英保留”策略实现排课算法理论。考虑的遗传算法的并行性，该算法在计算机上能快速稳定的进行排课求解。