求解排课问题的遗传蚁群混合算法

王丽红　刘平　于光华

针对排课问题，本文将遗传算法和蚁群优化算法融合，提出了一种遗传蚁群混合的优化算法。首先利用遗传算法产生初始信息素的分布，在运用蚁群算法求精确解。实验表明该算法取得了良好的适应度值和时间性能。

排课问题涉及到教师、教室、班级、课程、时间等诸多因素，是一个处理起来相当复杂的优化决策问题。排课问题已被证明是一个NP完全问题，也是一个很有研究价值的实际问题。

文献提出了一种新型的解决排课问题的离散粒子群算法，在三维空间中建立模型，并引入了冲突检测及变异等操作。文献提出了自适应遗传算法，该算法采用三维编码方案，并在交叉概率和变异概率、适应度函数、初始种群的生成等方面都进行了设计和优化。文献应用蚁群遗传算法进行排课研究。在本文将遗传算法与蚁群算法融合来研究排课问题。

排课问题描述

问题描述

排课问题实际上是一个五维空间上的组合优化求解问题。五维是指教室、教师、班级、课程、时间，要实现的目标是上述五元素的最优化配置，对于这一类组合优化问题要寻求一种合理的近似最优解。

约束条件

排课方案必须满足两大类约束：硬约束是衡量一个排课方案是否可行的标准，软约束是衡量一个排课方案优劣的标准，而反映一个排课方案优劣的标准有多种情况。

硬约束是指在排课过程中必须遵守的规则，一般包含以下几个方面：同一时间段内，一位教师不能排一门以上的课程，不能占有一个以上的教室；同一时间段内，一个班级不能上一门以上的课程；同一时间段内，一个实验室不能排一门以上的课程；教室能够容纳上课班级的学生人数。

软约束条件是指在排课方案中可以满足但又可以不完全满足的条件，根据各学院情况不同而有所差别，包含以下几个方面：专业相关的重要课程尽量安排在较好的教学时间段；多学时的课程每周的安排要错开（学时大于等于4课时，能够尽量隔天排一次课）；一周内每天课时尽量平均；教室利用率高，上课班级人数尽量接近教室可容纳人数。

遗传蚁群算法

算法基本思想

遗传算法在搜索初期具有较高向最优解的收敛速度，但是达到一定时刻后不能有效利用系统中的反馈信息，使搜索具有盲目性，导致求解速度会明显降低。由于信息素匮乏，蚁群算法在初期搜索速度缓慢，当信息素累积到一定程度之后，蚁群算法求解效率会迅速提高。而遗传蚁群混合算法的基本思想是，首先采用遗传算法产生初始信息素的分布，当遗传算法达到一定迭代次数或群体中向最优解的进化速率低于一定程度时结束遗传算法，应用蚁群算进行最优解的求解。如图1所示。

遗传算法

编码。针对排课问题的特点，使用三维数组对排课信息进行保存，具有编码和解码都很直观，方便冲突检测，算法的复杂度低等优点。

遗传操作。在标准遗传算法中，交叉概率和变异概率是固定不變的。为了保持种群的多样性，避免出现早熟和局部收敛现象，本文根据遗传操作前后最优染色体适应度值的变化情况，对交叉概率和变异概率采用自适应调整策略。