排课算法（精选10篇）
排课算法 篇1
摘要：通过对已有各种排课算法的了解及排课问题的研究,设计出了自动排课算法,即采用分治法、贪婪法、回溯法三者的思想,结合优先级算法,实现了整个排课算法的设计。
关键词：排课算法,研究,设计
高等院校的在校人数不断增加,排课人员的工作越来越繁重,而且一旦出现课表冲突调整课表是一件非常令人头痛的问题。计算机功能越来越强大,已经广泛应用到各行各业各个应用领域。实际上,用计算机进行排课的研究早在上世纪五十年代就开始了。
由于课程表问题所涉及的信息较多,并且求解课程表问题最优解的时间复杂性是课程表规模的指数级,所以一般采用求近似最优解的算法,而不一定非要最优解不可。因此,对于课程表问题,关键不是如何找到最优解,而是如何提高解的满意度。
1 排课问题调研
学校排课问题是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。在排课过程中,需要考虑课程教学效果(比如一门周课时为6的课程不能安排在一天内上完)、满足教师特殊要求等多项优化指标,将各门课程安排到相应的时间和教室。
1.1 排课问题要素
在排课过程中主要涉及的基本要素包括:教师要素、班级要素、课程要素、时间要素、场地要素。
教师要素主要包括:一是教师的基本信息,如教师所在部门、专业、教研室等;二是教师的特殊要求,如某教师要求他的课不能安排在某个时间。
班级要素主要包括:班级分为行政班级和教学班级,行政班级指招生时注册的班级,教学班级可以是几个行政班的组合也可以是行政班的一部分,是真正排课中的班级。每个教学班级都有一个唯一的ID号。
课程要素主要包括:课程的ID号、课程名、课程起始周次、周学时等,还有就是课程的优先级,课程优先级决定课程的排序次序,不同的课程优先级不同。
时间要素主要包括:一是在时间安排过程中要考虑三个方面的冲突:一同一个班级不能在同一个时间段上两门课;二同一个教师不能在同一个时间段上两门课;三同一个场地不能在同一个时间安排两门课。二是时间安排还要满足的一些要求,如:星期六、星期天、晚上一般不排课,有的学校一周有一次的开会时间不能安排课(如我院为周三下午开会)。
场地要素主要包括:场地有教室、实验室、体育课场地等,场地能容纳的人数是主要要素之一;场地的类型,如是否是多媒体教室,有的课需要在多媒体教室上课;场地的其它特殊要求。
1.2 符号与约束条件
相应的符号与约束条件:设课程集合:K={K1,K2,.,Kt.,KT};班级集合:B={B1,B2,.,Bm,.,BM};教室集合:J={J1,J2,.,Jn,.,JN};教师集合:S={s1,s2,.,sp,.,s P};时间集合:T={t1,t2,.,td,.,t D};时间与教室对的笛卡尔积为:G=T·J=(t1,J1),(t1,J2),.,(t D,JN);G中的元素称为时间教室对;课表问题的求解过程就转化成为每一门课程寻找一个合适的时间教室对。
排课过程中必须满足的约束条件可以归纳成两类:一是硬约束条件,硬约束条件是指在排课过程中因为资源有限,所以满足而无法变更的约束条件,主要有三类硬约束条件:同一时间,一个教师不能同时有一门以上的课程;同一时间,一个班级不能同时有一门以上的课程;同一时间,一个教室不能同时有一门以上的课。二是软约束条件,是指在排课过程中可以满足但又可特殊以不完全满足的约束条件,是排课过程中在满足硬约束条件的基础上能尽量要求满足的约束条件,不同的教学情况软约束条件会有所差异。软约束条件不是必须的,可以将一定要满足的软约束条件转换为“硬约束条件”。常见的软约束条件主要有:课程尽量安排在教学效果较好的节次;多学时课程每周的安排要错开(如,每周多学时(≥4)的课程,应该能够尽量将其隔天安排);满足教师所提出的上课时间和地点的要求。
2 排课算法设计
排课问题的关键是排课算法的使用。前人在排课算法的使用上已有许多成功的案例。主要的排课算法有:启发式算法、优先级算法、应用专家系统、人工智能应用、分组优化算法、约束满足方法、搜索算法、数据挖掘相关算法等。
通过分析已有排课算法的优缺点,本排课系统拟采用分治法、贪婪法、回溯法三者的思想,结合优先级算法,完成整个排课算法的设计。
分治法也称分割求解法,设计思想是,把一个大的大问题划分为原问题的规模较小的问题,先求出子问题的答案,然后把各子问题的解合并成整个大问题的解。这样就可以把一个大的复杂的问题,分解为小的容易解决的问题。
贪婪法的算法设计思想是分阶段工作,在每一个阶段选择局部最优,而不考虑将来后果。对最终的解不追求最优解,能够得到某种意义下的近似解的分级处理方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况。
教师、班级、教室的排课类似于贪婪算法中的机器调度问题。n门课程相当于n件任务,这n件任务由教师、班级、教室协同完成。每件任务的开始时间为si,完成时间为fi,si
一种获得最优分配的贪婪方法是逐步分配任务。每步分配一件任务,且按任务开始时间的非递减次序进行分配。若已经至少有一件任务分配给某个资源,则这个资源的状态变为已用;否则就是示未用的。在选择资源时,采用以下贪婪准则:根据欲分配任务的开始时间,若此时有已分配任务的资源可用,则将任务分给它。否则,将任务分配给未用的资源。
回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。回溯算法是所有搜索算法中最为基本的一种算法,其相当于采用了先根遍历的方法来构造解答树,可用于找解或所有解以及最优解。
可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈Si,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域,且|Si|有限,i=1,2,…,n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最简单的方法就是枚举法,即对E中的所有n元组逐一地检测其是否满足D的全部约束,若满足,则为问题P的一个解。但计算量相当的大。
回溯算法对空间的消耗较少,当其与分枝定界法一起使用时,对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用,以免产生循环。
自动排课算法,首先,根据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后,依据贪婪法的算法思想,在时间分配时,总是在尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时,会向上回溯搜索到发生冲突的最近一个记录,然后对它进行重排以解决冲突。
算法具体处理过程如下:
1)初始化设置
为了降低排课算法的复杂度,先对排课数据和时间单元进行初始化,初始化设置主要过程:
(1)划分等价类:将每学期的所有课程按年级和系别划分等价类。将有共同参与者的课程划分为同一等价类,同一等价类中的课程只有地点上的冲突没有时间上的冲突。这样就可以对每个等价类分别进行排课,从而大降低了算法的复杂度,提高排课算法效率。
(2)时间初始设置:时间初始设置包括构造时间模式库和构造时间模式数组。
时间模式库是为了提高上课安排的合理性,为不同周学时数的课程设置的时间组合模式。例如,每天上课时间安排为上午4节课,下午4节课,晚上4节课,可以把时间段划分为:上午1-2节一个时间段,用“1”表示;上午3-4节一个时间段,用“2”表示;下午5-6节一个时间段,用“3”表示;下午7-8节一个时间段,用“4”表示;晚上9-10节为一个时间段,用“5”表示,晚上11-12节为一个时间段,用“6”表示。星期一至星期天分别用“1”-“7”表示。用一个时间串来表示某门课程的上课时间模式,如:“11”表示星期一的1-2节上课,“42”表示星期四的3-4节上课。对于一个周学时数为4的课程,时间模式可以设置为:“11”和“32”、“12”和“31”、“11”和“42”等。在课程安排时对于课时数比较多的课程,要尽量隔天安排。
构造时间数组是为了表示教师、班级、教室的可排课时间。分别为他们建立一个12×7×30的三维数组。其中第一维表示每天的节数,第二维表示一周的天数,第三维表示一学期的周数。
(3)分别设置教师、教室、课程的空忙字段的值,这个字段的值是一个三维数组(X,Y,Z),用来表示是否可以排课,如果该位置的值为“1”表示可以排课,为“0”表示该时间段已用,不能排课。
2)设定优先级
对子类中的课程计算优先级L设优先级函数为:
其中,Z(g)表示该课程的周学时数;J(g)表示课程级别,选修课的课程级别设置为1,必修课的课程级别设置为2;R(g)表示该课程的参与人数;T1、T2、T3是可以调整的参数。由式(1)可以看出课程级别越高、周学时越多、参加人数越多的课程,其L(g)值越大,其优先级也越高;反之,L(g)值越小,其优先级越低。这样,就可以根据计算的优先级的高低对课程进行排序,优先级高的优先排课。
3)查询可用时间单元:首先,初始化某门课程的最大可安排时间数组,为(123456 123456 123456 123456 123456)。然后,找出参加该课程学习的所有班级。第3步,查询每个班级的时间数组,得到班级的已排课时间,并将其与课程的最大时间数组相“与”,从而得到该课程不能安排的时间单元。第4步,依次处理教师时间数组和相关教室时间数组,这样,该课程最终的可安排时间数组就是班级、教师、教室可排课时间的交集。
4)查找适当的时间模式:找到可排课时间后,就应根据课程的周学时数在时间模式库中匹配适当的时间模式。
以上排课工作完成后,就确定了课程的上课时间和地点。在处理中如果发生死锁,则可根据回溯法的思想向上回溯搜索到发生冲突的最近一个记录,对它进行重排,以解决死锁,如果死锁问题仍不能解决,则将该课程信息输出到冲突列表中。
5)人工干预的处理:计算机自动排课也需要进行人工干预,以便各个高校根据自己的具体要求设置和调整排课算法中的一些参数,而且可以对计算机排出的课表进行手动调整。人工干预主要包括以下几个方面:
等价类划分中参数的设置,教室类型的设置,时间模式库的设置,优先级函数中参数的设置。用户可以根据自己的具体要求对这些参数和库进行设置。另外,对于计算机排出的课程表,用户也可以通过手动进行适当调整,使得课程表能够满足用户的需要。
3 结束语
在自动排课系统设计过程中,排课算法的设计是关键,所用排课算法直接影响了系统的可行性。此排课算法经验证是可行的,通过不同阶段采用不同的算法,充分发挥了各算法的优点,使实现自动排课成为可能。
参考文献
[1]钱德凤.TTP在高校排课中的研究与应用[D].上海:上海师范大学,2006:10-11.
[2]湛德照.高校自动排课系统的算法研究与实现[D].重庆:重庆大学,2006:15-17.
[3]陈雪芳.教学管理系统中排课算法约束条件及其实现[J].东莞理工学院学报,2009(1):51-54.
[4]李明.一个基于智能化搜索的排课表算法及其Client/Server实现[J].现代计算机,1997(6).
[5]李增智,王云岚,陈靖.课程表问题的一种混合型模拟退火算法[J].西安交通大学报,2003,37(4).
[6]杨为民.使用遗传算法编排课程表的研究与应用[D].合肥:安徽大学,2003:20-23.
排课算法 篇2
1.首先把学期课程安排先设置好.先做排课属性设置：单单、双双、全全、随随
再设置哪些课程不排课
2.在智能排课—排课课表设置中设置：
一周天数：5上午：4下午：4晚上：3
课表设置：横是星期一至星期五纵是第一节至第六节
3．排课属性设置（重要）：
（1）首先要在连排设置中设置：单单、双双、全全、随随
（2）周课时为偶数：全部设置为2节连排
（3）周课时为奇数：选中课时数相同的教学班名称，如选中所有课时的教学时，然后点击相同周课时班级统一设置。
1课时：改成随随*1
3课时：改成全全*1，随随*1
5课时：改成全全*2，随随*1
7课时：改成全全*3，随随*1
4．排课性性设置里不能设置教室。
5．排课限制条件设置：（限制课时中进行设置）
星期三下午不排、体育课老师上午一、二节课不排
6．全部设置完成后，点击自动排课
7．自动排课完成后，进行手动调课
8．如果遇到课时为3课时的，就是单双周上课问题。
要想办法把单双周的课调到同一时间上。
方法：如遇到调不进去的课，可以先把单（双）周课删除，再把在这个位置让给其它课，再在双（单）周课时增加刚才删除的单（双）周。
（增加课程的方法：先点击添加课程，这时右边出现一个未排的课程，选中课程，再选中连排属性，再点击要排课的位置就可以了）。不参与排课班级及课程课程
高中专护理09-5（与师院联办）不参与排课
1、职业生涯规划与就业指导
2、军训
国防教育及军事技能训练
卫生健康教育
心理健康教育
就业教育
职业生涯规划与就业指导
社会实践
形势与政策
金工实习技能实训 CET2考试培训、CET3考试培训 是否排课具体与系部联系.专项技能训练
普专药学营销09-1不参与排课
排课算法 篇3
关键词：粒子群算法；中职学校；排课；适应性函数
在我国中等职业学校的教学中，排课是专业课程教学管理体系中的一项十分重要的教学管理工作，其具体的形式与内容都是非常复杂的，一个科学、有效的排课设计系统往往会极大的促进学校教育事业的发展与教学水平的提升。我们从中职学校的排课问题中能够看出一个带有约束性质的优化问题，而其中所说的约束条件就是指，所排出的课程安排不存在教师、教室、时间上的冲突，这是粒子群算法对其进行优化的前提条件，以便最大限度的使教师、教室、时间等资源消耗最小化，从而帮助职业学校取得最大合理化的排课效果。
1 “排课问题”与“粒子群算法”
1.1 排课问题
所谓“排课”，就是指教学课程的安排，具体意思就是说，学校为了能够正常的进行教学工作，然后对各年级、各教室、各教师以及教学课程等一系列的教学资源进行科学、合理的安排与优化，从而制定出学校教学使用的课程表。
排课问题是指科学、有效解决在教学时间、教学空间上资源矛盾的多因素优化决策的一个问题，主要的元素包括教室、教师、课程、班级等，有效的排课就是让这些基本因素之间在一定时间、地点内不发生任何的冲突、矛盾。（表1）
1.2 粒子群算法
粒子群算法——Particle Swarm Optimization ，也被称作为粒子群优化算法，简称——PSO。粒子群优化算法是一种与遗传算法非常相似的科学算法，但是从它的计算内容及形式上来看，PSO这种算法则突显的更为简单、实效。
2 中职学校排课问题的粒子群优化算法
2.1 粒子的编码
在粒子群优化算法中，我们应该对于每一个需要优化的问题进行全面的挖掘、分析，通过想象把一些潜在的问题解决方案通过D维搜索空间，将其看做成一个空间“点”，也就是我們所说的“粒子”。在某中职学校的排课中，对于每一个粒子元素，我们都可以将其设定为一个元素集，T代表时间、M代表教师、C代表课程、R代表班级、I代表地点，这也是在中职、高等学校排课中比较常用的五元组优化算法体系。
下面我们通过一个模型来表现“粒子编码”的操作概念：
图1 粒子编码模型图
2.2 适应性函数
Fit=
该公式中，m1、m2、m3、w1、w2、w3分别代表权值，也就是说权值的大小代表着各种约束条件的重要程度，图1中所表示的粒子元素，在函数中表示的则是一种可能的排课结果，具体的排课结果的优劣好坏是由适应性函数来决定的。
2.3 种群的初始化
在对中职学校进行排课结果研究计算过程中，粒子群优化算法中的种群初始化，也就是指初始化的粒子群，通俗点讲就是指元素集，就像在第一部分所提到的元素集一样，T代表时间、M代表教师、C代表课程、R代表班级、I代表地点。在粒子群初始化的状态下，所有粒子元素都是随机进行排列的，目的就是为了后面所进行的进化操作提供初始粒子群。
2.4 基于粒子群的排课算法设计
通过粒子编码与适应性函数在中职学校排课问题中的应用，制定出PSO基本算法的流程示意图，详见图2。
下面就以某中职学校的计算机信息工程专业的课程任务分配工作问题来进行排课，通过运用粒子群优化算法，并将粒子群优化算法与传统的遗传算法来进行对比，通过排课结果来体现出粒子群优化算法的科学性、准确性、实效性。
通过表3所计算出来的结果显示，基于粒子群优化算法下的中职学校排课结果的性能要优于传统的遗传算法的性能，非常有效的实现了学校在排课过程中避免了各种时间、空间上教育资源的冲突与浪费。
3 总结
本文主要介绍了利用粒子群优化算法来求解中职学校排课问题的具体方案，经过对算法结果的分析与验证，已经证明了PSO这种算法在实际应用中是非常有效果的。应用粒子群的编码方案以及适应性函数，能够很好地解决中职学校排课问题，并有效的保证了中职学校排课结果的正确性、实效性、科学性，对学校排课的合理化和整体教学管理水平的提高有极大的帮助，有效地促进了教学质量的提高。
参考文献：
[1]陈华.基于粒子群算法的高校排课系统设计与实现[D].扬州大学，2009.
[2]王超.基于离散粒子群算法的机房排课问题研究[J].计算机光盘软件与应用，2012（3）：206-207.
[3]张立岩，张世民，秦敏，等.基于改进粒子群算法排课问题研究[J].河北科技大学学报，2011，32（3）：265-268.
作者简介：
排课算法 篇4
针对上述问题, 该文采用Pareto多目标遗传算法来进行优化计算。该方法无需对优化的各个目标掌握先验知识, 并具有极强的鲁棒性、全局寻优能力和隐含的并行性等特点, 使得该方法成为多目标优化方法中的一个研究热点。
1 排课系统设计
课表的安排除了要考虑教学计划、教师资源以及教室使用情况, 同时还要以其他教学要求来评判课程安排的优劣, 如:
(1) 课程分布均匀, 避免课程都集中在某一两天的情况;
(2) 重要课程尽量安排在上午;
(3) 对于一周多节的课程要尽量保证同一门课程两节之间时间间隔较长。
该文设定一个班级一天排6节课, 上午排4节课, 下午排2节课, 即一周有30节课, 因此每一节上课时间的变量在整数区间 (1-30) 上取值。量化排课优劣程度的方法如下描述。
(1) 为了使重要课程尽量安排在上午, 首先将每一节课的值进行修正:一周有n节课时, 按先后顺序记课的值分别为1, 2, …, n。其中, 式中, 若该节无课, 则当前值设为0。假设排课结果为x1, x2, …, xn, 评价函数f1 (X) 如式 (1) 所示:
由式 (1) 可以看出, 当f1 (X) 的值越小时, 课程就越集中在上午。
(2) 为使课程安排均匀, 需统计一周每天安排的课程数目, 并求这5天课程数目的方差f2 (X) 。那么, 方差f2 (X) 越小则排课越均匀。
(3) 对于每周要安排多节的课程, 要使同一门课程两节之间间隔的时间尽可能长, 则计算同一门课 (每周需要安排多节的课程) 两次值的相差绝对值。那么, 一周内所有课的相差绝对值之和f3 (X) 越大, 则课程安排越合理。
2 多目标遗传算法优化
传统多目标优化方法是将多目标优化问题转化为单目标优化问题。如线性加权法, 将上述三个目标函数f1 (X) , f2 (X) , f3 (X) 按其重要程度给出一组权系数w1, w2, w3, 则评价函数的最优解如式 (2) 所示:
但该方法要求对优化问题掌握先验知识时。而该文采用Pareto多目标遗传算法来进行优化计算, 无需掌握先验知识。
Pareto占优定义如下:假设x1, x2∈某一可行域Ω, x1被x2占优是指对部分i, 有fi (X) ≥fj (X) , 而对其他的j≠i, fi (X) >fj (X) 。Pareto最优解x0是指在Ω中不存在任何x占优于x0。
从定义中可知, Pareto最优解不是唯一的, 而是由许多“非劣解” (非劣解, 是指在不降低其它性能指标的前提下, 再也不能提高该性能指标) 组成的解集, 因此群体搜索策略 (如遗传算法) 是非常合适的求解方法。
遗传算法是通过对一代群体按照寻优目标进行一系列的选种、交叉、变异而使下一代群体从整体上更接近最优解[3]。该文将选择算子中引入Pareto占优概念, 即Pareto遗传算法。
该文Pareto遗传算法操作流程如表1所示。
相比较以往传统遗传算法, 该文算法改进措施如下。
(1) 根据种群中占优的个数多少来赋予个体相应适应度。
(2) 在每代中采用部分种群来决定占优的情况。而且, 当两个个体之间彼此互不占优的时候, 其结果通过适应度共享来决定。由于该文没有在整个种群中使用Pareto意义选种, 而是在每代中只采用部分种群, 因此其能快速并产生较好的Pareto意义占优解。
(3) 相比较传统遗传算法, 该文算法还引入小生境技术[4,5]。该技术可以防止基因漂移, 使群体均匀分布在Pareto最优解集中。由于一周有5天课程, 该文将个体划分为5类, 即从这5个类当中选出适应度较大的个体作为该类的代表组群。
3 实验结果及分析
假设需为某班排课, 共6门课程, 英语、语文、数学等。其中英语、语文、数学每周需要安排6节, 其他课程每周安排2节。
首先通过随机方法生成30次排课解作为初始群体, 以上述f1 (X) , f2 (X) , f3 (X) 的极值作为优化目标。根据遗传算法进行优化计算, 设突变率为1%, 经过100代进化, 结果如表1所示。
由表1可以看出, 尽管实验没有提供对优化目标的先验知识, 但通过Pareto遗传算法优化后, 3个优化目标f1 (X) , f2 (X) , f3 (X) 都得到同时优化, 并且优化结果比较理想。
4 结语
该文针对传统多目标优化排课算法需要先验知识的缺点, 将Pareto多目标遗传算法应用到排课系统中, 并实验证明该方法的有效性。
摘要：中小学课表编排要考虑时间、空间和人员安排问题等多个目标的同时优化问题。传统方法是将多目标优化问题的多个目标函数通过适当方法 (如加权法等) 转化为单目标优化问题进行处理。该方法的缺点需要对优化问题掌握一定的先验知识, 否则难以确定加权系数。针对传统多目标算法需要对目标掌握先验知识的缺点, 该文提出一种基于Pareto多目标遗传算法的排课算法, 并实验证明该方法的有效性。
关键词：遗传算法,Pareto,多目标,排课
参考文献
[1]Tan K C, Lee T H, Khoo D, and et al.A multi-objective evolutionary algorithm toolbox for computer-aided multi-objective optimization[J].IEEE Transactions on Systems, Man and Cybernetics:Part B (Cybernetics) , 2001, 31 (4) :537-556.
[2]Vieira D A G, Adriano R, Vasconcelos J A, and et al.Treating constraints as objectives in multiobjective optimization problems using niched Pareto genetic algorithm[J].IEEE Transactions on Magnetics, 2004, 40 (2) :1188-1191.
[3]陆金桂.遗传算法原理及其工程应用[M].徐州:中国矿业大学出版社, 1997:40-52.
[4]乔佩利, 郑林, 马丽丽.一种小生境遗传算法研究[J].哈尔滨理工大学学报, 2011, 16 (1) :90-93.
走班排课方法 篇5
新高考后，混合教学模式给学校的排课工作带来了很多困扰。无论是课程安排还是分层走班，都无法通过普通的排课手段解决问题。
前阵子有时间研究了一些，主要是研究行政班和走班结合下走班排课的方法，就是研究选课科目的排课方法，当然非选考科目也适用。也找到了一些方法，并且成功排出来了。就讲其中一种思路吧：学生选3门科目，因此我就排3节课（3节选考、3节非选考），每星期上多少节就循环多少次。就以我们统计的数据来为例子说说以下两种方法： 方法一：先分班后排课
1.分层分班：分班分不好，后面很头痛，尽可能把相同组合分到一个班，这样约束条件就少一些，冲突更少一些
2.排课：排课就是在浩如烟海的数据当中找到没有冲突的那一种。比如700多个学生，假设选课都平均的情况，有24间教室，每科有4个教师，每个教师带两个班。这个数据到底有多大呢？把所有的数据列出来，有6的23次方，就是700多亿个亿，而且这么多的数据可能没有一个符合。这么多的数据怎么算呢？方法还是有的，可以先编程排两科，留下没有冲突的，再统一起来数据就没有那么大了。当然每算一步电脑都会运转几十分钟。
因此，我不赞同这种方法，数据大，而且不一定找到符合条件的。就算拿最优的方案来算微调也是很麻烦的事。方法二：先排课后分班
排课的人总是习惯分班后排课，变通一下后会有想不到的收获，先排课后分班。
基于回溯法的排课算法 篇6
1 排课基本原则
要排出科学、合理和实用的课程表,必须满足下列排课原则[6]:
1)同一教师不能同时给两门或两门以上的不同课程授课;
2)同一教室不能同时安排两门或两门以上的不同课程;
3)教室的座位数要大于等于上课的人数;
4)教室的类型要与课程的类型一致(如实验课等);
5)尽量将课堂教学安排在上午,而将试验课、体育课和电化教育课程安排在下午进行;
6)尽量保证每个教师的工作时间要错开,即在上课的时间上,不能让一个教师连续完成多个教学工作;
7)一般在某个特定的时间段不要安排教学任务,以便教师和学生都能够利用这个时间进行一些教学工作以外的活动;
8)尽量为特殊教师(如领导等)安排特定的教学时间;
9)同一个班级的同一门课在一个星期里尽量使其上课的时间错开,即均匀排课。
这里把1)、2)、3)、4)称为显约束,其余称为隐约束,显约束必须满足,而隐约束要似情况而定。
2 主要数据结构
排课的基本要素包括:课程、教师、班级、教室和时间。
课程信息表(课程编号,课程名称,课程性质,上课学时,周学时,上课班级,教师代码,教师姓名,是否已排,优先级);
教师信息表(教师编号,教师姓名,性别,年龄);
班级信息表(班级名称,人数);
教室信息表(教室代码,房间号,教室类型,可容纳人数,是否已排);
时间信息表(时间代码,节次,时间段)。
3 优先级原则
1)专业课的调度优先于非专业课;
2)参与班级较多的课程优先调度;
3)合班课优先调度;
4)多头课优先单头课调度;
5)对时间有特殊要求的课程先调度;
6)对教室有特殊要求的课程先调度。
根据以上原则,设计了一个优先级函数为:
其中F(x)表示优先级函数;J(x)表示课程的级别(专业课设置为3,基础课设置为2,非专业公共课1);W(x)表示该课程的周学时数;S(x)表示该课程的参与班级数;T(x)表示教师承担课程的任务量(承担一门课为0,两门课为1,三门课为2,依次类推);C1,C2,C3,C4为可调整的参数,由F(x)可知,课程级别越高、周学时数越多、参与班越多、教师任务越重的课程的优先级超高。这样按优先级进行降序排序,优先级高的优先处理。
4 优化原则
因为排课问题是NP完全问题,必须根据排课的基本原则对课程表进行优化,让其满足约束条件,从而达到最终目标,优化的基本原则是:
1)学习效率原则
不同类型的课程在不同的时间段学习的效率不同,排课时要尽量使学习效果最佳。
根据学习心理学,将课程划分为以下四大类:
(1)逻辑性强的课程:如数学、电路、数据结构等;
(2)记忆性强的课程:如语文、外语等;
(3)综合类课程:即既有理解记忆的部分,又有逻辑推理,如会计类课程等;
(4)体育类课程。
根所以上划分,可把学习效率用不同的系数表示如表1所示。
2)均匀排课原则
一周内上两次或两次以上的课程(一般为两次或三次),两次间隔均匀。现对可能出现的的情况作出统计并对其进行评分,如表2、表3所示。
3)资源利用原则
资源利用率,这里主要指教室资源的利用率,考虑上课人数与教室资源的比值,即人数/教室座位数,比值越大越好,最大值为1。
这里称上述原则为排课三原则。首先处理均匀排课,其次是学习效率,最后是资源利用率。根据排课三原则,可得到目标函数值的计算公式:
其中r1,r2,r3为原则1,2,3的得分值,w1,w2,w3为权重分别为3,2,1,由此可知目标函数值越大则课表越优化,目标函数值最大时对应的课表为最理想的课表。
5 回溯排课算法描述
回溯算法是求解多约束条件问题的最佳解时常采用的首选方法,希望一个问题的解能表示成一个n元式(x1,x2,…,xn)的形式,有时也称其为问题的解向量,对于具体的问题通常要求使解向量满足某些约束条件或者是使问题的目标函数最大化(或最小化)[8]。通过上述对排课问题的具体分析后,得出了回溯算法的目标函数值的计算方法,现将算法描述如下:
1)处理特殊情况,如固定时间的课程,领导的课程等;
2)排课;
(1)根据优先级函数F(x)计算调度优先级,并对优先进行降序排序;
(2)取排课信息;
若周学时为偶数;
判断该位置是否可排,可排则剩余周学时=周学时-2;
若周学时为奇数;
当周学时或剩余周学时为1时,必须分单双周处理;
当周学时或剩余周学时为3时,若不分单双周,则处理三节连排;
对上述两步若找不到合适的位置则回溯。
(3)若所有课程均排完,则计算目标函数值并保存;
(4)重复(2)(3)步并比较目标函数值,直到目标函数值最大时停止。
6 结束语
该算法已在我校排课中得到具体应用,结果表明,使用该算法编排的课表是成功的,各种约束条件都得到了满足,课表科学合理,编码简单,容易软件实现。
参考文献
[1]Even S,Itai A,Shamir A.on the The Complexity of Timetable and multicommodify flow problems SLAM[J].Journal on Computing,1976(5):691-703.
[2]Cooper T B,Kingston J H.The Complexity of Timetable Construction Problems[C].Proc.ICPTAT'95,1995:183-295.
[3]张健.基于图论的高校排课系统实现[J].重庆师范大学学报,2005(1).
[4]蒲保兴.基于遗传算法的排课算法[J].中央民族大学:自然科学版,2006,15(1):83-87.
[5]杜敏.基于知识的排课系统研究与实现[J].小型微型计算机系统,1989(8).
[6]杨兴旺.贪婪算法在排课算法中的应用[J].中央电大学科研究,2007(1).
[7]李志娟,王冠.高校自动排课算法的研究与设计[J].计算机与数字工程,2008(5).
排课算法 篇7
排课是高校教学管理中十分重要而又复杂的管理工作之一, 由于排课问题涉及的因素有时间、教师、教室、课程、班级等, 因此排课问题是一个有约束条件、多目标、模糊性极强的组合优化问题[1]。由于各学校资源差异较大, 约束条件复杂, 排课系统难以具有普遍适用性。一般教务排课仍以手工为主, 计算机为辅, 效率低下。研究灵活、高效、自动化程度高的排课系统需求迫切, 具有现实意义。
国外很早就有人研究课表的编排问题, 一般利用启发式函数, 并且大多数启发式方法都是模拟手工排课的过程实现的。国内对排课问题的研究较晚, 并且大部分学者研究的排课系统都依赖于各个学校的教学体制, 不具有普遍适用性[2]。从实际使用情况看, 国内研究的排课系统软件在性能上也达不到使用要求。
遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法;而禁忌搜索算法是对局部领域的一种扩展, 是一种全局逐步寻优的搜索算法。通过对比分析, 遗传算法和禁忌搜索算法在解决复杂优化问题中有明显的优势, 因而本文采用遗传算法和禁忌搜索算法来实现排课系统。
1 排课系统分析
排课问题的主要任务是将班级、教师、课程安排在一周内某一不发生冲突的时间和教室中, 保证课表在时间分配上符合一切共性和个性要求, 使安排在各个目标上尽量达到最优。
根据是否必须满足, 可以将约束条件分为硬约束和软约束。硬约束是指教师、班级、教室在时空概念上发生了冲突, 它是在排课过程中必须满足的约束条件, 否则将会使排课结果毫无意义。软约束是指排课过程中需尽量满足的约束条件, 它能够使课表更加合理。排课的目标是要满足所有的硬约束条件, 同时尽可能多地满足软约束条件, 实现一个使用方便、效率高的排课系统。
2 基于遗传算法与禁忌搜索算法的排课系统
在整个排课过程中, 首先需要确定教学计划, 然后根据教学计划生成教学任务, 教学任务确定了课程、教师、班级3者之间的关系。在排课问题中, 由于涉及到教师、教室、课程、班级、时间这5个因素, 可以将课程、教师、班级这3个因素绑定为一个整体, 作为一个元组, 并对这个元组随机分配时间与教室, 生成一个可行的课表。
本文应用遗传算法对排课问题进行编码, 然后再进行选择、交叉、变异等操作, 计算适应度函数。在遗传算法的运算过程中使用禁忌搜索算法来代替变异算子, 从而得到更优的个体解, 最终生成有效的课表。
2.1 遗传算法编码
遗传算法的编码方法有很多种, 针对排课系统, 本文采用混合式编码方式, 将混合式编码作为排课系统遗传算法的基因。该基因由教师编号、课程编号、班级编号组成, 每个教师都有一个唯一的教师编号, 用八位数字表示。课程编号用一位数字表示, 表示该教师教的第几门课程。班级编号也用一位数字表示, 表示该教师教的第几个班级。这种编码方式解决了特定时段教师课程的安排问题和普通时段课程的分配问题。系统只要按照算法流程对编码进行处理, 对结果进行不断的筛选, 就可以得到完善的课程表, 通过混合式编码将教师、课程、班级这3个因素的关系表示出来。
混合式编码在时间上主要采用时间片划分, 上课时间分为周一到周五, 一天有10节课 (上午4节, 下午4节, 晚上2节) , 上课方式为一个课次两个相邻小节。所以以一个课次为一个时间片, 一天可划分为5个时间片。这样一周就可划分为25个时间片。可以构造一个三维矩阵来表示排课系统, 其中X坐标表示时间片, Y坐标表示教师、班级和课程, Z坐标表示教室, 通过三维矩阵将影响排课系统的5个因素联系起来。
2.2 遗传算法适应度函数
适应度函数用于评价某个染色体的适应度, 随着排课的进行, 课表空间在不断变化, 个体的适应度也随着课表空间的改变而改变, 本文采用的方法是调整随机生成的初始群体, 但是在遗传算法运行过程中, 交叉和变异都可能产生冲突, 为了减少冲突, 可以引入负适应度值来降低冲突个体被选入的概率, 同时记录冲突未消除的个体, 并在下次迭代中继续消除。对有时间段冲突的两个个体, 可以用个体的冲突时间段与该个体的空闲时间段互换来消除冲突, 这样就消除了遗传算法运行过程中存在的冲突, 增加了个体的适应度。
2.3 遗传算法运行
2.3.1 选择操作
首先采用计算机模拟方法计算个体的选择概率, 这种方法的基本思想就是用事件发生的频率来决定事件的概率。接着采用轮盘选择法进行下一代个体的选择。其基本思想就是将整个群体根据个体的适应度不同分布在轮盘上, 适应度大的个体占的比例多。在选择算法过程中随机转动轮盘, 指针所指区域的个体被选中并生存。这种选择方法对适应度大的个体选中的机会较大, 实现了个体的优胜劣汰。
传统遗传算法的缺陷是初始种群分布不均匀, 为了改进这个缺陷, 本文采用分区域的初始种群选择, 将整个解空间分成m个区域, 初始化种群时, 分别在每个1/m小区域中随机选择1/m个体, 最后将m个小种群合并为初始种群, 这样产生的种群就覆盖了整个解空间, 保证了初始种群的均匀分布。
2.3.2 交叉操作
本文采用的是两点交叉, 其基本思想是在两个相互配对的编码串中随机选择两个交叉点, 将这两个交叉点之间的基因相互交换得到两个子个体, 两个11位的父个体, 交叉点的位置为2、6, 通过两点交叉运算得到两个子个体。两点交叉运算如下所示:
父个体1 11110011010子个体1 11101011010父个体2 10101000101子个体2 10110000101通过这种方式解决了选课学生人数和教室座位人数之间的冲突, 交叉操作产生的新个体遗传到下一代。
2.3.3 改进的遗传算法
传统的遗传算法收敛速度慢、局部寻优能力差、产生的最优解精度不高, 同时由于交叉算子使种群染色体之间存在局部相似性, 这样就很可能导致搜索停止。如果变异率降低, 还会导致“早熟”现象发生。遗传算法在进化过程中, 每代总要维持一个较大的群体规模, 从而容易使个体后代过多, 造成算法“局部收敛”而不能得到全局最优解。因此, 必须对个体以变异概率进行局部搜素, 跳出局部收敛, 获得全局最优解。
禁忌搜索算法在搜索过程中可以接受劣解, 具有较强的“爬山"能力, 新解不是在当前解领域中随机产生的, 而是从中选择的最好解, 即最好解产生的概率大于其它解。该算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索, 并通过藐视准则赦免一些被禁忌的优良状态, 增加获得全局最优解的概率, 因此禁忌搜索算法适合作局部搜索[3]。
由于传统的遗传算法存在许多缺点, 因此本文在变异阶段用到了禁忌搜索算法, 用TS代替变异算子, 防止“早熟”现象发生, 使个体呈现多样性。
2.3.4 改进后的遗传禁忌搜索算法
为了使原算法优点保留, 弱点被克服或被削弱, 提高算法的力度, 本文先用GA进行全局搜索, 搜索出所有可能的排课情况, 并将其分布在解空间的大部分区域, 然后在每个个体课表中用TS进行局部变异搜索, 得到最优排课情况[4]。下面给出遗传禁忌搜索算法的算法流程, 见图1。
2.3.5 改进后的遗传禁忌搜索算法
遗传禁忌搜索算法终止条件为: (1) 在种群中找到了能够接受的最优排课单元; (2) 最适应种群的个体占群体比例达到了预定的比例; (3) 达到了预定进化代数; (4) 达到了指定的最大时间。
在遗传算法的迭代中, 只要满足上述4个条件之一, 算法就终止。
TS运用于GA的局部搜索中, 避免了GA过度早熟的现象, 但是如果一直调用TS会浪费时间[5], 因此调用TS要根据GA的收敛情况来定, 开始时调用TS的次数很少, 随着迭代的进行, 调用TS的次数也越来越多[6], 因为各个排课单元越接近最优排课单元, 局部搜索的作用也越大, 因此在GA中要合理地使用TS。
3 结语
本文介绍了国内外排课系统问题研究现状, 对排课系统的实质进行了分析, 并对排课系统的实现提出了相应的解决方法。本文采用遗传算法和禁忌搜索算法实现排课系统, 首先对排课问题按照遗传算法进行编码, 然后定义好适应值函数后进行选择、交叉操作, 并引入了禁忌搜索算法来代替遗传算法中的变异因子, 完成了排课系统的算法设计, 达到了预期目的。
摘要：排课是高校教务管理工作中的重要业务之一。由于排课问题考虑的因素和约束条件很多, 加上不同的学校情况不同, 因此很难形成一个固定的排课模式。分析了排课问题的实质及解决方案, 主要采用遗传算法和禁忌搜索算法解决排课问题, 通过对比和计算分析, 取得了良好的效果。
关键词：排课系统,禁忌搜索算法,遗传算法
参考文献
[1]薛冬梅.充分利用资源科学合理排课[J].中原工学院学报, 2002 (1) :33-34.
[2]陈强.通用高校排课算法研究[J].科技广场, 2006 (7) :130-136.
[3]贺一, 刘广远.基于变异方法的禁忌搜索[J].计算机科学, 2002 (5) :29-33.
[4]郭东伟.遗传算法运行机理的研究[D].长春:吉林大学, 2002.
[5]陈守家.基于遗传禁忌搜索算法的排课问题[J].计算机应用, 2007 (6) :122-126.
基于遗传算法的排课问题研究 篇8
排课问题[1]是一个有约束、多目标的组合优化问题，同时也是一个NP-hard问题。为了解决此问题，首先对排课问题进行了描述，并利用遗传算法[2]的全局搜索和潜在并行性的优点，对其基因编码进行了构造和遗传操作进行了优化，使其更适合于排课问题的模型，进而使其能很好地解决排课问题，通过仿真实验，使之较快地找到了问题的最优解或次优解。
1 排课问题的描述
排课问题的实质是为教学任务书所规定的课程任务，包括班级、课程和教师信息，选择合适的时间和合适的教室，使得课表上任意一段时间，自然班不会发生冲突，教师不会发生冲突，时间-教室的占用不会发生冲突，即使各种教学资源被充分的利用，被合理的配置。为此，在排课的过程中必须严格遵守一些原则：
1)每一位教师在同一时间段内至多安排一门课程;
2)每个自然班在同一个时间段内至多安排一门课程;
3)每一个时间-教室对在同一个时间段内至多安排一门课程，并且其教室类型和容量要能满足待排课程的需求;
4)每门课程只能被安排一次，不能被重复安排。
此外，为了使排课的课表优化、合理，还要考虑以下一些人为满意度因素：
1)尽可能使每一门课程在一周内的上课时间分布合理，同时比较均匀;
2)根据课程的不同性质来安排不同的上课时间。比如英语不适合安排在下午上课，而实验课则不适合安排在上午上课等。
2 排课问题的优化目标
根据对排课问题的描述，将排课问题需要优化的目标归结为课程节次优化、教师期望优化和班级课表日分布均匀优化三个目标，具体情况如下：
1)课程节次优化，为了尽量将课程安排在教学效果较好的讲次中，引入了该指标，因为课程的上课教学效果与上课的讲次存在一定联系。
2)教师期望优化，因每位教师都有自己上课的要求或是偏好，需要考虑通过灵活可变的动态函数来实现教师期望的上课时间或地点是可满足的。
3)班级课表日课时分布均匀优化，为了将在一周之内的班级课程安排的均匀些，避免某一天课程出现十分集中或出现全天没课的现象，符合教学规律的要求。我们采用班级日课时分布均匀度这个指标，来尽量保证班级在每天上课讲数的相对均匀。
3 遗传算法运用与排课问题
1)基因构造
在教学任务书中，已经明确了课程、班级和教师三个元组的信息，所以把课程、教师、班级这三个元组作为一个新的元组来考虑，基因的构成规则变可以看作为：教师号+教学班序号+课程序号+时间集合+教室集合，分别对应不同的位置和位数，如图1基因构造图所示。
因此，排课问题转化为混合元组到时间和教室的笛卡尔积的一个映射，根据不同映射组合的适应度值的不同，可以进行遗传的选择、交叉和变异等遗传算子的操作，从而寻找出问题的最优解或次优解。
2)适应度函数[3]的构造
首先根据经验设置好一周内的每个时间内的课程节次优度，并计算其整个学院的节次优度的平均值ρ，同时计算整个学院所有班级的课表日课时分布均匀度的平均值覣和教师期望，即总体教师课表偏好密集度的平均值η，而一个班级的课时日分布均匀度和总体教师课表偏好密集度平均值计算方法如公式(1)所示。
在分析排课问题需要优化的三个目标的基础上，得到了如下的适应度评估函数：
其中，μ1，μ2，μ3的值可以由管理人员根据实际情况来自行定义，代表着对排课各个目标的重要程度。而e为组合可行度，是用来表示当前安排的课表方案是否存在冲突，它只有0和1这两个值，通过此方法来过滤那些不可行的排课方案，从而减少解得搜索空间，来提高算法的性能。
4 遗传算子设计和实验仿真
1)实验数据
如表1所示。
2)遗传算子设计
根据遗传算法的遗传算子操作，采用轮盘赌的选择操作，在保持基因信息完整的前提下来选择一个杂交点，在不同个体中进行单点交叉，同一个体中进行随机生成有效信息的变异操作来完成遗传操作，并通过仿真实验使其对各个目标收敛，得到其参数控制表，如表2所示。
3)结果分析
从图2适应值状态变化图可知，将遗传算法应用于排课问题，算法具有良好的收敛性和较少的运行时间，大大地提高了排课的效率，使学校的教学资源得到了充分有效的利用。
5 结论
排课问题是一个有约束、多目标的组合优化和NP-hard问题。而遗传算法是智能计算的重要分支之一，借鉴里生物界的自然进化机制，采用选择、交叉和变异等遗传操作对种群进行迭代进化，具有不依赖于具体问题和全局搜索的特点，被广泛应用于组合优化、自动控制和数据挖掘等领域，将遗传算法应用于排课问题非常合适，且具有较好的效果。
摘要：排课问题是一个有约束、多目标的组合优化问题,同时也是一个NP-hard问题。因此,该文选用将遗传算法引入排课问题中,首先对排课问题进行了描述,在此基础上提出了一种基于遗传算法的排课算法,并对其进行了仿真实验,最后较快的找到了问题的最优解或次优解。
关键词：遗传算法,排课问题,多目标
参考文献
[1]Schmidt G,Strohlein T.Timetable construction an annotated bibliography[J].The Computer Journal,1980,23(4):307-391.
[2]Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan press,1975.
自动排课系统的遗传算法探讨 篇9
高校的教务管理中, 排课工作非常复杂, 通常是手工操作, 要花费大量的精力, 且效率低下, 教学资源也很难充分利用。随着高校招生规模逐年的扩大, 以及计算机在教学工作中的普及应用, 用计算机代替劳动强度大、工作效率低的手工排课工作, 越来越成为教学管理中迫切需要解决的研究课题之一。
高校排课管理的主要任务是把全校各系或各授课部门的课进行汇总, 然后根据教学计划和教学资源制订全校的公共课、各院系的公共基础课和各班级的专业课课表, 以充分满足专业教学的要求, 并优化配置各种教学资源, 使教学工作科学、高效、顺利地进行。
时下大多数院校的排课方法是手工编排方法, 它主要通过人智能的判断和协调来完成, 排课者不堪重负, 工作结果也不尽人意。计算机排课, 它是把排课问题转化为计算领域的有约束的时空组合优化问题进行求解的。它对课表上的时间进行了分片和编号处理, 使分成的每个时间片和每个教室空间组合, 构建了一个个大小不等的时空组合块, 并根据求解规则, 对每个开课计划进行时空组合块分配, 而且分配的组合 (安排方案) , 必须在目标空间中表现出良好的人为满意度。这些人为满意度往往不仅多个, 而且是模糊的。
虽然利用计算机来模拟手工排课工作, 可以缩减问题空间的搜索范围, 以及有效组织排课, 使其在一定程度上呈现智能化。但由于其问题本身的求解规模过于庞大, 各要素之间的关联层出不穷, 以及人们对多个课表优劣评定的准则存在差异, 使计算机在求解排课问题的过程中, 面对难以穷尽的组合和多个模糊目标的优化, 也表现得无能无力。
就其实质而言, 排课问题是一个有约束的、非线性的、模糊多目标优化的、难解的、时空组合的数学问题, 即在满足各种已知的约束条件的情况下找到一组较优的时空组合。同时在具体实践上它受到教学组织形式、客观物质条件和求解目标等多种因素的相互影响, 使这一问题在实际解决时呈现出受具体条件制约的特点。
二、遗传算法
(一) 遗传算法的概念。
遗传算法 (Genetic Algorithms, GA) 是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法, 其主要特点是群体搜索策略和种群中个体之间的信息交换。它尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。如著名的巡回旅行商问题 (Travel Salesman Problem, TSP) 、作业调度问题 (Job Shop Scheduling Problem, JSP) 、背包问题 (Knapsack Problem, KP) 、排课问题等。
(二) 遗传算法的基本思想。
遗传算法是从代表问题可能潜在解集的一个种群 (population) 开始的, 而一个种群则由经过基因 (gene) 编码 (coding) 的一定数目的个体 (individual) 组成。每个个体实际上是染色体 (chromosome) 带有特征的实体。染色体作为遗传物质的主要载体, 即多个基因的集合, 其内部表现 (基因型) 是某种基因组合, 它决定了个体的性状的外部表现, 如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此, 在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂, 我们往往进行简化, 如二进制编码。初始种群产生之后, 按照适者生存和优胜劣汰的原理, 逐代 (generation) 演化产生出越来越好的近似解。在每一代, 根据问题域中个体的适应度 (fitness) 大小挑选 (selection) 个体, 并借助于自然遗传学的遗传算子 (geneticoperators) 进行组合交叉 (crossover) 和变异 (mutation) , 产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后代种群比前代更加适应于环境, 末代种群中的最优个体经过解码 (decoding) 。可以作为问题近似最优解。遗传算法采纳了自然进化模型, 如选择、交叉、变异、迁移、局域与临域等。计算开始时, 随机地初始化一定数目的个体 (父个体1、父个体2、父个体3、父个体4, ……, 父个体N) 形成初始种群, 并计算每个个体的适应度函数, 第一代 (初始代) 就产生了。如果不满足优化准则, 开始产生新一代的计算。为了产生下一代, 按照适应度选择个体, 父代要求基因重组 (交叉) 而产生子代。所有的子代按一定概率变异。然后子代的适应度又被重新计算, 子代被插入到种群中将父代取而代之, 构成新的一代 (子个体1、子个体2、子个体3、子个体4, ……) 。这一过程循环执行, 直到满足优化准则为止。
计算机具体实现步骤:
1、首先要针对问题选定目标函数 (适应度函数) , 并且将这个目标函数作为一个适应环境的能力的指标, 并设定控制参数;
2、透过一定的编码技术, 将系统组态编成一组基因码;
3、先随机产生一群基因码, 作为第一个亲代群体;
4、透过以下三种遗传算子, 完成世代交替及天择的演化过程:交叉算子 (crossover) ;突变算子 (mutation) ;选择算子 (selection) 。
5、反复进行上个迭代程序, 直到迭代次数到达限定值或目标函数值收敛到某一个极值。
三、具体算法
输入教室数据、课程数据 (包括排课安排表) 、教师数据
输出教室课表、班级课表、教师课表
1、根据教室数据生成空白教室课表;2、随机地将课程序号数据装入到空白教室课表中, 共装入n组, n是群体中个体的个数;3、计算各个个体的适应度向量F, 并计算该向量的范数‖F‖;4、如果适应度达到一定的要求 (如连续m代适应度不再改变) , 或进化代数达到一个指定数值, 则跳转到9;5、根据适应度的大小, 计算选择、交叉、变异概率, 再按概率选择优秀的排课方案, 淘汰适应度差的方案;6、进行教室切片及交叉运算;7、进行变异运算;8、跳转到4;9、从较优群体中选择一个最优方案进行切片, 分别生成教室课表、教师课表和班级课表。
四、总结
遗传算法虽然在一定程度上提高了排课效率, 但还是存在一定的局限性, 比如将遗传算法排课问题扩展到全校更多的班级、教师、课程, 使其具有更好的实用性;遗传算法的编码方式以及参数设置的进一步改进和探索, 使其更加符合排课问题的特点。并对改进的遗传编码和相应操作的收敛性做出进一步的研究;对遗传算法的初始种群比较多时使用并行遗传思想进行分割尝试。
参考文献
[1]唐勇, 唐雪飞, 王玲.基于遗传算法的排课系统.计算机应用, 2002, 10, 93-97;
[2]陈行平, 陈江, 陈启华.基于遗传算法的高校排课系统设计.绍兴文理学院学报, 2004, 24 (10) , 25-28;
基于遗传算法的排课系统研究 篇10
当课表所涉及的任何信息量稍有变化, 将会导致课表编排选择方案剧增, 以致产生搜索组合爆炸。因此, 研究在搜索过程中自适应地控制搜索过程, 从而得到最优解的通用搜索算法一直是令人瞩目的课题。
1遗传算法原理
遗传算法 (Genetic Algorithm, GA) 是一类以达尔文自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法[1]。它是具有广泛适应性的搜索方法。把“优胜劣汰, 适者生存”的生物进化原理引入编码群体中, 每个种群面对问题就是消除不适应因素, 寻找一种适应复杂和变化环境的方式, 从而有力加快搜索过程。
遗传算法中染色体编码一般都是一个数组, 每次用适应度来对解进行优劣程度评估, 若合适即为最优解, 通过选择替换 (t+1) 次的迭代的群体, 否则新群体成员通过变异、杂交变化, 形成新的个体, 再继续通过适应度来选择最优解。
染色体编码通过把对象抽象成一定顺序的排列的串, 其中可以包含N个因素, P (p1, p2, p3, p4, p5…) 。若两个父代的基因染色体1 (a1, b1, c1, d1, e1) 和基因染色体2 (a2, b2, c2, d2, e2) 经过交换可能产生新的染色体 (a1, b1, c1, d2, e2) 。
遗传算子的操作算子包括选择、交叉和变异三种基本形式, 构成了遗传算法强大搜索能力的核心, 是模拟自然选择和遗传过程中发生的繁殖、杂交和突变现象的主要载体[2]。其中选择操作目的是为了避免基因缺失、提高收敛和计算效率。遗传算法有效性主要来自于选择和交叉, 尤其交叉起到了核心作用。
2实际排课问题分析和数学模型
所谓课表就是将课程、任课教师以及学生在合适的时间段内分配到合适的教室中。在高校中排课工作更加复杂, 会涉及任课教师、学生班级、学生人数、教室容量、教室类型等硬性要求条件以及单双周、必修、限选课、通选课、课程均匀分布、授课时间分布和教室之间间距等其他软性要求条件。必须遵守以下原则:
(1) 每位教师在同一时间段内只能安排一门课程;
(2) 每个班级在一个时间段内只能安排一门课程;
(3) 每门课程所用教室的类型和容量要满足该课程需求;
(4) 每个班级的课程只能安排一次, 不可以重复;
(5) 同一班级连续课程选择的教室距离应足够近, 保证学生可以按时到达;
(6) 同一教师连续课程选择的教室距离应足够近, 保证教师可以按时到达。
任何违反以上基本原则的排课都会导致冲突课程, 使教学任务无法进行。为了合理优化排课还应考虑以下因素:
(1) 每门课在一周的上课时间分布合理均匀;
(2) 尽可能使学生连续两门课间更换教室次数少;
(3) 尽可能把同一门课程安排在同一教室;
(4) 每天必修课平均;
(5) 尽可能满足教师的特殊上课时间要求。
通识教育实际问题中会有两个班级或多个班级合在一起上计算机文化基础, 需要重新进行班级 (Class) 编码。比如2010级海洋技术1班为20100080201, 2010级海洋技术2班为20100080202, 合班在一起上课要重新按课程序号编码, 例如01年计算机文化基础01班, 则为01 (年) 28122490 (课序号) 01 (班) 。
3染色体编码
在遗传算法中排课染色体编码是关键步骤, 设置最初种群, 以春秋学期限选、必修课为例, 先设置25个时间片, 每天5个, 5天教学时间单位, 在这25个时间片中加入教室、教师、班级等信息, 就可以看作是基因, 每个记录代表一个班级的课程表, 把它们看作是染色体。通常把教室编码先放入字段中, 通过设置随机函数产生1~25间的数值作为时间片, 若产生冲突即有相同数据, 需要重新产生直到教师编码无重复为止。编码结构为教师序号+班级编号 (有可能非自然班级而是合并上课的新班级) +课程序号。染色体编码见图1:
因为排课系统是一个典型的NP问题, 所以无论什么方法都没有办法避免冲突产生, 同一教师在同一时间段排了两门课程就是最为明显的问题。为避免产生这类冲突, 在系统中必须设置冲突检测函数, 但产生新的编码后, 系统会利用检测函数对按教室、时间、课程、班级一一对安排的课表进行冲突情况检测并改正及报警提示。
4排课问题的算法
排课的情况非常复杂, 对于这些冲突进行如下分析。
第一, 将模型中的五个集合降为一个给定四维空间的V (S, T, R, C) , 称之为课表。其中S (教师) :学校所有任课教师;编码根据院系专业进行排序, 904001为信息工程学院计算机系排序第一的老师。T (时间) :上课的时间片, 每天分为1-2、3-4、5-6、7-8、9-10, 总共五个时间片, 每学期16周*5天/周, 共有400个上课时间片;R (教室) :学校所有可用教室, 包括教室大小、是否为多媒体或语音教室等, 编码01为普通教室, 02为语音教室……比如030001为多媒体教室排序第一的教室。C (班级) :新学期所有教学班级, 包括班级人数、是否合班等。
第二, 在课表V中求解存在着四维向量l (Sr, Tm, R, C) , 且l∈L, 那么称l为课。
5结语
多因素优化决策问题的排课使用了以上方法在实际中的应用效果显著。在使用遗传算法优化后的实际效率得到极大提高。适应度函数的设立可以能够很好反映排课的需求, 随着进化次数的迭代而呈不断上升趋势。染色体方面还应考虑更复杂的情况, 以满足课程排课要求。
参考文献
[1]刘勇, 康立山, 陈屏.非数值并行算法-遗传算法[M].北京:科学出版社, 1998.
[2]李敏强, 寇纪淞, 林丹, 等.遗传算法的基本理论与应用[M].北京:科学出版社, 2002.
[3]高喜玛, 张萍.大学自动排课系统内核算法设计[J].南阳师范学院学报, 2003 (12) .
[4]常洪江.遗传算法综述[J].电脑学习, 2010 (3) :115-116.
[5]刘立平, 牛熠.遗传算法综述[J].东莞理工学院学报, 2005, 12 (3) :48-52.
[6]Cantú-Paz E.A Summary of Research on Parallel Genetic Algorithms[D].Illinois:University of Illinois at UrbanaChampaign, 1995.