基于多维编码方案的遗传算法在高校排课系统中的应用

论文摘要

排课问题是典型的多重约束和组合优化问题,并且早在70年代已经被证明是一个NP完全问题。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的自适应随机搜索算法。它具有良好的并行性、通用性、稳定性,是一种非常有效的解决NP完全问题的方法。本文将遗传算法应用于求解排课问题,主要进行了以下几个方面研究工作:首先,系统分析了排课问题的各要素及多重约束条件,提出了排课问题的求解难点和优化目标,并完整设计了排课问题的数学模型。其次,着重分析比较常用的遗传算法编码方案并研究其在排课系统中的应用,在综合各种编码方案优缺点基础上,设计了一种更适合解决排课问题的多维编码方案。较之传统编码方案,该编码方案更简单、更高效、更易于理解。并且,根据设计的编码方案,重新设计了与之对应的交叉算子和变异算子。再次,结合排课问题具体数学模型,以Visual C++ 6.0为主要开发工具,将多维编码方案以及与之对应的改进遗传算子应用到排课系统中,设计并实现了基于上述改进型遗传算法的自动排课系统。最后,以实际排课数据测试了本论文设计的多维编码方案及对应的遗传算子在实际排课问题中的应用,并对测试结果从时间复杂度和排课结果两方面进行了性能分析,效果令人满意。

论文目录

• 摘要
• Abstract
• 1. 引言
• 1.1 课题背景与研究意义
• 1.2 排课问题研究现状
• 1.3 遗传算法研究现状及特点
• 1.3.1 遗传算法研究现状
• 1.3.2 遗传算法特点
• 1.4 排课问题常用解决方案及遗传算法优势
• 1.4.1 排课问题常用解决方案
• 1.4.2 遗传算法解决排课问题优势
• 1.5 现有基于遗传算法的排课系统常见不足
• 1.6 论文研究内容和目标
• 1.7 论文组织结构
• 2. 遗传算法解决排课问题概述
• 2.1 排课问题概述
• 2.1.1 排课问题描述
• 2.1.2 排课问题中的基本规则
• 2.2 遗传算法概述
• 2.2.1 遗传算法基本术语
• 2.2.2 遗传算法基本思想
• 2.2.3 遗传算法表示
• 2.2.4 遗传算法与排课的对应关系
• 2.2.5 遗传算法基本流程
• 2.2.6 基本遗传算子
• 3. 改进的遗传算法理论描述
• 3.1 几种常用编码方案
• 3.1.1 二进制编码
• 3.1.2 格雷码编码
• 3.1.3 实数编码
• 3.1.4 编码方案分析
• 3.2 改进的遗传算法编码方案
• 3.3 模型设计
• 3.3.1 几种典型的约束条件
• 3.3.2 数学模型
• 3.3.3 适应度函数
• 3.4 改进的遗传算子
• 3.4.1 选择算子
• 3.4.2 交叉算子
• 3.4.3 变异算子
• 4. 排课系统详细设计与实现
• 4.1 系统总体设计
• 4.1.1 编程环境
• 4.1.2 系统结构图
• 4.1.3 系统主要功能模块设计
• 4.1.4 功能模块设计说明
• 4.2 用户主界面设计
• 4.3 排课系统重要模块实现
• 4.3.1 排课准备设置模块设计
• 4.3.2 执行排课模块设计
• 4.3.3 排课查询模块设计
• 5. 排课系统性能测试与分析
• 5.1 时间复杂度性能分析
• 5.1.1 遗传迭代数的测试分析
• 5.1.2 课程对象数量测试分析
• 5.2 排课结果性能分析
• 5.3 结论分析
• 6. 总结和展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 研究生期间发表论文