| 【中文题名】 | 基于三维编码的自适应遗传算法在排课系统上的应用 |
| 【英文题名】 | The Application of Self-Adaptive Genetic Algorithm Based on Three-Dimension Coding on Curriculum Scheduling System |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-10-29 |
| 【中关键词】 | 排课,遗传算法,三维编码,自适应,时间表, |
| 【英关键词】 | Curriculum Scheduling,Genetic Algorithm,Three-Dimension Coding,Self-Adapting,Timetable, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>计算机软件>专用应用软件> |
| 【论文摘要】 |
排课问题是一个有约束、多目标的组合优化问题，并且已经被证明为是一个NP完全问题。
遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、自适应的随机搜索算法，是一种非常有效的解决NP完全的组合问题的方法。
本论文将遗传算法应用于排课问题的求解，进行了以下几个方面研究工作：
(1)系统、完整地讨论了排课问题中的影响因素、主要约束条件和求解目标，用数学模型描述了排课问题；
(2)改进了遗传算法的一般编码方法，综合采用三维编码和自适应的交叉、变异概率设计方法，提出了一套基于三维编码的自适应遗传算法；
(3)以Delphi7.0为前台开发工具，SQL Server 2000为后台数据库，设计并实现了基于上述改进型遗传算法的自动排课系统。经过对一个具有110间教室和389个授课事件的实例测试，在教室利用率、课程日分布均匀度、体育课上课时间三个因素组成的目标空间上进行求解，取得了令人满意的结果。
上述自动排课系统已在我省某高校的排课工作中实际使用，大大提高了工作人员的排课效率。 |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
ABSTRACT |
4-8 |
|
第1章 引言 |
8-20 |
|
1.1 问题的提出及课题来源 |
8-9 |
|
1.1.1 问题的提出 |
8-9 |
|
1.1.2 课题来源 |
9 |
|
1.2 研究现状与发展趋势 |
9-12 |
|
1.2.1 国内外的研究现状 |
9-11 |
|
1.2.2 当前的发展趋势 |
11-12 |
|
1.3 排课问题解决方法综述及遗传算法解法的优势 |
12-17 |
|
1.3.1 排课问题解决方法综述 |
12-16 |
|
1.3.2 遗传算法解法的优势 |
16-17 |
|
1.4 现有遗传算法解决方案及其不足之处 |
17-18 |
|
1.4.1 现有遗传算法解决方案 |
17 |
|
1.4.2 现有遗传算法解决方案不足之处 |
17-18 |
|
1.5 论文的研究内容及创新点 |
18-20 |
|
1.5.1 论文的研究内容 |
18-19 |
|
1.5.2 论文的创新点 |
19-20 |
|
第2章 问题的描述 |
20-28 |
|
2.1 时间表问题 |
20-22 |
|
2.1.1 时间表问题的描述 |
20-21 |
|
2.1.2 时间表问题的相关定义 |
21-22 |
|
2.2 课程表问题 |
22-28 |
|
2.2.1 课程表问题的相关因素 |
22-23 |
|
2.2.2 课程表问题中的冲突与约束 |
23-26 |
|
2.2.3 课程表问题的数学描述 |
26 |
|
2.2.4 课程表问题的求解目标 |
26-28 |
|
第3章 遗传算法简介 |
28-35 |
|
3.1 遗传算法的简要由来 |
28 |
|
3.2 遗传算法的常用术语 |
28-29 |
|
3.3 遗传算法的基本原理 |
29-31 |
|
3.4 遗传算法的主要操作 |
31-32 |
|
3.4.1 选择 |
31 |
|
3.4.2 交叉 |
31-32 |
|
3.4.3 变异 |
32 |
|
3.5 遗传算法设计的一般步骤 |
32-33 |
|
3.6 遗传算法研究的新领域 |
33-35 |
|
第4章 排课系统的设计 |
35-46 |
|
4.1 软件结构设计 |
35-36 |
|
4.1.1 软件模块结构 |
35-36 |
|
4.1.2 各模块功能简介 |
36 |
|
4.2 数据库设计 |
36-39 |
|
4.2.1 数据流图 |
36-38 |
|
4.2.2 E-R图及关系模式 |
38-39 |
|
4.3 自动排课模块的基于三维编码的自适应遗传算法设计 |
39-46 |
|
4.3.1 三维编码方式 |
40-41 |
|
4.3.2 初始群体及种群规模 |
41-42 |
|
4.3.3 遗传算子的设计 |
42-43 |
|
4.3.4 个体适应度评价函数 |
43-44 |
|
4.3.5 遗传运算终止条件 |
44 |
|
4.3.6 自适应的交叉和变异概率 |
44-45 |
|
4.3.7 冲突检测 |
45-46 |
|
第5章 排课系统的实现 |
46-55 |
|
5.1 数据库结构 |
46-49 |
|
5.1.1 数据表的结构 |
46-48 |
|
5.1.2 数据表之间的关系 |
48-49 |
|
5.2 自动排课模块的基于三维编码的自适应遗传算法实现 |
49-55 |
|
5.2.1 三维编码的实现 |
49 |
|
5.2.2 初始种群的产生 |
49-51 |
|
5.2.3 冲突检测 |
51-52 |
|
5.2.4 个体适应度计算 |
52-53 |
|
5.2.5 自适应地产生交叉、变异概率 |
53 |
|
5.2.6 选择操作 |
53 |
|
5.2.7 交叉操作 |
53 |
|
5.2.8 变异操作 |
53-54 |
|
5.2.9 课程表的产生 |
54-55 |
|
第6章 排课系统的测试与分析 |
55-59 |
|
6.1 测试 |
55-57 |
|
6.1.1 对自适应参数的测试 |
55-56 |
|
6.1.2 对种群规模的测试 |
56 |
|
6.1.3 对课程数量的测试 |
56-57 |
|
6.2 分析 |
57-59 |
|
6.2.1 本排课系统的合理性 |
57 |
|
6.2.2 本排课系统的特点 |
57-58 |
|
6.2.3 本排课系统的不足之处 |
58-59 |
|
第7章 总结与展望 |
59-61 |
|
7.1 总结 |
59 |
|
7.2 展望 |
59-61 |
|
致谢 |
61-62 |
|
参考文献 |
62-65 |
|
附录 |
65-73 |
|
攻读学位期间的研究成果 |
73 |
|
| 【DOI】 | LunWen.ID:2.2008.389119 |
