几种智能排课算法的对比探讨

黄岭 秦春娣 陈伟

摘要：该文给出了排课系统避免冲突所需要遵循的条件和因素，对可实现于排课的几种智能算法做了介绍和分析，并对智能算法以后的发展进行了探究，为今后的各种排课需求提供参考。

关键词：排课;智能算法;分析对比

中图分类号：TP312

文献识别码：

文章编号：1009-3044（2020）04-0159-02

收稿日期：2019-12-05

基金项目：江苏省大学生实践创新训练计划项目校级项目“机房排课系统的设计与实现"（项目编号：51800021644）

作者简介：黄岭（1979—），男，江苏常州人，讲师，硕士，研究方向为电子及计算机应用;秦春娣，女，工程师，本科;陈伟，男，专科生。

Comparison of several intelligent Course Scheduling Algorithms

HUANG Ling，QIN Chun-di，CHEN Wei

（Changzhou Vocational Institute of Textile and Garment，Changzhou 213164，China）

Abstract：This paper gives the conditions and factors that need to be followed to avoid conflict in course scheduling system，analyzes and compares several intelligent algorithms that can be used to solve course scheduling problems，and forecasts the development pros-pect of intelligent algorithm，so as to provide reference for future various courses scheduling needs.

Key words：course scheduling;intelligent algorithm;analysis and comparison

人類每一次的思考创新都离不开技术革新带来的取代传统手工操作，转向高效人工智能处理的进步。一直困扰着学校教务的排课问题也随着专业、班级、课程等必要条件的不断扩展而显得愈演愈烈。排课问题作为资源分配调度的一种典型问题，已经被证明是非确定性多项式（NP）完全问题。完成排课课程表这个过程的课程调度算法也是NP问题中较难的一类。近些年，许多研究人员将人工智能、神经网络、模糊算法、进化算法等方面的研究成果不断在控制盒优化、复杂线性系统模型.创建方面进行探索，并产生了一系列的智能排课算法，本文就常用的几种算法做一个比较分析。

1 排课问题分析

排课问题需要解决的是根据具体教学需要满足诸如节次、班级、教学地点、教师这一系列因素的组合，并且能够很好地处理特殊需求，协调各因素之间的矛盾冲突，换言之就是要借助计算机技术权衡各种制约条件，最终达到课程安排合理化的结果[1]。

排课系统中的涉及的约束条件归纳起来主要有三种：基础硬约束、硬约束和软约束。

1）基础硬约束：是指教师、班级和教学地点在节次上不可发生的冲突，包括“同一节次同一班级不能上两门不同的课程”;“同一节次同一教师不能上两门不同课程”，这类约束条件是所有排课模型都会涉及的，最基础的要求，这个约束若无法

满足，排课也就没有意义了。

2）硬约束：是指排课时需要遵循的教学计划规定的一些硬性要求或实际教学场地的条件限制的原则。如“课程按照最小两节或六节进行”;“课程的总周数有要求”;“教学地点容纳学生数限制”等。

3）软约束：是指在若能够完成基础硬约束和硬约束排课的前提下，可适当考虑教学规律或个性化排课需求。如“每个班级的课程周分布均匀”;“教师特定时间段上课”等。

2 几种算法比较

当前常用的排课算法，主要包括回溯算法、人工免疫算法、遗传算法、粒子群优化算法、图着色算法、贪婪算法、模拟退火算法、蚁群算法等，下面对这几种常用算法的特点加以描述。

2.1 回溯算法

回溯算法也称为试探法，它是一种类似枚举 的系统搜索问题解的方法，原理是在搜索探试过程中寻找问题的解，当发现不满足求解条件时，就“回溯"返回，尝试别的路径。

回溯算法基本步骤：面向设定问题，定义问题的解空间，它至少包含问题的一个解;设计易于搜索的解空间结构模型，使其能用回溯法搜索整个解空间;以深度优先的方法搜索解空间，并且在搜索过程中用剪枝函数来避免无效的搜索。

其优势是整体结构清晰，容易理解;空间占比较小;适合处理组合数较大且有限的问题。其不足体现在算法计算量较大，回溯层次多时过于耗时[1]。

2.2 遗传算法

遗传算法是在20世纪六七十年代由美国密歇根大学的Holland教授创立的。Holland在设计人工自适应系统时建议参考遗传学基本原理来模拟生物自然进化的方法。遗传算法是一种基于进化论的自然选择、遗传进化并行，且随机自适应的搜索算法[2]，将问题解通过复制、交叉、变异来编码，生成的“染色体”群通过一代代的不断进化、收敛，最终成为最适应的群体。

遗传算法的基本步骤：预估期望进化代数，计数器初始设置，随机生成多个初始群体;评估群体中各体适应度;在评估基础上将优化的个体直接或者配对交叉产生新个体遗传到下一代;将交叉算子（在此算法中起核心作用）作用于群体;群体通过选择、交叉、变异运算这一系列手段修改来自个体串的某些基因座上的基因值从而得到下一代群体;若计数达到期望进化代数，则可得到最大适应度个体，即最优解[2]。