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

王丽红　刘平　于光华

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

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

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

排课问题描述

问题描述

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

约束条件

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

硬约束是指在排课过程中必须遵守的规则，一般包含以下几个方面：同一时间段内，一位教师不能排一门以上的课程，不能占有一个以上的教室；……