遗传算法在高职院校排课问题中的研究与应用*

康 彦

(安徽城市管理职业学院，安徽 合肥 230001)

遗传算法在高职院校排课问题中的研究与应用*

康 彦

(安徽城市管理职业学院，安徽 合肥 230001)

新形势下的高职教育具有丰富多样的教学形式，传统的人工编排方式在应对大量的教学活动编排工作时，效率较为低下，而一些市面上常见的教学管理系统中的排课模块大多是按照本科的教学模式设计，无法适应高职院校的教学活动编排问题的特殊性.该文研究和分析高职院校排课活动的特点，通过对普通遗传算法的改进，提出一种解决高职院校排课问题求解算法，并对改进后的算法进行效率分析.

遗传算法；排课问题；高职院校

我国高等教育事业的发展，从上个世纪的八十年代开始迎来了一个发展的高潮，特别是高等职业教育，也被纳入到了高等教育序列中来，二十多年来，高等职业院校的数量和规模不断扩大.截至到2012年，我国具有高考招生资格的高职类院校已有1288所，在校生人数超过1000万人[1].伴随着职业教育的快速发展，近年来，高职院校办学特色不鲜明，定位不准确，教学质量无法保证等问题慢慢凸显出来.为了改变这一现状，高职教育的课程改革也在不断作出调整,通过实施“工学结合、校企合作”及项目化教学等手段，进一步开发实训模块、提高学生职业能力，使高职学生真正成为企业需要的高级技能型人才.

这一变化使得原本套用本科教学安排模式的高职教学安排问题变得越来越复杂.除了正常的公共课程(“两课”、体育、英语、高数和一些专业理论基础课)以外，大多数实践实训类课程教学为了达到良好的操作技能学习效果就需要在几天甚至几周时间内连续进行授课,还有的课程需要去公司企业进行实际操作培训.

1 遗传算法

遗传算法是借鉴了生物进化理论的一种全局搜索优化的概率性算法.在生物进化理论中，种群(Population)是生物进化的基本单位[2].单个生物个体(Individual)无法进行遗传进化.种群通常是一个有大量生物个体构成的集合.种群中的个体都不重复，因为每个个体所表现出来的外部特征都是不同的，比如人类个体的肤色差异、性格差异、运动能力差异等等.之所以存在这些差异，是因为每个生物个体都具有独一无二的染色体.染色体是遗传因子(Genetic Factor)的载体.遗传因子是由许许多多遗传基因(Gene)按不同的排列组合而成的.生物进化过程中种群中的个体之间进行随机的交配，产生下一代种群.通过基因交叉(Crossover)、突变(Mutation)和自然选择等操作后，使得下一代种群更为适应外部自然环境[3].遗传算法正是模拟了生物进化的这一过程，通过遗传迭代一定代数后，得出适应度最高的种群.实现生物进化理论中的“优胜劣汰，适者生存”[4].

2 高职院校教学活动的特点

(1)本科的学制一般是4年，而专科为3年.由于受到高职学生需要进行近半年的顶岗实习的要求限制，实际上很多高职院校学生的在校学习时间仅有2.5年或者2.25年.在如此短的时间完成包括公开课、专业基础课及专业实践实训课在内的所有课程难度较大.

(2)大部分高职院校由于建校时间短，规模发展快，普遍存在师资不足的情况.在加大本校专职教师的工作量的同时，还需聘请部分校内和校外兼职教师.

(3)高职院校重视学生实际动手能力和实践技能的培养，专业课程的实验实训的比例一般不低于50%，这就导致很多教学活动不能安排在普通教室或是多媒体教室中进行，需要在专业的实验实训室开展，甚至有的实训活动需要到校外的实训基地或者行业企业中进行.因此，高职的教学活动编排必须充分考虑实验实训室的场地资源的合理调配和学生外出实践的时间安排.

(4)在新的高职院校的教学模式中，有一些纯实践类的课程需要进行时间连续的教学安排.如某系的数字媒体技术专业的“影视后期制作”课程采取的上项目化教学方式，教学时间是安排某学期中连续的2周内完成.这就要求在具体排课的时候，要减少同学期中其他课程的授课周数，增加周课时数来完成教学计划.

综上所述，这些特点都是高职院校在进行具体教学活动编排时遇到的一些共性的问题.正确地理解和分析它们，有助于我们在解决高职院校排课问题上提高，改进和创新.

3 基于遗传算法的高职院校排课算法

求解排课问题的遗传算法首先需要解决的就是如何对排课记录进行合理的编码，实质上就是为排课记录设定教学场地时间对[5-6].将基因按一定的顺序组合到一起，就是一条染色体.在排课问题中，基因是排课记录，染色体就是一张完整的课表.通过对课表染色体的选择、交叉和变异等一系列遗传操作后得出适应度较高的个体作为最后的解.排课算法的整体流程如图1.

图1 排课算法流程

本文在研究分析传统的遗传算法的特点之后，对其进行了改进，设计出一套符合高职院校特点的排课算法，主要改进如下：

(1)为每个排课记录设置优先级，设计出基于优先级的课表染色体，提高了生成有效课表的效率.

(2)改进优化目标，将硬约束写入课程基因中，减少了遗传操作中无效课表的出现比例.

(3)引入课表个体自动修复，将冲突较少的无效课表个体在有限的时间代价内修复为有效个体.减少课表生成次数.

4 算法性能分析

实验的数据来自于某高职学院信息工程系2012～2013学年第一学期的实际教学活动数据.

(1)迭代次数比较.表1是交叉概率为0.6，变异概率为0.02条件下种群个体适应度趋于稳定的代数.

表1 迭代次数对比-1

表2是交叉概率为0.5，变异概率为0.01条件下种群个体适应度趋于稳定的代数.

表2 迭代次数对比-2

通过上述数据的对比，可以看出在不同的种群规模下，改进后的遗传算法得到稳定的适应度的迭代次数均小于普通遗传算法.证明其搜索性能优于普通遗传算法.

(2)算法时间消耗分析.通过对上述实际排课数据进行模拟不同的迭代次数来比较改进后的遗传算法和普通遗传算法之间的时间消耗.假设初始的种群规模为50.迭代次数分别为100次、150次、200次和300次.具体结果见表3、表4.

表3 迭代次数100次

表4 迭代次数200次

通过对上述对比数据的分析，我们得出以下结论：

① 不管是普通遗传算法还是改进后的遗传算法，在种群规模确定的情况下，迭代次数越高，时间消耗越大.产生适应度较高个体的数量也随着迭代次数的增加而增加.

② 在相同迭代次数中，改进后的遗传算法的时间效率和产生较高适应度的个体数明显优于普通遗传算法.

③ 出现适应度较高个体数在迭代次数超过200次以后，基本趋于稳定.

5 总结

高职院校的教学活动安排问题是一个涉及诸多学科的现实问题.本文以某高职学院为例分析和总结了高职院校教学活动安排问题的特点.当今的高职院校教学模式多为“工学结合、校企合作”模式[7]，注重提高学生的实践操作能力的培养.实验实训课程的比例相对较高.从而加大了教学活动编排的复杂度.本文在研究分析了传统的遗传算法的特点之后，对其进行了改进，设计出一套符合高职院校特点的排课算法.

[1]边昊.我国高职院校教学改革的现状与趋势分析[J].辽宁科技学院学报，2014(03).

[2]A.Colorni,Dorigomarco,V.Maniezzo. Metaheuristics for high school timetabling[J].Computer Optimization and Application,1998,9(7):275-298.

[3]Pillay N，Banzhaf W.An informed genetic algorithm for the examination timetabling problem[J].Applied Soft Computing，2010，10(2)：457-467.

[4]任克强,赵光甫,张国萍. 高校排课问题的模型与算法[J]. 计算机与现代化,2007(10)：80-82.

[5]张献.蚁群算法在排课问题中的应用研究[J]. 长春大学学报,2007(10)：80-82.

[6]祝勇仁,邓劲莲,胡献华,张炜.排课问题的一种遗传算法适应度求解方法[J].四川大学学报(工程科学版),2007(S1):277-282.

[7]韦玉,冯速. 免疫遗传算法在排课问题中的应用[J]. 北京师范大学学报(自然科学版),2008(02):168-173.

(责任编辑:王前)

10.13877/j.cnki.cn22-1284.2015.04.013

2015-02-10

2014 年省级教学质量与教学改革工程项目“高职院校软件设计类课程自主学习平台的研究与应用”( 2014jyxm603)

康彦，男，安徽合肥人，讲师.

TP31

A

1008-7974(2015)02-0034-03