学位论文 > 优秀研究生学位论文题录展示

时间表问题的研究

作　者: 丁晶
导　师: 吴萍
学　校: 华东师范大学
专　业: 计算机应用技术
关键词: 分组遗传算法序列模型算法时间表问题大学课程表问题
分类号: TP301
类　型: 硕士论文
年　份: 2008年
下　载: 135次
引　用: 0次
阅　读: 论文下载

内容摘要

时间表问题是一类特殊的资源调度问题，广泛应用于学校课程安排、会议日程安排、体育比赛和航班时刻表的制定等。所以如何求解时间表问题成为一个关键的问题。本文以大学课程安排为例子，介绍了一种图形学和人工智能算法相结合的一种方法来对时间表问题进行求解。图形理论中的着色问题其本质是一个划分问题，将相互之间有冲突的点划分到不同的子集中去。所以，由于图形着色的这种独特的能力，在现实中有着广泛的应用，尤其是在需要解决冲突的领域。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的算法，具有高度并行、随机、自适应强的特点，是一种非常有效解决NP完全问题的方法。课程安排问题由于要考虑的限制条件相对来说比较多，属于限制满足的问题，根据这个特征，本文利用图形着色理论(Graph Color Theory)的点着色来表示这些限制条件，将整体的排课分解成三种图形(周图形、日图形、教室图形)来表示。图形中各个节点为要进行分析的对象，即教师、课程、时段以及教室，每条边表示对象之间的互斥关系。本文的工作重点在于对点着色模型进行求解。针对点着色模型，提出了两个切实可行的求解方法。第一个是分组遗传算法，第二个是基于序列模型的点着色求解方法。

全文目录

摘要  7-8
Abstract  8-11
第1章绪论  11-14
  1.1 引言  11
  1.2 研究背景  11-14
    1.2.1 遗传算法  11-12
    1.2.2 图着色  12
    1.2.3 本文的主要工作  12-14
第2章文献回顾  14-21
  2.1 排课问题  14-16
  2.2 排课问题的相关研究  16-17
  2.3 图着色方法  17-19
  2.4 智能算法  19-20
  2.5 本章小结  20-21
第3章基本原理与方法  21-33
  3.1 图形着色理论  21-23
    3.1.1 点着色  21-23
  3.2 遗传算法  23-33
    3.2.1 遗传算法的发展历史  23-24
    3.2.2 遗传算法的基本理论  24-32
    3.2.3 本章小结  32-33
第4章排课问题的求解  33-46
  4.1 着色理论应用于排课问题  33-38
    4.1.1 排课中的点着色  33-34
    4.1.2 排课问题图形化  34-38
  4.2 遗传算法求解图形着色  38-41
    4.2.1 编码(Representation)  38-39
    4.2.2 适应度函数(Fitness)  39
    4.2.3 选择算子(Selection Operation)  39
    4.2.4 交叉算子(Crossover Operation)  39-40
    4.2.5 变异算子(Mutation Operation)  40-41
  4.3 算法程序描述  41-45
  4.4 本章小结  45-46
第5章基于排列模型求解k着色问题  46-52
  5.1 Merge Model(MM)  46-48
  5.2 合并排列模型(Permutation Merge Model PMM)  48-50
  5.3 运用进化算法求解合并排列(PMM)  50
  5.4 适应度函数(Fitness)  50-51
  5.5 本章小结  51-52
第6章实验验证  52-58
  6.1 实验环境  52-54
    6.1.1 Genertor介绍  52-53
    6.1.2 实验数据  53-54
    6.1.3 实验结果  54
  6.2 实例验证  54-57
  6.3 本章小结  57-58
第7章总结与展望  58-59
  7.1 本文工作总结  58
  7.2 进一步的展望  58-59
参考文献  59-61
致谢  61-62
附录: 攻读研究生期间发表的论文  62

时间表问题的研究

内容摘要

全文目录

相似论文