| 【中文题名】 | 基于蚁群算法的排课问题的研究 |
| 【英文题名】 | Research of Courses Arrangement Based on Ant Colony Algorithm |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-6-4 |
| 【中关键词】 | 排课问题,二部图,蚁群算法,,, |
| 【英关键词】 | Courses Arrangement Problem,Bipartite Graph,Ant Colony Algorithm, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>一般性问题>理论、方法>算法理论 |
| 【论文摘要】 | 为了保证教学质量，学校必须制定一套规范的教学计划，而课表编排是教学计划得以顺利执行的重要一环。随着高校学生数量猛增，数据规模大、各种约束复杂，在教学资源一定的情况下排课越来越繁难。人工排课已经难以完成课表编排的工作要求。因此，利用计算机解决排课问题成为当务之急。
蚁群算法是近十几年才提出来的一种新型模拟进化算法，通过候选解组成的群体的进化过程来寻求最优解。该过程包括适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流以期产生性能更好的解。蚁群算法通过正反馈和负反馈相结合的机制使算法朝着最优解方向发展，又保持搜索范围避免过早停滞。从而得到一定程度上的满意解。
本文对基本蚁群算法的思想及原理进行了分析，结合排课问题的自身特点提出一种适于排课问题的改进的蚁群算法。在此，对排课问题进行了抽象，将解决排课问题转化为寻求二部图的最大匹配问题，由于排课问题可以描述为图结构，这给蚁群算法介入排课问题提供了一个契机。而如何满足排课问题中的多种约束条件是排课问题的关键问题，在此算法中引入个体启发信息等策略。考虑把这些约束具体抽象成一些合适的数字，适... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
Abstract |
6-11 |
|
第1章 绪论 |
11-15 |
|
1.1 引言 |
11-12 |
|
1.2 研究的目的和意义 |
12 |
|
1.3 排课问题的研究现状 |
12-13 |
|
1.4 本文研究内容 |
13-15 |
|
第2章 排课问题分析 |
15-19 |
|
2.1 排课问题概述 |
15-16 |
|
2.2 排课问题的数学描述 |
16-19 |
|
2.2.1 排课问题中的因素 |
16-17 |
|
2.2.2 排课问题的数学描述 |
17 |
|
2.2.3 排课问题中约束的描述 |
17-19 |
|
第3章 基本蚁群算法 |
19-30 |
|
3.1 蚁群算法原理 |
19-23 |
|
3.1.1 蚁群算法的生物原型 |
19-20 |
|
3.1.2 蚁群算法模型 |
20-22 |
|
3.1.3 蚁群算法的系统特征 |
22 |
|
3.1.4 蚁群算法的应用 |
22-23 |
|
3.2 基本蚁群算法分析 |
23-27 |
|
3.2.1 基本蚁群算法的数学模型 |
23-25 |
|
3.2.2 基本蚁群算法描述 |
25-26 |
|
3.2.3 基本蚁群算法的复杂度分析 |
26-27 |
|
3.3 蚁群算法的改进 |
27-30 |
|
第4章 基于蚁群算法的排课系统研究 |
30-52 |
|
4.1 应用蚁群算法求解的问题形式 |
30 |
|
4.2 排课问题的二部图模型 |
30-33 |
|
4.2.1 二部图模型的顶点集 |
30-31 |
|
4.2.2 二部图模型的边集 |
31 |
|
4.2.3 二部图各边的权值 |
31-32 |
|
4.2.4 二部图模型 |
32-33 |
|
4.3 排课问题的求解方案 |
33-35 |
|
4.3.1 导入数据 |
33 |
|
4.3.2 确定二部图模型 |
33-35 |
|
4.3.3 应用蚁群算法寻优 |
35 |
|
4.4 排课问题中的蚁群算法设计 |
35-41 |
|
4.4.1 蚂蚁个体的构造 |
35-37 |
|
4.4.2 蚂蚁的一次周游 |
37 |
|
4.4.3 信息素策略 |
37-38 |
|
4.4.4 概率转移策略 |
38-40 |
|
4.4.5 改进蚁群算法的仿真实验 |
40-41 |
|
4.5 约束的解决 |
41-47 |
|
4.5.1 硬性约束 |
41-43 |
|
4.5.2 软性约束 |
43-47 |
|
4.6 排课算法流程图 |
47-52 |
|
第5章 实验结果分析 |
52-67 |
|
5.1 实验案例一 |
52-59 |
|
5.1.1 实验案例一数据介绍 |
52-56 |
|
5.1.2 实验案例一效果图 |
56-59 |
|
5.2 参数对基于蚁群算法排课系统的影响 |
59-64 |
|
5.2.1 迭代次数的影响 |
59-60 |
|
5.2.2 蚂蚁数目的影响 |
60-61 |
|
5.2.3 启发式因子的影响 |
61-63 |
|
5.2.4 挥发系数的影响 |
63-64 |
|
5.3 实验案例二 |
64-66 |
|
5.4 排课质量分析 |
66-67 |
|
结论 |
67-69 |
|
参考文献 |
69-73 |
|
附录A 基于蚁群算法的排课系统数据表 |
73-76 |
|
附录B 案例二的详细排课结果 |
76-81 |
|
附录C 基于蚁群算法的排课系统源代码 |
81-95 |
|
攻读学位期间公开发表论文 |
95-96 |
|
致谢 |
96-97 |
|
研究生履历 |
97 |
|
| 【DOI】 | LunWen.ID:2.2008.358263 |
