智能排课系统范文（精选9篇）
智能排课系统 第1篇
本文研究了科学编排课表所需要遵循的原则和编排课表所涉及的各种因素、问题,总结出了在课表编排中所出现的各种时间、空间资源的冲突。根据课表编排的特点,以优化时间和空间两种资源为目标,采用分治法、贪婪方法、回溯算法的主体思想[2],结合优化算法,设计了智能排课系统。
1 课程编排准备
1.1 信息的录入。
根据计算机学院的具体情况,针对排课系统进行了以下信息的采集:院系信息,教学楼信息,教师信息。院系信息包括:所属的年级,教学任务。教学楼信息包含:教室个数,教室位置信息,教室的容量。教师信息包含:教师可以教授的课程,教师的人数。
1.2 教学任务、时间片和时空片。
一门课程的每个教学班为一个教学任务,每一周次可以编排课程的每个节次为一个时间片,即时间片是个三元组([周次、星期几、节次])[3]。称课程任务的时间片及对应的上课地点为时空片。之所以把时间片精确到某一周次,是因为在实际情况下高校每学期各课程的起止周不完全一样,例如计算机科技1班1~6周上“编译原理”,7~12周上“计算机系统结构”,假设这两门课程的其他上课要求均相同,那么完全可以将这两门课安排在一周内的同一个时间段,例如,前6周上“编译原理”,后6周上“计算机系统结构”。如果时间片没有精确到周次,而仅仅是个二元组([星期、节次]),就无法做到这一点,不能充分利用宝贵的时间资源。
1.3 排课的原则。
在课程编排的过程中,必须严格遵循以下三条基本原则[4]:a.每个教室在一个时间片最多只能有一个教学任务;b.每位教师在一个时间片最多只能有一个教学任务;c.每个行政班在一个时间片最多只能有一个教学任务(“全校公选课选”除外)。
2 排课算法设计
排课问题的关键是所使用的排课算法。主要的排课算法有:启发式算法、遗传算法、人工智能应用、蚁群算法、分组优化算法、约束满足方法、数据挖掘相关算法等[5]。
本排课系统采用分治法、贪婪算法、回溯法三者的思想,结合优先级算法,进行整个排课算法的设计。
分治法即分而治之,算法设计思想是,将原问题划分为规模较小、相互独立、与原问题形式相同的子问题,先求出子问题的解,然后将各子问题的解合并成原问题的解。这样就可以把一个大的复杂的问题,分解为小的容易解决的问题。
贪婪算法的算法设计思想是分阶段工作,在每一个阶段选择局部最优解,以当前情况为基础作最优选择,而不考虑各种可能的整体情况。贪婪算法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
教师、教室、班级的排课类似于贪婪算法中的机器调度问题。n门课程相当于n个任务,这n个任务由教师、教室、班级协同完成。每个任务的开始时间为si,完成时间为fi,si<fi。[si,fi]为处理任务i的时间范围。一个可行的任务分配是指在分配中没有两个重叠的任务分配给同一个教师、教室或班级。因此,在可行的分配中每个教师、班级或教室在任何时刻最多只处理一个任务。最优分配是指使用的教室、班级或教室资源最少的可行分配方案。
应用贪婪方法获得最优分配方案,首先将按任务开始时间的非递减次序进行排序,其次要按顺序逐步分配任务,若已经至少有一件任务分配给某个资源,则这个资源的状态变为已用;否则就是示未用的。在选择资源时,采用以下贪婪策略:根据欲分配任务的开始时间,若此时有已分配任务的资源可用,则将任务分给它。否则,将任务分配给未用的资源。
回溯法是在包含问题的所有解的解空间树种,按照深度优先搜索的策略,从根结点出发搜索解空间树。搜索到解空间树的任一结点,总是先判断该结点是否满足问题的约束条件。如果满足则进入该子树继续深度优先搜索,否则,逐层向祖先结点回溯。
可用回溯法求解的问题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的一个解。
智能排课算法,首先根据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后,依据贪婪法的算法思想,在时间分配时,总是在尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时,会向上回溯搜索到发生冲突的最近一个记录,然后对它进行重排以解决冲突。
3 智能排课系统的实现
智能排课系统分为输入模块,处理模块,输出模块三部分。
输入模块:用结构体的形式存储课程信息,将多种信息组合在一块形成一个特殊的元素体,进行存储,使排课处理过程能够快速的检索出符合条件的信息。具体输入数据存储在Excel表格中,包括教师信息表、班级信息表、教室信息表、课程信息表。
处理模块:自动排课,先对输入的信息及约束条件进行判断,然后开始进行预排序,在检测排出的课表是否符合需求。符合则将排出的课表传给输出模块;不符合,返回上一步,重新进行最后一步的排序,在检测排出的新课表是否符合需求,符合则将排出的课表传给输出模块;不符合在重复上一次操作,逐步向上回溯,直到解决问题为止。
输出模块:对排课模块处理生成的课程表,进行整理分类,将整理好的课表输出。班级课表,教师课表,教室课表,以Excel的形式输出。
结束语
基于VC++的智能排课系统在Windows 7操作系统上,选用VS2013为开发环境,使用C++语言进行开发,针对二级学院排课过程,实现了自动排课功能。该智能排课系统,降低了排课人员的工作量,同时考虑到每学期的课程尽量平均分配给各位教师,提高了排课管理工作的效率。
摘要：针对学院教室资源短缺问题,本文设计了一种基于VC++的小型智能排课系统。主要解决的问题是给学校教学计划中设置的课程安排合适的时间和地点,也就是给每个班的课程安排时间、地点、任课教师等。避免教师、班级在上课时间、地点上的冲突。主要采用分治法、贪婪法、回溯法来进行自动排课功能的求解及优化。
关键词：回溯算法,分治法,贪婪算法,排课问题,组合优化问题
参考文献
[1]刘敏娜,李延香.基于B/S的排课系统的设计与实现[J].电脑知识与技术,2015,11(6).
[2]高明芳,赵敏.高校自动排课系统排课算法的研究与设计[J].电脑知识与技术,2010.10,6(9).
[3]潘以锋.高校智能排课系统的算法[J].上海师范大学学报(自然科学版),2006,10,35(5).
[4]赵陶钰.基于JAVA EE的排课管理系统的设计与实现[J].电脑开发与应用,2015,26(3).
智能排课系统 第2篇
每个新学期开始，对于学校教务科来说首要而急需完成的任务是：如何合理而高效的排课。其本质是将课程、教师和学生在合适的时间段内分配到合适的教室中。但由于涉及到的问题较多，同时学校扩招，学生和课程数量比以往大大增加，教室资源明显不足，在这种情况下排课很难在同时兼顾多重条件限制的情况下用人工方式排出令教师和学生都满意的课表。
虽然排课问题很早以前就成为众多科研人员和软件公司的研究课题，但是真正投入使用的排课软件却很少。原因是多方面的，其中算法的选择是最关键的一个问题，S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题，即若是用“穷举法”之外的算法找出最佳解是不可能的。然而由于穷举法成本太高，时间太长，根本无法在计算机上实现。如果假设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制情况下，能够推出的可能组合就有nm*k种，如此高的复杂度是目前计算机所无法承受的。而遗传算法的出现正好解决了排课在算法上的问题，可以很有效的求出最优解。轻松而快速的解决了困扰教务科的一大难题，能在短时间内排出符合各项条件的课程表。国内外研究现状
计算机排课问题是一个多目标，有限资源，带有模糊约束条件的组合规划问题，是计算机应用领域一个具有代表性的问题。20世纪60年代末，Gotlieb.C.C教授就对课程表问题进行了形式化描述。随后，此类研究发展起来。70年代中期，S.Even等人就论证了课表问题是NP完全类问题，将该问题理论化，同时也说明课表问题有其自身的理论化模型，即课表问题存在解。并且能找到解。但是根据计算和难解性理论，目前还没有解决NP完全类问题的多项式算法。到1979年，Schmit 和Strohein在文献中就列出了 300多篇已发表的文献。近年来研究这一问题的人员不断增多，国外的运筹学杂志几乎每年都有相关内容的文章那个发表，此外它还广泛的出现在计算机，应用数学，教育管理等杂志上。80年代初，我国的很多大学也开始研究排课系统软件。大体上说这些排课系统软件可以分为两大类：第一类以所谓班——教员模型为主，它是在Gotlieb.C.C工作的基础上发展起来的。主要讨论此模型的定义扩充，解的特性及分析，不断提出新的猜测和推论。基本模型变化不大，并且这类模型适合课程长度一致，无合班教室的情况，并不适合一般院校的实际情况。第二类事所谓的课程调度问题，多于图的节点的着色问题有关，模型一旦产生，它的变量往往太多，规模太大，此外根据具体的校情对模型提出的各式各样要求对模型影响较大，有的甚至没有具体的模型可寻。通过对资料的查阅发现以往对课程问题的研究多侧重于自动生成，难度较大实现不易，往往是理论研究上的工作多，而实际应用方面的工作很少。有一些实际的例子，也往往是特定条件下对实际情况简化得到的，至今还没有自动生成可课表系统的软件应用于实际。对计算机而言，不像人工编排那样可以对任何情况进行合理的取舍，因此不存在完全冲突的课表很难排出来。
国内高校排课系统中，大连理工大学是从事此类软件开发较早单位。1987年该校开发了《教学组织管理及课程调度系统》1.00版本，之后在此基础上又推出了《教学组织管理及课程调度系统》2.00版本，1902年又推出了《教学组织管理及课程调度系统》2.01版本和安排考试补考的《考试调度系统》。1994年又推出了《教学调度系统》2.20版本。1998年 年推出的在Windows下运行的3.00版，现在在各大高校使用比较多，反映较好的有大连理工大学开发的系统和清华大学开发的《综合教务排课系统》，以及北京大学开发上的一套比较新的排课管理系统。
3毕业设计论文的主要内容
1.遗传算法的形成及基本应用，遗传算法的基本实现技术和特点。
2.排课中所要考虑的约束条件，课表编排的基本规则和课表编排中存在的矛盾和问题 3.将遗传算法应用于排课系统；
4.所采用的方法、手段以及步骤等
1.详细了解课表编排中存在的矛盾和课表编排的规则，将其逐条列举出来，选取必须兼顾的重要的约束条件，2.分析学生，教师，课程，教室之间的关系建立概念模型和逻辑模型 3.产生初试种群
4冲突检测和消除：对各种冲突进行检测，如有冲突则消除它 5计算适应度函数 期望值
6遗传操作包括选择 交叉 变异 7可行课表的生成
5.阶段进度计划
第一周——第三周：查阅资料，学习遗传算法的基本理论，查阅相关文献完成 开题报告
第四周——第五周：详细学习遗产算法，并对所做课题进行详细构思
第六周——第七周： 完成英文资料的翻译
第八周——第九周 ：分析调查排课问题所面临的具体问题和矛盾以及缩影可考虑的因素，分析找出座位乖蹇的约束条件
第七周——第九周：对各个模块进行设计 第十周——第十一周：对各个部分进行分析完善 第十二周——第十三周：撰写论文
第十四周：完成PowerPoint制作的论文答辩电子稿
第十五周——第十六周：论文答辩 6参考文献
智能排课系统 第3篇
关键词：SSH框架,排课算法,用户体验
机房排课需要完成的任务包括[1]:1)按照正常的课表计划,安排常规课的机房实验课程。此部分排课由管理员操作,计算机软件辅助完成。2)依据实践环节的计划,安排课程设计的机房课表。此部分排课由计算机软件自动完成,自动产生机房课表。3)管理员可以方便地进行C/S模式的各类查询;机房课表用Excel电子表格输出。4)教师、学生可以方便地进行B/S模式的各类网络查询。5)对理论总课表、每周的理论课表调整作相应处理。6)对原始数据进行修改、删除、增加等操作。这样不仅减轻了机房管理员的工作量,而且让排课过程变得更加公平和便捷。同时考虑到排课过程有可能产生冲突,因此提供了相应的可视化操作使管理人员人工参与,规避冲突,更好的实现排课。
本文利用目前J2EE领域中比较流行和热门的SSH(Struts2.1+Spring3.0+Hibernate3.3)架构技术进行开发设计排课系统[2],能够保证系统架构的灵活性和健壮性。整个系统分为表现层、中间层(业务逻辑层)和数据服务层(见图1)。三层体系将业务规则、数据访问及合法性校验等工作放在中间层处理。客户端不直接与数据库交互,而是通过组件与中间层建立连接,再由中间层与数据库交互。
1 排课系统功能设计
在文献[1,2,3,4,6]基础上,文中结合学校自身特征,排课系统功能设计,如图2所示。系统具备的特征包括:1)系统采用基于图论的启发式排课算法,能够为管理员提供一个比较合理的排课安排建议,管理员在这个建议的基础上还可以进行人为的手工调整,达到合理安排的目的;2)系统与用户交互的接口十分良好,不需要有很高的专业知识水平,整个排课过程可以再拖拉操作中完成;3)可以为各种角色的用户打印出Excel报表,方便用户统计和分析;4)系统前台于后台采用Ajax方式交互,保证了系统的用户体验;5)系统使用可多个目前流行的各类框架,例如jQuery,Log4j,Flexgrid等[5];6)系统具有良好的扩展性,稍加修改可以扩展为教室或者其他学校的排课过程;7)系统框架设计模块独立性强,还可以增加学生模块,使得学生可以预定课外使用机器。
其中,系统的核心是排课过程的实现。系统用户可以提出机房使用申请,申请的过程需要填写一些相应的信息,例如:课程名称,人数,课程时间,课程备选时间,优先级等等。等各个用户都提交完自己的申请后,管理员可以对用户的各个申请进行排课。排课的过程分为机器自动排课和手动调整课程这两个过程。在机器自动排课过程中,系统主要是使用一个基于有向图的启发式排课算法。算法的大致流程是这样的:首先系统将所有课程按照各自的首选安排时间和备选安排时间放入一个二维表中。然后检查表格每个单元格的安排,如果有课程安排冲突,则立即以当前检查到的冲突课程为图的一个结点,根据课程的备选时间,建立起一个有向图。这个图中每个结点的权值就是其课程的优先级。然后根据优先级对课程进行调整,实在无法调整的课程放入不能安排的课程链表中,由用户解决这个冲突。重复这个过程直到整个图的每个结点都没有冲突。然后再考察二维表的其他单元格,重复操作,直到所有单元格都无冲突,结束排课过程。接着,系统将排课信息反馈给用户,供用户手工调整,用户手工调整完成后保存到数据库和生成excel排课表。这时普通用户也可以查看相应的机房课程安排。整个排课过程结束。具体排课算法流程如图3所示。
2 基于SSH排课系统实现
根据图1SSH架构,排课系统的的程序代码结构如图4所示。页面总体分为三个框架:1)框架滚动显示通知公告区域,中间有两个圆点,点击左边的圆点就会滚动显示通知,点击右边的圆点就会滚动显示公告;2)左边的框架是按照功能类型划分的所有功能菜单,击功能类型右上角的圆形按钮可以隐藏或者显示其下的功能。3)下面的框架包含退出系统的功能。点击红色的退出按钮,将出现和WINDOWS XP系统一样的退出菜单。其中客户端和管理实现界面分别如图5和图6所示。
3 结束语
本系统是为学校机房排课而设计开发的,整个系统从两类角色去进行功能划分和数据共享,前台提交申请,后台管理员排课,从申请到排课全部可以在线完成,提高了效率和减少了人力资源,同时还提供用户登录安全和操作的日志管理,提高了系统的安全性。另外该系统设计的时候充分考虑到可扩展性,一方面我们使用了最新的SSH架构,使得开发的各个功能模块耦合度降到最低,便于增加新的模块;另一方面虽然学校的机房和学院数目是固定的,但是我们依然开发了机房管理,账号管理等功能模块,使得系统扩展性进一步加强,因此可以推广到一般机房排课的应用中去。同时,还使用了各种Web控件和Ajax等技术使得页面具有一定的观赏性,提升用户体验。
参考文献
[1]彭复明,孟庆杰.高校机房自动排课系统的设计与实现[J].广东水利电力职业技术学院学报,2007,5(4):68-70.
[2]邓子云.精通J2EE网络编程[M].北京:清华大学出版社,2007.
[3]陶宁,栾方军,徐力.基于JSP的机房排课系统的开发[J].现代计算机,2007,267(9):103-104.
[4]杨名念.Ajax技术在机房排课系统中的应用[J].电脑知识与技术,2009,5(19):5193-5195.
[5]Bibeault B,Katz Y.jQuery实战[M].北京:人民邮电出版社,2009.
智能排课系统 第4篇
【关键词】教务管理系统；排课子系统；学分制；数据库设计
1.需求分析
该课题是根据学分制教务管理的特点以及国家和教育厅各部门有关教务管理的规定组织开发的一个管理信息系统，具有教务网络管理的规范性、科学性、及时性等特点，可以完成高校教务管理的计划、组织、运行、评价、统计等多种功能，能够满足和适应高等职业院校的教务网络管理需求。另外鉴于各高职院校的管理模式均有一定的特殊性，所以该系统将留有一定的调整空间和余地，使该系统有较大的推广价值和应用价值。
2.总体设计方案
2.1 开发模式
本系统使用B/S模式的开发方案，WEB服务器采用Windows2003 Server+IIS，数据库服务器使用Microsoft SQL Server2000，用ASP和Dreamweaver作为客户端开发工具，使用到的CASE工具有Microsoft Visio2003，Microsoft Project2003。
排课是一个设计多种因素的动态组合规划问题，它要保证各种教学资源不产生冲突，并且要满足教师的要求和教室资源等方面的约束条件。目前国内外常用的排课算法主要采用遗传法、模拟退火算法、专家系统方法、回溯算法、优先级算法等。根据高职院校网络教务管理系统的功能，对排课问题进行了一般描述，提出了改进的排课策略。
2.2 系统网络平台
本系统是在学院原有教务管理系统基础上进行开发的，原有系统为本系统提供了很多现成的比较规范的技术文档、数据资料；学院领导、教务处及各系部对本系统的开发给予了高度的重视和大力的支持。这些为本系统的实现提供了保障。
本着节约的原则，新系统基本沿用原有系统的软、硬件设备、网络设备，新系统的只需要增加一台数据库服务器、一台WEB服务器、一台应用服务器；另一方面，本系统采用的主要是自主开发的方式，因此大大降低了系统的开发费用。系统的运行和维护将由本学院的相关教师承担，所以系统的运行和维护费用也很低。
本系统采用如下网络拓扑结构，如图1所示：
l)内部局域网与外部Intemet站点之间通过数据交换器交换数据，既保证内部办公网数据安全，外部站点又可以与内部系统进行数据交换。
2)外部站点有独立的域名，可以通过校园网间接接入因特网，也可通过其它方式直接接入因特网。保证站点能接受外部用户不间断访问。
3)其它校区、院系教学点的局域网用户可以通过拨号接入局域网办公。
本系统采用三层网络体系结构，B/S/S(浏览器/应用服务器/数据服务器)模式。相比传统B/S模式，三层/多层模式多了一个中间层服务器。中间层服务器呈组件形式，封装了所有的业务规则。使得当业务发生变化时，只需改变服务器组件，前端客户端和后端数据库服务器无需作任何变动，便于维护和易于扩展。
2.3 系统设计与实现
排课是落实教学任务、实施教学活动的依据。因此排课是学校教学管理中十分重要，又相当复杂的管理工作之一，是为学校所设置的课程安排时间和地点，合理配置教师资源，使整个教学能够有计划和有秩序地进行。排课管理子系统提供智能排课、辅助调课和课表查询等功能模块，智能判断各种冲突条件并以直观方式显示，并提供时时“空闲班级”、“空闲教室”、“空闲教师”查询，使课程的安排更加人性化和合理化。排课子系统主要功能模块有：初始参数设置、排课数据管理、自动编排课表、排课漏课处理、课表调整处理、课表冲突检查，下面对各模块的界面和技术实现给予详细的叙述。
一般地，对排课问题描述如下：
(l)定义课程实体型：Course（课程编号，课程名称，教师姓名，教学班编号，上课时间片，上课人数，教室类别，周学时，课程类别），则所有待排课程可以表示成该课程实体型的一个实体或元素。
(2)定义时间片：将每周的上课天数Days、每天上课节数Chapt、每节课的时间Times规定好，时间片即为上课的单元，可以一节一个时间片，也可以两节、三节组合成一个时间片，用Tij表示，i表示每周上课的第i天，j表示每天上课的第j个时间片。
(3)那么排课问题就可以描述为：按照一定排课算法或策略，将待排课程集合。
Course中的每个元素，赋予一个合理的、符合约束条件的时间片Tij。
研究排课问题，解决排课系统的最终目标是给出排课问题的最优解，相当于将教师任教的课程填充到设置好的时间片上，一般情况下排课问题总有解。许多研究者提出了一些基于某个初始解，通过迭代求最优解的算法，但算法的时间复杂度是课表规模的指数级，实现有一定的难度，因此求最优解仍是理论上的。如果排课结果满足了所有的约束条件，那么它至少是次优解。
为了降低排课问题的复杂度，以求得次优解(满意解)为目标，在课程的编排中应遵循一定的规则(约束条件)，只有按照基本规则来进行课程的编排才能够减少冲突的发生，这些基本规则主要有以下几条：
1)一个教师在同一天同一个时段内不能安排两个班的课。
2)一个班级在同一天同一个时段内不能安排两门课。
3)一个教室在同一天同一个时段内不能安排两个班的课。
4)教室的容量必须大于所上课班级的学生数。
5)一个班在同一天里不能重复上一门课。
6)一个教师一天内所上的课不能超过规定的节数(如6节)。
依据以上这些规则，对排课时可能遇到冲突进行分类，可以分为两大类：
硬冲突：包括规则1)、2)、3)、4)所引起的冲突，发生这些冲突，教学工作将无法正常开展，因此这类冲突必须要避免。
软冲突：包括规则5)、6)所引起的冲突，发生这些冲突会影响教学效果，所以这类冲突不一定非要避免。
具体实现算法如下：
(1)确定待排教师。根据排课计划，按教师的周课时总数、班级类型、未排课时数降序排序，逐个对任课教师排课。合班课、课时多的教师排课优先。
(2)初排。从第一个教师的第一门课的第一个任课班级开始，动态建立教师、教室、班级的空闲时间数组，检测空闲时间，分类处理约束条件，确定排课时间片，记录排课结果。
(3)排平行班。再考虑另一个平行班的排课，先检测另一班的相关空闲时间，分类处理约束条件，确定排课时间片，记录排课结果。若有多个平行班，继续第3步，如无平行班，则转第4步。
(4)下一轮排课。进行该课程的下一轮排课。体现均匀排课原则，排课间隔天数为T，记录排课结果。一般地，当第一轮排课在周I后，下一轮排课应在周(I+T)以后排课。
(5)下一轮平行班排课。同第3步。
(6)重复第4、5步，直到该教师该门课程的未排课时全部为0。
(7)重复第2一6步排该教师的其他课程和其他教师的课程。
在排课中“记录排课结果”，包含将排在Tij时间片上的课程、任课教师、教学地点等信息分别记录在相应的表中，修改空闲时间数组，并将最近排课的信息标记，以便在出现冲突时，进行回溯重排。按照上述排课策略，得到的满足给定约束条件的课表一定是次优解（目标解）。
3.结束语
通过这套系统，将学院还停留在非网络化办公的模式上的教务流程进行设计重组，使教务管理流程适合网络化办公。通过专门开发的接口，将学院原有的教务系统与新开发的网络教务管理系统成功集成。成功实现了学分制下的排课系统，为学院教学资源的合理、有效的利用创造了条件。
参考文献：
[1]王树利.教务管理排课软件的系统设计[J].华东船舶工业学院学报(社会科学版),2003,6.
[2]鲍嘉,马永强,卢坚.Dreamweaver8完美网页设计[M].中国青年出版社,2006.
[3]于鹏.VBScript/ASP网页设计语言教程[M].电子工业出版社,2004.
[4]郭玲.ASP在排课系统中的应用[J].科技信息,2007(15).
[5]张光慧.高等教育信息化的概念和教育信息化的内涵[J].教育信息化,2005,2.
遗传算法在智能排课中的应用研究 第5篇
近年来, 随着高校新生的扩招力度加大, 专业设置、课程设置不断向深度和广度发展, 各高校都面临着教室资源紧张的问题, 要在每个学期末的一个短时间内拿出一份涉及到有关全校教室统调的课表来, 对高校的教务处来说是一个很艰巨的任务。课程表是一个学校日常教学工作和其它各项活动的指挥调度表。它不仅是学生和教师上课的依据, 而且对学校其它工作的统一安排也有直接影响。现在大多数院校的排课方法是手工编排方法, 它主要通过人智能的判断和协调来完成的。而手工排课不可避免的工作繁琐, 工作量巨大, 效率低下的缺点也就越来越突出了, 同时手工操作也不易于充分利用资源满足经常变化的需求。笔者因工作原因而深知排课的复杂性, 主要是因为安排课表是一个具有不确定性、非线性的、有约束的、多目标的组合优化问题。
在计算机技术日新月异的今天, 用计算机代替劳动强度大、工作效率低的手工排课工作, 越来越成为教学管理之中迫切需要解决的研究课题之一。由于计算机具有运算速度快, 处理能力强等特点, 很自然地进入到教务“排课”这一应用领域中。所谓计算机排课, 就是把排课问题化为计算机应用领域的有约束的时空组合优化问题进行求解。当前优化领域, 对有约束的组合优化问题的求解, 效果较好的是基于自然选择和基因遗传的遗传算法 (Genetic Algorithm, GA) 。该算法目前已被大量用于求解组合优化问题, 且效果非常好。因此, 利用遗传算法解决复杂的智能排课问题具有很高的研究价值, 且实现起来可行性较高。
1 GA优化算法
遗传算法 (Genetic Algorithm-GA) 是在模拟自然界生物的进化和遗传机制上产生和发展起来的搜索优化方法, 是由美国数学家John Holland在上个世纪60年代提出的, 它是模拟大自然生物进化一类随机搜索优化算法, 常用来求解许多传统方法难以解决的高维的﹑多模态的﹑非线性的复杂问题。它是一类以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法, 它通过模拟达尔文“优胜劣汰、适者生存”的原理鼓励产生好的结构, 模仿孟德尔遗传变异理论在迭代过程中保持已有的结构, 同时寻找更好的结构。以概率论为基础在解空间中进行随机搜索, 最终找到问题的最优解。
典型的遗传算法都有以下一些部分组成:
(1) 染色体, 每一个染色体都是给定问题的解, 它由基因组成。
(2) 初始种群, 是由染色体构成的个体集合。
(3) 遗传算子, 对整个种群进行遗传操作, 不断更新种群中的个体, 从而整个种群得到不断的演化。
(4) 适应值函数, 目的是评估个体质量 (问题解) 的好坏。
在遗传算法中, 每个问题的解被编码为称之为染色体的串, 通常表示为位串 (Bit String) , 每个染色体称之为个体。通常设计一个遗传算法的基本步骤如下:
(1) 确定解的编码方案:通常遗传算法求解问题不是直接作用在问题的解空间上, 而是利用解的某种编码表示。选择何种编码表示有时会对算法的性能、效率等产生很大的影响。
(2) 设计适应度函数:适应值是对解的质量的一种度量, 遗传算法在求解过程中, 基本上不利用外部信息, 而仅利用群体中个体的适应值来进行搜索, 所以适应度函数的选取至关重要, 直接影响到算法的收敛速度以及性能。适应度函数通常以目标函数或费用函数的形式来表示。
(3) 选择策略的确定:优胜劣汰的选择机制使得适应值较大的个体有较高的存活概率, 不同的选择策略对算法的性能有较大的影响。
(4) 遗传算子的设计。
(5) 控制参数的选取。
(6) 确定算法的终止准则。
遗传算法的主要特点如下:
(1) 自组织性、自适应性和自学习性
达尔文进化论的引入使比较好的个体 (适应值大) 以较大的机会得以生存。一般来说, 越好的个体也越具有优良的结构, 它所产生的后代比其他个体所产生的后代具有更高的适应值, 利用遗传算子来重组个体信息往往会使种群得到优化, 因此在演化的过程中种群会变得越来越好。用遗传算法解决问题的时候, 我们没有必要知道问题的复杂性, 所以它非常适合于解决非常复杂的问题。
(2) 本质并行性
每一个个体都是给定问题的一个解, 这些个体随机的分布在解空间 (搜索空间) 内, 一方面, 遗传算法具有内在并行性 (Inherent Parallelism) , 它非常适合大规模并行计算。最简单的是让几百台甚至是上千台计算机进行彼此独立的演化计算, 在计算的同时, 每台计算机都可以相互通信。另一方面, 遗传算法具有内含并行性 (Implicit Parallelism) , 遗传算法并不是从搜索空间的一个点出发, 而是从许多点同时进行搜索, 并彼此之间互相交换信息。
2 排课问题的本质分析
排课过程中涉及的对象很多, 诸如:教师、课程、课时、班级、教室、时段等。很显然排课问题的目的, 就把这些排课对象有机的组合在一起, 以达到令人满意的效果。通过对手工课表的研究, 我们可以发现多样性是课表的一个基本特, 也就是最终可以获得多个不包含冲突的课表。对于不同的课表没有一个统一的标准来判定哪一个才是最优的结果, 我们采用遗传算法智能排课, 就是利用具有启发式的优化策略, 让计算机去搜索一个近似最优的结果。
因此排课问题可以从以下几个方面描述它的本质特性:
(1) 多样性。如前所述, 多目标是排课计算的目标之一。排课方案有多个, 结果并不是唯一的。
(2) 约束性。排课过程必须受到资源、可行性及满意度等方面的限制。约束往往主要表现为3个方面:资源不足型约束, 教室, 教师, 班级是排课的对象, 也是排课过程中的主要资源。如果排课过程对如上任何一种资源的需求总是大于学校所能提供的该种资源的总量, 那么排课根本是不可能的;硬冲突型约束是指, 在资源充足的情况下, 进行排课而产生的非法结果。比如某教师被多次排在同一时段的不同教室上课, 某教室在同一时段被两门不同的可所争夺等等;软冲突型约束, 指在前两种约束都被满足的情况下, 课表排列过程中受到的教学满意度方面的约束。
(3) 复杂性。课表问题是NP完全的, 它意味着在一个多项式时间内无法找到问题的解。这个论证确立了课表问题的学术地位, 把人们对课表编排复杂性的认识提高到了理论的高度。
综上, 我们可以发现排课问题是一个多目标, 受到模糊约束限制, NP完全的, 组合优化问题。应用遗传算法的计算机排课就是减少硬冲突, 尽量提高软冲突满意度, 并最终产生可行的较优解集合的过程。
3 基于遗传算法排课的原理
从遗传算法的基本原理及组成部分可以发现, 要利用遗传算法去实现课程表的安排, 关键在于基因个体的确定 (基因的构成) 、适应度函数的规定及遗传算子的设计。
3.1 基因个体
分析整个排课过程可以发现, 课程表中每一条排课记录涉及到的数据都包含教师、课程、课时、时段、班级、教室这些数据信息, 因此每个基因个体就应该包含这些数据。对这些数据进行分析可以发现:
(1) 教师、课程、课时、班级4个对象, 应该是排课以前根据客观情况事先设计好的, 即哪位老师教授哪门课, 该门课程有哪几个班来学习, 以及该门课程的周学时等情况都应该是在排课以前根据实际情况设定好的, 而并不是排课系统本身所应该决定的。这4种对象的组合其实是根据实际情况确定的固定组合, 所以将这4项设计组成基因个体。
(2) 时段和教室可以构成二维表或二维数组。那么排课表的问题可以看作是把基因个体放入二维数组的过程, 而我们希望获得的就是那个最能令人满意的二维数组。
(3) 二维数组又可以转化为一维数组, 此数组每一个元素都包含时段和教室的信息。
(4) 由于数组中每一个元素都包含时段信息, 而时段是有顺序的, 所以, 该表元素的前后次序即可代表时序。
(5) 教室容量可以作为每一元素的权重, 表示某一时段某一教室的容量。
至此, 排课问题转化为1维数组元素的排序过程。我们搜索较优课表的过程转为寻求满意度较高、不存在硬冲突的一维序列的过程。时段权重并不会影响排序的结果是否合法, 所以该数据不参加遗传, 但可以作为评价序列满意度的标准。
3.2 适应度函数
为了衡量每个课程表的好坏, 可以用一个适应值函数计算每一张课程表的适应度值, 适应度值高的说明这张课程表的安排合理性较高。本文设计的适应度函数有以下几个部分:
(1) 课程适应度
根据实际的调查, 可以给不同的课程以不同的适应度值 (用1~10之间的一个数来表示) , 同时每一门课程在一天的5个时段具有不同的适应度值, 所以每一门课程被安排在周一至周五的25个时段, 就可以有5种适应度值。以体育课为例, 它的适应度值为:
因此对于每张课表, 可以分别统计每门课程的时间段位置, 统计它的总适应度值Fc (i) , 则总的课程适应度Fc:Fc=∑Fc (i) 。
(2) 课程离散度适应度
一门课在一周内分散安排, 提供可引导性学习环境, 因此可以给一门课程两次上课时间之间的时间差值, 赋以一个适应度。如:
检测每一门课程的每一次上课的位置, 计算出时间的差值, 然后对所有时间的差值所对应的期望值Fs (i) , 课程离散度期望值函数为Fs:Fs=∑Fs (i) 。
(3) 好时段适应度
尽量把难度大、较抽象的课程 (理论课) 安排在好的教学日、教学时间点 (如上午比下午好) 。对于每一个班级来说, 一学期的所有课程中总有几门课是比较难的课程, 把难度大、较抽象的课程设法安排在较好的时段。所以需定义“好时段”的适应度值:
检测每一个班的难度大、较抽象的课程 (理论课) 的位置, 对适应度进行求和。即定义“好时段”适应度函数Ft:Ft=∑Ft (i) 。
定义课表的适应度函数F为:F=k1*Fc+k2*Fs+k3*Ft
其中k1、k2、k3为控制各种适应度对总适应度的影响 (权重) , 它们需根据实际情况确定。
3.3 遗传算子的设计
遗传算子主要包括杂交算子和变异算子。
(1) 杂交算子:可以使用单点杂交。设表示问题解的二进制串长为L, 该方法在1~L-1之间随机地选择一个杂交点, 然后将两个父体在该杂交点右边的子串进行交换, 生成两个后代。单点杂交的示意图如图1所示。
(2) 变异算子:引入变异算子的目的在于群体中染色体的多样性, 防止算法的非成熟收敛。变异算子以某一预先指定的概率pm对群体中染色体的基因进行变异。若染色体的某一位被选择进行变异时, 当该位为1时, 则变为0, 否则变为0。概率pm是期望改变的群体中染色体中的基因个数与基因总数的百分比。
按照上面的设计, 就可以依据遗传算法的实现步骤, 实现基于遗传算法排课过程。
4 结束语
作者基于遗传算法, 在Delphi开发环境中已经设计出一个简单的智能排课系统。通过实验证明:基于遗传算法的智能排课思想, 具有操作简便的特点和很强的可行性与实用性。但正如文章中所述, 排课问题受到资源、硬冲突和软冲突三方面的制约。如果资源远远超过需求, 那么排出一个令人满意的课表并不难。但是, 如果资源仅能刚好满足需求, 并且资源和需求都十分巨大, 乃至是千头万绪, 那么排出一个不包含硬冲突的课表就很难了, 而在此基础上还要尽量提高满意度, 则更是难上加难。因此, 对于利用计算机智能排课, 还有很大的研究空间, 这给作者以后的研究工作以很大的动力。
参考文献
[1]XIN YAO AND YANG LIU Fast Evolutionary Programming, Comp utational Intelligence Group[D].School of Computer Science Uni versity College, The University of New South Wales Australian Defence Force Academy, Canberra ACT, Australia, 2006.
[2]孙建平, 梅晓勇, 肖政宏, 等.关联规则在高校智能排课系统中的应用[J].计算机应用, 2002 (5) .
[3]魏静波.计算机自动排课的技术研究[D].大连:大连铁道学院, 2003.
[4]张健.基于图论的高校排课系统实现[J].重庆师范大学学报 (自然科学版) , 2005 (1) .
[5]胡顺仁, 邓毅, 王铮.基于高校排课系统中的图论问题研究[J].计算机工程与应用, 2002 (4) .
[6]赵辉, 秦维佳.基于资源匹配的一种大学排课方法[J].沈阳工业大学学报, 2004 (5) .
基于遗传算法的排课系统 第6篇
1 遗传算法的描述
遗传算法 (Genetic Algorithms, GA) 是根据自然界的选择和进化原理发展起来的高度并行、随机、自适应的随机搜索算法。其模拟达尔文的适者生存原理, 每个种群所面临的问题是寻找一种对复杂和变化着的环境最有利的适应方式。
遗传算法维持一个潜在的群体 (染色体、变量) , 定义一个函数为:
染色体通常形成是一串的数组, 近年来基于实数编码的遗传算法也得到广泛的应用。每个解用其“适应值”进行评价其优劣程度。然后通过选择更新 (t+1次迭代) 个新的群体。新群体的成员通过杂交和变异进行变换, 以形成新的解。杂交组合了两个亲体染色体的特征, 并通过交换父代相应的片断形成了两个相似的后代。例如, 如果父代用五维向量来表示, 如下:
在第二个基因后杂交, 染色将产生后代
杂交算子的意图是在不同潜在解之间进行信息交换。
变异是通过用一个等于变异率的概率随机地改变染色体上的一个或多个基因。变异算子的意图是向群体加入一些额外的变化性。
我们可以把遗传算法简化以下部骤:
1) 产生初始遗传群体的方法。
2) 用“适应值”评价解的适应度的评价函数。
3) 改变后代组成的遗传算子。
4) 遗传算子所使用的各种参数:
流程图如图1。
2 实际排课问题
整个排课流程如下:
1) 初始化种群:对教师行编码, 即产生染色体, 形成一个初始化的二维表, 包括对各种数据的初始化。
2) 对各种冲突进行检测和消除, 如果存在则消除它。
3) 计算其适应度。
4) 进行选择交叉和变异操作, 这是遗传算法的三个基本属性。
5) 则可以得出排课结果。
2.1 对排课问题进行染色体编码
排课系统的好坏染色体编码是关键, 使用一个数椐表初始种那种群, 设置有15个时间段, 每天有3个时间段, 共5天的课时量, 在15个时间子段中填入教师等信息, 称之为“基因”,
1个记录代表一个班级的课程表, 称之为”染色体“;N个染色体组成“个体”;种群是由N个“个体”组成, 在表中, 一行代表班级本时间段的课表, 一列代表该班级的1-15个时间片。首先把教师编码放入时间字段中。用随机函数产生1-15个数, 如有存在相同的数据, 则重新产生, 直到所有的教师编码无重复的填入数字为止, 则这个产生的初始表就构成初始种群。
采取的编码方式是教师号+班级号+课程号, 其宽度为:6+1+4共11位。如图2所示。
1) 教师号
教师号课标中一个重要的元素, 在编码中, 每一门课程和授课老师让他共同组合, 以便解决一个老师上多个班级的冲突。
2) 班级号
在教师号后面添加一个班级号是为了标识一个老师教授多个班级的问题, 如用1来表示教师所教授的第一个班级, 2表示第二个班级, 以此类推, 如222202为教师号, 则2222022表示老师教授的第二个班级。以此类推。
3) 课程号
课程号是为了第一个数字是解决一个老师教授多门课程的问题, 如用1表示老师教师所教授的第一门课程, 2表示第二门课程。以此类推。后面三位是标识课程的输在代码问题
2.2 排课问题的冲突与检测
对于同一时间段, 同一个班级同时上一门以上课程的冲突, 在编码过程中已经解决, 不必考虑, 我们需要消除的是同一时间, 一个教师同时上一门以上课程的冲突:
1) 首先读取二维数组kcb (15) 第一行第一列的教师号;
2) 然后与二维数组同一下一列的教师号进行比较, 如有相同的重新产生随机数J, 否则将两个数组元素的值互换。再重新比较。
3) 继续读取该行第二列的教师号, 重复2的操作, 直到所有的元素的教师号不相同;
4) 开始读取二维数组kcb (15) 第一行第二列的教师号;重复2、3直到所有的元素的教师号不相同, 既没有同时间段、一个教师同上一门的课程。
2.3 适应度函数
在实际排课中要排除一个合格、适用的系统, 必须要考虑课程的适应度问题, 如课程的离散度, 具体课程的上课时间段, 体育课, 计算机课我们可以安排在下午, 英语等课我们一般安排在上午。
2.3.1 英语, 体育等课程的期望值
定义一个时间点, 一周五天的期望值为:
一周上午1时间段的期望值为0;
一周上午2时间段的期望值为5;
一周下午3时间段的期望值为10;
1) 查找英语, 体育课程的位置, 即查找二维数组的课程号编码, 如是则读取其时间段, 从而找出其相应的期望值Fx (i) (i=1, 2, 3, 4.....15) , 并对期望求和。
2) 检测自习课的期望值, 即读取教师编码为空的时间片, 对期望求和。Fz (i) (i=1, 2, 3, 4.....15)
对所有的期望值求和, 定义函数如下:
2.3.2 课程的离散度的期望值
把一星期课程为不同的时间段。使用编号相同的课程的时间差来描写离散度,
查找每一门课程的位置, 计算机出他们的时间差, 然后查找出他们对应的离散度, 并对其进行求和
2.3.3 总期望值
K1, K2为控制总期望值的影响参数 (权重) 。
2.3.4 设计遗传算子
1) 选择操作
从群体中选择一些优质的个体, 并复制到下一个群体中, 代替原来较差的个体。适应度值是个体被选择的决定性因素。
2) 交叉操作
交叉操作就是选择个体中一部分的与另外一个个体积习难改交换操作, 如可以把2个父本分为前后2部分, 第一部分后部与第2个副本前部相交生成第1个个体, 第1个父本的前部与第2个父本的后部组合生成第2个个体。
3) 变异算子
对于具有相同特性的染色体的2个基因位 (如教师编码) 之间, 对其教师或者其他编码值进行交换, 就成为变异操作,
3 结论
实现自动排课问题是一项艰巨的任务, 但其意义非常重大, 至今仍没有一套完整, 成熟的方案来实现。本文根据遗传算法的基本原理, 并根据实际需求, 大胆创新, 对排课中的约束性等问题提出了一套适用的方案, 基本满足了实际工作中的需求, 但对于多项限制条件等排课问题求解, 仍没有达到最优解, 这对于多说研究人员来说是继续探讨的课题, 希望在排课领域的研究有所长者给予指正。
摘要：排课问题是一直是业界NP完全问题, 牵涉到多约束, 多条件, 多目标等问题, 遗传算法一直是当今解决排课问题的优先选择算法。把班级, 课程, 教师, 教室等因素进行染色体编码, 利用遗传算法的选择、交叉, 变异等特性进行对排课因子进行选择筛选, 得到的最优解, 基本能满足当代大学排课的基本需求, 在实际运行中有一定的实用价值。
关键词：排课,遗传算法,染色体编码,智能排课
参考文献
[1]孙建平, 梅晓勇.关联规则在高校智能排课系统中的应用[J].计算机应用, 2002 (5) :37, 38, 42.
[2]王力.高校通用排课管理信息系统设计与实现[J].贵州工业大学学报, 1999, 28 (1) :87-90.
[3]谭定英, 蔡逸仪, 李学征.基于遗传算法的排课系统研究[J].现代计算机:下半月版, 2009 (9) .
高校排课系统的算法研究 第7篇
随着高校现代化管理水平的进步, 在高校教学管理中运用教务管理系统已经得到普及, 排课系统是教务管理系统的核心功能模块。排课系统的主要实现目标就是对下学期开设的课程进行合理及最优化的资源分配, 其中涉及到的主要因素有: 班级情况、教师情况、教室资源等。由于近年高校办 学规模的膨胀式扩大和实验课程的普及, 直接导致各类教学资源紧张, 为达到高效调配教学资源的目的, 就需要通过高级算法智能优化排课功能。
2 问题分析
2.1 基本约束条件
排课问题是一个复杂度极高的问题, 要达到最优化排课的目的, 就要满足排课过程中的各类约束条件:(1) 每位教师在一个时间片中只能完成一个教学工作任务;(2) 每个教学班级在一个时间片中只能接受一个教学任务;(3) 每个教室在一个时间片中只能安排一个教学任务;(4) 考虑到学生的知识接受能力, 为达到最好的教学效果, 同一门课程不能在一天内连续安排;(5) 教师对学校的教学资源较为熟悉, 了解自己所授课程需要的教学环境, 所以应满足教师提出的教学场地需求, 例如: 多媒体教室、专业实训教室、户外教学场地等;(6) 考虑到高校的教学区域面积大, 有的高校甚至有多个分校区, 一定要确保教师和教学班级在完成两个连续教学任务的场地距离不能太远。
2.2 优化目标
在满足了基本约束条件的基础上, 为达到最好的教学效果, 智能排课算法还应尽量满足一定的优化目标:(1) 为避免行政工作冲突, 行政领导排课尽量优先;(2) 外聘教师由于工作性质的要求, 往往要将上课时间相对集中安排;(3) 大学每学期课程较多, 为调节学生学习兴趣, 同一课程的多个课元应尽量均匀间隔;(4) 考虑到体育课对学生体力消耗过大后影响文化课程的学习精力, 体育课程一般不安排在一二节, 且尽量安排在文化课之后;(5) 在排课过程中, 涉及到人数较少的班级或某些人数较多班级甚至合班上课班级, 应根据实际教学班级人数规模安排不同规模的教室, 达到教室资源最优化使用;(6) 在课表生成后, 根据用户实际情况, 必然有需要修改课表的编排, 为避免死锁, 每个教学任务的时间片和教室应尽量不唯一;(7) 考虑到公共课程往往在多媒体教室合班上课, 需同时满足多个约束条件, 公共课程合班教学应优先安排教学资源;(8) 班级课表中的课程安排应尽量均匀, 不能过于集中;(9) 为便于开展全校性活动, 要保留某个半天不予排课。
3 功能需求
3.1 对象描述
排课系统主要涉及到5个对象, 其属性分别如下: (1) 教师 (教师工号、教师姓名、教学课程);(2) 班级 (班级名称、学生数量、所属系部及专业);(3) 教室 (教室号码、座位数、教室类别);(4) 课程 (课程编号、课程名称、课时数、 课程相关属性);(5) 时间 (上课时间)。
系统需要结合以上5个对象, 通过算法的搜索, 寻找问题解。概念模型如图1所示。
3.2 功能需求
根据实际需求, 系统的主要功能包括排课数据导入、数据处理、课程编排、 课表查询、数据维护、数据导出等, 结构如图2所示。
其中, 数据导入功能主要是将教师、班级、教室、课程 等数据录入到系统中, 这是一个较大的工作量, 并且随着教室功能的变更, 后期还需对这类数据进行更新维护; 数据处理功能是将录入后的数据根据数据属性加以排序, 并将前期教师提出的教学时间要求和教室要求进行处理; 课表编排功能是根据约束条件和优化目标将所有资源进行编排, 搜索符合条件的解, 形成课表, 是整个系统的关键功能模块; 课表查询功能是在课表编排结束后, 系统对教师和学生用户开放, 便于用户查询、了解自己课表的实际情况, 并且可以根据现有资源提出修改意见; 数据维护功能是结合用户需求对现有课表进行优化整合, 以及对现有课表的缺陷进行修改, 最大限度满足用户要求; 数据导出功能是将最终课表导出。
4 算法描述
要满足高校智能排课系统的课程编排功能需求, 就要通过复杂算法引导数据处理, 常用的算法包括: 模拟退火算法、蚁群算法、专家系统排课算法、贪心算法、 回溯算法、遗传算法等, 选择一个合适的排课算法可以达到最大限度地减少死锁冲突以及优化排课结果。就排课系统开发过程中常用的回溯算法、 贪心算法和遗传算法做出描述。
4.1 回溯算法
回溯算法也叫试探法, 它是一种系统地搜索问题的解的方法, 可以被认为是一个有过剪枝的DFS (深度优先搜索) 过程。回溯算法解决排课问题的主要过程有:(1) 根据排课问题的约束条件定义问题解的空间集合, 该空间集合必须满足排课的所有约束条件, 该空间一定要涵盖一个以上的问题的解, 不然会出现问题无解的情况;(2) 根据各排课条件选择便于求解的空间结构, 需要构建空间树, 树的任意一条完整路径都是一个解, 从根节点出发, 以深度优先的方式搜索整个空间;(3) 当搜索到空间结构的任意一个节点时, 先判断该节点是否包含排课问题的解以及能否继续深度移动, 如不符合条件, 则往回回溯至最近的一个活节点, 从这一活节点开始, 重新遍历深度, 继续搜索排课问题的解, 在整个过程中, 不断“回溯”又不断的“前进”, 直至找到满足所有要求的解。
回溯算法的空间结构构架清晰, 易于理解, 能够有效的提高分析问题、解决问题的效率。回溯算法在搜索的过程中, 需要保留从开始节点到当前节点的路径信息, 回溯算法的缺点就是运算过程中时间复杂度较大。
4.2 贪心算法
贪心算法也叫贪婪算法, 利用贪心算法对问题进行求解的时候, 可以贪心的认为当前的得到的解就是最优解, 贪心算法不需要从整体考虑该解是否是最优解, 这样造成的结果往往是得到的解只是局部的最优解, 而非整体最优解。在排课问题中, 贪心算法的思路是以排课的某一个条件为出发点, 朝着解决所有排课约束条件这一目标前进, 判断当前节点是否可以解决一个解元素, 如果可以就认为当前路径最优, 继续判断下一个解元素, 直到无解才停止, 贪心算法找到的第一条问题的全解路径就被认为是最优算法。
贪心算法的优点在于时间复杂度较低, 空间结构架构清晰, 但是相对于整体求解而言, 由于找到的一般不是全局最优解, 所以并不适用于解决所有的可行性问题的求解。以排课问题为例, 贪心算法所得的排课结果一般都存在还有进一步优化的必要, 可能存在教学资源的闲置。
4.3 遗传算法
遗传算法是以达尔文的《生物进化论》作为理论基础, 先根据条件构建候选解群, 通过这些候选解的交叉组合后筛选, 以适者生存、优胜劣汰的遗传机制模拟生物进化的过程, 最后得到最优解。针对排课问题, 遗传算法首先根据各约束条件产生十进制或二进制编码作为初始个体, 然后选择合适的函数计算个体的适应度, 根据适应度判断个体是否满足约束条件, 并对满足条件的个体进行交叉、变异等遗传演化, 继续淘汰不适应的新个体, 经过不断的遗传演化和淘汰, 最后找到满足所有排课条件的解。
遗传算法的运算速度快, 能有效地避免局部最优解, 是一种比较理想的排课问题求解算法, 其缺点在于算法比较复杂, 在约束条件较多时, 排课时间需求量大, 存在没有可行解的可能性。
5 结语
多功能排课系统探析 第8篇
随着科学技术的不断提高, 计算机科学日渐成熟, 其强大的功能已为人们深刻认识, 它已进入人类社会的各个领域并发挥着越来越重要的作用。作为计算机应用的一部分, 使用计算机对选课信息进行管理, 有着手工管理所无法比拟的优点。例如:检索迅速、查找方便、可靠性高、存储量大、保密性好、寿命长、成本低等。这些优点能够极大地提高人事劳资管理的效率, 也是企业的科学化、正规化管理, 与世界接轨的重要条件。在高等学校的教务管理工作中, 课程表的编排是一项十分复杂、棘手的工作。在排课过程中, 除了满足大量的制约条件以外, 还必须解决许多冲突与矛盾, 例如:两位教师不能同一时间在同一班级上课、一位教师不能在同一时间上两门课等等。利用计算机辅助进行课表编排工作, 既提高了排课工作的科学性, 又可大大减轻管理人员的工作强度, 提高工作效率, 从而使学校教务管理现代化迈上了一个新台阶。我国不少高校都实行了学分制, 它的核心是允许学生自由选课, 即把学习的自主权交给学生。在这里, 自动排课时的制约因素比较复杂, 工作量也很大, 而且往往需要在较短的时间内完成。运用计算机辅助选课, 即能实时地对大量选课数据进行检验和统计, 十分方便地输出选课结果, 同时也避免了人工处理时容易产生的错误。现在广大高校的工作都借助计算机来辅助完成。我们希望通过算法的比较和确定、数据库的建立, 来设计一套符合广大高校实际情况的多功能排课系统。
1 问题阐述
目前广大高校所设置的课程大致分为两类:一类是根据各个专业指定的学生培养方案和教学大纲要求, 对每个年级安排的必修课、专业选修课等;另一类是根据专业性质设定或面向全校的公共选修、辅修课。前一类课程由各个学院以及专业进行安排管理, 课程相对固定;而后者需要根据全校学生的选择结果进行统计, 对人数过少的课程不予开课, 对人数过多的课程合理配比学生和老师。对于排课问题需要满足很多的约束条件, 以进行最合理的安排。对于这些约束条件, 将必须满足的约束条件称为硬约束条件, 尽量满足的约束条件称为软约束条件。下面将阐述一些非常常见, 并且在设计需要注意的约束条件。
硬约束条件: (1) 同一老师的课程不能安排在同一时间; (2) 每个专业的不同课程应该间隔安排; (3) 教室必须满足课程的需求, 例如容纳人数足够, 是否能够提供多媒体; (4) 同一时间每个班不能有两门课程。
软约束条件: (1) 上课班级的人数要最大程度的接近教室的容量; (2) 体育课安排在每天上午的最后和下午的刚开始; (3) 年龄稍长的教室, 每天不要安排大量的课程; (4) 难度较大的课程尽量安排在学生精力充沛的时候; (5) 减少学生在不同教学楼、不同楼层之间的转换。
2 系统设定
根据上面对问题阐述, 再结合我们对系统的易用性以及多功能理解, 对系统的总体结构做如下的设计。
2.1 登陆界面
用户通过登陆界面输入帐号密码进入系统。对于系统的安全性提高, 可以后期加入看门狗功能, 用于保证排课系统不被不法人员破解登陆。
(1) 学生信息模块完成学生的登陆, 然后根据各位同学所在的系不同, 调出相应的课程模块。其中学生登录模块的功能是验证登录人员确实是本院的学生, 学生启动本系统后, 系统提示输入学生学号码和密码, 验证后进入主控操作界面。
(2) 教师信息模块完成教师的登陆, 然后根据各位教师所在的系不同, 教师所教的课程不同, 调出要排课的课程。其中教师登陆模块的功能是验证登录人员确实是本院的教师, 教师启动本系统后, 系统提示输入教师工号和密码, 验证后进入主控操作界面。
2.2 系统模块
本模块可以安排一个星期五天的课程, 主要通过界面实现对初始化和各种数据的录入, 主要包括课程、教师、教室、专业、班级、教学安排等, 并且可以对各种数据进行细化。教师可以根据实际情况制定课程表, 并可安排任课老师的安排, 课程的安排方便课程查询时需要, 以便及时发现错误能及时修改。
2.3 资源管理
主要是对各种数据资源进行分类管理, 方便用户操作。
2.4 排课模块
(1) 掌握学校所有的课程和教师的信息。包括每门课程的时间、班级以及任课老师的姓名等。
(2) 针对不同的人员授予不同的权限。提供灵活的浏览、查询功能。可以查看某个系、某个班级所有课程的信息。
(3) 可以对一个或多个班级进入课程管理与排课表管理, 可以不限次的生成该班级课程表。
(4) 可以对课程进行变动管理。既可以手工排课, 又可以实现自动排序功能。
(5) 帮助系统维护可以实现操作日志、重新登录、打印设置, 包括统计各种报表及打印、退出等操作。
(6) 提供一种或多种课程表输出功能, 并使用活动的模板输出功能, 输出样式可以由用户自定义。
2.5 课表管理
可以根据专业、班级、教师、教室等方面对课表进行查询、打印等工作。并且可以生成某一时段的课表, 已方便教室的临时借用。
3 算法选定
若以班级为最小单位, 则排课过程其实就是从五个独立的集合, 即教师、教室、班级、课程、时间中各选出一个元素进行组合成一个个体, 在满足许多实际的约束条件下, 使得最后所有的两个个体之间不发生冲突。
目前, 解决排课问题的方法有:遗传算法、贪心算法、蚁群算法、回溯算法、FP-Grow th关联规则算法等[1]。遗传算法的基本思想是基于达尔文的“物竞天择, 适者生存”原理, 将问题的所有可能解映射为生物学上的染色体, 不同解对应染色体的等位基因不同, 多个染色体构成一个解的集合即种群, 经过初始化种群、选择、变异、形成下一个种群步骤, 通过控制迭代次数或种群的适应值控制最终收敛的解。遗传算法具有思路简单、编程容易实现、对排课的多因素协调问题具有很好的适用性、算法的收敛性较好等优点从而为解决排课问题提供一个很好的途径, 更重要的是遗传算法由于解通过迭代和进化得到可以避免“组合爆炸”现象。
4 数据库建立
我们将整个排课系统五个要素, 每个要素在数据库中都有个code字段, 以便初始化种群和组合成染色体和已知染色体检索出相关字段信息。数据库使用的是My SQL 5.0, 建立的表格有classset、courseset、teacherset、timeset、roomset、chromosomeset。图1中每个矩形代表一个表格, 其矩形周围的圆角矩形对应于表格中一个字段, 中间的圆角矩形是其主码, 整个数据库达到了3NF, 表格建立时必须遵循courseset最先建立, chromosomeset的行数是在程序运行中动态增长的。
5 排课系统实现
图2是整个系统的操作流程。管理员通过登陆界面进入系统, 通过添加参数或者导入表格两种方式中的一种, 将有关的数据 (如课程、班级、教室、教师等) 导入系统。再通过相应设置和管理后进行排课。对于某些临时冲突在排课后进行相应的手动调整。最后打印课表或导出Excel表格。
6 程序设计
系统采用MFC类库, 利用Visual C++6.0开发, 类结构骨架图如图3。
7 最终效果
本系统利用了遗传算法, 通过C++语言和Visual C++6.0软件的利用, 最终实现了多功能排课系统的实现。本系统对系统要求低, 操作简便, 人机交互性好, 并且能够规避上述的一些约束条件, 快速生成所需课表。但该系统还有许多不尽如人意的地方, 比如联机文档比较少, 用户界面不够美观, 出错处理不完善等多方面问题。这些都有待进一步改善。
8 结论
本系统通过遗传算法有效的解决了系统内部各个资源的冲突问题, 合理的利用了各种资源, 达到了我们创新性研究目的。本系统目前还存在不固定部分班级-课程-教师而导致算法搜索空间过大的的问题, 主要是因为目前许多大学排课问题班级-课程-教师是内定的而这样可以很快地使遗传算法收敛到最优解。需要在后期进行进一步的理论探索和论证, 以解决此类问题。并且对于系统安全保护, 添加相应的外部硬件, 该模块通过USB借口与电脑连接, 用来激活排课系统。这样可以进一步提高整个系统的安全性。
摘要：课程编排系统是一个学校不可缺少的部分, 它的内容对于学校的决策者和管理者来说都至关重要, 所以自动课程编排系统应该能够为用户提供充足的信息和快捷的查询手段。现在广大高校的工作都借助计算机来辅助完成。我们希望通过算法的比较和确定、数据库的建立, 来设计一套符合广大高校实际情况的多功能排课系统。
关键词：多功能排课系统,高校,数据库
参考文献
限制型拓扑结构的大学排课系统 第9篇
大学课程一般是课程之间相互关联,有先行关系,即学习一门课的前提是要先学习另一门课程。例如计算机专业学习数据结构之前我们要先学习高级语言程序设计。同时不同类型的学校或同一学校不同专业对每个学期最大课程数量和最大学期数都有限制。例如一所普通大学的本科专业限制学期数是8学期。计算机专业又限制每学期的课程不得超过6门。根据种种限制我们利用拓扑排序思想,通过条件限制,可以达到大学排课的需求。
2 排课拓扑结构
根据课程的先行课关系建立课程间的拓扑序列见图1。
建立拓扑序列的方法:用贪婪算法建立拓扑序列,算法用从左到右建立拓扑序列,每一步在排好的序列加入一个顶点,加入的顶点b不得存在这样的入边(a,b),a不在已经排好的拓扑序列中。
拓扑排序算法的伪代码:
3 实现方法
根据课程的拓扑结构建立课程之间的关系矩阵:高级语言a,数据结构b,编译原理c,操作系统d,数据库e,高等数学f,计算机网络g,数字逻辑h,计算机原理i,汇编语言j,大学英语k。
(注:在矩阵中如果a是b的先行课,则(a,b)设置为1,否则是0)
拓扑结构对无限制型排课的实现方法:
在对没有学期数和课程数限制的条件下通过拓扑序列的建立,搜索第一组没有入围的课程:结果是高级语言、高等数学、大学英语和数字逻辑,把这些课程放到第一学期,并把这些课程在拓扑序列中删除。寻找第二组没有入围的课程:数据结构、数据库、操作系统、计算机原理、汇编语言,把这些课程放到第二学期上,并把这些课程在拓扑序列中删除。剩下的课程都没入围放到第三学期。
限制条件在拓扑排序中的实现:
在很多情况下对课程的学期数和每学期上的最多课程数都是有限制的,这样会得到更加合理的排课表。把上面要排课的课程限制为4个学期,每学期最多上3门。这时对原来的拓扑排序要加以修改,首先搜索没有入边的课程,搜索到4门,但是每学期最多上3门,这时自动把第4门课放到候选课程,即这门课可以在以后的学期中随时安排。这其中涉及到一个堆栈,该堆栈负责存放没有入边(即满足要求的课程)但是由于该学期课程已经被安排满而没有被安排的课程。堆栈中的课程都是满足要求的,所以实际上每学期的课程都是在堆栈中调用的。
代码实现如下:
通过限制型的拓扑排序得到的课程安排如表3所示。
4 软件实现
输入要排课的课程号和课程名以及先行课,如图2所示。
在没有限制情况下得到的排课结果,如图3所示。
在最大学期数是4,每学期最多上3门课的情况下得到的排课结果如图4所示。
5 总结
拓扑排序的应用很好地解决了在有先行课的情况下对学期课程的排序。限制型拓扑排序的应用很好地解决了在有学期限制和每学期最大课程数限制的情况下对课程的排序。通过建立一个堆栈存放满足条件的课程,在拓扑排序的前提下每学期从堆栈中取出最大课程数,放到该学期。这样可以满足学期和课程的双重限制。本系统利用拓扑排序和堆栈原理根据先行课的关系,同时允许设置最大学期数和每个学期上的课程数。很好地解决了大学课程的排课算法。同时它解决了排课算法的不规范性,能够准确无误地排出课程,可以说是大学教务的好帮手!
参考文献
[1](美)Sartaj Sahni著.汪诗林,孙晓东译.数据结构算法与应用———C++语言描述[M].机械工业出版社,2007年7月.
[2]苏仕华著.数据结构与算法解析[M].中国科学技术大学出版社,2007.