| 【中文题名】 | 遗传算法在求解时间表问题中的应用研究 |
| 【英文题名】 | Research on the Application of Genetic Algorithm in Solving TTP |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-8-8 |
| 【中关键词】 | 遗传算法,时间表问题,大学课程时间表,启发式算法,多目标,向量评价遗传算法 |
| 【英关键词】 | Genetic Algorithm,Timetable Problem,University Course Timetabling,Heuristic Algorithm,Multi-objective,Vector Evaluated Genetic Algorithm, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 时间表问题是一类特殊的资源调度问题,广泛应用于学校课程和考试的时间安排、各类大型会议、体育比赛、航班(火车、飞机、轮船等)时刻表的制定等。本文以大学课程安排时间表问题为研究对象,分析了其约束条件,建立了数学模型。由于大学课程时间表问题属于NP完全问题,随着求解规模的扩大,传统的求解算法将很难得出其优化解。
遗传算法是一种借鉴生物界自然选择和进化机制发展起来的算法,具有高度并行、随机、自适应强的特点,是一种非常有效解决NP完全问题的方法。
根据大学课程时间表问题的特点,我们对遗传算法做了多方面的改进。文中提出了基于班级课表的主染色体和教室课表、教师课表的辅助染色体,从而方便了问题的求解。针对标准遗传算法局部搜索能力弱、收敛速度慢的缺点,将一些传统的启发式算法引入到遗传算法中,提出了两阶段启发式混合遗传算法,实际的应用结果表明该算法的改进是非常有效的。
在已有的遗传算法求解大学课程时间表问题中,普遍采用了线性加权的方法将各优化目标转化为单目标来进行求解,但由于各优化目标之间存在着相互冲突和矛盾,加权系数难以确定,求解的结果收敛于 |
| 【论文题纲】 |
|
摘要 |
3-5 |
|
ABSTRACT |
5-9 |
|
第一章 绪论 |
9-11 |
|
1.1 研究背景 |
9-10 |
|
1.2 研究内容和特色 |
10-11 |
|
第二章 时间表问题 |
11-22 |
|
2.1 时间表问题 |
11-13 |
|
2.1.1 时间表问题概述 |
11 |
|
2.1.2 时间表问题的一般数学模型 |
11-12 |
|
2.1.3 时间表问题的求解难度 |
12-13 |
|
2.2 排课时间表问题 |
13-17 |
|
2.2.1 排课问题概述 |
13 |
|
2.2.2 人工排课的思维过程 |
13-15 |
|
2.2.3 人工排课的特点 |
15-16 |
|
2.2.4 排课时间表问题是NP完全问题 |
16-17 |
|
2.3 排课时间表问题求解模型 |
17-19 |
|
2.3.1 符号约定 |
17-18 |
|
2.3.2 优化模型 |
18-19 |
|
2.4 排课时间表问题常用求解方法 |
19-22 |
|
第三章 遗传算法的基本原理和方法 |
22-35 |
|
3.1 遗传算法发展历史 |
22-23 |
|
3.2 遗传算法的基本思想 |
23-24 |
|
3.3 遗传算法的基本过程 |
24-32 |
|
3.3.1 编码 |
24-26 |
|
3.3.2 群体设定 |
26 |
|
3.3.3 适应度函数 |
26-28 |
|
3.3.3.1 几种常见的适应度函数 |
26-27 |
|
3.3.3.2 适应度函数的作用 |
27-28 |
|
3.3.3.3 适应度函数的设计 |
28 |
|
3.3.4 遗传操作 |
28-32 |
|
3.3.4.1 选择 |
29-30 |
|
3.3.4.2 交叉／重组 |
30-32 |
|
3.3.4.3 变异 |
32 |
|
3.4 遗传算法的收敛性 |
32-33 |
|
3.5 遗传算法机理的简要分析 |
33 |
|
3.5.1 模式定理 |
33 |
|
3.6 遗传算法的特点 |
33-35 |
|
第四章 基于遗传算法的排课时间表问题求解 |
35-55 |
|
4.1 排课时间表的资源集合 |
35-36 |
|
4.2 排课时间表问题的优化目标 |
36-39 |
|
4.2.1 节次优先度 |
36-37 |
|
4.2.2 上课周次组合优先度 |
37 |
|
4.2.3 教师期望时间优先度 |
37-39 |
|
4.2.4 班级日课时分布均匀度 |
39 |
|
4.3 基于遗传算法的排课时间表求解算法设计 |
39-42 |
|
4.3.1 算法总体思想 |
39-40 |
|
4.3.2 算法总体框架 |
40 |
|
4.3.3 遗传算法设计 |
40-42 |
|
4.3.3.1 染色体结构及编码方式 |
40-42 |
|
4.3.3.2 初始种群的产生 |
42 |
|
4.3.3.3 适应度函数 |
42 |
|
4.4 基于单目标优化的排课时间表求解 |
42-49 |
|
4.4.1 适应度函数设计 |
42-44 |
|
4.4.2 遗传操作 |
44-46 |
|
4.4.3 运算结果与分析 |
46-49 |
|
4.5 启发式算法在排课时间表中的应用 |
49-53 |
|
4.5.1 启发式遗传算法的基本原理 |
49-52 |
|
4.5.2 运算结果及分析 |
52-53 |
|
4.6 本章小结 |
53-55 |
|
第五章 多目标遗传算法在排课时间表问题中的应用 |
55-71 |
|
5.1 多目标优化遗传算法 |
55-61 |
|
5.1.1 多目标优化的基本概念 |
55-59 |
|
5.1.2 MOP的基本求解方法 |
59-60 |
|
5.1.3 多目标优化遗传算法 |
60 |
|
5.1.4 多目标优化遗传算法框架 |
60-61 |
|
5.2 向量评价方法在排课时间表问题中应用 |
61-70 |
|
5.2.1 各单目标的排课遗传算法优化 |
61-64 |
|
5.2.2 向量评价遗传算法(VEGA) |
64-66 |
|
5.2.3 基于VEGA的排课时间表算法框架图 |
66-67 |
|
5.2.4 遗传操作 |
67-68 |
|
5.2.5 运算结果及分析 |
68-70 |
|
5.3 本章小结 |
70-71 |
|
第六章 总结与展望 |
71-73 |
|
6.1 全文总结 |
71 |
|
6.2 研究展望 |
71-73 |
|
参考文献 |
73-76 |
|
攻读硕士学位期间参加的科研项目和发表的论文 |
76-77 |
|
参加的科研项目 |
76 |
|
发表的论文 |
76-77 |
|
致谢 |
77 |
|
| 【DOI】 | LunWen.ID:2.2008.387378 |
