２０１１牟第３期　

中图分类号：ＴＰ３０１　文献标识码：Ａ文章编号：１００９—２５５２（２０１１）０３一Ｏｌ１９—０３　

一种改进的混合排课算法研究与实现　

杨东风　

（陕西延安大学计算中心，延安７１６０００）　

摘要：针对目前常用的排课算法中存在的不足，分析了基于遗传算法的单一排课算法存在影　

响排课因素多、难以进行最优组合及排课效率低等问题，提出了一种基于优化的遗传算法和贪　

婪算法组合的混合排课算法。该算法首先采用改进的遗传算法对教学时间片进行安排，然后再　

采用贪婪算法进行教学场地安排，该算法的创新点在于简化了影响排课结果的因素，将一个复　

杂的过程分解为两个阶段来实现，保证了排课结果的合理性、提高了自动排课的效率、有利于　

后期部分课程的手动调整。　

关键词：排课问题；遗传算法；贪婪算法；研究；实现　

Ａｎ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｔｈｅ　ｍｉｘｅｄ　ａｒｒａｎｇｅｍｅｎｔ　ａｎｄ　ｉｔｓ　ｒｅａｌｉｚａｔｉｏｎ　

ＹＡＮＧ　Ｄｏｎｇ—ｆｅｎｇ　

（Ｃｏｍｐｕｔｅｒ　Ｃｅｎｔｅｒ，Ｙａｈ’ａⅡＵｎｉｖｅｒｓｉｔｙ，Ｙａｎ’ａｎ　７１６０００，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ　ａｔ　ｔｈｅ　ｉｎｓｕｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ｃｏｍｍｏｎ　ｃｏｕｒｓｅ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｔｉｃ　

ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｎａｌｙｚｅｄ，ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｇｒｅａｔｌｙ　ｉｎｆｌｕｅｎｃｅｄ　ｂｙ　ｓｉｎｇｌｅ　ａｒｒａｎｇｅｍｅｎｔ　ａｎｄ　ｔｈｅ　ｏｐｔｉｍａｌ　

ｃｏｍｂｉｎａｔｉｏｎ　ｃａｎ　ｇｒｅａｄｙ　ａｎｄ　ｔｈｅ　ｌｏｗ　ｅｆｆｉｃｉｅｎｃｙ　ｗａｓ　ｐｒｏｐｏｓｅｄ，ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｇｅｎｅｔｉｃ　

ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ｈｙｂｒｉｄ　ａｌｇｏｒｉｔｈｍ　ｃｏｍｂｉｎｅｄ　ｓｃｈｅｄｕｌｉｎｇ．Ｔｈｅ　Ｍｇｏｒｉｔｈｍ　ｆｉｒｓｔｌｙ　ｂｙ　ｔｈｅ　

ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｏｒｇａｎｉｚｅ　ｔｅａｃｈｉｎｇ　ｔｉｍｅ，ｔｈｅｎ　ｂｙ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｅａｃｈｉｎｇ　ｆｉｅｌｄ　

ａｒｒａｎｇｅｍｅｎｔ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｉｎｎｏｖａｔｉｏｎ　ｉｓ　ｓｉｍｐｌｉｆｉｅｄ　ｇｒｅａｔｌｙ　ｉｎｆｌｕｅｎｃｅ　ｆａｃｔｏｒｓ，ｔｈｅ　ｒｅｓｕｌｔｓ　ｗｉｌｌ　ｂｅ　ａ　

ｃｏｍｐｌｉｃａｔｅｄ　ｐｒｏｃｅｓｓ　ｉｎｔｏ　ｔｗｏ　ｓｔａｇｅｓ，ｇｕａｒａｎｔｅｅ　ｔｈｅ　ｒａｔｉｏｎａｌｉｔｙ　ｏｆ　ｃｏｕｒｓｅ，ｉｍｐｒｏｖｅ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　

ａｕｔｏｍａｔｉｃ　ａｒｒａｎｇｅｍｅｎｔ　ｆｏｒ　ｔｈｅ　ｌａｔｅｒ　ｐａｒｔ　ｏｆ　ｃｏｕｒｓｅ，ｍａｎｕａｌ　ａｄｊｕｓｔｍｅｎｔ．　

Ｋｅｙ　ｗｏｒｄｓ：ｃｏｕｒｓｅ　ａｒｒａｎｇｅｍｅｎｔ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ；ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍｓ；ｒｅｓｅａｒｃｈ；ｒｅａｌｉｚａｔｉｏｎ　

０　引言　

排课问题称为课程表问题。课程表的关键问题　

就是直接解决排课中时间和空间资源的冲突问题。　

近年来，由于高校招生规模不断扩大、课程设置也相　

对越来越复杂，随之而来就出现了学生数量、开课门　

数与教学资源严重不足之间的矛盾。尽管各个高校　

尽量提高教学资源的利用率，但教学资源严重不足　

的问题还是没有解决。这样，就给高校的排课工作　

带来很大困难。因而，在合理利用现有教学资源的　

前提下，设计一个让教师、学生都满意的排课方法就　

显得十分重要¨　。　

１　遗传算法分析　

排课过程的实质是教师、教室、班级、课程和时　间五个基本元素的最优化过程　Ｊ。既要避免相互　

冲突，又要合理。目前通常采用的遗传算法是一种　

通过模拟自然界生物进化过程求解极值的一种优化　

算法。它是基于自然选择和基因遗传学原理的搜索　

算法，将“优胜劣态，适者生存”的生物进化原理引　

入待优化参数形成的编码群体中，按照一定的搜索　

技术，将种群代表一组问题解，通过对当前种群进行　

遗传操作，从而产生新一代的种群，并逐步使种群进　

化到包含近似最优解的状态　Ｊ。但遗传算法在实　

际求解过程中存在诸如依据适应函数选择的染色体　

收稿日期：２０１０—０９—１３　作者简介：杨东风（１９７３一），男，硕士，讲师，主要研究方向为信息　系统　

一ｌ

　ｌ９一　是否为合理染色体、依据交叉和变异所选的染色体　

是否为合理染色体以及在多个因素中如何选定基因　

等问题。　

２贪婪算法描述　

贪婪算法是一种简化解题复杂度的算法，是一　

种不追求最优解，只希望得到较为满意解的方法，它　

采用逐步构造最优解的思想，在问题求解的每一个　

阶段，都作出一个在一定标准下看上去最优的决策；　

决策一旦作出，就不可再更改。制定决策的依据称　

为贪婪准则。也就是说，它总是把整个解题过程分　解成一个个细小的步骤，并根据其难易程度确定其　

处理顺序，做出在当前看来是局部最优的选择，逐步　

逼近给定的目标，以尽可能快地获得满意的处理结　

果　引。　

３　混合排课算法的设计与实现　

在该混合排课算法的设计过程中，由于考虑到　

排课问题中的诸多因素（教师、班级、时间、课程和　

教室），因而整个排课过程分两步实现。首先采用　

改进的遗传算法给每个教学任务分配合理的教学时　

间片段，然后对生成的包含教师、课程和时间片段的　

教师教学任务利用贪婪算法分配教室，从而产生最　

优化的一张课表　Ｊ。　

３．１　时间片安排算法的设计与实现　

（１）设置控制参数：排课过程中涉及到一系列　

控制参数，如基因编码、种群的规模、选择率、交叉　

率、变异率等、迭代次数Ｍ，计数器Ｎ。　

种群规模：在该问题中，初始种群是由班级、教　

师和时间片组成的二维序列，按照一般教学单位的　

规模来讲，该种群数量介于５０～２００之间。　

选择率：为了使得适应度值最高的个体得以保　

留，应确保这样的个体不进行配对交叉而直接复制　

到下一代中，所以，我们构造一个选择率的计算公　

式：Ｑｓｅｌｅ＝ｆｉｔ（　）／ｆｉｔ。其中ｆｉｔ（　）为某个个体适应度　

值，６ｔ为种群适应度值总和，ｉ：１，２……种群规模　

总数。　

交叉率：采用单点交叉。　

变异率：为了避免传统的遗传算法中因“近亲”　

繁殖导致的进化停止和收敛于非最优解，提出了一　

种新的自适应变化的方法，即变异率ＰＭ与父串相对　

距离成反比，随迭代率（迭代次数与最大迭代次数的　

比值）指数下降自适应变化。。　。　

ｆｐ…ｅｘｐ（一ｔ／ｔ　）。（１一Ｒ／Ｒ　）Ｐ　＜ｐ　ｉ　Ｐ　《　【Ｐ…Ｐ　＞ｐ　其中，ｐｍａｘ／ｐｍｉｎ分别为最大和最小变异率，ｔ／＇ｔｍａｘ　

分别为迭代次数和最大迭代次数，Ｒ＼Ｒｍａｘ分别为　

１　２０一　父串间的欧氏距离和最大欧氏距离。　

基因编码设计：将教师、班级、课程进行捆绑，组　

成一个教学任务单元并编号，然后以班级为列，以周　

教学时间片段为行，组成班级二维表作为染色体。　

（２）适应度函数：计算方法为Ｆ＝∑　）×　

Ｗ（ｉ）　ｉ）为各优化条件，　（ｉ）为各优化条件所占　

权重。　

在该排课问题中，我们所确定的适应度函数必　

须要考虑以下优化条件：　

①不同性质的课程时间段安排的科学性、合理　

性，表示为　１）。　

②自然班每天课程安排的均匀性，表示为＿厂（２）。　

③同—教师每周匕课时间安排均匀性，表示为　３）。　

（３）初始化种群：为了保证遗传算法搜索的全　

局性和稀疏性，首先把每周划分为５个大的均匀的　

时间片，由此构成一个时间片小区域，然后在每个均　

匀的时间片区域中使用随机函数产生一个小于等于　

每天教学时间片（小于等于５）段数的随机数代表时　

间片段，再检测该任务所涉及到的所有班级、教师　

等硬约束条件，如果所有对应的数组变量中均无冲　

突，则将任务编号填入班级和教师二维表中，否则重　新产生。当每一个任务的所有时间片都完成这样一　

个过程后，就在每个区域产生了一个无冲突的染色　

体　。最后，由每个小区域中产生的原始染色体组　

成初始种群。然后计算出每个个体的适应度函数　

值，Ｎ＝１。　

（４）选择：在改进的遗传算法中采用最佳个体　

保存法。最佳个体保存法的思想是把群体中适应度　

值最高的个体不进行配对交叉而直接复制到下一代　

中　。　

（５）交叉：采用单点交叉生成新的染色体组成　

的群体并进行冲突检测和消除。　

（６）计算新的群体中各染色体的适应度函数　

值，并与最优染色体进行比较，将最优的染色体保留　

下来，在当前群体和最优群体中选取若干个个适应　

度函数值较高的染色体组成最优群体。　

（７）变异：在排课问题中，变异操作发上在同一　

染色体中的两个基因位（时间片）之间，即我们随机　

选择一个班的一个教学时间片，让它随机变换成另　

一个时间，在变异过程中最好采用擦除重分配策略，　

并要进行冲突检测和消除。　

（８）执行（６）。　

（９）判断Ｎ值与Ｍ值大小，如Ｎ值大于Ｍ，结　

束退出，生成时间任务安排表，否则转（４）。　

教学任务时间安排的改进遗传算法流程如图１所示。

　开始　

利用改进编码方式编码　

利用改进方法产生初始种群　

计算每个染色体适应度值　

使用最佳个体保存策略选择操作　

随机再排列染色体的位置　

两个相邻个体单点交叉　

计算每个个体变异概率。以此概率随机变异　

计算新种群每个染色体适应度值　

数器Ｎ＞迭代　＼一　Ｉ是　否Ｎ＝Ｎ＋１　

图１　教学任务时间安排的遗传算法流程图　

３．２上课教室安排贪婪算法的设计与实现　

场地安排的贪婪算法流程如图２所示。　

算法具体实现如下：　

（１）将上边算法产生的教学任务时间安排表中课　

程要求的教室信息进行编码，为了更加科学、合理的安　排场地，该编码包括最优编码和可替代编码　Ｊ。　

（２）再将全校所有可用教室按照场地属性要求　

进行统一编码。　

（３）将已经编码的时间任务信息按照优先级进　行排序。　

（４）将已经编码的教室按照优先级生成一棵二　

叉树。　

（５）统计需安排场地的时间任务数，标记为Ｎ，　

然后初始化计数器Ｍ。　

（６）取出第一个时间任务的最优编码，与二叉树　

的根节点进行匹配，如匹配成功转（１２），否则转（７）。　

（７）遍历该教室二叉树的左子树，形成节点队列　

进行匹配，如匹配成功转（１２），如不成功则转（８）。　

（８）遍历该教室二叉树的右子树，形成节点队　

列进行匹配，如匹配成功转（８），如不成功则转（９）。　

（９）取出第一个任务的可替代编码，转（６）。　

（１０）如可替代编码都已经遍历完成，仍然无法　

找到相应的匹配节点，则转（１１）。　

（１１）该任务无法安排场地，取出相邻的任务，　

Ｍ＝Ｍ＋１，再转（６）。　

（１２）对节点教室进行安排，然后分解节点。　（１３）如果Ｍ大于Ｎ，退出。　

图２场地安排的贪婪算法流程图　（下转第１２４页）　

ｌ２１—