基于遗传算法排课系统的设计与实现黄海(东南大学计算机科学与工程系,江苏南京210096)【摘要】排课任务是教务管理中是比较烦琐的一项,该系统可以通过使用遗传算法,对课表进行优化。文章就遗传算法排课系统的设计与实现进行了阐述。【关键词】时间表;排课;遗传算法;适应度函数【作者简介】黄海(1971-),男,江苏盐城人,东南大学计算机科学与工程系讲师,研究方向:数据库应用。课程表问题又称时间表问题,是一个多因素的整体优化问题。1975年,S.Even等人论证了课表问题是NP完全类问题。由于课程表问题所涉及的信息较多,并且求解课程表问题最优解的时间复杂性是课程表规模的指数级,所以一般采用求近似最优解的算法。在现实生活中,人们一般也只是要一个满足各种条件的近似最优解,或者说“满意解”,而不一定非要最优解不可。因此,对于课程表问题,关键不是如何找到最优解,而是如何提高解的满意度。遗传算法是John.H.Holland根据生物进化的模型提出的一种优化算法,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则和搜索算法。它从一个种群开始,利用选择、交叉、变异等遗传算子对种群进行不断进化,最后得到全局最优解或近似最优解。根据其算法特点,遗传算法非常适合于排课表问题。一、问题描述考查课表的约束条件,最基本的要求无外乎这样几个:(一)每个班级在同一时间只能上一门课;(二)每个普通教室和实验室在同一时间只能容纳一个班上课,大教室和操场可以容纳其容量允许的班级数上课;(三)每个教师在同一时间只能在一个地点上课。以上约束,称为硬约束,因为不如此,课表是不可行的。还有一些约束如:某个教师希望或不希望在某个时段上课;自习课和体育课最好不排每天的一二节课;同一门课在一周内的分布尽可能均匀等,这些要求称为软约束,因为它们或者可以通过排课以外的方法,如变更其他事务的日程安排等加以解决;或者只能尽可能满足,而不可能全部满足。满足硬约束的课表是合法的,但却不一定是令人满意的。那么如何提高一个课表的满意度呢?可以请各个教师填一张“时段偏好”表,在每个上课时段上标上相应的数值,以确定他希望或不希望在某个时段上课――0表示不希望,1表示无所谓,2表示希望,3表示强烈希望。并且每个教师根据职称,或职务,或所上课程重要性的不同确定优先级:1,2,3级逐级递增,这样一张课表的满意度就很好计算了:每个上课时段所对应的上课老师的“时段偏好”值乘以这个老师的优先级的积的总和。另一个决定课表好坏的度量就是同一门课在一周内的分布尽可能均匀,即课程的分散度。如果该课程一周只上一次,分散度设为1,如果一次以上,则可以将每次间隔的时段数相乘,因为分布越平均,其乘积就越大。将所有课程的分散度相加即总的课表的分散度。定义适应度函数:适应度=满意度+分散度。二、数据库设计本学期课程信息表中记载了每个课程的信息,每个记录称为一个“课元”,包括:课程编号、课程名称、周课时、任课教师、开课班级、教室要求。班级信息表包括:班级编号、班级名称、人数。教师信息表包括:教师编号、姓名、时段偏好、优先级。教室信息表包括:教室编号、教室类型、可容纳学生数、已排。已排字段用来记录该教室已排的时段。在C#中读入这六张表到数据集(dataset)ds1,根据“本学期课程信息表”来填充“排课表”初始值:复制“课程编号”到排课表,并根据周课时确定复制次数,“上课时段”和“教室”均为null。排课表中每条记录称为一个“排课元”。三、遗传算法(一)初始化根据班级信息表以及它与本学期课程信息表的关系,找到每个班的所有课元,再根据这些课元,以及本学期课程表和排课表之间的关系,找到这个班的所有排课元。假设每星期上5天课,每天2节连上,有3个时间段,则每星期有15个上课时间段。那么将这15个时间段随机地分配给上述某个班的所有排课元,也就是排好了一个班的课表。一个班的“排课元”的数目一定是小于或等于15的。如果小于则有时段未排到,即是自习时间。可在“班级信息表”新建一个临时字段“自习”,记录这些自习时间。再来排教室。给每个班安排一个满足人数要求的教室作为固定教室。一般的课程就在固定教室上,如果是语音课则排语音室,如果是体育课则安排操场,如果是实验课则排实验室。排的时候注意比较该教室的“已排”字段,如与已排时段有冲突,则更换时段。对每个班做上述工作,则排好了一张初始课表。这张初始课表肯定有很多“硬冲突”,必须消除。由于排课时已经注意了教室的时段不能冲突,所以只要查看教师的时间有无冲突即可。根据教师信息表与本学期课程信息表的关系,得到每个教师的课元,再根据这些课元,以及本学期课程信息表与排课表的关系得到该教师的所有排课元。检查这些排课元的时段,如有重复,则须调课:首先考虑与自习课调,班级信息表的“自习”字段记录了该班的自习时段。如果这些自习时段都与该老师的上课时间有冲突,则考虑能否用大教室,查看该老师在该时段所上课程的教室要求能否用大教室,如能,统计该老师在该时段的上课班级的总人数,安排一个能容纳这么多学生的大教室。如果大教室方案不能解决问题,则只能和同班的其他老师调换,但注意只能和未检查过冲突的老师换,以免循环调换。(二)建立初始种群计算消除了硬冲突的课表的适应度函数,记录在数组中。将该排课表考贝到新数据集ds2。拷贝过来的这个排课表即一个“染色体”。重复上述过程,直至染色体数目达到种群规模。(三)遗传操作对ds2中的每张表做如下操作:1.选择。采用“随机竞争法”。随机选取两张表,比较它们的适应度,删除适应度小的表,复制适应度大的表替换它。2.变异。设变异概率为Pm,随机产生一个(0,1)范围内的数,如果小于Pm,才进行变异操作。随机选取两天,让这两天的时段互换。这样做的好处是不用纠错。3.交叉。类似地,设交叉概率为Pc,随机产生一个(0,1)范围内的数,如果小于Pc,才进行交叉操作。这里采用“单点交叉”。随机选两张表,再随机选取一个序号,让这两张表中这个序号的记录的“上课时段”值互换。互换后这两张表都要纠错,消除硬冲突。过程仿初始化时的消除冲突过程。只是要注意,如果调换的排课元涉及到大教室,须换回所在班的固定教室。重复该过程,注意每一步操作后都要更新适应度数组,使数组值与表一致。迭代500代后,选取最大适应度的表传回ds1排课表。四、结论以某高职院的实际数据进行上述操作,并记录每一代的最大适应度值。绘成图表如下:基于遗传算法的高职院校排课系统的研究与实践傅亚莉(1.江苏无锡科技职业学院,江苏无锡214028;2.江南大学,江苏无锡214122)摘要:排课问题已经被证明是一个NP完全问题,遗传算法是一种随机搜索算法,非常适合于解决NP问题。本文通过遗传算法解决排课问题,从遗传算法标准设计流程的角度分析了排课问题的基因编码、初始化种群、确定适应度函数、设计各遗传算子等问题,最后形成排课的整体优化算法。关键词:遗传算法;排课系统;基因编码;适应度函数中图分类号:G718.5文献标识码:A文章编号:1008-7508(2010)011-0106-02无锡科技职业学院自2003年建院招生以来,逐年扩大招生规模。学生人数的增加,使得各院系开课的班级越来越多;专业设置的增多,使得开设的课程名目繁多,然而教室资源的稀缺、教师要求的繁琐等情况,使得我院教务部门的排课问题变得越来越复杂。高职院校的排课问题是根据各专业的教学计划,汇总出需开设的课程,在给定教师资源、教室资源前提下,合理安排班级课表满足教学要求的问题。遗传算法是受自然选择和进化机制启发而发展起来的一种随机搜索算法,具有良好的并行性、通用性、稳定性。遗传算法通过选择、交叉、变异等遗传算子的作用对可行解进行分析,使得种群不断进化,从而得到最优解,因此遗传算法是一种非常有效的解决排课问题的方法。一、排课的约束条件排课问题是一个带有约束的多目标组合优化问题。种,有约束的则是指排课过程中有一定约束条件限制。约束条件主要是指冲突,避免冲突是排课问题中要解决的核心问题,只有在所有排课方案全部不发生冲突的基础上,才能保证整个教学计划合理正常进行,使得全校的教学工作能够井然有序。根据排课的工作实际,我院在排课过程中的约束条件主要体现在以下几个方面:(1)相同的教室在同一时间不能上两门不同的课程;(2)相同的教师在同一时间不能在两个教室上课;(3)相同的学生在同一时间不能上两门不同的课程;(4)上课班级的总人数必须小于所安排的教室座位数。另外,为保证充分发挥各资源的优势和提高教学质量,在排课过程中还需考虑一些尽可能优化课表的排课规则:(1)相同班级同一门课程上课时间有间隔;(2)实践类、体育类课程尽量安排在下午;(3)对外聘教师等教师的特殊上课时间要求优先排课;(4)理实一体化课程需考虑四节连排的课程优先排课;(5)公共选修或公共类等涉及面广的课程需优先排课,周学时多的课程优先排课;(6)对于一些指定了教学区、不规则周次的特殊课程需要进行合理安排。遗传算法中根据约束条件和相关规则设定适应度函数,并计算出相应的适应度值,借此检查是否违反约束条件,如果没有违反,则表明是可行解,否则,就是不可行解。二、遗传算法的设计遗传算法(GeneticAlgorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程求解复杂的优化问题。后搜索到问题的最优解。能性。标准遗传算法基本流程如下:〖BG(〗〖BHDWG65mm,WK50mmW〗〖BG)W〗1、基因编码编码就是在遗传算法中把一个问题的可行解从其求解空间转换到能处理的搜索空间的转换方法。编码方法决定了个体的染色体排列形式,也决定了如何进行群体的遗传进化运算。排课过程中主要是将班级、教师、课程、上课时间和教室这5个元素进行安排,形成合理的课表。本院在课表安排过程中,每周上五天课,每天上8节课,课程采用2节连排方式,因此每2小节为1个时间段,每周共计4*5=20个时间段。可以采用实数编码方法对每条染色体编码,结构如下:班级号,教师号,课程号,上课时间,教室号2、初始化种群编码之后的任务是初始种群的设定,并以此为起点一代代进化直到按进化停止准则终止进化过程,得到最后一代群体。排课系统的初始化种群是先由计算机随机生成一定数目的排课方案。对每一个班级而言,是将随机产生的班级-教师-课程-时间-教室编码,从中挑出好的不重复的个体填到数组,这样就产生了一个班级的初始课程表。按班级的多少,产生一定数量的初始表,构成初始种群。3、选择适应函数适应度值确定了群体中每个个体的好坏程度,遗传算法在进化中是以每个个体的适应度值为依据来选取下一代种群的,因此适应度函数设定至关重要,会直接影响到遗传算法的收敛速度和能否找到较优解。根据排课问题的约束条件设置适应函数,可综合考虑排课冲突检查、课程时间间隔、课程理想时段、教师上课要求等约束条件进行设置。如果一个排课方案发生冲突,代表该课表不是可行解,则此时的适应度为0。这样,这个染色体在遗传操作中就会被淘汰掉。同一班级相同课程时间间隔长,则适应度值高,否则适应度值低。专业类课程安排在上午上课,实践类课程安排在下午上课的适应度值高,否则适应度值低。满足教师上课地点、时间要求的则适应度值高,否则适应度值低。因此,适应度函数可考虑设定如下:Fn=Y*(x1*K+x2*S+x3*J)Y为冲突检查结果,检查不冲突则值为1,冲突则值为0。K,S,J分别表示课表优化中课程时间间隔、课程理想时段、教师上课要求、教室的有效利用等期望值。这里x1、x2和x3分别代表各期望值在总期望值中的权重。权重数值可以根据学院实际需求,由排课人员自行设定,其中x1+x2+x3=1。通过适应度函数的计算,如果一个排课方案适应度值较高,则该排课方案相比而言较优,则该染色体会遗传保留下来。4、遗传算子的设计(1)选择选择遗传是用来确定重组或者交叉个体,以及被选个体将产生多少个子代个体。在进行适应度值计算之后,从种群中选择出适应度较高的个体,为染色体的交叉和变异做准备。选择时可采用轮盘赌选择法,将适应度值按比例转化为选中概率,然后模拟轮盘赌操作,随机生成若干个0至1之间的随机数,与之前
本文标题:排课系统
链接地址:https://www.777doc.com/doc-5059697 .html