基于蚁群算法的高校排课问题的研究_韦芳萍.pdf
《基于蚁群算法的高校排课问题的研究_韦芳萍.pdf》由会员分享,可在线阅读,更多相关《基于蚁群算法的高校排课问题的研究_韦芳萍.pdf(4页珍藏版)》请在咨信网上搜索。
1、2023.7电脑编程技巧与维护1概述排课是高校教务的重点、难点问题,涉及规模大且复杂的排课条件限制,手动排课将带来巨大的工作量,耗时耗力且效率低下。编排出合理的课程表,能够保证全校教学工作的有序进行,提高教学质量,对学生的身心发展及学习效果都有积极的影响,另外,编排课程还是学校教育、教学管理水平的体现。显而易见,基于蚁群算法的排课问题具有较高的研究价值。2排课问题分析在高校教学管理工作中,排课是比较棘手的问题,因为在排课过程中需要考虑的因素较多,受到很多的条件限制,各方面的冲突都需要解决。排课过程中涉及教师、教室、时间、班级及课程因素,这5个因素相互制约,有些情形必须解决(硬性条件),而有些情
2、形则可以考虑优化(软性条件)。系统设计的目标是使各因素之间互不冲突且排出科学、合理的人性化课表,满足师生的需求。排课涉及的因素的定义集合如下:教师的集合:TH=TH1,TH2,TH3,.,THi,其中,i为全体教师人数,也指第i位教师。班级的集合:CA=CA1,CA2,CA3,.,CAj,其中,j为所有班级数,也指第j个班级。课程的集合:CS=CS1,CS2,CS3,.,CSk,其中,k为所开课程数,也指第k门课程。时间的集合:TM=TM1,TM2,TM3,.,TMn,其中,n为时间片数,也指第n个时间段。教室的集合:CL=CL1,CL2,CL3,.,CLm,其中,m为所有类型教室数,也指第m
3、个教室。2.1硬性条件(必备条件)硬性条件是必须满足的条件,包括以下5种情况:(1)一间教室在同一时间只能给一个班级上课。(2)一个班级在同一时间只能上一门课。(3)一个教师在同一时间只能给一个班级上课。(4)上课的班级总人数须小于等于教室容量。(5)教室类型(多媒体、机房等)须与课程性质(理论课、操作课等)相匹配。2.2软性条件(非必备条件)软性条件是在满足硬性条件的基础上,非必须满足但尽可能满足的条件,包括多种情况。(1)同一班级的同一门课程在一周之内应该间隔安排。(2)专业课或较难的课程应该安排在上午,体育课、选修课应安排在下午或晚上。(3)教师、学生相隔时间短的课程,安排的教室不宜离得
4、太远。(4)每个班级每天安排的课程量应均匀。(5)每个教师每天安排的课程量应均匀。3蚁群算法及二分图模型3.1蚁群算法基本思想蚁群算法是一种仿生学算法,是受自然界中蚂蚁觅食的行为启发而产生的。蚂蚁在巢穴和食物之间反复往返,释放了一种被称为信息素的物质。由于路径的长短差异,蚂蚁所需觅食时间不同,则随着时间的推移,信息素浓度也会发生变化。长路径所需的时间长、次数少、信息素浓度低,而短路径则恰恰相反,信息素浓度越高被选择的机率越大,从而找出最短路径。假如m只蚂蚁在n座城市间觅食,任选一座城市出发,需要走过所有城市,每座城市只可走一次,最终回到原点,寻求最短路径。矩阵P为城市之间的信息;作者简介:韦芳
5、萍(1994),女,本科,工程师,研究方向为数据库技术、算法与数据结构。基于蚁群算法的高校排课问题的研究韦芳萍(广西城市职业大学,广西 崇左532200)摘要:随着高校学生规模的不断扩大,排课难度系数也随之加大,致使手动排课方式的劣势逐步显现。为提高教务排课的高效性,优化排课系统模式,解决在排课过程中教室、教师、班级、课程和时间的冲突及组合优化的问题,阐述了利用二分图模型实现资源优化分配,提出了基于蚁群算法的智能排课研究。研究结果证明,系统智能排课功能的实现,提高了排课效率,排出科学合理的人性化课表,满足了广大师生的需求。关键词:二分图模型;蚁群算法;智能排课32DOI:10.16184/pr
6、g.2023.07.0302023.7电脑编程技巧与维护矩阵Y为蚂蚁经过所有路径所释放的信息素;BestShort为最短路径。为每只蚂蚁设置一个城市禁忌表Qk=Q1,Q2,Qi,记录该蚂蚁已经访问过的城市,表示这些城市将不能再访问,再设置一个城市访问表Tk=T1,T2,Ti,记录该蚂蚁未访问过的城市,表示这些城市还可以访问,算法总共运行MAX次,运行时间为t,控制参数(,)。蚁群算法计算过程如下:(1)初始化蚁群算法参数、信息素浓度、公用权值等,如Y初始化为0,Qk置空,Tk为加入所有节点。(2)t时刻,为每只蚂蚁在节点i时选择下一个节点j,指导蚁群搜索过程中的相对重要程度ij与城市间的距离d
7、ij,决定了下一个节点被选择的概率,如公式(1)所示:(1)(3)蚂蚁每次访问遍历结束,信息浓度均发生变化(为信息浓度挥发系数),更新信息素浓度方式如公式(2)所示:(2)(4)检查终止条件,如果达到最大代数MAX,则算法终止,输出最优值BestShort;否则,重新初始化全体蚂蚁的Y中的元素为0,将Qk清空,在Tk中加入所有的城市节点,再随机选择或直接指定起始位置,在Qk中加入起始节点,在Tk中去掉该起始节点,重复执行以上步骤。(5)输出最优值BestShort。3.2排课二分图模型二分图是由顶点、边、权值这3个对象所构成的无向图,假定图结构为G=(P,E,W)。其中,P为顶点集合;E为边集
8、合;W为权值集合。将集合P中的元素分成两部分,即P的两个子集合:P1,P2。Eij,(iP1,jP2)为这两个子集合的顶点所构成的边,边上附带有权值,权值的意义视实际情况而定,如在典型的JSP旅行商问题中,权值为城市间的距离,W中的元素直接影响下一个城市的选择。对于解决排课问题,在此将采取对教室、教师、班级、课程及时间的集合进行笛卡尔积计算CSCATHTMCL,对所构成的解空间不断寻求满足各条件中最优解的方法。根据教学计划安排,已知课程、班级及教师的安排是确定的,即元组在排课过程中无需考虑,需要考虑的是如何为每门课程寻求合理的时间和教室,即元组的求解。设定时间和教室的关系集合为RTM,CL,R
9、TM,CL=TMCL=(TM1,CL1),(TM2,CL2),(TMn,CLm),记C为时间和教室集合的有序对,设定课程、班级、教师的关系集合为RCS,CA,TH,RCS,CA,TH=CSCATH=(CS1,CA1,TH1),(CS2,CA2,TH2),(CSk,CAj,THi),记S为课程、班级、教师集合的有序对。综上所述,排课问题转变为求课程CS到C的幂集P(C)的一个映射f:CSP(C),即求RCS,CA,TH与RTM,CL的最大匹配问题。4基于蚁群算法自动排课的实现4.1蚁群算法排课思路针对排课问题,通过构造二分图模型及应用,可以在满足硬性条件的基础上排出基础课表,即在二分图模型RCS
10、,CA,TH与RTM,CL这两个集合中,课程属于RCS,CA,TH集合,教室属于RTM,CL集合,所排课表的基本要求为教学计划中的所有课程必须都有教室安排,且教室类型(多媒体、机房等)与课程性质要求(理论课、操作课等)相一致,教师、时间及班级互不冲突,班级人数小于等于教室容量,此时排出的课程表可继续采用蚁群算法结合软性条件需求自动调整优化。排课主要操作步骤如下:(1)构造二分图模型,即设定课程、班级、教师的关系集合为RCS,CA,TH,时间和教室的关系集合为RTM,CL,为两集合中的顶点根据条件进行边的连接,并为边附上权值。(2)初始化参数,即对信息素浓度,最大循环迭代值,、等参数赋予初始值。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 算法 高校 问题 研究 韦芳萍
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。