基于遗传算法的排课问题研究

论文摘要

排课问题是一个有约束、多目标的组合优化问题,已经被证明是一个NP完全问题。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法,由于其具有健壮性,特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。本文将遗传算法应用于排课问题求解,首先讨论了排课问题的影响要素、主要约束条件、求解目标和组合不确定性,建立了排课问题的数学模型;其次根据排课问题的特点将课表编排分解为时间安排和教室安排两部分在时间安排中分两个步骤进行,一是对某一门课程的时间安排(单目标),从中找到几个近似最优的安排方案,二是对所有课程集合的时间安排(多目标),寻找所有课程安排的一个先后顺序排列。然后在时间安排的基础上对教室进行安排,提出了解决“甩课”问题的“回溯”调整方法。本文讨论的模型是遗传算法在排课问题中一种很有效的应用,随着对此问题越来越多的关注,相信遗传算法一定可以更好的解决排课问题。

论文目录

• 摘要
• Abstract
• 第1章 排课问题概述
• 1.1 大学课程表问题的描述
• 1.1.1 时间表问题概述
• 1.1.2 时间表问题的一般数学模型
• 1.1.3 大学课程表问题概述
• 1.2 大学课程表问题的研究情况
• 1.2.1 大学课程表问题的理论研究
• 1.2.2 大学课程表问题的常用解决方法
• 1.3 排课问题各种算法的比较
• 1.4 本文的主要研究内容
• 第2章 遗传算法简介
• 2.1 遗传算法简介
• 2.1.1 遗传算法的发展
• 2.1.2 遗传算法的基本思想
• 2.1.3 遗传算法的一般结构
• 2.1.4 遗传算法的基本操作
• 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.2.1 排课问题的资源集合
• 3.2.2 排课问题的基本约束条件
• 3.2.3 排课问题的优化目标
• 3.2.4 排课问题的数学模型
• 3.3 排课问题的求解方案
• 第4章 基于遗传算法的排课问题算法设计
• 4.1 单目标排课问题的遗传算法设计
• 4.1.1 单目标排课问题的遗传算法设计
• 4.1.2 单目标排课问题遗传算法的结束条件
• 4.2 多目标排课问题的遗传算法设计
• 4.2.1 多目标排课问题的遗传算法设计
• 4.2.2 算法存在的问题及其改进
• 4.2.3 多目标排课问题遗传算法的结束条件
• 4.3 算法框架
• 第5章 教室安排算法设计
• 5.1 教室安排流程设计
• 5.2 解决"甩课"问题的方法
• 5.2.1 "回溯"调整法
• 5.2.2 "回溯"调整的两种方式
• 结论
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文