模拟退火算法在高职排课系统中的应用研究

李承敬

摘 要：文章针对高职排课系统中精度搜索效率较差的问题，通过对排课系统中6个关键属性和属性间的约束的分析，建立了排课系统模型和属性约束模型，基于该模型在高职排课系统中采用启发式模拟退火搜索算法进行排课，最后通过实验仿真，验证了SA算法在排课系统中的有效性，可以得到近似最优解。

关键词：模拟退火算法；排课系统；启发式搜索

中图分类号：TP393 文献标志码：A 文章编号：1673-8454（2014）12-0084-03

一、引言

随着教育和技术的深度融合，高职教育中教务管理也经历了手工、计算机辅助、信息系统自动管理三个阶段，其中排课问题的求解更是体现了信息技术在高职教务管理中的优势。[1]教务排课问题是教学计划安排和教学过程管理的保证，研究人员对排课问题的研究由来已久，该项研究具有较高的理论和现实意义。[2-3]

上世纪70年代，Cooper等从计算复杂性的角度证明了排课问题是NP完全问题，说明排课问题可以通过建立问题的数学模型找到问题的近似最优解。[4]NP完全问题可以在多项式时间内判定给定结果是否正确，可以通过精确搜索和启发式搜索来求近似解，精确搜索过程中，计算复杂性呈指数增长，对中间结果没有充分利用，存在盲目性，不利于解决大型问题，此方法适用于小规模的搜索问题。启发式搜索对中间搜索位置进行评估，根据评价函数，在较好的位置再进行搜索，求得近似最优解，此方法可以用于排课算法等大规模搜索问题的解决，常用的启发式搜索方法有蚁群算法、遗传算法、模拟退火算法、神经网络算法、免疫算法等。[5]

模拟退火算法（Simulated annealing SA）是针对组合优化问题，采用迭代求解的思路，随机进行寻优的一种通用概率启发式算法，适用于较大空间的搜索问题，在多项式时间内期望找到全局最优解或最优近似解，排课算法是典型的大空间组合优化问题，因此可以在排课算法中采用模拟退火SA算法。[6]

排课算法其实质是一个周期时间内，关键属性（教师、班级、课程、教室、课时段）满足一定的约束条件、使得排课时间分布合理，并一定程度上达到近似最优解。[7]在排课过程中为了避免属性之间冲突，同时兼顾教学过程的合理性和师生的上课效率，还需要根据教务实际情况设置一些排课附加条件。本文主要采用模拟退火的方法对高职排课系统中的排课算法进行多目标的优化，寻求较优的解决方法，下面从排课系统相关概念、系统模型、模拟退火算法、系统实现四个方面进行分析。

二、相关概念

排课问题是一个涉及多属性约束组合优化的问题，其中涉及到的关键属性包括校区、时段、教室、教师、学生、课程等6个方面。通过合理安排属性，满足约束条件是排课问题的关键。

校区属性是学校在地理位置上不同分布的区域，由于空间跨度大，是排课首要考虑的关键属性，校区用代码进行区分。

时段属性在排课过程中涉及周、天、天时段三个属性组成，周分为单周和双周，天分为5个工作日，天时段包括上午5个时段，下午4个时段，晚上3个时段。

教室属性是上课的地点，主要包括教室类型、教室容量、所在教学楼等信息。教室类型主要包括普通教室、多媒体教室、机房、体育馆、琴房、画室、报告厅等多种类型，排课过程中，教室属性首要满足教室类型，在功能上吻合，其次上课人数要不大于教室的容量，也不宜选择容量过大的教室，浪费教学资源。在相连课程的教室的选择上，兼顾教室所在教学楼的距离，尽量减少学生的奔波。

学生属性对于排课系统是一个逻辑概念，由上同一门课程的学生组成的集合，学生来源可以是同一个行政班、多个行政班或者多个行政班的部分学生，如公共课，学生来自多个专业不同的班级，基础课一般是同一专业的不同班级，专业课一般是同一专业的同一个班级。排课根据学生属性的限制条件多少，确定排课的优先级，先对限制条件多的学生属性优先排课。

教师属性主要包括专业课教师、基础课教师、外聘教师，对于外聘教师在排课时要考虑校区距离的因素，优先安排。

课程属性在教务系统中主要分为挂牌课、公共课、专业基础课、专业课。挂牌课是由知名教授主讲面向全校学生开设的公共课程，该类课程具有知名度高、选修学生多、跨校区和专业性强等特点。 公共课是面向全校各专业开设，通常是必修的与学位挂钩的课程，对于学生来说较为重要，如计算机基础、大学英语等，该类课程具有跨校区和专业，教师学生数量较多，通常存在合班上课，对上课时间和教学地点座位数量要求较高，因此此类课程应该优先处理。专业基础课是针对各个专业开设的本专业的重要课程，为专业的教学做好理论知识准备，该类课程主要面向特定专业，对教学地点限制较多，如语音室、琴房、舞蹈房、机房等。专业课是面向较小规模的师生，在排课系统中优先级较低，与其他属性冲突时，可以安排在特殊时间点，如晚间10-12课时段。

排课算法中约束主要包括下面几种情况：

1.常规约束

常规约束是排课算法中必须要满足的约束条件，如同一课时段、同一教室只能安排一个教师，一个学生集合最多一个课程。

2.附加约束

根据排课算法的相关属性，附加约束是根据教务要求，人为附加的约束条件，主要包括对教师、学生、教室、课程的排他约束，以及对课程密度的约束。

排他约束如教师张三在每周三课时段6-9不安排课程，工商管理二班第5-6周异地实习，实验楼第一阶梯教室第2周维修，不安排课程，数据库原理第15周要安排在机房做课程设计。

课程密度约束，如学生每天课时数限制，每周课时数限制，教师每天最多课时数限制，以及教师、学生连续课时数限制，保证教学的质量和师生的合理作息。

3.组合属性约束

组合约束是在常规约束和附件约束的基础上，进行合理的约束条件组合，产生更加细的约束条件，如课程动画设计第16周安排在Apple机房进行课程设计。在排课系统中优先满足组合属性约束。

三、排课系统模型

在排课系统模型中，假设课程的排课周期为一周，那么排课问题可以描述为在一个学习周期内W={w1，w2……wj}j

课程ci的任课教师表示为tea(ci)，学生集合表示为stuset(ci)，某课时段内是否安排该课程表示为assign(ci,tdp)∈[0.1]。排课系统模型就是求解满足约束条件的解的集合S={s1，s2…si}，si=(ci，tdp，ri)。

根据第二节描述，排课约束条件可以分为常规约束、附加约束、组合约束。约束条件可以采用如下方式进行描述：

Constraints1：排课系统完成所有课程的编排

∀ci，∃（ci，tdp，ri)∈S

Constraints2：同一课时段，同一教室，有且仅有一门课程

∀(ci，tdp，ri)，(ci，tdp，ri)∈S，(ci=ci′）∧（tdp=tdp′）∧（ri=ri′）

Constraints3：同一课时段，不同的课程，教师和学生不能重复

∀(ci，tdp，ri)，(ci，tdp，ri)∈S，sea(ci）≠tea(ci′)∧stuset(ci)∧stuset(ci′)

Constraints4：教师某课时段不安排课程

∀(ci∈sea(ci）,assign(ci，tdp)=0,(ci，tdp，ri)∈S

四、模拟退火算法

模拟退火算法（Simulated Annealing，SA）包括产生函数、评价函数、冷却策略、稳定准则、退火结束标准。SA算法初始化较高的温度，采用Metropolis抽样策略，在一定领域范围内进行搜索，不断重复抽样进行迭代，判断是否满足退火结束标准，寻找目标函数的全局最优解。为了形式化描述SA算法，定义J(x)状态时的评价函数值，Xi表示时刻的状态，T系统初始化的温度，Tmin表示退火结束标准，温度的下限，a(a∈(0.1))表示冷却策略，a越大降温越慢，a越小降温越快。

SA算法流程形式化描述如下：

init(T)

while(t>Tmin){

tmp=J(Xi+1)-j(Xi)

if(tmp≥0）

J（Xi+1)=J(Xi)

else if (exp()>random(0,1))

J(Xi+1)=J(Xi)

T=a*T

i++}

对于SA算法中的冷却策略a(a∈(0.1))，满足非线性公式 ai=（i=1,2……K），使得温度降低不至于过快，而陷入局部最优，也不至于降低过慢，影响算法的性能。

通过对SA算法描述进行分析，不难发现SA算法从初始化温度开始，对约束条件均匀的要求，求解效果较好，收敛速度快。控制参数的选择较难，对算法结果影响较大，还要在降温策略和评价函数进行多次仿真测试。

五、系统实现

为了验证模拟退火SA算法在排课系统的应用，采用Microsoft C#实现基于标准邻域的SA算法的排课系统，其系统工作流程如图1所示。

测试过程中，选取电子商务专业25位教师、40门课程对排课系统进行仿真测试，每个实例运行50次，经过测试，初始化参数T设置为38.6，降温参数a(a∈(0.1))设置为，a=0.98,Tmin=23.87。测试结果表明基于模拟退火SA算法的排课系统是有效的，可以便捷的得到相对最优解。

本文针对高职排课系统中精度搜索效率较差的问题，通过对排课系统中6个关键属性和属性间的约束的分析，建立了排课系统模型和属性约束模型，基于该模型在高职排课系统中采用启发式模拟退火搜索算法进行排课，最后通过实验仿真，验证了SA算法在排课系统中的有效性，可以得到近似最优解。

参考文献：

[1]滕姿,邓辉文,杨久俊.基于遗传算法的排课系统的设计与实现[J].计算机应用,2007(S2):199-201.

[2]谭保华,彭伟.基于蚁群遗传算法的高校排课系统[J].计算机仿真,2008（12）:294-297.

[3]苏明杰,陈建勋.基于线性规划模型的高校排课系统[J].微计算机信息,2011（8）:197-200.

[4]宗薇.高校智能排课系统算法的研究与实现[J].计算机仿真,2011（12）:389-392.

[5]于娟,尹积栋.面向排课系统的遗传算法改进研究[J].太原理工大学学报,2012（5）:572-574，579.

[6]刘涛.农林高校学分制排课系统的设计及绩效分析[J].安徽农业科学,2009(28)：3927-3928，3950.

[7]李振,王晓全,张子蛟,候跃生.基于专家系统的交互式排课系统的实现[J].郑州大学学报(工学版),2010（4）:124-128.

（编辑：鲁利瑞）