基于遗传算法的高校排课问题探讨

刘 腾，吴仁协，李 毅

（广东海洋大学1.教务处；2.水产学院，广东 湛江524088）

排课是高校的重要教务管理工作，关系到高校教学秩序。从20世纪50年代末期开始，国外一些学者开始探讨排课问题，1963年Gotlieb率先提出时间表问题的数学模型[1]，1999年Safaai和Sigeru采用遗传算法解决在教室不足情况下如何合理分配教师和利用教室资源的排课问题[2]。从20世纪80年代初期开始，国内开始研究运用数学和运筹学方法、人机交互方法、基于人工智能方法、基于启发式算法等解决排课问题的方法[3]。高校经历了从模拟手工排课到运用人工智能构建专家系统或决策支持系统排课的过程，这些方法都是辅助排课工具，还不能完全替代人工排课。

近年来，随着国内高校规模越来越大、课程越来越多。虽然高校的教学条件得到了很大的改善，但是教学资源仍然有限，排课压力很大。在排课过程中，不仅要有效地利用各种教学资源，而且还要避免班级、教师、课程、时间、教室等排课要素之间发生冲突。如何编排科学、合理的课表，是排课人员面临的一项重大课题。随着计算机技术和人工智能的迅速发展，遗传算法广泛用于求解排课问题。遗传算法是美国Holland教授于1975年最先提出的一种模拟自然界生物进化过程的全局优化搜索算法[4]，能够通过计算机科学技术使初始解逐渐逼近最优解或准最优解。遗传算法具有良好的并行性、通用性、稳定性，是求解排课问题的一种有效方法。本文探索利用遗传算法求解排课问题的策略，以优化排课系统和提高排课效率。

1 排课问题分析

求解排课问题的实质是消除在多约束条件下的资源冲突，优化课程、班级、教师、教室和时间等要素之间的组合。

1.1 排课的约束条件

求解排课问题受到多种条件的约束，以避免约束条件之间发生冲突。约束条件包括硬约束和软约束。硬约束是不可违反的约束条件，是排课过程中必须满足的条件，它决定排课方案的可行性，决定班级、教师、教室等因素之间是否相容。软约束条件影响排课的合理性和教师对排课的满意度，既是为了优化排课方案而设置的条件，也是衡量排课方案优劣的标准。软约束条件包括授课时间的合理性、教师和班级行课的均衡性等，同时也包括个别教师对排课提出的特殊要求。在排课过程中，先满足硬约束条件，再满足软约束条件。

1.2 排课问题求解的数学模型

为了方便求解，将排课问题用数学模型进行描述。设学校的课程为li，班级为ci，任课教师为pi，教室为ri，授课时间为 ti。则课程集合为：L={l1，l2，l3，…，li}；班级集合为：C={c1，c2，c3，…，ci}；教师集合为：P={p1，p2，p3，…，pi}；教室集合为：R={r1，r2，r3，…，ri}；时间集合为：T={t1，t2，t3，…，ti}。教室-时间对的笛卡尔积为：D=R×T={(r1,t1),(r2，t2)，(r3,t3)，…，(ri,ti)}。 设课程周学时为 wi，则课程 li的属性集合为：li={wi，ci，pi，ri，ti}。课程、班级、任课教师在排课之前已经安排好，为已知变量，则排课问题的求解过程转换为确定每门课程的授课教室、授课时间的过程。

1.3 排课问题的组合爆炸效应和不确定性

排课问题的求解是一个典型的组合规划问题。只要制约排课的因素发生变化，必然导致课程表的编排方案数急剧增加，形成排课组合爆炸效应。具体来讲，只要调整任何一门课程，必然导致其他课程表的数据发生变化，排课问题更加复杂，难以获得排课问题的最优解。因此，求解排课问题的关键是缩小搜索空间，并采取适当的措施，以抑制“组合爆炸”效应。同时，不追求排课问题的“单个绝对最优”解，降低衡量课表满意度的标准，只追求获得一套完整的、无任何硬性约束条件冲突的课表，并符合人们主观规定的软约束条件。

1.4 排课问题的求解目标

排课问题被认为是一个多目标的、带有模糊约束条件的、资源有限的组合优化问题[5]。多目标是指在排课可行解域中的排课组合方案是一个集合，不容易达到“单个绝对最优”方案。模糊约束条件是指各学校的排课软约束条件不尽相同，很难满足所有的约束条件，且软约束条件难以用数学公式表示。资源有限是指教师、教室、时间等教学资源有限。因此，在排课组合规划问题中，除了必须完全满足硬约束条件外，应以 “科学、合理、人性化”的要求作为优化排课方案的目标，不必追求“单个绝对最优”方案。因此，排课问题求解应达到两个目标，一是课表无硬性约束条件冲突，二是尽量满足软约束条件。

2 排课问题的遗传算法设计

2.1 排课问题的基因编码

遗传算法是利用基因编码技术和繁殖机制，从一个随机产生的初始种群（初始解）开始，通过若干代的种群迭代实现对复杂问题的求解[6]。运用遗传算法求解排课问题的关键是对排课问题进行编码。编码质量关系到有效遗传信息表达的完备性，并影响算法的计算效率。课表编排是对课程安排合适的授课时间和授课教室。课程是课程号、课程名称、授课周学时数、授课教师、授课班级等构成的信息集合，可用“课程—教师—班级”组合体表示待排课程信息。用一个 “课程—教师—班级”和“时间”的二维矩阵进行编码，在排课中将“教室”安排到“课程—教师—班级”和“时间”的二维矩阵中。

2.2 初始种群和适应度函数的设计

产生初始种群的具体步骤如下。第一，对于“课程—教师—班级”组合，随机产生课程的授课时间；第二，将授课班级的学生人数由小到大排列；第三，按照教室容量从小到大编排教室编号；第四，根据教室编号搜索教室，系统选取当前可用、教室容量足够大且最接近授课班级人数的教室；第五，重复以上操作，直至所有课程排完为止。依据这种方式产生的初始种群，班级学生人数与教室容量之间尽可能接近，以尽量满足软约束条件。在课程编排过程中，还要对约束条件之间是否发生冲突进行检测，以获得满足全部硬约束条件的可行初始解。

适应度函数是指度量个体优劣程度的函数。适应度函数设计质量直接影响遗传算法的迭代方向、收敛速度，甚至影响能否获得满足目标的最优解[7]。为了能够获得合理、可行、满意的课程表，尽量利用相关经验和常识进行编排课表。而“相关经验和常识”是模糊的，且具有不确定性。此外，涉及诸多要素和约束条件，很难判断课程表编排的优劣。为了更好地判断一个课程表的优劣程度，必须根据课程表的适应度值进行评价。适应度函数为：

Fitness=(A×wl+(b×ql+c×q2)×w2)×d×e。

其中表示当前组合方案的教师上课节次优度的平均值A=(a1+a2+a3+…+an)/n，b为上课日组合优度，c为上课节组合优度，d为课表分布优化度，e为组合可行度，q1和q2分别为上课日组合优度和上课节组合优度各占的权重，q1+q2=1；w1和w2为节次优度和组合优度各占的权重，w1+w2=1。

2.3 选择操作、交叉操作和变异操作

选择操作采用轮盘赌的方法。轮盘赌的选择方法与博彩游戏的轮盘赌原理类似，整个轮盘被分为不同比例的扇形区域，分别对应种群中各个个体。随机转动轮盘，直到轮盘自然停下，指针所指的扇面代表的个体则是选择出来的个体。在轮盘赌过程中，“不同比例的扇形区域”中的“比例”是按照个体适应度的大小来分配的，轮盘中面积越大的区域的个体适应度越高，被遗传到下一代的概率就越大。相反，轮盘中面积越小的区域的个体适应度越低，被淘汰的概率越大。

交叉操作是遗传算法中最重要的操作，在遗传算法中起核心作用。借助交叉算子可以产生新的个体。本文采用单点交叉操作方法。第一步，将经过选择操作后产生的个体进行随机配对；第二步，随机选定一个交叉点，该点将两个父本个体的基因串分成前后两部分，执行交叉操作，该点前后两个父本个体的部分结构进行互换，并产生两个新的子代个体。

在遗传算法中，变异改变种群个体模型值，维持种群的多样性。繁重搜索陷入局部次优解，有效抑制遗传算法产生的不成熟收敛现象。本文采用逆转变异方法，在父本个体基因串中随机挑选两个逆转点，然后将这两个逆转点间的基因值以逆序排列。

3 排课结果分析

通过对某高校的排课数据进行遗传算法实验，实验结果表明所有课程均能根据教学任务要求安排在合适的上课时间和教室，没有发生课表冲突现象，符合学生及教师的上课要求，排课结果满足了所有硬约束条件和软约束条件，排出的课表可行、合理、有效。因此，基于遗传算法的排课问题求解可行，能够得到令人满意的课程表。

4 结语

本文针对排课问题进行了详细分析，并根据排课问题的特点建立数学模型，探讨基于遗传算法求解排课问题的应用方法，并通过实验证明遗传算法运用于高校排课系统的可行性，且能最大程度地减少排课人员的工作量，有效地提高了工作效率和排课效果。排课问题是一个复杂的多目标组合优化问题，影响因素多、且数据量庞大。目前国内高校普遍实行学分制改革，所开设课程数量大幅度增加，排课问题更加复杂。因此，今后有必要进一步探索和改进高校排课系统设计，以满足在学分制条件下的排课需求。