排课问题的研究与改进

排课问题的研究与改进（共4篇）

排课问题的研究与改进 篇1

0 引言

排课问题称为课程表问题。课程表的关键问题就是直接解决排课中时间和空间资源的冲突问题。近年来,由于高校招生规模不断扩大、课程设置也相对越来越复杂,随之而来就出现了学生数量、开课门数与教学资源严重不足之间的矛盾。尽管各个高校尽量提高教学资源的利用率,但教学资源严重不足的问题还是没有解决。这样,就给高校的排课工作带来很大困难。因而,在合理利用现有教学资源的前提下,设计一个让教师、学生都满意的排课方法就显得十分重要[1]。

1 遗传算法分析

排课过程的实质是教师、教室、班级、课程和时间五个基本元素的最优化过程[2]。既要避免相互冲突,又要合理。目前通常采用的遗传算法是一种通过模拟自然界生物进化过程求解极值的一种优化算法。它是基于自然选择和基因遗传学原理的搜索算法,将“优胜劣态,适者生存”的生物进化原理引入待优化参数形成的编码群体中,按照一定的搜索技术,将种群代表一组问题解,通过对当前种群进行遗传操作,从而产生新一代的种群,并逐步使种群进化到包含近似最优解的状态[3]。但遗传算法在实际求解过程中存在诸如依据适应函数选择的染色体是否为合理染色体、依据交叉和变异所选的染色体是否为合理染色体以及在多个因素中如何选定基因等问题。

2 贪婪算法描述

贪婪算法是一种简化解题复杂度的算法,是一种不追求最优解,只希望得到较为满意解的方法,它采用逐步构造最优解的思想,在问题求解的每一个阶段,都作出一个在一定标准下看上去最优的决策;决策一旦作出,就不可再更改。制定决策的依据称为贪婪准则。也就是说,它总是把整个解题过程分解成一个个细小的步骤,并根据其难易程度确定其处理顺序,做出在当前看来是局部最优的选择,逐步逼近给定的目标,以尽可能快地获得满意的处理结果[4]。

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

在该混合排课算法的设计过程中,由于考虑到排课问题中的诸多因素(教师、班级、时间、课程和教室),因而整个排课过程分两步实现。首先采用改进的遗传算法给每个教学任务分配合理的教学时间片段,然后对生成的包含教师、课程和时间片段的教师教学任务利用贪婪算法分配教室,从而产生最优化的一张课表[5]。

3.1 时间片安排算法的设计与实现

(1)设置控制参数:排课过程中涉及到一系列控制参数,如基因编码、种群的规模、选择率、交叉率、变异率等、迭代次数M,计数器N。

种群规模:在该问题中,初始种群是由班级、教师和时间片组成的二维序列,按照一般教学单位的规模来讲,该种群数量介于50~200之间。

选择率:为了使得适应度值最高的个体得以保留,应确保这样的个体不进行配对交叉而直接复制到下一代中,所以,我们构造一个选择率的计算公式:Qsele=fit(i)/fit。其中fit(i)为某个个体适应度值,fit为种群适应度值总和,i=1,2……种群规模总数。

交叉率:采用单点交叉。

变异率:为了避免传统的遗传算法中因“近亲”繁殖导致的进化停止和收敛于非最优解,提出了一种新的自适应变化的方法,即变异率PM与父串相对距离成反比,随迭代率(迭代次数与最大迭代次数的比值)指数下降自适应变化[6]。

其中,pmax/pmin分别为最大和最小变异率,t/tmax分别为迭代次数和最大迭代次数,RRmax分别为父串间的欧氏距离和最大欧氏距离。

基因编码设计:将教师、班级、课程进行捆绑,组成一个教学任务单元并编号,然后以班级为列,以周教学时间片段为行,组成班级二维表作为染色体。

(2)适应度函数:计算方法为w(i),f(i)为各优化条件,w(i)为各优化条件所占权重。

在该排课问题中,我们所确定的适应度函数必须要考虑以下优化条件:

(1)不同性质的课程时间段安排的科学性、合理性,表示为f(1)。

(2)自然班每天课程安排的均匀性,表示为f(2)。

(3)同一教师每周上课时间安排均匀性,表示为f(3)。

(3)初始化种群:为了保证遗传算法搜索的全局性和稀疏性,首先把每周划分为5个大的均匀的时间片,由此构成一个时间片小区域,然后在每个均匀的时间片区域中使用随机函数产生一个小于等于每天教学时间片(小于等于5)段数的随机数代表时间片段,再检测该任务所涉及到的所有班级、教师等硬约束条件,如果所有对应的数组变量中均无冲突,则将任务编号填入班级和教师二维表中,否则重新产生。当每一个任务的所有时间片都完成这样一个过程后,就在每个区域产生了一个无冲突的染色体[7]。最后,由每个小区域中产生的原始染色体组成初始种群。然后计算出每个个体的适应度函数值,N=1。

(4)选择:在改进的遗传算法中采用最佳个体保存法。最佳个体保存法的思想是把群体中适应度值最高的个体不进行配对交叉而直接复制到下一代中[8]。

(5)交叉:采用单点交叉生成新的染色体组成的群体并进行冲突检测和消除。

(6)计算新的群体中各染色体的适应度函数值,并与最优染色体进行比较,将最优的染色体保留下来,在当前群体和最优群体中选取若干个个适应度函数值较高的染色体组成最优群体。

(7)变异:在排课问题中,变异操作发上在同一染色体中的两个基因位(时间片)之间,即我们随机选择一个班的一个教学时间片,让它随机变换成另一个时间,在变异过程中最好采用擦除重分配策略,并要迸行冲突检测和消除。

(8)执行(6)。

(9)判断N值与M值大小,如N值大于M,结束退出,生成时间任务安排表,否则转(4)。

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

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

场地安排的贪婪算法流程如图2所示。算法具体实现如下:

(1)将上边算法产生的教学任务时间安排表中课程要求的教室信息进行编码,为了更加科学、合理的安排场地,该编码包括最优编码和可替代编码[9]。

(2)再将全校所有可用教室按照场地属性要求进行统一编码。

(3)将已经编码的时间任务信息按照优先级进行排序。

(4)将已经编码的教室按照优先级生成一棵二叉树。

(5)统计需安排场地的时间任务数,标记为N,然后初始化计数器M。

(6)取出第一个时间任务的最优编码,与二叉树的根节点进行匹配,如匹配成功转(12),否则转(7)。

(7)遍历该教室二叉树的左子树,形成节点队列进行匹配,如匹配成功转(12),如不成功则转(8)。

(8)遍历该教室二叉树的右子树,形成节点队列进行匹配,如匹配成功转(8),如不成功则转(9)。

(9)取出第一个任务的可替代编码,转(6)。

(10)如可替代编码都已经遍历完成,仍然无法找到相应的匹配节点,则转(11)。

(11)该任务无法安排场地,取出相邻的任务,M=M+1,再转(6)。

(12)对节点教室进行安排,然后分解节点。

(13)如果M大于N,退出。

4 结束语

该混合算法首先将教师、课程进行捆绑,简化了问题,降低了复杂度;同时,将教学任务的时间片安排与教学场地安排分步进行,避免了单一算法考虑因素太多的问题,也有利于后期的手动调整,从而保证具有最优的或最起码可行的安排方案,不至于完全死锁[10]。

参考文献

[1]赵鲁涛.计算机职能排课系统的研究与实现[D].北京科技大学,2004,3:50-52.

[2]向燕飞.高职院校教务管理系统的设计与实现[D].华南理工大学,2007,11:35-37.

[3]徐艳斌.基于遗传算法的高校排课系统设计与分析[D].广东工业大学,2007,5:38-41.

[4]陈增发.高校教务管理系统研究与实现[D].苏州大学,2008,4:42-44.

[5]王小平,曹立明.遗传算法一理论、应用与软件实现[M].西安交通大出版社,2002:10-20.

[6]唐勇,等.基于遗传算法的排课系统[J].计算机应用,2002,1:93-94,97.

[7]乔树清.改进后的遗传算法在排课系统中的应用研究[J].齐齐哈尔医学院学报,2007,28(16):1984-1986.

[8]唐勇.基于遗传算法的排课系统[J].计算机应用,2002,22(10):38-41.

[9]许郡.基于贪婪算法的排课系统[J].扬州教育学院学报,2009,27(3):32.

[10]黄锟,陈志刚.混合算法在大学课程表问题中的应用研究[J].电脑与信息技术,2008,16(2):25-27.

排课问题的研究与改进 篇2

从50年代末开始,就有人着手研究用计算机来解决课表问题。此后,人们对课表问题的数学模型、 课表问题的解及解的存在性等问题进行了深入的探讨,但一直未能得到满意的结果。直到1975年课表问题被证明是NP - 完全类[1]以后,人们才将注意力更多地转向课表编排实用算法的探索与研究。

通过图论方法来研究解决排课问题是一个比较典型的方法,有依据最大匹配对图的顶点着色的[2 - 3],也有基于偶图边着色的研究[4],但大多数情况下对排课的数学抽象都过于简单,同时也陆续出现了很多利用人工智能如遗传算法[5]、专家系统[6]、模拟退火算法[7]等方法对排课问题在理论上做近似优化讨论,往往缺乏实用性。

在此基础上,将结合图论中顶点着色理论和遗传算法,利用两者的优点,旨在寻求实用性和有效性较好的排课方法。本文首先给出了基于图论的排课模型,并对一般顶点着色模型进行了扩展,接着详细介绍了遗传算法在此排课模型上的应用,最后给出了实验结果。

1基于图论的排课模型

1. 1基于顶点着色的一般排课模型

基于图着色的排课是将其安排结果用图模型来标示,实用的图模型由二元式组成,其中,顶点集表示课程班,而边集表示连接的两个课程班之间存在冲突,如图1所示。

1. 1. 1课程班的表示

定义1课程班约定为一个四元组的集合:( CRi,TCj,STk,WAn) ,其中,CRi表示课程,TCj表示教师,STk表示学生,WAn表示课程的周安排。并用CTSWm表示课程班m。

通过定义,可将课程班的关联用一个三分图来表示,类似文献[8]中给出,如图2所示。

依关联图可知,每个课程顶点及其所连接的边可以唯一标示课程班,对于课程顶点主要有以下三种情况:

( 1) 该课程只有一位教师任教,如CR2和CR3所示。

( 2) 该课程由多位老师任教,授课学生一致,如CR4所示。

( 3) 该课程由多位老师任教,授课学生不一致, 如CR1所示。如图2课程顶点集中虚线标示的CR1,此时两个顶点虽为同一课程号,但加上与边的组合,两者属于不同的课程班。

课程与教师的边集CR - TC中,赋予权值WAij, 表示课程CRi与教师TCj的周安排情况,用12位二进制数来表示,高2位表示周次数,次5位和第5位分别表示开始周次和结束周次。周次数的有效值为01和10,一学期通常是为20周,故开始周次和结束周次的有效值范围为00001到10100。

综上,结合定义与课程班关联图,可以有效的表示任一课程班的课程、教师、学生以及周安排信息。

1. 1. 2排课模型中边的确立

定义2如果两个课程班的上课周安排彼此之间有交集,则称它们“周安排相容”。

通过图1所示一般模型可知,图中各边表示的是该边连接的两顶点之间存在冲突,通过表示冲突, 即可确立图中的边集,主要由以下两种冲突确定:

( 1) 学生冲突,如果任意两个课程班对应的学生有重复,并且“周安排相容”,那么这两个课程班之间存在冲突。

( 2) 教师冲突,如果任意教师对应课程班的数量超过1,并且这些课程班是“周安排相容”的,那么这些课程班之间存在冲突。

1. 1. 3顶点颜色表示

目前排课的图着色问题中,一般选择时间段为颜色进行着色,由于排课的目的就是为了安排教室和时间,将采用“教室+ 时间”的组合为颜色,相对以时间段为顶点颜色,本文方法不需要安排教室后再安排时间,一次就可以同时完成教室和时间的安排,大大减少了操作次数。

1. 2引入动态边,扩展模型

当一个课程班的授课周次数为2时,则需要分配两种颜色,此时,可将该课程班顶点一分为二,形成两个内部顶点,但对其他课程班而言,仍然将其看成一个顶点。

定义3若课程班CTSWm的两个内部顶点CTSWm - 1和CTSWm - 2着色后发生时间安排冲突,则用一条边连接该两个顶点,称该边为“动态边”。

为方便处理动态边,即课程班内部冲突,可将课程班内部两顶点着色冲突定义以下判定规则和类型:

( 1) 冲突类型1: 内部顶点颜色被安排在同一天的同一时间段。

( 2) 冲突类型2: 内部顶点颜色被安排在同一天的不同时间段。

( 3) 冲突类型3: 内部顶点颜色被安排在相邻的两天的时间段。

引入动态边后,可将模型扩展成如图3所示形式( 包含上述三种情况) 。

2遗传算法的应用

2. 1染色体编码表示

以课程班为染色体,基因串由课程班编号及颜色编号组成,即为“课程班+ 教室+ 时间段”,算法中,采用120门课程,950名学生作为实验数据,故课程班编号需要7位二进制位编码,设定颜色为18位,故基因串共有25位,采用二进制编码,具体如图4所示。

需要注意的是,染色体和课程班具有一一对应的关系,课程班编号是其唯一标识。

2. 2适应度函数设计

适应度函数的设计思想是对每条染色体中存在的冲突类型进行加权求和,其中权值Wi代表的是第i个冲突的重要程度,Pi则标示冲突是否发生,如果产生冲突,则置为1,否则为0。

其中,受到的惩罚值为Wi* Pi,适应度函数是对染色体中存在的冲突进行加权求和并加上1后, 再求其倒数:

各种冲突描述及其相应的判定规则如下所示:

( 1) 冲突1: 教室冲突,权值W1= 25。判断同一个教室在同一个时间段是否被安排了两次以上的课程。

( 2) 冲突2: 课程班冲突,权值W2= 25。判断有边相邻的课程顶点是否被安排在了同一时间段上课。

( 3) 冲突3: 特殊需求冲突,权值为W3= 20。对有特殊需求的课程,判断其所安排的教室或时间是否满足给定的需求。

( 4) 冲突4: 课程班同一天同一时间段冲突,权值为W4= 15。判断同一课程班的两次授课时间是否安排在同一天的同一时间段。

( 5) 冲突5: 课程班同一天不同时间段冲突,权值为W5= 15。判断同一课程班的两次授课时间是否安排在同一天的不同时间段。

( 6) 冲突6: 课程班相邻两天冲突,权值为W6= 10。判断同一课程班的两次授课时间是否安排在相邻的两天。

其中,冲突4到6为动态边中的冲突。

2. 3遗传算法的着色实现

2. 3. 1初始化

在初始化着色的时候,分配颜色采用SFS( Spe- cial Fit Strategy) 和FFS( First Fit Strategy) 策略相结合的方式来处理。

定义4 SFS策略,即特殊适应策略,在分配颜色时,如果一些课程班有特定的教室或时间安排需求,则分配其对应的颜色。

通过SFS策略,可满足一些课程班的特殊要求, 使排课更合理的同时减少了排课过程中的复杂性。

定义5 FFS策略,即最先适应策略,从以下两个方面考虑:

( 1) 对课程班分配颜色时,每次总是给上课人数最多的课程班先着色。

( 2) 对课程班分配颜色时,每次对其分配教室总是从小到大查找一定范围的教室,在满足尽量少的教室冲突情况下,找出超过课程班人数的一个下界,即分配最适合课程班人数和冲突的教室作为其对应的教室颜色。

通过FFS策略,可以最大限度的利用教室的资源,不会造成大教室上小班的情况,避免了资源的浪费。

2. 3. 2遗传操作

在进行具体的遗传操作之前,先给出以下两个定义:

定义6在图G = { V,E} 中,若Vi对应染色体的颜色基因是通过SFS分配的,则Vi归入一个集合中,定义这样的集合为“固定集”。

定义7在图G = { V,E} 中,若Vi和Vj对应染色体颜色中的教室基因相同或属于同一类型( 容纳人数相同) ,就将Vi和Vj归为同一个集合中,这样形成的不同集合,定义为“团集”。

交叉( 交叉概率PC = 0. 65)

交叉操作针对同一团集的不同染色体,对每个团集,随机选择两条染色体,按照PC进行交叉操作,交叉采用单点交叉,即交换两者的颜色基因。

变异( 变异概率PM = 0. 2)

仍然以团集为单位,选择一条染色体,搜索其图中相邻课程班结点,若存在冲突,则对该染色体进行变异,只针对颜色的时间基因进行变异。

2. 3. 3算法流程

( 1) 初始化种群,利用初始化策略SFS和FFS对各染色体分配颜色,转步骤( 2) 。

(2)交叉操作。

1选择一团集。

2从该团集中选择未被标记交叉的染色体CT- CRi,再任意选择染色体CTCRj,以概率PC对其进行交叉操作,并标记CTCRi和CTCRj。

3判断该团集中所有染色体是否全部被标记, 若是,则转步骤4,否则转步骤2。

4判断是否所有团集均已进行交叉操作,若是, 则转步骤( 3) ,否则,转步骤1,对下一团集重复步骤( 2) 中的所有流程。

(3)变异操作。

1选择一团集。

2从该团集中选择存在冲突的染色体CTCRi, 以概率PM对其进行变异操作。

3判断该团集所有存在冲突的染色体是否均已进行变异操作,若是,转步骤4,否则,则转步骤2。

4判断是否所有团集均已进行变异操作,若是, 则转步骤( 4) ,否则,转步骤1,对下一团集重复步骤( 3) 中的所有流程。

( 4) 计算当代各染色体的适应值,从而得出平均适应值,判断其是否达到目标值,若达到,转步骤( 6) ; 否则,转步骤( 5) 。

( 5) 判断遗传代数是否达到设定的上限,若达到,转步骤( 6) ,否则,转步骤( 2) ,继续下一代的遗传操作。

( 6) 终止算法。

3实验结果与分析

实验中,对传统方法( 标准遗传算法) 和本文方法进行了对比,其中测试数据集为本校实际教学数据,实验参数有: 种群数量120,交叉概率PC为0. 65,变异概率PM为0. 2,最大遗传代数为40,目标平均适应值为0. 9。

3. 1初始化结果比较

采用衡量的参数有: 教室利用率、平均适应值和冲突次数,如表1所示。

备注:表1中AV表示平均适应值,RU表示教室利用率,CN表示冲突次数。

由表1数据可知,相较于传统方法,本文方法通过SFS和FFS策略,初始化结果中的平均适应值、 教室利用率以及冲突次数均具有显著的优势。

3. 2遗传操作结果比较

采用衡量的参数有: 每代的平均适应值和冲突次数。

( 1) 种群1: 初始适应值为0. 858856740,冲突次数为16。

( 2) 种群2: 初始适应值为0. 832392379,冲突次数为19。

由图5和图6可知,相较于传统方法( 标准遗传算法) ,本文方法中种群1和种群2分别在遗传迭代次数为11和10已达到目标适应值,从而提前终止算法,并且平均适应值和冲突次数均有明显改进。

4结束语

从以上比较结果可知,本文提出的算法思想相较传统方法,有显著的优势,无论是初始化还是遗传操作,均获得良好的效果。

另外,本文课程班中的授课对象,直接采用学生,适合研究生或选修课等人数较小的情况,相对本科生等大规模排课,可以将班级作为直接授课对象, 针对此类情况,本算法同样适用。

摘要：排课问题是典型的NP问题,文中以顶点着色为基础,通过引入动态边,扩展了现有的排课问题图模型。初始化中采用了特殊适应和最先适应策略,同时定义了团集的概念,将其作为交叉变异算子的操作对象。通过实验结果分析,针对平均适应值、教室利用率以及冲突次数等评价指标,文中提出的初始化和遗传操作方法均能取得较好的结果。

国土窗口存在的问题与改进 篇3

尊敬的各位领导、同事大家晚上好！

针对7月11日省行风检查中出现的问题及原因，从而反应出我们在日常工作中还存在很多的不足与缺点，有待我们及时改进与提高。现就问题我个人发表以下看法。

在行政服务中心的正确领导下，国土窗口全体工作人员以自己的辛勤工作使得窗口工作渐趋规范，社会成效初显，但我们通过这次事件也深知，我们的工作离中心和局党组对我们的要求还有很大的距离，还存在着一些问题有待改进：

1.学习主动性还有所欠缺、业务能力有待进一步提高；

2.工作繁忙时，对人态度热情不够，微笑服务不够到位；

3.受理件的审批工作流程还不是十分顺畅，有待完善；

4.与中心、局里各科室职能部门地沟通协调不够到位，尚待加强。以上存在的问题，须从以下方面加以改进：

首先：加强各规章制度及业务知识的学习，遇到不理解不明白的地方要及时互相讨论及请教，从而达到加深影响、深入理解。熟悉窗口的日常审批业务，做到能够独立承担工作，抓紧学习相关业务的法律法规及标准。努力提高办事效率，提高群众满意度为首要前提；

其次：强化效能，优质服务。日常工作中，我们要注重热情服务、礼貌待客，急群众之所急，接受群众及各职能部门的监督检查，力争使窗口的整体办事效率得到最大的提高，同时实行首问负责制、一次性告知，积极探索强化窗口管理的新做法，结合实际，对行政许可工作制定完善、科学的工作考核办法，健全工作激励机制。

再次：加强各部分之间的联系，沟通，为更好的提高办事效率，缩短办事时限，提高办事群众的满意度；

最后：我希望领导可以随时指出我们的不足与缺点，我们也会通过这次的自我总结中，为今后工作的方向指明方向，努力做好各自的工作。

排课问题的研究与改进 篇4

排课一直是学校进行教育的首要考虑的一个问题,排课的结果也是影响教学结果的一个重要因素。排课需要考虑班级、教师、教室、课程等诸多因素。由于各个学校环境不同,因此采用的排课方式也不完全相同。传统的手工方式由于工作量庞大、效率低下、排课效果不能满足实际需求,已经逐渐放弃使用。

利用计算机排课是人们一直关注的一个领域,但由于排课系统的复杂性,排课问题一直没有获得最佳的解决方案。考虑到排课系统实际上就是利用现有的资源,合理的组合班级、师生、教室、课程等问题,本文利用优化思想将该问题转化为带有约束的组合优化问题,使得班级、师生、教室、课程等需要考虑的因素组合成满足一定条件的最佳优化组合,从而使排课结果满足实际的教学实践工作。

目前国内外一些学者利用遗传算法求解排课问题。Chu PC和Beasley利用遗传算法的全局搜索能力对排课问题进行了求解。张春梅等人对大学课程进行分类,然后使用遗传算法进行求解。这些求解方案能快速有效的解决排课问题,但遗传算法本身容易陷入局部最优,进而不能获得最佳结果。本文采用分布估计算法(Estimation of distribution algorithms,EDAs)求解该问题。

分布估计算法结合了统计学理论与随机优化算法的特点,建立了一种基于概率模型和采样进化模式。在宏观层面上建立一个描述解分布情况的概率模型,然后通过随机采样产生新的种群。本文利用分布估计算法进行排课方案设计,将排课过程转化为优化过程。利用概率分布获取概率上的最优排课方案。

2 算法设计

使用分布估计算法求解排课方案,首先要对设计到的各个对象进行编码。

2.1 编码。

在排课之前需要设计教室、教师、班级、课程的代码以及相关属性。教室:教室代码、教室容量;教师:教师代码、姓名、部门;班级:班级代码、院系、专业、班级人数;课程:课程代码、课时、课程名称;选课:班级代码、课程代码、教师代码。

2.2 课表安排的解空间设计。

对于高校课表而言,实际上就是合理的安排上课时间、上课教室以及上课班级和老师。对此需要构造一个解空间,以便使用分布估计算法实现该问题的求解。这里我们假设某高校每周上课从周一到周五,上午俩大节课,下午俩大节课,晚上一节课。针对每个教室每天可以安排五次课,每周五天课,如下图。从这个表格中可以发现这是一个5×5的二维向量,每个单元格可以安排一次课程,课程按照课程代码+教师代码+班级代码设计,比如C011T50223B121,其中前四位“C011”为课程代码,“T50223”为教师代码,后四位B121为班级代码。如果某次课没有安排课程则默认为“00000000000000”。

然后按照行顺序如下图把该班级的一周的课程安排组合成一个一维向量。当然其中每次课都是由上述的五个字串组成,因此这个一维向量其实是包含25个字串,其中每个字串能确定在这个教室某次课的教师、班级、以及所上的课程。

假设Á共有100个教室,每个教室按照上述设计方案设计,然后再按照顺序把每个教室的课程安排字串组合成一个一维向量。

2.3 适应度函数设计。

分布估计算法在进化中需要根据一个适应度函数来衡量一个设计方案的优劣。算法根据适应度函数值才能找到最佳方案。本文设计的适应度函数主要考虑俩个方面。一个方面是排课过程中的硬约束,另一个是排课过程中的软约束。

硬件约束:

(1)在同一节课,一间教室只能安排一门课程;(2)在同一节课,一个教师或一个班级只能安排一门课程;(3)一个教室必须要有足够多的座位来容纳这堂课的所有的学生;

软约束条件:

(1)尽量不让教师连续上课;(2)对于同一门课同一教师尽量少换上课地点;(3)对于某门课程在一周中应尽量分散分布,这样教师有充足的时间备课和批改作业,学生也有时间做作业和复习消化;(4)单个教师的所有课程在一周中应分散分布,避免单个教师的课排满一整天;(5)学生的上课时间在周一至周五尽量均匀分布,应避免一天课程很满而另一天却一整天没课的情况。根据以上约束设计适应度函数,由于硬件约束是正常上课必须满足的条件,所以在更新设计方案的时候首先应该检查新的个体方案是否满足硬件约束,不满足则重新获取。对于软件约束采用如下函数进行约束。如果发现某个教师连续2次上课则g1(x)=g1(x)+1,如果是发现连续3次上课则g1(x)=g1(x)+2,以此类推。同样如果发现设计方案中某教师教授的某一门课连续俩次在不同教室上课则g2(x)=g2(x)+1,如果是发现连续3次在不同的教室上课则g2(x)=g2(x)+2,以此类推。对于所有课程检查每个班级的上课时间是否分散,如果发现有连续上课的则按以上的方式进行操作g3(x)=g3(x)+n,其中n=1,2,3……。同样按照这个原则可以获得g4(x)=g4(x)+n,g5(x)=g5(x)+n。在获得以上数据之后,按照如下适应度函数来评估设计方案。

其中λ取0到1之间的数,用来控制软约束条件的重要性。

2.4 算法步骤。

使用分布估计算法解决排课问题,能够找到概率上的最优解,但是首先需要生成一个种群,然后才能利用该算法进行优化,找到满足各种约束的最佳方案。初始化种群的时候,本文只考虑满足硬件约束,暂时不考虑软件约束。初始化具体算法如下:(1)首先顺序从选课表选择数据填充课表。(2)随机选择数据填充其余的每一次课,然后和其他表格比较判断是否满足硬件约束,不满足则重新选择,同时对比前面选取的课程检查是否该课程学时已经满足。(3)如果选取数据无法完成初始化,那么返回(1)重新初始化种群。算法步骤:第一步、使用已经设计好的教师、班级、课程对象生成每次课程的代码,如上述的字串“C011T50223B121”。第二步、使用均匀分布模型计算每次课程组合使用某个教室的某次课的概率。假设这里选课项共有100项,那么每次课程的概率为0.01。第三步、按照概率模型随机生成20个可行解。第四步、计算每个可行解适应度函数值。第五步、选取一部分适应度函数值较好的个体,利用概率模型重新计算各个字串的概率。第六步、使用新的概率重新生成20个字串。第七步、返回第四步,直到满足条件输出最后结果。

3 结论

本文提出应用分布估计算法研究排课系统的编码模式,以及通过调整参数实现最佳方案的进化方式。该排课方案可以在合理的范围内取得良好的结果,并且利用该思想可以容易的添加其他约束条件,具有较高的扩展性。以某校实验课安排测试系统,发现该系统能较满意的实现排课。

摘要：排课问题是一个NP完全问题,没有绝对的最优方案。本文首先对课表进行编码,然后设计了合适的适应度函数,利用概率模型逐步进化。采用分布估计算法实现高校排课,将排课过程变成一个组合优化过程,从而取得最佳方案。

关键词：分布估计算法,高校排课,组合优化

参考文献