基于C#运用遗传算法的排课系统概要_基于c
基于C#运用遗传算法的排课系统概要由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“基于c”。
第18卷 V01.18 第12期 No.12 电子设计工程
Electronic Design Engineering 2010年12月 Dec.2010 基于C舟运用遗传算法的排课系统 王军.陈建云
(南京信息工程大学计算机软件学院,江苏南京210044 摘要:排课问题是典型的组合优化和不确定性调度问题,并且是NP完全问题。随着高校的发展,在教务管理系统中 使用的排课模型也变得越来越复杂,针对遗传算法排课中存在的初始解生成不合理及一周多学时课程不好安排的问 题,为了避免同一门课程在一周内的不合理上课情况。针对这种情况。给出了排课问题的数学模型.提出了基于C群运 用遗传算法解决方案。结果表明,该算法能比较有效的解决排课问题。该方法易于学习和应用,且不毖依赖特殊的实 现模式。
关键词:排课;数学模型;C#;遗传算法
中图分类号:TP3ll 文献标识码:A 文章编号:1674—6236(201012—0085加3 Apply genetic algorithm to design timetabling system based on C sharp WANG Jun,CHEN Jian—yun(Department ofComputer Science and Technology,Nanjing Univers以ofInformation Science&Technology,Nanjing 210044,China
Abstract:The problem of timetabling system is the typical of combinatorial optimization and uncertainty,and it also is NP--completene problem.With the development of colleges and universities,the cla arrangement model is also becoming more and more complicated in the educational administration system.In view of this situation.the paper presented the mathematical model of the problem,and proposed solutions to apply genetic algorithm based on C sharp.The results show that the algorithm c肋solve the timetabling problem effectively.This method is easy to learn and apply.And it does not need any special realization model.Key words:timetabhng;mathematical model;C群:genetic algorithm 随着高校的发展,课程安排已成为教务部门头痛的事 情,经常会出现课程排列冲突,比如:一个教师在同一时间上 两门课,有两个教师同时去一个教室上不同的课程.有些教 师在特定时间不可以上课但却安排有课。如果没有很好地解 决这些冲突,必将产生教学混乱等现象。可见,排课算法的正 确性、高效性是非常关键的。
1排课问题的数学模型
学校排课问题本质上是时间表问题的一类典型应用实 例.是为了解决课程安排对时间和空间资源的有效利用并避 免相互冲突。在排课过程中,需要考虑课程教学效果、满足教 师特殊要求等多项优化指标,将各门课程安排到相应的时间 和教室需要付出一定的成本。
1.1符号与约束条件
设课程集合:P-{pl,p2,...,P。,...,p.I;教师集合:肘={m-, m2,...,nap,...,mPI;教室集合:S=f8l,s2,...,吼,...,sK};班级集合: C=fcl,c2,...,c……cNl;时间集合:r={tI,t2,...,td,...,tDI;时间与 教室对的笛卡尔积为:G=T・S=(tI,SI,(tl,s2,...,(tD,SK;G中
收稿日期:2010--05—26稿件编号:201005094 的元素称为时间教室对;课表问题的求解过程就转化成为每 一门课程寻找一个合适的时间教室对。
排课过程中必须满足各种约束条件.各种约束条件可以 归纳成2类,这样能简化分析过程。
1.1.1硬约束条件
硬约束条件是在排课过程中由于各类资源的有限.因此 必须满足而无法变更的约束条件,通常只要满足下面3类硬 约束条件就能够保证在排课的过程中不发生此类冲突。1同一时间,一个教师只能上一门课程,记为X1,且Xl ≤l,其中:p=l,...,P;d=l,....D。当XI=I时,教师‰在时间 td和教室敏上课pm;当J1=o时,不成立。
2同一时问。一个班级只能上一门课,记为X2,且X2≤ l,其中:n=l,..，N;d=l,...,D。当X2=I时,班级C。在时间td 上教师lIIp的课程pm;当X2=0时,不成立。
3同一时间.一个教室只能上一门课,记为X3,且X3≤l,其中:k=l,...,K;d=l….,D。当X3=l时,教室st在时间td 由教师IIlp上课程pm;当X3=0时,不成立。
1.1.2软约束条件
软约束条件是在排课过程中可以满足又可以不完全满
作者简介:王军(1970-一,男,安徽铜陵人,教授。研究方向:软件工程、CSCW、信息系统应用。
—-85..万方数据
《电子设计工程2010年第12期
足的约束条件,是排课过程中在满足硬约束条件的基础上能 尽量要求满足的约束条件。软约束条件会因不同的教学情况 而有所差异。通常也可以通过调节软约
束条件的满足程度而 改变排课的效果。可以将一定要满足的软约束条件转换为 “硬约束条件”。
以下是排课过程中常用的软约束条件: 1教师①老师一天之中连续上课节数;②老师课程大 部分在上午或下午;③总学分为奇数的课程一次连上三小 节;④早上8点(第一节是否排课;⑤下午4点以后(最后 一节是否排课;⑥中午12点(第五节是否排课;⑦一门课 尽量分散在一个星期中。
2学生①中午(12:00尽量不要排课;(参上完体育课 尽量不要排课;③共同科目同班级一起上;④选修科目各班 级分开选课;⑤对于总学分为偶数的课程采取两学分课连 上;⑥对于总学分为奇数的课程采取三学分课连上;⑦学生 课表中的上课时间不能过分集中。应避免一天课程很满而另 一天却一整天没课的情况。
2排课问题的算法 2.1算法流程
遗传操作流程如图l所示。图1遗传操作流程图
Fig.1How chart of Genetic operation 2.2染色体编码
遗传算法(GA中首要考虑的是如何表现其问题,即如 何对染色体编码,使之适用于GA操作。在经典的遗传算法 中,常采用浮点数或二进制的编码方法,而研究中,每条染色 体代表每位教师的课表,其结构表示如图2所示。
图2课表用染色体表示的结构
Fig.2Structu陀of schedfle《chromosomes
班级ID染色体在程序中可用十进制数编码,例如:某一 个教师编号为1234,要教“计算机基础’’这门课,课程编号为 5678,周学时为4,班级为JSJ08001、JSJ08002,随机产生上课--86-时间,随机选择大于两班总人数的教室,则可生成染色体如:“JSJ08001JSJ***401224l”其中0240l,2241分别代表教室及上课时间星期二第二个教学单元(即上午3、4节和星期四第一个教学单元(即上午1、2节。
按如上编码,两条染色体对后9位作交叉操作,不会影 响到每位教师所教授的课程。也不会造成教师课表内含其他 教师的教授课程或每代演化后染色体结构不合理等同题。2-3初始种群生成一个染色体就是一个可能的排课结果.是一个mx26的 数组,需处理的数据量较大,结构相对比较复杂。如果初始 种群中个体的分布不好。将很容易使整个排课结果陷入局部 最优而得不到好的排课结果.因此初始种群的生成对整个算 法的影响较大。
2.4选择操作
在排课表问题中。选择操作方式采用轮盘赌方法。按照 轮盘中的比例进行区域的分配。适应度较高的方案占据区域 较大,选中的概率也较大,适应度低的方案占据区域较小,选 中的概率也较小。
2.5交叉操作
编排课时.根据点交叉算子的思想。可在P个开课时间 和教师课表中随机采样两个厶,对所有只和瓦的值进行互 换。将互换后的两个个体作为两个子代插入新种群。也可以 选择某个班级的课表TC和学生课表s。,对TC集合和S集 合中的所有时间安排进行互换。此时.交换的基因是若干个 ￡时间安排组成的集合。
2.6变异操作
变异虽然以很小的概率发生.但是它保证种群的多样 性。防止搜索得到的解陷入次优解。有效抑制遗传早熟现象 的发生。随机的方法可以保证个体的迥异,从而保证初始解 在解空间的均匀性。在变异操作中随机选择一个个体的基 因,这个基因可以是时间也可以是教室等,让它随机变换成 另一个时间或者教室.使其在原始空问位置做轻微扰动,有 利于搜索空间逐渐向全局最优空间靠拢。
2.7适应函数
编排课表主要将以下几方面因素作为排课表所要达到 的目标:教师对时间的期望满意度、教师课时分布密度、班级 课时日分布均匀度、大多数学生愿意上此节课的程度。将以 上4个目标分别赋予不同的权值蚍,运用线性加权法,得适 44 应函数为:F(茹=a∑WiXi,∑毗=1,Wa E【0,l】,a∈【o,11。式 ‘:I j=l
中,a代表可行系数,当进行交叉形成不可行的课表(出现了 教师、教室、时间等的冲突时,则该方案的适应度为O,在求 解过程中直接被剔除。由于在交叉过程中会产生许多适应度 为0的方案.所以采用随机生成初始种群的办法不断形成等 量的可行解,以保持群体规模,避免算法的过早收敛。
2.8停止规则
如果一轮适应度计算比较以后。利用轮盘赌的方法按照 万方数据
王军,等基于C#运用遗传算法的排课系统一定的概率进行选择操作,将适应度较高的个体选择出来, 在实际应用中也町能没有终止条件,目的是可以依次提供不 以便于保留优秀的个体为以后的操作,没有达到理想的状 同的可行解以供使用者选择直到所有解给完或者使用者终 态.则按照一定的交叉概率进行个体之间的交叉和遗传变异 止。如果只考虑最优解的问题,可以使用迭代的适应度几乎 操作,重组个体后再计算下一代的适应度。直到有一代的适 不变作为终止条件或者规定迭代次数。值得一提的是,有些 应度达到预期要求。如
果遗传的代数达到了最大数,则将结 实际问题的可行解可能是唯一的,比如教学场地或教师资源 果输出,若满足适应度.且各个约束条件都已经不存在冲突, 紧缺的情况,更严重的是如果约束条件太苛刻,甚至可能没 则认为排课结果比较合理,宣告遗传算法正常结束。有可行解,在此类情况下人工干预还是有必要的。系统结果展示
煮:曩.遗传算法的基本理论与应用【M】.北京:科学出版 开发排课系统。简要介绍C#运用遗传算法的实现过程。
在VS2005运行。生成主页面排课系统,有排课向导,如图3所示。然后输入教师lD号、教师姓名、所教课程与优先级排 课。输入完之后点击下一步,到最后有开始排课,就会给出排 课的各种方案。如图4所示。
图3排课系统主页面 Fig.3 Main page of timetabling system
图4排课后的方案 Fig.4 Scheme after the timetabling 4结论
该模型与求解方法已在实际中得到应用.取得了较好的 效果。在使用遗传算法优化后排课算法的实际效率有极大的 提高。因此用遗传算法实现类似排课问题的最优解也是一种 比较简单实用的方法。收敛速度很快,时间段分配均匀。但是
社.2002.【2】韦玉,冯速.免疫遗传算法在排课问题中的应用叨.北京师 范大学学报,2008。44(2:168—172.WEI Yu。FENG Su.1he印plication of immune genetic algo-rithm int the proble of timetabling[J1.Journal of Beijing Normal University。2008,44(2:168—172.【3】魏平熊,伟清.用遗传算法解组卷问题的设计与实现明.微 电子学与计算机。2002,8(4:44—50.WEI Ping-xiong,WEI Qins.Test paper problem solving by generic algorithm【J】-Microelectronics&Computer,2002,8(4:4和50.【4】4 Salem M,AIYakoob,Hanif D S.A mixed-integer program— ming approach to a cla timetabling problem:a case study witll gender policies and traffic considerations【J】.European Journal of Operational Research。2007(180:1028.【5】膝姿,邓辉文,杨久俊.基于遗传算法的排课系统的设计与 实现【J】.计算机应用,2007,27(12:199—201.QI Zi,DENG Hui—wen,YANG Jiu-jun.Timetabling system’s
design and implementation based on the genetic algorithm[J1.Journal of Computer Application,2007。27(12:199-201.【61陈静.自动排课系统算法的分析与设计叨.科技情报开发 与经济,2007。17(34:217—219.CHEN Jing.Analysis on and design of the algorithm of the auto-arranging curriculum system[J].Sci-techinformation dev-elopment&economy。2007,17(34:217-219.【7】唐慧丰.遗传算法原理与应用[EB/OL].(2006-05—20 [2010-03—20I.http://wenku.baidu.com/.一87— 万方数据
基于C#运用遗传算法的排课系统
作者:王军 , 陈建云 , WANG Jun, CHEN Jian-yun 作者单位:南京信息工程大学,计算机软件学院,江苏,南京,210044 刊名: 电子设计工程
英文刊名:ELECTRONIC DESIGN ENGINEERING 年,卷(期:2010,18(12 参考文献(7条
1.李敏强.遗传算法的基本理论与应用[M].北京:科学出版社.2002.2.韦玉,冯速.免疫遗传算法在排课问题中的应用[J].北京师范大学学报,2008,44(2:168-172.WEI Yu,FENG Su.The application of immune genetic algo-rithm int the proble of timetabling[J].Journal of Beijing Normal University,2008,44(2:168-172.3.魏平熊,伟清.用遗传算法解组卷问题的设计与实现[J].微电子学与计算机,2002,8(4:44-50.WEI Ping-xiong,WEI Qing.Test paper problem solving by generic algorithm[J].Mieroelectronies & Computer,2002,8(4:44-50.4.Salem M,AIYakoob,Hanif D S.A mixed-integer program-ming approach to a cla timetabling problem:a ease study with gender policies and traffic considerations[J].European Journal of Operational Research,2007(180:1028.5.膝姿,邓辉文,扬久俊.基于遗传算法的排课系统的设计与实现[J].计算机应用,2007,27(12:199-201.QI zi,DENG Hui-wen,YANG Jiu-jun.Timetabling system's design and implementation based on the genetic algorithm[J].Journal of Computer Application,2007,27(12:199-201.6.陈静.自动排课系统算法的分析与设计[J].科技情报开发与经济,2007,17(34:217-219.CHEN Jing.Analysis on and design of the algorithm of the auto-arranging curriculum system[J].Sci-techinformation dev-elopment & economy,2007,17(34:217-219.7.唐慧丰.遗传算法原理与应用[EB/OL].(2006-05-20[2010-03-20].http://wenku.baidu.com/.本文链接:http://d.g.wanfangdata.com.cn/Periodical_dzsjgc201012024.aspx
