基于混合遗传算法的高校排课问题的研究

摘要

排课问题是一个具有多约束条件的多目标组合优化问题。早在1976年，排课问题就已经被证明是一个NPC问题。结合国内高校的实际情况，由于每个高校的教学计划、教学要求以及教学约束条件都是各不相同的，排课过程中涉及的排课因素也比较多，所以很难得到排课问题的最优解。传统的人工排课的方式不仅需要花费大量的时间，而且排课结果也不能满足现代教学活动的要求。现在，越来越多的学者开始研究如何利用启发式算法在短时间内得到排课问题的满意解，而不是最优解。　　遗传算法是一种全局优化搜索算法。该算法具有良好的并行性、通用性、稳定性，是一种有效地解决NPC问题的算法。模拟退火算法是一种启发式搜索算法，它是基于Monte-Carlo迭代求解策略的一种随机寻优算法。该算法可以用来处理高复杂性和高维度的问题，其求解的结果具有高质量、高效率等特点。但该算法受参数影响大、收敛速度慢、且算法不具备并行性。　　本文通过对高校排课问题的分析与建模，提出了一种基于遗传算法与模拟退火-分支限界法相结合的高校排课算法。本文首先介绍了排课问题的研究背景与意义，主要介绍了国内外对排课问题的研究现状和存在的一些问题。然后重点介绍了排课问题中常用的算法：遗传算法和模拟退火算法，同时也介绍了分支限界法。之后，本文对高校排课问题涉及的排课因素和约束条件进行了分析和建模，将高校排课的实际问题转化为数学问题。针对高校排课的实际情况，提出了一种基于遗传算法与模拟退火-分支限界法相结合的高校排课算法。算法一方面改进了遗传算法中的遗传操作过程，促进种群不断向较好的方向遗传进化。另一方面，算法利用模拟退火算法与分支限界法相结合的思想进行个体优化。个体优化时，模拟退火算法在操作过程中产生多个个体，从而改进该算法不具备并行性的缺点。然后，利用分支限界法的思想，对产生的个体规模进行控制，使得个体规模不会太大。通过这样，算法既提高了个体的适应度，同时也使得运算时间不会太大。最后，实验结果表明，与传统的模拟退火算法、遗传算法和遗传模拟退火算法相比，本文算法平均多耗时 8730～10300 秒之间。但本文算法的最优解适应度要高于其他算法 0.0311～0.0411 之间，本文算法的平均适应度要高于其他算法 0.0313～0.0409 之间。虽然本文算法需要更多的时间，但是本文算法可以得到适应度更好的个体，即算法可以得到更好的排课结果。

目录

1 绪 论

1.1 研究背景与意义

1.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.3 分支限界法

2.4 本章小结

3 高校排课问题的分析与建模

3.1 高校排课问题的概述

3.2 高校排课问题涉及到的因素分析

3.3 高校排课问题的约束条件

3.4 高校排课问题的数学建模

3.4.1 排课问题中各因素的数学模型

3.4.2 排课问题中约束条件的数学描述

3.5 本章小结

4 基于遗传算法与模拟退火-分支限界法相结合的高校排课算法

4.1 算法设计整体思路

4.2 染色体的编码

4.3 初始种群的生成

4.4 适应度函数设计

4.5 选择操作

4.6 交叉操作

4.7 变异操作

4.8 个体优化

4.8.1 邻域交换设计

4.8.2 模拟退火算法与分支限界法相结合的算法设计

4.9 参数设置

4.10 本章小结

5 实验结果与分析

5.1 实验环境的搭建

5.2 实验数据集

5.3 评价指标

5.4 实验结果与分析

5.5 本章小结

6 总结与展望

6.1 论文总结

6.2 未来工作展望

参考文献

附录

A. 作者在攻读硕士学期期间发表的论文

B. 作者在攻读硕士学位期间参与的科研项目

C. 学位论文数据集

致谢