罗义强 陈智斌(昆明理工大学理学院 云南 昆明 650500)

0 引 言

高校课程编排是一项分配时间和空间给课程同时满足一定约束的活动。很多教育机构的课程编排系统没有完全自动化，需要一定的人工辅助。主要是因为课程编排的组合性和动态变化性。课程编排是计算机科学(CS)、运筹学(OR)、人工智能(AI)等领域的一个比较重要和带有挑战性问题。课程编排可以建模化为约束满足问题(CSP)对待。约束满足问题是组合优化问题并且被证明是NP-complete的[1]。搜索空间庞大并随变量指数级增长使得大多数NP-complete问题难以有效和优化地求解。

高校课程编排被大量的学者进行了广泛的研讨。各种各样的方法被提出去求解高校课程编排问题。这些方法包括：图着色[2]，将高校课程编排问题转化为一个图，顶点代表课程，边代表约束。颜色的数目相当于可行的时间档。图着色法分配有限的颜色给顶点，没有被一条边联结的相邻两个顶点同一种颜色。遗传算法(GA)[3]，以基因编码课程编排限制，以惩罚函数评估课程满意度。线性规划[4]、模拟淬火算法(SA)[5]、禁忌搜索算法(TS)[6]等。这些算法的不足之处是难以处理课程编排过程的约束，只能产生可行解，结果令人难以满意。

一些研究表明混合算法在解决高校课程编排问题显示出有前景的结果。整合局部搜索算法(LS)到粒子群算法(PSO)中，构建了高校课程编排的最优解[7]。约束传播与遗传算法相融合，得到了高校课程编排的近似最优解。遗传算法的不足之处是计算耗时长。……