| 【中文题名】 | 基于遗传算法和蚁群算法的网格任务调度策略 |
| 【英文题名】 | A Task Scheduling Strategy in Computational Grid Based on Genetic Algorithms and Ant Algorithms |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-1-9 |
| 【中关键词】 | 网格,遗传算法,蚁群算法,任务调度,SimGrid, |
| 【英关键词】 | Grid,genetic algorithm,ant algorithm,task scheduling,SimGrid, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
网格计算是解决科学计算、工程计算和商业计算等大规模计算的下一代极具潜力的计算平台。网格核心服务是网格的重要组成部分,是连接网格底层和高层功能的纽带,是协调整个网格系统有效运转的中枢,对这部分网格技术的研究具有重要意义。任务调度技术是网格核心服务之一。
大量任务请求使用网格资源时,必须对它们进行合理调度才能达到资源的优化利用。一个良好的任务调度策略能高效地协调和分配网格资源,有效降低网格计算的总执行时间和总耗费,从而使网格达到最大的性能。任务调度技术对网格系统的应用至关重要。
目前存在的网格任务调度策略,如遗传算法、蚁群算法、模拟退火算法、禁忌算法等,皆优缺点分明,都不能够单独实现对网格任务的最优调度,而且没有将遗传算法和蚁群算法结合在一起来解决网格任务调度问题的策略。本文详细分析了遗传算法和蚁群算法在各自不同时期的搜索优、劣势,并在自己设计的模型中存优去劣地实现新的网格任务优化调度。其创新点在于网格任务调度的前阶段利用遗传算法群体性全局搜索能力,能够快速形成初始解,在满足终止遗传算法的条件之后,将遗传算法调度的“最终结果”转化为蚁群算法所需要的初期信息素,然后利用蚁群算法所具有的正反... |
| 【论文题纲】 |
|
目录 |
8-10 |
|
0 引言 |
10-11 |
|
1 概述 |
11-15 |
|
1.1 课题的研究背景 |
11-12 |
|
1.2 遗传算法和蚁群算法的研究现状及特征 |
12-13 |
|
1.3 论文的研究内容及成果 |
13-15 |
|
2 网格任务调度技术及其存在的问题 |
15-29 |
|
2.1 概述 |
15-16 |
|
2.2 网格任务调度模型 |
16 |
|
2.3 网格计算的特点 |
16-17 |
|
2.4 网格计算环境中任务调度面临的问题 |
17-18 |
|
2.5 目前存在的任务调度算法及其特点 |
18-27 |
|
2.5.1 传统的调度算法及特点 |
18-20 |
|
2.5.2 遗传算法、蚁群算法及特点 |
20-27 |
|
2.6 使用新算法解决任务调度问题的可行性分析 |
27-29 |
|
3 基于遗传算法与蚁群算法动态融合的网格任务调度策略 |
29-51 |
|
3.1 概述 |
29-30 |
|
3.2 条件设定 |
30-31 |
|
3.3 必要定义 |
31-32 |
|
3.3.1 NP 完全问题 |
31-32 |
|
3.3.2 DAG 图 |
32 |
|
3.3.3 组合优化问题 |
32 |
|
3.4 遗传算法与蚁群算法动态融合的设计 |
32-34 |
|
3.4.1 基本原理 |
32-33 |
|
3.4.2 两种算法动态融合的临界点确定 |
33-34 |
|
3.4.3 结论 |
34 |
|
3.5 算法实现及源代码 |
34-50 |
|
3.5.1 初始定义及假设条件 |
34-35 |
|
3.5.2 遗传算法规则 |
35-40 |
|
3.5.3 蚁群算法规则 |
40-45 |
|
3.5.4 遗传算法与蚁群算法的衔接 |
45 |
|
3.5.5 网格任务调度算法过程 |
45-46 |
|
3.5.6 算法必要说明 |
46-49 |
|
3.5.7 算法源代码 |
49-50 |
|
3.6 小结 |
50-51 |
|
4 网格模拟器 |
51-58 |
|
4.1 概述 |
51-52 |
|
4.2 SIMGRID 简述 |
52-53 |
|
4.3 SIMGRID 关键特征 |
53-54 |
|
4.4 SIMGRID 与其他仿真工具的比较 |
54-55 |
|
4.5 SIMGRID 使用分析 |
55-57 |
|
4.6 小结 |
57-58 |
|
5 仿真实验及结果 |
58-63 |
|
5.1 实验目的 |
58 |
|
5.2 实验参数的设定 |
58-59 |
|
5.3 仿真结果 |
59-62 |
|
5.4 实验结论 |
62-63 |
|
6 总结与展望 |
63-64 |
|
参考文献 |
64-67 |
|
致谢 |
67-68 |
|
作者研究生期间论文发表情况 |
68 |
|
| 【DOI】 | LunWen.ID:2.2008.388257 |
