基于多维遗传算法的成教排课系统的研究和设计

论文摘要

成人教务排课系统的任务是按照教学计划的规定,把各授课点每学期各专业的课程安排进行汇总,然后制定成人教育学院所有专业各班级的课表。排课问题属于多重约束和组合优化问题,并且已经被证明是一个NP完全问题。遗传算法(Genetic Algorithms简称GA) ,可以通过模拟物种进化的过程来构造人工系统,它具有良好的并行性、通用性、稳定性,是一种有效的解决NP完全问题的方法。本文进行了以下几方面的研究工作:首先,全面系统地分析了成教学院排课问题的各要素及多重约束条件,总结出了排课问题的解决瓶颈和优化方向,并设计了排课问题的相应数学模型。其次,对比分析了传统遗传算法编码方案的各自优缺点,并研究在排课系统中的应用效果,在综合集中编码方案优缺点的基础上,设计了一种更适合解决排课问题的多维编码方案。较之其他编码方案,更加高效和易于理解,并且更加适合成教学院的特点。根据设计的编码方案,构造了相应的交叉算子和变异算子。然后,以C#为开发环境,依据排课问题的数学模型,设计了多维编码方案及改进后的遗传算子,设计了基于上述改进型遗传算法的成教自动排课系统。最后,用实际检测数据,证实了本文设计的多维编码方案在高校成教部门自动排课中的实际效果,从时间复杂度、排课效果及排课速度等方面进行了效能分析,结果理想,可以作为其他同类问题的参考。

论文目录

• 致谢
• 摘要
• Abstract
• 1 绪论
• 1.1 成教排课问题的研究背景及其意义
• 1.2 排课算法在国内外的研究状况
• 1.3 解决排课问题常用的算法及优势算法
• 1.3.1 在解决排课问题中常用的算法
• 1.3.2 目前的优势算法——遗传算法
• 1.4 本文研究的内容及目标
• 1.5 本文结构说明
• 2 遗传算法基本原理
• 2.1 遗传算法的介绍
• 2.2 遗传算法的操作过程
• 2.3 遗传算法的基本原理
• 2.4 遗传算法基本流程
• 2.5 本章小结
• 3 成教排课问题的研究
• 3.1 成教排课问题综合分析
• 3.1.1 成教排课问题所涉及要素
• 3.1.2 排课问题中的约束规则
• 3.2 排课问题的数学描述
• 3.3 排课的求解目标
• 4 成教排课系统的UML 建模
• 4.1 UML 基础知识
• 4.1.1 UML 的结构
• 4.1.2 UML 的建模过程
• 4.2 UML 建模工具的选择
• 4.2.1 常见UML 工具介绍
• 4.2.2 Rational Rose 介绍
• 4.3 软件开发过程RUP
• 4.4 系统需求分析
• 4.4.1 系统要求的提出
• 4.4.2 排课质量的衡量标准研究
• 4.4.3 系统用例图分析
• 4.5 系统分析模型
• 4.5.1 系统静态模型
• 4.5.2 系统顺序图分析
• 4.6 本章小结
• 5 基于多维编码的遗传算法的优越性分析
• 5.1 遗传算法常用编码的改进
• 5.1.1 遗传算法编码的特性
• 5.1.2 常见编码方案的对比分析
• 5.2 基于多维编码的遗传算法方案的提出
• 5.3 多维编码方式
• 5.4 几种典型的约束条件
• 5.5 种群的初始化
• 5.6 适应度函数
• 5.7 设计遗传算子
• 5.7.1 选择算子
• 5.7.2 交叉算子
• 5.7.3 变异算子
• 5.8 冲突检测
• 5.9 本章小结
• 6 成教排课系统的实现和测试
• 6.1 模块化设计
• 6.2 数据库设计
• 6.2.1 数据库概念模型设计
• 6.2.2 数据库逻辑模型设计
• 6.2.3 数据库物理模型设计
• 6.3 系统工作流程及详细功能介绍
• 6.3.1 系统详细功能介绍
• 6.4 系统重要实现思想
• 6.4.1 面向对象思想的应用
• 6.4.2 教室调度算法
• 6.4.3 基因初始化算法
• 6.4.4 冲突检测算法
• 6.5 测试与分析
• 6.5.1 本系统环境要求
• 6.5.2 对自适应参数的测试分析
• 6.5.3 对种群规模的测试分析
• 6.5.4 遗传迭代数的测试分析
• 6.5.5 基于测试结果的性能分析
• 6.5.6 测试与分析总结
• 7 总结及应用展望
• 7.1 论文总结
• 7.2 应用展望
• 参考文献
• 作者简历
• 学位论文数据集
• 中文详细摘要