基于改进的混合遗传算法的排课问题研究

摘要

为了保证教学质量，学校需要制定一套规范的教学计划，而课表编排是教学计划得以顺利执行的重要一环。随着高校学生数量猛增，数据规模增大、约束条件增多，在教学资源一定的情况下排课越来越复杂，人工排课已经难以满足课表编排的工作要求。因此，利用计算机解决排课问题成为当务之急。
　　 排课问题是典型的带有多重约束的多目标组合优化问题，并且早在70年代已经被证明是一个NP完全问题。排课的本质就是将课程分配到合适的时间段和合适的教室。由于排课问题复杂多变，几十年来一直没有很好解决。本文的目的就是要寻找一种解决这种复杂问题的新方法。
　　 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的自适应随机搜索算法。它具有良好的并行性、通用性、稳定性，是一种非常有效的解决NP完全问题的方法。目前，使用遗传算法解决排课问题已经成为众多学者和高校的研究热点。贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。本文所做的工作就是针对单一算法存在的问题和不足，设计改进的混合遗传算法，并利用改进的混合遗传算法对高校排课问题进行较为深入的研究。
　　 本文首先对排课问题进行了概述，介绍国内外对这一问题的研究现状和发展趋势，从高校排课实际情况出发，提出排课问题的数学模型。然后概括说明了遗传算法和贪婪算法的结构、功能、特征，并分析了组合优化理论的主要特点及现状。针对遗传算法的不足，把贪婪策略和最优保存策略加入到遗传算法中，有效地引导交叉和变异操作;在遗传算法中加入贪婪策略后，大大地拓展了算法的搜索空间，同时避免了基本遗传算法容易陷入局部极小的缺陷。最后论文采用改进的混合遗传算法对排课问题进行编程，通过分析测试运行结果，证明了改进的混合遗传算法完全适用于排课问题，而且具有更高的效率，为排课问题的发展提供了新的思路。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究综述

1．2．1 国外研究历史和现状

1．2．2 国内研究历史和现状

1．3 现存问题与研究内容

1．4 论文组织结构

第2章 排课问题的分析与建模

2．1 排课问题概述

2．2 排课问题的数学建模

2．2．1 排课问题中的五大要素

2．2．2 排课问题中的约束条件

2．2．3 排课问题的求解目标

2．2．4 排课问题的数学模型

2．3 排课问题的求解算法综述

2．4 排课问题的组合优化求解策略

2．4．1 典型的组合优化问题

2．4．2 解决组合优化问题的常用算法

2．5 本章小结

第3章 基本算法介绍

3．1 遗传算法介绍

3．1．1 遗传算法发展过程

3．1．2 遗传算法基本术语

3．1．3 遗传算法的基本思想

3．1．4 遗传算法的基本操作

3．1．5 遗传算法的特点

3．2 贪婪算法介绍

3．2．1 贪婪算法的基本思想

3．2．2 贪婪算法的求解步骤

3．2．3 贪婪算法求解问题性质

3．3 混合遗传算法

3．4 本章小结

第4章 基于改进混合遗传算法的排课问题求解

4．1 采用改进混合遗传算法求解排课问题的原因

4．2 改进的混合遗传算法流程图

4．3 改进的混合遗传算法实现方法

4．3．1 编码及其染色体表示

4．3．2 基于预处理的种群初始化操作

4．3．3 选择操作

4．3．4 交叉操作

4．3．5 变异操作

4．3．6 适应度函数

4．4 本章总结

第5章 实验结果分析

5．1 实验环境的搭建

5．2 数据结构的设计

5．3 实验案例分析

5．4 算法合理性分析

5．5 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢