基于改进混合遗传算法的高校排课问题研究

发布时间：2017-05-28 00:01

  本文关键词：基于改进混合遗传算法的高校排课问题研究，由笔耕文化传播整理发布。

【摘要】：高校排课问题是一个多目标和多约束的组合优化问题,能否有效地解决它,直接关系到资源利用率和教学质量的高低。高校排课问题是一个NP完全问题,人工进行求解是非常低效的,因此需要借助计算机和人工智能算法进行求解。在众多智能算法中,遗传算法是一种借鉴了生物进化和自然选择思想的随机搜索算法,具有自组织、自适应和自学习性,能够并行地进行全局搜索,非常适用于求解NP完全问题。 该文首先分析了高校排课问题所涉及到的相关约束条件、设计了预期达到目标的函数、建立了相应的数学模型。其次,根据问题的特点,应用遗传算法和模拟退火算法构造了模型的人工智能求解方法。在解算过程中,通过在产生初始种群时进行乱序处理、在选择操作时保留最优个体、在交叉操作时引入竞争机制和在变异操作时应用模拟退火算法,大大提高了模型解算的效率,并能够在求解过程中跳出局部最优解,更好地进行全局最优解的搜索；另外在数据处理上应用Matlab与Access混合编程,大大地提高了处理大规模数据的效率。最后,针对一个存在大量合班现象的实际高校排课问题,应用本文提出的混合算法进行了求解,得到了满意的结果,从而证明了本文模型和算法的实用性和有效性。
【关键词】：高校排课问题 混合遗传算法 模拟退火算法 混合编程
【学位授予单位】：北京林业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：G647.3
【目录】：

• 摘要4-5
• ABSTRACT5-8
• 1 引言8-21
• 1.1 研究背景和意义8-9
• 1.2 国内外研究现状分析9-19
• 1.2.1 国外研究现状9-13
• 1.2.2 国内研究现状13-18
• 1.2.3 对国内外研究的总结18-19
• 1.3 本文的主要研究内容和框架19-21
• 2 相关算法理论概述21-30
• 2.1 遗传算法概述21-26
• 2.1.1 遗传算法的产生与发展21
• 2.1.2 遗传算法的生物学原理21-23
• 2.1.3 遗传算法的基本思想23-24
• 2.1.4 遗传算法的基本流程24-26
• 2.1.5 遗传算法的特点26
• 2.2 模拟退火算法概述26-30
• 2.2.1 模拟退火算法的物理学原理27
• 2.2.2 模拟退火算法的基本思想27-28
• 2.2.3 模拟退火算法的基本流程28
• 2.2.4 模拟退火算法的关键设置28-29
• 2.2.5 模拟退火算法的特点29-30
• 3 高校排课问题的分析与数学建模30-40
• 3.1 排课问题概述30
• 3.2 排课问题的相关术语定义30-31
• 3.3 排课问题的数据结构和变量设置31-34
• 3.4 排课问题的约束条件分析34-36
• 3.4.1 硬约束条件分析35-36
• 3.4.2 软约束条件分析36
• 3.5 排课问题的目标函数设计36-40
• 4 基于混合遗传算法的高校排课问题的解算40-51
• 4.1 染色体设计40
• 4.2 初始种群的生成方法40-43
• 4.3 选择操作设计43-44
• 4.4 交叉操作设计44-46
• 4.5 变异操作设计46-47
• 4.6 模拟退火算法的引入47-48
• 4.7 混合遗传算法的完整流程48-49
• 4.8 排课结果的检查机制49-51
• 5 实例验证51-61
• 5.1 实验环境51
• 5.2 实例简介51
• 5.3 参数设置51-53
• 5.3.1 交叉概率和变异概率设置51-52
• 5.3.2 种群规模设置52
• 5.3.3 迭代次数设置52-53
• 5.3.4 模拟退火算法的参数设置53
• 5.4 解算结果及分析53-56
• 5.5 可视化结果输出56-61
• 5.5.1 每个小班的课表57
• 5.5.2 每位教师的课表57-58
• 5.5.3 每间教室的课表58-61
• 6 总结和展望61-62
• 6.1 总结61
• 6.2 展望61-62
• 参考文献62-66
• 个人简介66-67
• 导师简介67-68
• 获得成果目录68-69
• 致谢69-70
• 附录1 实例数据70-90
• 附录2 解算结果90-91

【参考文献】

中国期刊全文数据库 前10条

1 张献;;蚁群算法在排课问题中的应用研究[J];长春大学学报;2007年10期

2 张健;基于图论的高校排课系统实现[J];重庆师范大学学报(自然科学版);2005年01期

3 江齐,兰竞;遗传算法在排课问题中的运用[J];重庆大学学报(自然科学版);2005年11期

4 马涛;王芬;;基于改进蚁群遗传算法的排课问题研究[J];宁夏师范学院学报;2011年06期

5 胡顺仁,邓毅,王铮;基于高校排课系统中的图论问题研究[J];计算机工程与应用;2002年04期

6 罗军;;基于动态规划和模拟退火算法的排课系统[J];计算机与现代化;2007年05期

7 朱颢东;李红婵;;采用十进制最佳个体置换遗传算法求解高校排课问题[J];计算机工程与科学;2011年06期

8 王念桥;姚四改;;基于改进粒子群优化算法的排课问题[J];计算机应用;2013年01期

9 林漳希,林尧瑞;人工智能技术在课表编排中的应用[J];清华大学学报(自然科学版);1984年02期

10 祝勇仁;邓劲莲;胡献华;张炜;;排课问题的一种遗传算法适应度求解方法[J];四川大学学报(工程科学版);2007年S1期

  本文关键词：基于改进混合遗传算法的高校排课问题研究，，由笔耕文化传播整理发布。

本文编号：401439