| 【中文题名】 | 基于遗传算法的自动排课问题的研究 |
| 【英文题名】 | |
| 【学科专业】 | 化工过程机械 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2004-6-24 |
| 【中关键词】 | 排课问题,遗传算法,多目标优化,多目标决策协调,组合优化, |
| 【英关键词】 | Timetabling Problem, Genetic Algorithm, Multiobjective Optimization, Combination Optimization, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明为一个NP完全问题。
遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法，是一种非常有效的解决NP完全的组合问题的方法。本文将遗传算法应用于排课问题的求解，进行了以下几个方面研究工作：
1．系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和难点，用数学模型完整地描述了排课问题，并提出了排课问题求解方法的总体框架和技术路线。
2．给出了排课问题的ERD和类图，设计了排课系统的数据结构，并以此对课表安排过程的各个子算法进行了研究，提出了一个具有局部回溯和启发能力的、易于快速生成可行方案的随机安排算法。
3．对多个模糊排课目标进行定量分析，建立了排课优化目标空间。
4．针对排课问题研究了染色体编码方式以及遗传操作算子的设计，并引入多目标决策协调模型，提出了一种基于多目标决策协调模型的适应度计算方法，并改进了遗传算法一般结构，形成了一套多目标协同优化的排课算法。
5．以VC++和Delphi为基本开发工具，MS SQL S... |
| 【论文题纲】 |
|
摘要 |
2-3 |
|
Abstract(英文摘要) |
3-5 |
|
目录 |
5-8 |
|
第一章 第一章 绪论 |
8-21 |
|
1.1 排课问题的概述 |
8-10 |
|
1.2 排课问题研究评述 |
10-13 |
|
1.2.1 排课问题的理论研究 |
10 |
|
1.2.2 排课问题的求解方法 |
10-13 |
|
1.3 遗传算法的简述 |
13-20 |
|
1.3.1 遗传算法的基本思想 |
14 |
|
1.3.2 遗传算法的一般结构 |
14-16 |
|
1.3.3 遗传算法的特点 |
16-17 |
|
1.3.4 遗传算法与其他搜索技术的比较 |
17-20 |
|
1.4 本文研究内容 |
20-21 |
|
第二章 排课问题的建模 |
21-34 |
|
2.1 排课目标分析 |
21-27 |
|
2.1.1 排课问题的要素 |
21-22 |
|
2.1.2 排课过程的约束条件 |
22-24 |
|
2.1.3 排课问题的组合爆炸和不确定性 |
24-26 |
|
2.1.4 求解目标 |
26-27 |
|
2.2 排课问题的数学模型 |
27-31 |
|
2.2.1 排课问题的优化求解模型 |
27-28 |
|
2.2.2 排课问题的约束满足模型 |
28-31 |
|
2.3 排课问题的求解方案 |
31-34 |
|
第三章 随机可行排课方案的研究 |
34-63 |
|
3.1 面向对象技术在排课系统中的应用 |
34-39 |
|
3.1.1 排课系统的实体关系图(ERD) |
34-36 |
|
3.1.2 排课系统的OOA |
36-39 |
|
3.2 数据结构 |
39-47 |
|
3.2.1 时间要素的处理 |
40-42 |
|
3.2.2 数据库描述 |
42-45 |
|
3.2.3 变量描述 |
45-47 |
|
3.3 主要算法 |
47-62 |
|
3.3.1 排课难度量化 |
48-50 |
|
3.3.2 两个时间安排的冲突判断 |
50-51 |
|
3.3.3 课程拆分算法 |
51-53 |
|
3.3.4 数据读取和对象初始化 |
53-54 |
|
3.3.5 课程安排算法 |
54-58 |
|
3.3.6 课程冲突检验流程 |
58-59 |
|
3.3.7 冲突转移算法 |
59-60 |
|
3.3.8 教室资源维护算法 |
60-61 |
|
3.3.9 教室安排算法 |
61-62 |
|
3.4 本章小结 |
62-63 |
|
第四章 基于GA的多目标排课优化 |
63-85 |
|
4.1 多目标优化的基本概念 |
63-68 |
|
4.2 排课问题的多目标分析 |
68-72 |
|
4.2.1 节次优度 |
68-69 |
|
4.2.2 班级课时日分布均匀度 |
69-70 |
|
4.2.3 教师期望时间的满足度 |
70 |
|
4.2.4 教师课时分布的密集度 |
70-72 |
|
4.3 排课问题中的遗传算法设计 |
72-76 |
|
4.3.1 编码及其染色体表示 |
72 |
|
4.3.2 选择操作 |
72-73 |
|
4.3.3 交叉操作 |
73-74 |
|
4.3.4 变异操作 |
74-75 |
|
4.3.5 修补算子 |
75-76 |
|
4.4 基于多目标决策协调模型的适应度计算 |
76-85 |
|
4.4.1 多目标决策协调模型理论 |
77-81 |
|
4.4.2 适应度的计算 |
81-85 |
|
第五章 实例求解 |
85-95 |
|
5.1 实例说明 |
85-88 |
|
5.2 参数设置 |
88-90 |
|
5.3 初始解生成性能分析 |
90 |
|
5.4 实际求解效果 |
90-93 |
|
5.5 测试数据分析 |
93-94 |
|
5.6 本章小结 |
94-95 |
|
第六章 研究工作总结与展望 |
95-97 |
|
6.1 研究工作总结 |
95 |
|
6.2 展望 |
95-97 |
|
参考文献 |
97-100 |
|
致谢 |
100 |
|
| 【DOI】 | LunWen.ID:2.2008.386972 |
