蚁群算法在求解一类时间表问题中的应用研究

论文摘要

排考问题是一类典型的时间表问题，是对考生、考场、时间、考试科目和监考人员等因素进行配置的决策性问题。由于排考问题的普遍性和复杂性，众多科研机构和研究者已投入大量研究力量寻找其解决方案，因此本文的研究具有实际意义。论文在对西安电子科技大学网络教育学院考务流程及考务系统功能进行分析后，构建排考问题数学模型，研究模型求解过程中需要的关键算法，并提出具体的求解方案。首先基于图着色算法的理论，对考试科目进行分组预处理，并根据分组数确定具体考试时间；其次使用蚁群算法寻找考试科目分组与时间的最优化组合，对考试时间安排进行优化；然后基于贪心算法的思想安排考场；最后构造监考适合度函数合理安排监考人员。实验表明，该方案在优化考试时间、尽量满足约束条件、资源节约利用等方面，均能够产生良好的效果，具有较强的可行性和适用性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外现状
• 1.3 研究意义及工作
• 1.4 论文结构
• 第二章 相关理论及技术
• 2.1 图着色问题
• 2.1.1 图着色问题描述
• 2.1.2 Welsh-Powell 算法
• 2.2 组合优化问题及其求解
• 2.2.1 组合优化问题
• 2.2.2 邻域函数与局部搜索
• 2.2.3 启发式搜索理论
• 2.3 基本蚁群算法
• 2.3.1 蚁群觅食行为与觅食策略
• 2.3.2 基本蚁群算法模型
• 2.3.3 基本蚁群算法实现步骤与特性
• 2.3.4 基本蚁群算法的改进
• 2.4 本章小结
• 第三章 排考问题模型建立
• 3.1 考务流程及考务系统功能
• 3.2 排考问题的需求分析
• 3.2.1 排考问题的基本要素
• 3.2.2 排考问题的约束条件及考试安排目标
• 3.3 排考问题模型的建立
• 3.3.1 模型假设
• 3.3.2 符号说明及函数定义
• 3.3.3 约束条件
• 3.3.4 目标函数定义
• 3.4 本章小结
• 第四章 排考问题模型求解与方案设计
• 4.1 求解方案总体设计
• 4.2 图着色算法解决分组预处理
• 4.2.1 简单无向图的构造
• 4.2.2 图着色算法进行考试科目分组
• 4.3 基于蚁群算法的考试时间优化
• 4.3.1 可行解的构造
• 4.3.2 目标函数的定义
• 4.3.3 考试时间优化的简单无向图
• 4.3.4 蚂蚁具备的行为特征
• 4.3.5 蚁群算法解决排考问题的关键要素
• 4.3.6 考试时间优化算法
• 4.3.7 算法性能分析与比较
• 4.4 物理考场及监考人员安排
• 4.4.1 物理考场安排
• 4.4.2 监考人员安排
• 4.5 本章小结
• 第五章 测试及结果分析
• 5.1 测试环境与输入数据
• 5.2 考试科目分组预处理
• 5.3 蚁群算法求解过程描述
• 5.4 参数选择对蚁群算法求解排考问题的性能影响
• 5.5 后续操作
• 5.6 考试安排结果显示与分析
• 5.7 本章小结
• 第六章 总结与展望
• 6.1 论文总结
• 6.2 研究展望
• 致谢
• 参考文献
• 读研期间研究成果