基于差分算法的高校排课系统的优化与实现

余彬　丁锐

【摘 要】差分算法借鉴优化选择和差分机制，使用搜索技术，根据学生的学习进度情况，合理配置教学资源，对教学安排工作进行优化调整。高校调课涉及到学生学习基础、教室容量、教学硬件设施配备、班级人数、教师要求和上课时间六方面相互关联的因素。通过对差分算法进行优化改进，调整参数设置，对教学资源合理化使用有着比较显著的作用。

【关键词】差分算法；排课问题；优化条件

0 引言

目前差分基因算法的排课研究已经进行有一段时间了，大多是基于优化选择和进化机制发展起来的自适应随机搜索算法，但是对于约束条件存在漏洞。排课工作是一项教学服务性的工作，随着教育的发展，人性化服务显得越来越重要。之前的排课系统没有考虑到每个学校教学资源的硬件配备和时空距离。随着教育信息技术的发展，大多数高等院校都已实现了多媒体教室全覆盖化，软件集中管控化。以往的排课系统往往不能够满足这些方面的需要。比如，大学校园教学楼之间的距离较远，课间休息时间较短，如果排课出现问题，在上课之前，老师和学生都很难抵达教室；在正常的教学过程中，很多课程是相互之间致命不可分的，有时候会因为老师调课学生请假，从而影响其他科目的教学进度。

本研究对差分算法进行了特定模拟参数设置以适应排课问题。根据参数设置，课程之间的关联性、教师的时间分配、上课教室的位置关系作为主要优化参数，根据差分算法思想对调课算法设计，其过程如下：

（1）数据初始化：搜索教室，教师，班级等主要参数，对任务进行排序；

（2）根据人物排列顺序，检测查分选项中，教师时间安排、上课地点、班级信息进行自适应度评估；

（3）如果不存在冲突，则选择差分项较小的教室号来进行排课；如果存在冲突，则跳过此任务继续进行，并保留任务号；

（4）按照选择算法部分的教室，进行差分优化；

（5）重新搜寻保留的任务号，自动生成优化区间，完成排课。

1 主要算法实现

1.1 数据收集和差分

数据收集函数完成以下功能：

1）定义任务序列，并设置课程信息、教师信息、学生信息、上课条件为基本参数；

2）对于任务进行排序，生成任务的扩展信息EXInfo；

3）对任务内容进行搜索优化，生成课程项EXItem；

4）设置系统信息锁定状态解锁。

数据差分函数完成以下功能：

1）如果任务序列有未处理的数据，则判断是否锁定；如果没有锁定，则跳出函数；

2）删除序列中的上课项EXItem、课程扩展信息EXInfo、条件设定EXRule；

3）删除教师、班级、科目以及学生信息；

4）设置系统状态复位。

1.2 安排课程项

课程上的安排是本次任务的关键所在，他负责将相邻的时间序列中将空余教室号差值最小的信息优先安排，教室容量和相邻时间段的判断由其他参数判定，本算法主要完成任务序列的选取。

function Arrange EX Item （select AEX Item： PEX Item） ： Boolean；

while FEX Arrange do

{

If （not Time T Allow） or （not Room R Allow） then Continue

If FEX Arrange null then Add Time T ID， Room R ID to T R N

} then Result

Result： =Count （EX R T N）

If Result NULL

{

X ： =Random （Count（E X R T N））；

If AEX Item. Time ID=N-1 then F Arrange （A Item）：=null

NULL Arrange [EXRT[X]]：=AEX Item N escape

}

function End

1.3 对于已知任务号进行差分优化

优化模型是应用差分算法的核心，也是优化排课是否成功的关键。在任务项序列当中，设定任务序列N、时间序列T、教师序列I、班级序列C、上课地点R为基本参数，N为序列号每安排一项任务N=N+1，当T和I为固定值时候，计算C序列和R序列差值参数P1；当T和C为固定值时候，计算I序列和R序列差值参数P2；当T和R为固定值时候，计算C序列和I序列差值参数P3；以此类推，得出参数P4、P5、P6。然后计算，P1、P2、P3、P4、P5、P6之间的差值，将差值最小的参数PN设定为最佳配置，然后进行下一条任务。通过测试证明这种优化改进的差分算法是经过多种算法数据分析后决定的，效率比较高，参数设置简单，置换性较强，优化操作也可针对有部分课程信息项进行。

1.4 排课结果进行调查分析

排课完成后需要对结果进行检测并给出检测结果。教师和学生的调课率，作为排课结果的认证标准。通过调查证明，这种排课方法调课率较低，成功率较高，安排的课程，比较合理。

2 结束语

本文在差分算法的基础上进行了部分改动，灵活的设置了排课参数，将排课的合理性和调课率联系起来，为今后此类型的研究提供一定的理论基础。随着信息化的发展和大数据的应用，此差分算法可增加参数设定，具有较好的延展性和前瞻性。

【参考文献】

[1]李锐.高校排课系统算法的研究与实现[D].吉林大学，2010.

[2]熊卫卫.高校排课系统算法设计与实现[D].吉林大学，2004.

[3]商凌霞.高校排课系统的设计与实现[D].浙江工业大学，2012.

[4]齐萍.基于蚁群算法的高校排课系统优化策略[J].湖北工业大学学报，2010，02：68-69+78.

[5]林瑞金，卓清寅.基于遗传算法的高校排课系统设计与实现[J].荆楚理工学院学报，2010，09：27-29.

[责任编辑：汤静]