改进的遗传算法在排课问题上的应用研究

论文摘要

本文对高校计算机排调课问题进行了详细分析,并对排课问题的多目标进行了详细的描述且加以量化;结合UML分析方法对排课需求进行数据库建模;通过分析遗传算法和模拟退火算法,合理的将遗传算法和模拟退火算法加以结合并加以改进,有效的增强了经典遗传算法的局部寻解能力。同时将此算法应用于排课系统中,并结合排课的具体问题对该算法再次进行改进,使改进后的遗传算法更适合解决NP完全问题;最后运用当今B/S模式的主流技术(spring/struts/hibernate)实现了基于改进的遗传算法的高校排课系统。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 引言
• 1.2 计算机排课问题的研究动态
• 1.3 本课题主要研究内容
• 2 排课问题分析
• 2.1 排课问题概述
• 2.2 排课目标分析
• 2.2.1 排课问题的心理分析
• 2.2.2 排课问题的要素
• 2.2.3 排课问题的约束条件
• 2.2.4 排课问题的组合爆炸和不确定性
• 2.3 排课问题的数学模型
• 2.4 高校排调课问题的特点
• 2.5 高校排调课问题的逻辑模型
• 2.6 本章小结
• 3 遗传算法的改进
• 3.1 遗传算法的生物学基础
• 3.2 基本遗传算法
• 3.2.1 遗传算法的发展
• 3.2.2 基本遗传算法
• 3.2.3 基本遗传算法的应用步骤
• 3.3 模拟退火算法
• 3.4 遗传算法中融入模拟退火算法
• 3.5 GSA 算法的改进
• 3.5.1 初始种群的均匀化改进
• 3.5.2 最佳个体替换策略
• 3.6 小结
• 4 排课系统中的UML 的分析方法
• 4.1 统一建模语言UML
• 4.1.1 UML 简介
• 4.1.2 软件工程化过程 RUP 简介
• 4.1.3 UML 建模过程
• 4.2 基于GSA 算法的排课系统的建模过程
• 4.2.1 功能描述
• 4.2.2 建立用例模型
• 4.2.3 设计数据库
• 4.2.4 建立对象模型
• 4.2.5 建立动态模型
• 4.2.6 检查模型的一致性
• 4.3 小结
• 5 基于GSA 算法的排课系统的设计与实现
• 5.1 排课问题的多目标分析
• 5.1.1 硬约束分析
• 5.1.2 软约束分析
• 5.2 应用GSA 算法的排课方案
• 5.3 排课系统核心算法GSA 算法
• 5.3.1 排调课的染色体设计
• 5.3.2 课程冲突检测及解决
• 5.3.3 初始种群设计
• 5.3.4 适应度函数设计
• 5.3.5 选择操作
• 5.3.6 交叉操作
• 5.3.7 变异操作
• 5.3.8 个体模拟退火操作
• 5.4 系统测试及参数选择
• 5.4.1 初始种群和遗传代数
• 5.4.2 交叉概率
• 5.4.3 变异概率
• 5.4.4 个体模拟退火初温
• 5.5 排课质量评估
• 5.5.1 基本硬约束（Basic Hard Constraint）评估
• 5.5.2 排课的多目标评估
• 5.6 小结
• 6 结论与展望
• 6.1 本文研究的主要结论
• 6.2 展望
• 参考文献
• 致谢
• 攻读硕士期间参与的科研项目
• 攻读学位期间发表的论文
• 附录A