遗传算法在高校教务排课系统中的应用研究

高冬梅 陈利科

摘 要： 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法。针对高职院校课表的特点，本文详细分析遗传算法在排课系统中的基本思想及遗传算法的设计步骤，主要论述了利用遗传算法求解高职院校课表的编排问题，提出了应用遗传算法解决排课问题的有效方法。

关键词： 遗传算法 适应度函数设计 遗传算子设计

引言

随着我国职业教育事业的迅速发展，高职院校办校规模的不断扩大，教学资源越来越紧张，高校教学单位和课程众多，教师和教室短缺，使得教务管理系统中的排课模型的难度增加。虽然每个学校都不尽相同，但在教学排课中出现的实质问题仍需要综合考虑。即课程、教师、多媒体教室、机房实训室、课程和时间等变量中诸多资源的合理利用、优化配置、以教学计划和各种特殊要求为制约条件的组合规划问题。传统的手工排课易于出错且非常麻烦，针对这一复杂问题，许多学校都提出如模拟退火、列表寻优搜索、遗传算法等方法。

遗传算法是一种借鉴生物界自然遗传机制和自然选择的随机化搜索算法。它的主要特点是直接对结构对象进行操作，不存在函数连续性和求导的限定；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，适当地调整搜索方向，不需要确定的规则，具有内在的并行性和更好的全局寻优能力。针对高职院校课表的特点，本文提出了应用遗传算法解决排课问题的方法，即利用遗传算法解决排课问题。只要给出目标函数的计算规则，更少地依赖于实际问题的情况，就能实现课表的优化。实验表明，遗传算法结构清晰，思路简洁，效率较高，作为一种有效的求解最优算法，其可以有效地解决排课问题。

1.遗传算法的设计

遗传算法的基本原理是，采用某种编码方式将解空间映射到编码空间，每个编码对应问题的一个解，一般通过随机方法确定一个初始种群，在种群中根据适应度值或某种机制选择个体，用各种遗传操作算子产生下一代，反复计算，直到满足期望的终止条件，产生最优解。

1.1遗传算法步骤

1.1.1课表的染色体编码：

由于遗传算法通常不直接作用于问题的解空间，而利用解的某种编码表示进行进化，将实际问题中的课表转化为计算机可以识别的变量。同时考虑到高职院校课表的时间制度每周5天，每天最多8节课，程序中采用长度为20的二进制编码表示课表基因。1表示1次课（2节），0表示没有课。其记录了不同时间段每个老师要上课的次数，就样就建立了老师与班级、课程之间的联系。

1.1.2适应度函数的设计：

遗传算法通常基于适应度值进行遗传操作，合理的适应度函数能够将各个个体的优劣程度充分、准确地体现出来，使得遗传算法能够在目标空间中尽快找到最优解。一般而言，适应度函数是由目标函数变换而成的，基本有以下3种：

（1）直接由待求解的目标函数转化为适应度函数。

（2）若目标函数为最小化问题，则：

（3）若目标函数为最小化问题或最大化问题，则适应度函数分别为：

Fit（f（x））=1/（1+c+f（x））

Fit（f（x））=1/（1+c-f（x））

其中，c为函数界限的保守估计值。

1.1.3遗传算子的设计：

（2）交叉算子：所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc，按某种方式相互交换其部分基因，从而形成两个新的个体。

由于存在一个老师讲授多个班级的课或合班上课的情况，为避免冲突的产生，在交叉算子执行后，必须对新产生的染色体进行冲突检验。如：在N1个老师中随机选取一个老师，对他的时间安排进行单点交叉操作，或者在N2个授课班级中随机选取一个班级，对授课班级的时间安排进行单点交叉操作。

（3）变异算子：变异操作发生在同一个染色体中的两个基因位之间，即在所选的变异个体中随机产生一个行，在该行中任选两个基因编码进行互换。产生新的个体的辅助方法，保证种群的多样性，能有效地抑制遗传算法早熟现象的发生。在交叉运算和变异运算的相互配合中，共同完成对搜索空间的全局搜索和局部搜索。本文采用的是：首先随机生成1-5中的两个数，（对应星期一到星期五），表示为要交换的时间段，若生成的两个数不同则交换这两个时间段所有授课班级的课程，交换后进行检测和处理。

2.排课过程中出现的问题

在排课中要对班级、教师、教室、课程和时间五个相制约的因素进行安排。就要满足“多头课、一师多班、多学时”等条件，要想处理好这些排课中出现的问题，我们就要把这些需要满足的条件归纳为硬约束条件和软约束条件。

硬约束条件：

（1）同一个老师在同一时间不能授课两门课程。

（2）同一地点在同一时间不能安排两门课程。

（3）同一班级在同一时间不能安排两门课程。

软约束条件：

目前大多数高职院校校区不集中，分散班分教学，课程安排较集中，实训课与理论课分开行课。

（1）尽量满足个别老师的特殊上课时间、地点。

（2）班级课表在一周的上课时间分布均匀，避免有一天没有课的情况，每天的第一节课不能为自习课。

（3）班级课程相邻的地点尽量距离较近，以免学生课间不能按时到课。

（4）每一门课程在一周内的上课时间分布合理，让学生在学与练之间能够有充足的时间。

3.排课系统的实现

高职院校教学管理系统中的排课系统功能的主要功能包括：开课计划、课程设置、手动排课、自动排课、课表查询、课表打印、系统维护等，为了使整个排课系统的功能更合理、更优化，要完成以下操作。

排课的基本步骤：

（1）根据开课计划对开课数据进行处理。为了实现排课，需要对原始的数据（开课计划与课程设置）进行加工，单独的数据产生关联，生成一些有效的数据。

（2）对课程的资源结构进行系统分析。对排课的主体对象及排课资源编成可适用的遗传算法使用的编码进行运算。通过算法，得出排课系统近似最优解。

（3）运用遗传算法对排课进行求解。排课问题进行编码后，为求得出最优化结果，要经过选择、交叉、变异等操作。

（4）用算法解码处理。对得出的最优化结果的编码进行“翻译”，得出排课的结果，形成课表。

解决的问题：

（1）详细分析遗传算法的设计步骤及基本思想。

（2）说明排课问题中的制约因素和常用的约束条件，分析排课问题的求解难点和目标。

（3）设计排课系统的数据资源模型。

（4）排课遗传算法的设计求解及实现。

（5）用ASP.NET实现交互界面，以C#为脚本，采用SQL Server2005为后台数据库，对主要的算法进行实现。

4.结语

本文主要论述了利用遗传算法求解高职院校课表的编排问题，详细分析了遗传算法和排课问题。以遗传算法理论研究为择指导，结合高校排课的具体要求，针对大部分高校的教学管理模式和教学资源的配置情况进行了具体分析，数据采用的染色体编码和适应度值是合理的，不存在课表冲突问题，在对待特殊的课程安排上，完全达到排课人员的期望。遗传算法对系统中排课的方法给予了具体的实现，使高校教务管理工作趋于网络化、智能化的管理。

参考文献：

[1]傅学芳.现代优化计算方法——遗传算法简介[J].昌滩师专学报，2001，20（2）：42-46.

[2]陆峰，李新.自动排课系统算法的设计与实现[J].微机发展，2005，15（11）：2.

[3]陈国良.遗传算法及其应用[M].北京：人民邮电出版社，2004：35-48.

[4]王小平，曹立明.遗传算法[M].西安：西安交通大学出版社，2004：30-87.

基金项目：河北省廊坊市科技局2013年立项课题（201301025）