基于蚁群算法的考场编排问题研究

发布时间：2019-07-27 11:45

【摘要】：随着高校的扩招,在校学生人数剧增,而教学资源有限,使学校的考场编排工作成了一个难题。人工编排已经不能适应现代考场编排工作,人们将计算机技术引入考场编排过程中,使考场编排工作自动化,不仅省时省力,编排效果也好,解决了人工编排过程中出现的许多困难。本文对考场编排问题进行了分析,讨论了考场编排过程中所涉及的因素,给出了考场编排的规则和要求,介绍了几种考场编排算法;对蚁群算法的原理、优缺点进行了分析,讨论了蚁群算法的研究进展,给出了蚁群算法的数学模型和蚁群算法的流程图,介绍了蚁群算法的应用;对考场编排问题进行了分析,给出了考场编排问题的数学描述和约束描述,研究了考场编排问题的二部图模型;对考场编排问题的蚁群算法应用进行了分析,给出了蚁群算法解决考场编排问题的流程图;对考场编排的一个应用实例进行了分析,讨论了蚁群算法解决考场编排问题中的参数影响。本文将考场编排问题转变为二部图的匹配问题,大大降低了算法的复杂度,应用蚁群算法可以对考场编排问题进行优化,得到较优解,可使考场编排的效果更好,从而提高考试的质量。
【图文】：

法原理食行为是第一个被生态学家研究的行为，蚂蚁总是能找到一条路径。从蚂蚁觅食行为受到启示，Marco Dorigo 首次法模型[7]。从此，科学家对蚁群算法的研究取得进一步的何找到食物和蚁穴之间的最短路径的呢？通过对蚂蚁觅食觅食行为是随机的，当蚂蚁发现食物以后，行为就会逐渐的蚂蚁都经过相同的路径，经过一段时间之后，所有的蚂径。这是因为蚂蚁散发一种名为信息素的外激素，通过信食物源，同伙接收到信息素的信息之后，就沿着这条路径最短路径上的信息素浓度越来越大，就会有越来越多的蚂是一种正反馈机制。 所示为蚂蚁觅食的过程。图 3-1(a)表示蚂蚁可以在食物源径；图 3-1(b)表示当食物和蚁穴之间出现障碍物时，蚂蚁；图 3-1(c)表示当某一条路径上的蚂蚁越来越多时，后来越多的情况。

10图 3-2 蚂蚁觅食原理如图 3-2 所示，假设 A 为蚁穴，F 为食物源，d 表示两者之间的距离，共有20 只蚂蚁参加觅食过程。如图 3-2(a)所示，在 t=0 时刻，有 20 只蚂蚁准备开始出发，很明显，在蚂蚁出发之前，所有的路径上都没有信息素。如图 3-2(b)所示，在 t=1 时刻，所有的蚂蚁从蚁穴 A 出发，到达 B 点，在 点蚂蚁面临选择，而此时所有路径上的信息素都为 0，，所以蚂蚁以相同的概率选择路径，每侧将有 10 只蚂蚁经过。如图 3-2(c)所示，在 t=4 时刻，右侧的 10 只蚂蚁到达食物源，而左侧的 10只蚂蚁刚到达 C 点。如图 3-2(d)所示，在 t=5 时刻，从右侧经过的蚂蚁找到食物源返回并到达 点，左侧的蚂蚁刚好也到达 E 点，两支蚂蚁在 E 点相遇，这时候，两条路径上的
【学位授予单位】：江西师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 杨彦红;;算法分析与设计(双语)课程实践教学模式探索[J];中国管理信息化;2017年19期

2 李绍静;许海洋;吕建波;;应用型人才培养中《算法分析与设计》课程教学方法研究[J];科技资讯;2017年04期

3 刘子旋;;中国古代算法的探究与模型建立[J];中华少年;2017年04期

4 曹千秋;;求离散点最小包围圆在算法初步教学中的案例分析[J];中华少年;2017年11期

5 郭亚玲;;算法初步的几个着力点[J];高中生学习(试题研究);2017年09期

6 杨波;肖自碧;;信息与计算科学专业“算法分析与设计”研究性教学探索[J];中国电力教育;2013年01期

7 郑大伟;董大南;;自回归谱估计的Marple算法及其在天文资料分析中的应用[J];天文学报;1987年04期

8 郑卓嘉,吴佑寿,李叔梁;计算机三维逼真图形显示的一种改进算法[J];计算机学报;1988年01期

9 廖先n\;赵先铭;张赤红;;分布式计算机系统容错互斥算法[J];计算机研究与发展;1988年07期

10 李玉忱;徐恭学;;特殊数据的排序方法[J];山东工业大学学报;1988年03期

相关会议论文 前10条

1 唐乾玉;陈翰馥;;用扰动分析的优化算法的收敛性——PARMSR算法分析[A];1993年控制理论及其应用年会论文集[C];1993年

2 刘远新;邓飞其;罗艳辉;舒添慧;;ERP柔性平台下物流运输配送系统算法分析[A];第二十六届中国控制会议论文集[C];2007年

3 柳俊;周斌;黄九鸣;;基于二部图投影的微博事件关联分析方法研究[A];第29次全国计算机安全学术交流会论文集[C];2014年

4 常迎香;;一类无完美匹配的二部图[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

5 王巍;杨武;张乐君;郑军;;支持网络话题管理的文本挖掘算法分析[A];全国网络与信息安全技术研讨会论文集（下册）[C];2007年

6 王晓刚;王耀兴;;RIM算法分析及优化方案[A];2016山西省通信学会学术年会论文集[C];2016年

7 马兴;罗恒;鲁建壮;;ECC校验的算法分析与设计实现[A];第十八届计算机工程与工艺年会暨第四届微处理器技术论坛论文集[C];2014年

8 李海亮;赵转萍;;用于圆检测的Hough变换和改进算法分析[A];江苏省计量测试学会2005年论文集[C];2005年

9 董滨;赵庆卫;颜永红;;发音质量自动评估的现有算法分析[A];第八届全国人机语音通讯学术会议论文集[C];2005年

10 宋欣;王娟;张斌;叶世伟;;流形学习算法分析及在人脸数据库上的应用[A];2008年全国开放式分布与并行计算机学术会议论文集(上册)[C];2008年

相关重要报纸文章 前2条

1 本报记者 李新玲;《算法帝国》预测机器可能统治世界[N];中国青年报;2014年

2 科文;VIXD算法分析Web异常[N];中国计算机报;2008年

相关博士学位论文 前10条

1 苏敏;无条件稳定的LOD-FDTD算法研究[D];国防科学技术大学;2016年

2 吕翠翠;基于压缩感知的无线传感器网络数据采集算法研究[D];哈尔滨工业大学;2017年

3 康岚兰;粒子群优化算法若干改进策略及其机理分析[D];武汉大学;2017年

4 卢思超;食品冷链运输相关优化模型及算法研究[D];北京交通大学;2018年

5 付钰;面向物联网的RFID标签识别算法研究[D];吉林大学;2018年

6 谢刚;免疫思维进化算法及其工程应用[D];太原理工大学;2006年

7 于滨;城市公交系统模型与算法研究[D];大连理工大学;2006年

8 陈耿;面向中观审计的规则发现算法研究[D];东南大学;2005年

9 李宁;粒子群优化算法的理论分析与应用研究[D];华中科技大学;2006年

10 黄训诚;基于蚁群算法的超大规模集成电路布线研究[D];西安电子科技大学;2007年

相关硕士学位论文 前10条

1 张欢;基于蚁群算法的考场编排问题研究[D];江西师范大学;2017年

2 刘康;压缩感知中块结构字典学习算法的改进与应用[D];辽宁工程技术大学;2017年

3 范京;基于码本模型的目标检测算法改进及跟踪算法研究[D];福州大学;2017年

4 郭冬宝;改进萤火虫算法及其在约束优化中的应用[D];暨南大学;2018年

5 侯立夫;基于决策树量化的行车路线规划算法研究与实现[D];北京工业大学;2018年

6 李宗泽;基于数据多重密度特性的自适应半监督聚类算法[D];云南大学;2017年

7 王义宗;化学图论算法和大规模图染色算法研究[D];兰州交通大学;2018年

8 陶斯涵;氨基酸网络比对的算法研究[D];江南大学;2018年

9 刘军;基于多目标蚁群算法的车间设施布局方法研究[D];南京信息工程大学;2018年

10 彭丽君;电力系统有功优化经典算法的研究[D];南昌大学;2018年

本文编号：2519976