基于遗传算法的高校排课系统的设计与实现

论文摘要

排课问题是一个有约束、多目标的组合优化问题,并且已经被证明为是一个NP完全问题。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法,是一种非常有效的解决NP完全的组合问题的方法。本论文将遗传算法应用于排课问题的求解,进行了以下几个方面的研究工作：（1）系统、完整地讨论了排课问题中的影响因素、主要约束条件和求解目标,用数学模型描述了排课问题；（2）改进了遗传算法的一般编码方法,综合采用三维编码和自适应的交叉、变异概率设计方法,提出了一套基于三维编码的自适应遗传算法；（3）以Netbeans6.0为前台开发工具,MySQL为后台数据库,基于MVC的Servlet+JSP+JavaBean架构设计并实现了基于上述改进遗传算法的自动排课系统。经过对一个具有100间教室和400个授课事件的实例测试,在教室利用率、课程日分别均匀度、体育课上课时间三个因素组成的目标空间上进行求解,取得了令人满意的结果。上述自动排课系统的核心功能模块已经过测试,继续基于B/S进行系统完善,可以大大提高教务工作人员的排课效率。

论文目录

• 摘要
• Abstract
• 第一章 前言
• 1.1 问题的提出
• 1.1.1 国外研究现状
• 1.1.2 国内研究现状
• 1.1.3 当前的发展趋势
• 1.2 系统解决的主要问题
• 1.3 本文的主要工作
• 1.4 本文的组织
• 第二章 遗传算法的基本理论
• 2.1 遗传算法的发展
• 2.2 遗传算法的基本思想
• 2.3 遗传算法的一般结构和遗传操作
• 2.4 遗传算法的特点
• 2.5 遗传算法与其他搜索技术的比较
• 第三章 排课问题的建模
• 3.1 排课问题概述
• 3.2 排课的目标分析
• 3.2.1 排课因素
• 3.2.2 排课的约束条件
• 3.2.3 排课问题的组合爆炸和不确定性
• 3.2.4 排课的求解目标
• 3.3 排课问题的数学描述
• 3.3.1 排课问题数学描述
• 3.3.2 排课问题的优化求解模型
• 3.4 遗传算法设计的一般步骤
• 3.4.1 步骤简述
• 3.4.2 算法流程
• 3.5 排课问题的求解方案
• 第四章 基于遗传算法的排课优化
• 4.1 排课问题的优化目标分析
• 4.1.1 节次优度
• 4.1.2 班级课时日分布均匀度
• 4.1.3 班级日组合优度
• 4.2 遗传算法的改进
• 第五章 排课系统相关技术
• 5.1 Web相关技术
• 5.1.1 Web技术的发展
• 5.1.2 Servlet
• 5.1.3 JSP
• 5.1.4 JavaBean
• 5.2 基于MVC的Web开发框架
• 5.2.1 模型1
• 5.2.2 模型2与MVC
• 5.3 数据库访问
• 5.3.1 JDBC驱动程序的类型
• 5.3.2 JDBC API
• 第六章 排课系统的设计与实现
• 6.1 软件结构设计
• 6.1.1 系统实现模式
• 6.1.2 系统模块功能说明
• 6.2 数据库设计
• 6.2.1 数据流图
• 6.2.2 E-R图及关系模式
• 6.3 基于遗传算法的排课系统设计与实现
• 6.3.1 编码方案
• 6.3.2 初始化群体
• 6.3.3 定义适应度函数
• 6.3.4 选取交叉变异概率参数
• 6.3.5 遗传算子的设计
• 6.3.6 遗传运算停止规则
• 6.3.7 冲突检测
• 6.3.8 生成课程表
• 6.4 测试
• 6.4.1 对种群规模的测试
• 6.4.2 对交叉概率Pc的测试
• 6.4.3 对变异概率Pm的测试
• 6.4.4 对自适应参数的测试
• 结论
• 参考文献
• 致谢
• 附录