基于遗传算法的排课算法

基于遗传算法的排课算法蒲保兴(邵阳学院信息与电气工程系,湖南　邵阳　422001)摘　要:　本文把排课问题转化为一个组合优化问题,在此基础上以罚函数的方法建立数学模型,并给出了基于遗传算法的解法,提出“动态罚值权定标方法”和“分块遗传策略”.关键词:　排课算法;遗传算法;分块遗传策略;培养型变异;动态罚值权定标中图分类号:G 642 文献标识码:A 文章编号:100528036(2006)0120083205收稿日期:2005206201作者简介:蒲保兴(1965-),男(瑶族),邵阳学院信息与电气工程系,副教授、硕士,主要从事人工智能研究. 优化排课问题就是在给定教师资源、教室资源和开课计划的前提下,如何合理地安排课表问题.其实质是含约束条件的目标函数优化问题,运筹学中论及了一些特殊的优化问题求解方法,如线性规划的单纯形法等[1].在对排课问题建立数学模型后,发现它难以用传统的启发式算法求解,而且其约束条件和目标函数难以用解析式表示出来,因此,必须寻求其他的算法.遗传算法[2～5]作为一种有效的全局搜索方法,从产生至今不断扩展了其应用领域,由于它的鲁棒性,适用范围广,有组织性、自适应和学习性、并行性、不需要求导和其他辅助知识等特点,在求最优化问题时,甚至只需给出目标函数的计算规则而不必给出目标函数的解析式等优点,备受人们喜爱,遗传算法为排课问题的求解提供了有效的途径.1　数学模型的建立在实际排课过程中,以某一等长的时间段为课表的时间安排单位,称之为时间单元.一个可行的课表安排应满足以下约束条件:课表以一个星期为一周期,一个星期的课表就是一个学期的课表;课表应满足班级、教师、教室上课不冲突;教室的座位应该满足上课班级学生的需要;其他一些特殊要求.在满足以上约束的前提下,应尽量使课程安排合理,符合教学规律,这叫做优化目标.优化目标包括以下几个方面:同一班级的同一门课程在时间安排上应尽量均衡;同一教师担任的所有的课程在时间上应安排均衡;同一班的同一门课程或同一教师担任的所有课程在节次上应错开,即不能均是相同的节次,例如,某一门课程每周开3次,这三次中最好有1—2节、3—4节、5—6节,不能都是1—2节或3—4节;若教室有空余的时间单元可以不排课,则这些空余时间单元应放在较差的时间段内,比如说下午.以上的约束条件和优化目标可能会互相矛盾,在教师、教室资源比较紧张的情况下,有可能会发生顾此失彼的现象,这里应当说明的是,对于约束条件和优化目标是难以用解析式描述的.设教室有n 1间,一个星期内有n 2天为上课时间,每间教室在每一天能排课的时间单元数为n 3,则一周内所有的教室可以排课的时间单元数为n 1×n 2×n 3,不妨把这些可供安排的时间单元记为T 1,T 2,Λ,T n ,我们把它称之为教室时间单元,其中n =n 1×n 2×n 3.为了方便操作,可以把属于同一间教室的时间单元放在一起,同时记下每一间教室在每一天的时间单元所对应的序号.2006年2月第15卷　第1期中央民族大学学报(自然科学版)Journal of the CUN (Natural Sciences Edition )Feb.2006V ol.15　N o.1根据教学计划,可以得出每一个班级、每一门课程在每周内应安排课的次数,我们把每一次课称之为课程时间单元,它要占用一个教室时间单元,综合各个班的每门课程每周内应安排课的次数,便可以得出一周内所有的班级、所有课程所需要的课程时间单元,不妨记为C1,C2,Λ,C m,同时记下每一课程时间单元对应的班级名称、课程名称和任课教师.那么,排课问题就是如何把课程时间单元C1,C2,Λ, C m指派到教室时间单元T1,T2,Λ,T n中去的一个指派问题.一般来说,有m≤n,当m<n时,可以添加n-m个虚拟课程时间单元后,凑成n个课程时间单元,其中虚拟课程时间单元并没有对应实际的课程,这样就变成了n个课程时间单元指派到n个教室时间单元的一个非平衡指派问题.进一步分析,让C1,C2,Λ,C n和T1,T2,Λ,T n的次序固定,那么一次具体的指派就是把每一课程时间单元Ci 指派给某一个教室时间单元,不妨记为Tli,从而一次具体的指派与n个自然数的全排列l1,l2,Λ,l n对应,反之亦然,即n个自然数的一个全排列l1,l2,Λ,l n对应一个具体的排课指派,其中:l i∈{1,2,Λ,n},且当i≠j时有l i≠l j 从以上分析可以看出,问题的实质是一个组合优化问题,为了便于操作,把约束条件以罚函数的方式计入目标函数,若某一课程、某一班级或某一教师的排课不满足约束条件,则给目标函数加上一个单位的罚值,若有多处不满足,则进行罚值累加.优化目标同样也以罚函数的方式计入目标函数,当某一排课在某一处不满足优化目标,则给予相应的罚值,若多处不满足,进行罚值累加.从而目标函数值是约束罚值与优化罚值的带权和.其最小值为0,对应为最为理想的排课方式.从此可以看出排课问题是一个求最小值问题.其数学模型为:min F(l1,l2,Λ,l n)l i∈{1,2,Λ,n}　i=1,2,Λ,n(1)st　l i≠l j　当i≠j时(2) 2　基于遗传算法的优化排课问题的求解2.1　基于动态罚值权定标的目标函数的计算方法约束条件和优化目标有轻重缓急之分,约束条件是必须满足的,优先级别最高,而各种优化目标也有优先级之分,应尽量满足级别高的优化目标.由于它们都转化为罚值,则其罚值权是不同的,高一级的罚值权比所有低级的罚值和还要大.从此可以看出,采用静态定标罚值权的方法是不可取的,我们采用动态罚值权的定标方法.遗传进化在进行选择操作中,我们着眼于目标函数或适应度函数的相对值而不关心其绝对值,确定个体的目标函数的真正目的是在于确定个体在群体中的优劣,因此我们根据整个群体情况来统一定标罚值权,我们把各级的罚值用一个向量来表示,而目标函数便是各级罚值的带权和.设有k级罚值,其优先级是从大到小严格按顺序排列的,其中第一级罚值对应的是约束罚值,其余各级罚值是根据优先级排列的各级优化罚值,每一级罚值应有一个罚值权,一次具体的排课对应于不同级别的罚值分别为(p1,p2,Λ,p k),它构成了一个k维向量,那么目标函数便是各分量的带权和,不妨记为:F=‖(p1,p2,Λ,p k)‖ 现在来说明目标函数计算方法,设群体规模为M,每一个体对应一种排课方式,第i种排课方式对应的罚值向量为(pi1,p i2,Λ,p ik),则它对应的目标函数值记为F i=‖(p i1,p i2,Λ,p ik)‖.第1步　定所有个体的目标函数的初始值为0,即0→Fi(i=1,2,Λ,M),k→t;第2步　取Gt=1,即优先级最低的罚值权为1;第3步　分别计算Fi =F i+G t×p it,其中i=1,2,Λ,M;48中央民族大学学报(自然科学版)第15卷　第4步　t -1→t ,若t =0,结束;否则,取G t =max (F 1,F 2,Λ,F M ),转第2步;以上求出(G 1,G 2,Λ,G k )便是各级的罚值权,同时计算出了每一个体的目标函数.2.2　编码策略与适应度函数标准的遗传算法采用二进制编码[6～7],但是,排课问题若采用二进制编码则不太直观,且交叉和变异较难操作,因此,就取这n 个自然数的全排列作为染色体编码:l 1l 2Λl n 这样交叉和变异操作就变得容易一些,且解码操作也非常容易.采用上述所述动态目标函数的计算方法,从计算过程可以看出,函数值越小,说明其罚值越小,其排课的质量越高,因此,原问题是求目标函数的最小化问题.适应度函数应反映目标函数的相对大小,另外,对于较差的个体应减小其选择压力[4].因此适应度函数为:f i =(1+c )×(max (F 1,F 2,Λ,F M )-min (F 1,F 2,Λ,F M ))-(F i -min (F 1,F 2,Λ,F M ))其中c 为一非负数,它的变化可以引起选择压力的变化.2.3　交叉算子和变异算子采用单点、对称、大片断基因保留、小片断基因保序的交叉办法[8],即对于父个体1和父个体2,随机地选择一个交叉点,同时确定该交叉点的对称点,父个体1的基因被交叉点分成了两部分,同时父个体2的基因被对称交叉点分成了两部分,在父个体1中选取较长的一部分基因直接遗传给子个体1,父体1中较短的那一部分基因接在父个体2中的顺序重新排列后组成子个体1的另一部分基因.同理,把父个体2的较长的一部分基因直接遗传给子个体2,把父个体2中较短的那一部分基因接在父个体1中的排列顺序重新排列组成子个体2的另一部分基因.例如,有以下两个父个体:父个体1:347651289,父个体2:134562987产生一个[1,8]之间的随机整数作为交叉点位置,比如交叉点位置为6,则对称交叉点的位置为3,那么交叉点和对称交叉点把两个父个体的基因分成了两部分父个体1:347651|289,父个体2:134|562987把父个体1中较长的一部分基因(347651)直接遗传给子个体1,父个体1中较短的那一部分基因(289)在父个体2中的顺序为(298),于是得出子个体1,同理可以得到子个体2.子个体1:347651|298,子个体2:341|562987从以上可以看出,新的个体保留两个父个体的共同特性,它继承了其中一个父个体中较长的基因片断和另一父个体中较短的基因顺序.尽量保证父个体中的优良模式遗传到下一代.此外,这种交叉方式能保证经交叉后的子个体仍然在所讨论的遗传空间中.采用随机交换基因变异法,其操作如下,对每一个体,其各位基因变异的顺序是从第一位基因开始,从左至右逐位变异.对每一位基因,在变异概率的作用下,进行操作,产生一个[0,1]之间的随机数r ,若r >p m (其中p m 为变异概率),则该位不发生变异,否则,该位发生变异.当某一位发生变异时,首先,产生一个[1,n ]之间的随机整数p ,然后使该位处与第p 位处的基因进交换.例如对于个体234578916,假设对第4位(该位的基因为5)进行变异,产生一个1至9之间的随机整数,不妨为7,则对该位的变异就是把该位的基因与第7位的基因进行交换,经变异后的个体为:234978516.显然,经变异后的个体仍然在所讨论的遗传空间中.此外,根据人类进化的规律,变异应该是往更好的方向发展,子个体虽然继承了父个体的特性,同时应有别于父个体,增加新的、更好的特性,在变异过程中,一方面是随机的,另一方面应有向适应高方向发展的趋势,因此,我们提出了“培养型变异”策略,其基本思想是:当个体被变异后产生了新的个体,比较新个体的适应度与父个体的适应度,若新个体比父个体的适应度高,则把新个体替换原有个体,否则,再进行一次变异,而第二次变异对适应度不作检查,直接替换原有个体.改进后的变异策略,一方面保持了变异的随机性,另一方面含有向适应度高的方向发展的趋势[9].58　第1期蒲保兴:基于遗传算法的排课算法3　分块遗传策略和算例就实际排课的情况来看,作为指派的对象教室和被指派的对象班级往往存在着分块对应的关系[10～11],即按系或学院分配教室的情况居多,有时甚至所有班级的教室固定.这样,教室被分成了若干块,而班级也分成了相应的若干块,每个班的课程只能安排在相应的教室块内,且可共享该块内的所有教室.各块之间的排课既有一定的独立性,又有一定的联系,因为教师资源是共享的,同一教师可以在两个以上的班级块内任课.针对这种情况,我们提出了“分块遗传策略”.分块遗传策略的基本思想是:根据教室分块情况和班级分块情况,把教室时间单元分成若干块,同样把课程时间单元也相应地分成与教室单元块数量一致的若干块,调整各块之间的排列顺序,使教室时间单元块与课程时间单元块一一对应.在进行排课指派时,应满足这一基本原则:每一课程时间块中任一单元可以被指派到相应教室时间块中的任一单元,但不能被指派到别的块中.因此,为了满足这一原则,在交叉和变异过程中,只要限制交叉和变异操作在块内进行即可.问题的实质便是“交叉、变异块内进行,适应度计算综合考虑”.具体操作如下:设可以指派的教室时间单元和被指派的课程时间单元分别被分成了相应的p块,同时对每个课程时间单元块添加若干虚拟课程时间单元,凑成单元数目与相应教室块的单元数目一致.教室时间单元和课程时间单元如下:T11T12ΛT1k1T21T22ΛT2k2ΛTp1T p2ΛT pkp,C11C12ΛC1k1C21C22ΛC2k2ΛCp1C p2ΛC pkp 每一块内的排课方式与一个自然数的全排列对应,这样一个自然数的全排列组成了染色体一个基因段,整个染色体编码由若干块基因段连接而成.块内排课的可按上述介绍的方法进行,所有的块并行地进行块内交叉和变异操作,而目标函数的计算则综合考虑,不仅考虑了块内排课的约束和优化,还需考虑块间排课方式由于教师资源的共享而不至于冲突.适应度的计算与精英保留策略是针对整染色体来考虑的,这便构成了分块遗传策略,它屏蔽了大量的“不可行解”,使得遗传空间缩小,从而提高了算法的运行效率.根据上述算法原理,我们给出了一个仿真系统,采用该仿真系统对下述数据进行了计算,得到了较为满意的结果.现有可供排课的教室2间,属于同一块,每一周有5天上课时间,每天3个时间单元,对一个星期的教室时间单元进行展开,得到了30个教室时间单元,设它们的编号分别为1,2,Λ,30,同时记下每个教室时间单元对应的教室编号、所在块号,以及工作日号和节次号.并假设有3个班参与排课,教学计划如表1.表1　排课计划T ab.1　Plan of school timetable arrangement班级编号班级名称课程名称教师编号教师姓名每周次数块号1中文系一班中国革命史1陶老师311中文系一班高等数学2王老师211中文系一班普通物理3刘老师311中文系一班公共外语4孙老师212数学系二班中国革命史1陶老师212数学系二班高等数学2王老师312数学系二班体育5李老师212数学系二班哲学6曾老师313物理系一班普通物理3刘老师213物理系一班公共外语4孙老师213物理系一班体育5李老师313物理系一班哲学6曾老师21 68中央民族大学学报(自然科学版)第15卷　以上共有16门课,在一个块内安排,与教室分块对应,每周共有29个课程时间单元,添加1个虚拟的课程时间单元,凑成30个课程时间单元,记它们编号分别为1,2,Λ,30,并记下它们对应的班级编号和任课教师编号,从而染色体的串长为30,群体规模取70,交叉概率为0.04653,变异概率为0.021,采用上述算法进行计算,两分钟后,得到最优个体为:10,5,30,26,4,2,13,9,29,6,11,1,19,14,3,22,8,1,28,24,20,15,7,18,23,21,25,17,12,16.它对应的各级约束罚值分别为:第一级　可行性约束罚值为0,说明满足可行性约束,课表不会发生冲突;第二级　同一班同一门课程不能安排在同一天,其罚值为0;第三级　虚拟时间单元尽量安排在较差的时间段,其罚值为0;第四级　课程安排在时间上均衡以及同一门课程在节次上错开,其罚值为8.上述最优个体的意义是第一个课程时间单元被安排在第10个教室时间单元(第一间教室的星期四1-2节课),第二个课程时间单元被安排在第5个教室时间单元(第一间教室的星期二3-4节课),依此类推,便可以得出完整的课表.从以上分析论证可以看出,该算法是切实可行的,采用该算法完全可以开发出一个较为满意的排课系统,它不仅适用于大专院校教室共享、分块共享的情形,同时也适合中小学教室独占、即每个班的教室独占的情况.该算法在运行时间上可能稍长了一点,但并不妨碍算法的使用,如能采用一些启发式方法改善运行时间,则算法的效果将更加好.参考文献:[1]　《运筹学》教材编写组.运筹学[M].北京:清华大学出版社,1999.[2]　周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.[3]　陈国良,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.[4]　李敏强,寇纪淞,等.遗传算法基本理论与应用[M].北京:科学出版社,2002.[5]　王小平,曹立明.遗传算法[M].西安:西安交大出版社,2002.[6]　梁吉业.遗传算法应用中的一些共性问题研究[J ].计算机应用研究,1999(7).[7]　彭伟,等.一种函数优化问题的混合遗传算法[J ].软件学报,1999(8).[8]　梁艳春,等.遗传算法求解旅行商问题时的基因片断保序[J ].系统工程与实践.2000(7).[9]　胡欣,等.遗传算法求解投资项目选择问题[J ].计算机应用研究,1999(4).[10]　刘锋,等.基于改进型遗传算法的门阵列模式布局[J ].小型微型计算机系统,2002(3).[11]　王斌,等.一种防止遗传算法过早收敛的“两阶段交替法”[J ].小型微型计算机系统,2003(3).T he A lgorithm o f A rranging School T im etab le B ased on G enetic A lgorithmsPU Bao 2xing(Department o f Information and Electricity Engineering ,Shaoyang College ,Shaoyang 422001,China )Abstract :The paper trans forms the problem of the school timetable arrangement to the problem of combinatorial optimization ,upon which ,the mathematical m odel is created by penalty function and the s olution to the problem is given based on genetic alg orithms.Furtherm ore it puts forward “the dynamic scaling approach of penalty weight ”and “the blocked genetic method ”.K ey w ords :school timetable arrangement alg orithm ;genetic alg orithm ;blocked genetic method ;culturemutation ;dynamic scaling approach of penalty weight[责任编辑:杨　玉]78　第1期蒲保兴:基于遗传算法的排课算法。