基于遗传和禁忌搜索算法的排课系统研究与实现

论文摘要

排课问题是学校教学管理中十分重要而又复杂的管理工作之一,随着课程的增多,学生人数的增加,在教室资源有限的情况下,要在短期内排出一张令所有教师和班级都满意的课表难度相当大,它是一个有约束的、多目标的组合优化问题,并且已被证明是一个NP完全问题。本文分析了大学课表问题的一般性质以及各种求解方案的优势和不足,并针对目前国内高校的教学实际设计了大学课表问题的模型。该模型考虑了教学实际中所涉及的一般因素和约束,由于遗传算法是一种适合求解带有多参数、多变量、多目标和在多区域但连通性较差的NP—HARD优化问题的智能优化算法,所以本文考虑用遗传算法来解决排课问题,但是遗传算法具有早熟的现象,很快收敛到局部最优而非全局最优解,因此结合了局部搜索方法之一的禁忌搜索算法,用遗传算法结合禁忌搜索算法来解决排课问题,对比比较和计算分析,取得了良好的效果。本文主要进行了以下几个方面的研究工作:1、系统讨论了排课问题中的影响因素、主要约束条件、求解目标和难点,用数学模型描述了排课问题。2、设计了排课系统的数据结构,并对一些子算法进行研究。3、研究染色体编码和遗传算子,并在变异阶段用禁忌搜索算法来实现,形成一个多目标的优化排课算法。4、以VS2005为开发工具,SQL SERVER2000为数据库实现了GA(GeneticAlgorithm)结合TS(Tabu Search)的智能排课系统,分析显示该系统能完成预期要求,结果令人满意。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景
• 1.2 研究的意义及方法
• 1.3 排课问题研究综述
• 1.3.1 基于传统数学和运筹学的方法
• 1.3.2 基于人——机交互的方法
• 1.3.3 基于人工智能的方法
• 1.3.4 基于启发式算法的方法
• 1.3.5 遗传算法与其他搜索技术的比较
• 1.4 国内外研究现状
• 1.5 本文主要特色
• 1.6 本文的组织结构
• 第二章 排课问题分析
• 2.1 排课问题概述
• 2.2 排课问题的数学描述
• 2.2.1 排课问题因素
• 2.2.2 排课问题中约束的描述
• 2.2.3 排课问题的优化求解模型
• 2.3 排课问题的求解方案
• 2.4 本章小结
• 第三章 排课问题的算法设计
• 3.1 排课问题的双目标分析
• 3.1.1 班级课时日分布优度
• 3.1.2 班级日组合优度
• 3.2 排课问题的GATS算法设计
• 3.2.1 GA编码
• 3.2.2 初始群体的产生及冲突的消除
• 3.2.3 适应度函数的定义和计算
• 3.2.4 GA的运行
• 3.3 与其他排课算法的比较
• 3.3.1 关联规则FP—growth算法
• 3.3.2 基于时间位图迭加匹配算法
• 3.3.3 基于分组优化决策算法
• 3.3.4 分支定界算法
• 3.3.5 有限回溯
• 3.4 本章小结
• 第四章 排课问题的系统分析
• 4.1 系统开发模式
• 4.2 排课系统流程图
• 4.3 数据流程图
• 4.4 数据表分析
• 4.5 系统架构约束与目标
• 4.6 系统整体框架
• 4.7 系统安全架构
• 4.8 功能模块分析
• 4.9 系统的非功能性需求
• 4.10 本章小结
• 第五章 系统设计
• 5.1 选择VS.net作为开发工具优点
• 5.2 系统建模
• 5.3 数据库设计
• 5.3.1 数据库管理系统特点
• 5.3.2 数据库管理技术
• 5.3.3 排课数据库分析
• 5.4 概念模型设计
• 5.5 逻辑模型设计
• 5.6 数据库详细设计
• 5.7 算法引入参数的定制
• 5.8 功能模块的设计
• 5.8.1 形成开课任务模块
• 5.8.2 院系安排任务反馈模块
• 5.8.3 自动排课模块
• 5.8.4 调整模块
• 5.8.5 冲突检查模块
• 5.8.6 课表输出和打印模块
• 5.9 排课系统操作流程和界面设计
• 5.10 本章小结
• 第六章 总结和展望
• 6.1 总结
• 6.2 展望
• 附件
• 参考文献
• 攻读硕士学位期间完成的学术论文
• 致谢