基于遗传算法的排课问题研究及其应用

论文摘要

排课是学校教学管理中十分重要确又相当复杂的管理工作之一,随着高校教育事业的发展,学生人数的不断增加,在教室资源有限的前提下课程编排显得更加繁重,同时课程的编排也成为教学管理工作的关键,在一定程度和深度上影响着学生培养与教学质量的提高。本文将遗传算法和多目标优化理论应用于排课问题的求解,提出一个课表方案的随机生成和优化算法,能够较大程度地反映实际排课情况和尽量达到多个目标最优。本论文的主要工作包括:①详细讨论了排课问题中的影响因素、主要约束条件,分析排课问题的求解难点和目标,用数学模型完整地描述了排课问题,并提出求解排课问题方案的总体思路和技术路线。②针对排课问题设计了基因编码方案、染色体结构以及遗传算子,并提出了个体适应度评价函数的计算方法。③以JSP为前台开发工具,MYSQL为后台数据库,设计并实现了基于遗传算法的自动排课系统。④利用上述基于遗传算法的排课优化算法进行求解,并对系统一些中间参数进行跟踪分析,从实验的角度论证算法的可行性。本文重点研究了排课遗传算法对排课系统效率的影响。研究发现,通过构建遗传算法的混合式基因编码、改进杂交方式、量化教师上课时间偏好权值参数,能显著降低算法的复杂性,提高排课系统的搜索效率。实验结果表明,其过程的目标值跟踪显示,算法稳健趋优,所得结果令人满意。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 问题的提出及研究意义
• 1.1.1 问题的提出
• 1.1.2 研究意义
• 1.2 国内外排课问题的研究现状
• 1.2.1 排课问题的理论研究
• 1.2.2 排课问题的求解方法
• 1.2.3 遗传算法与其他搜索技术的比较
• 1.3 本文研究的目的和主要内容
• 1.3.1 本文研究的目的
• 1.3.2 本文研究的主要内容
• 1.4 本文结构安排
• 2 遗传算法的基本理论
• 2.1 遗传算法简介
• 2.1.1 遗传算法的产生和发展
• 2.1.2 遗传算法的基本术语
• 2.1.3 遗传算法的基本思想
• 2.2 基本遗传算法的表示
• 2.3 遗传算法的基本操作和特点
• 2.3.1 遗传算法的基本操作
• 2.3.2 遗传算法的特点
• 2.4 遗传算法设计的一般步骤
• 2.5 遗传算法存在的缺陷及改进
• 2.5.1 初始种群的均匀化改进
• 2.5.2 自适应的交叉概率和变异概率改进
• 2.5.3 选择算子的改进
• 2.5.4 交叉和变异算子的改进
• 2.5.5 并行遗传算法
• 2.6 本章小结
• 3 排课问题的建模
• 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.3.3 排课问题的优化求解模型
• 3.4 本章小结
• 4 排课系统的设计
• 4.1 系统架构
• 4.1.1 系统开发平台
• 4.1.2 系统体系结构
• 4.2 需求分析
• 4.2.1 业务需求分析
• 4.2.2 功能需求分析
• 4.3 数据库设计
• 4.3.1 概念模型设计
• 4.3.2 逻辑模型设计
• 4.3.3 数据表的结构
• 4.4 遗传算法的设计
• 4.4.1 构造基因编码和染色体
• 4.4.2 产生初始种群
• 4.4.3 冲突检测与消除
• 4.4.4 个体适应度评价函数
• 4.4.5 遗传算子的设计
• 4.4.6 遗传运算终止条件
• 4.5 本章小结
• 5 排课系统的实现
• 5.1 排课系统的主界面
• 5.1.1 登录系统
• 5.1.2 排课参数设置
• 5.1.3 自动排课
• 5.2 参数查看模块
• 5.3 课表查询及打印模块
• 5.4 用户维护模块
• 5.5 本章小结
• 6 排课系统的测试与分析
• 6.1 排课系统的测试环境
• 6.2 排课系统测试
• 6.2.1 种群规模
• 6.2.2 交叉概率
• 6.2.3 变异概率
• 6.3 实验数据分析
• 6.4 本章小结
• 7 结论与展望
• 7.1 主要结论
• 7.2 后续工作的展望
• 致谢
• 参考文献
• 附录