| 【中文题名】 | 并行遗传算法求解应急系统最短路径的研究 |
| 【英文题名】 | Research on Shortest Path in Emergency System Using Parallel Genetic Algorithm |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-11-14 |
| 【中关键词】 | 并行遗传,应急系统,最短路径,MPI,工作站机群, |
| 【英关键词】 | parallel genetic,emergency system,shortest path,MPI,cluster of workstation, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 近年来突发事件频繁爆发,我国格外重视危机管理、突发事件的预警与应急决策系统的建设。现有应急系统大多通过专家系统和方法库进行知识的搜索和定位,以辅助决策。而决策系统知识的准确性与系统反应的时效性是衡量应急决策系统性能的两个重要指标。为加速决策的时效性和准确性,本文以应急系统中的救援物资调度为背景,对实现并行遗传算法求解应急系统中的最短路径问题进行了研究。
首先,本文对应急决策支持系统和并行遗传算法的发展和特点进行综述,并介绍并行处理的硬件系统及其并行环境下的支撑软件,其中主要叙述工作站机群平台上所采用的高效的编程环境MPI。在此基础上针对应急系统中的救援物资调度决策过程,对原始道路图进行预处理,建立其相应的网络拓扑关系,将应急决策支持系统中最短路径问题用图论术语描述。
其次,论文重点分析遗传算法固有的隐式并行性,结合主从并行程序设计特点,提出了工作站机群环境中基于MPI求解最短路径的并行遗传算法,并将模拟退火算法和多种群并行遗传算法相结合,对并行算法加以改进,即利用Boltzmann机制接收交叉和变异后的个体,避免遗传算法中存在的早熟收敛问题,增强算法的全局收敛性。在该算法并行设计的... |
| 【论文题纲】 |
|
第一章 绪论 |
8-17 |
|
1．1 引言 |
8-9 |
|
1．2 本文的写作背景及现状 |
9-15 |
|
1．2．1 国内外应急系统研究现状 |
9-10 |
|
1．2．2 最短路径问题 |
10-11 |
|
1．2．3 遗传算法分析 |
11-14 |
|
1．2．4 并行遗传算法的设计与研究动态 |
14-15 |
|
1．3 本文的主要内容 |
15-17 |
|
第二章 并行计算机结构与并行算法基础 |
17-32 |
|
2．1 并行处理的硬件系统 |
17-21 |
|
2．1．1 并行计算机系统的发展 |
17-18 |
|
2．1．2 并行计算机结构模型及存储组织 |
18-21 |
|
2．2 并行算法的设计基础 |
21-24 |
|
2．2．1 并行算法的定义和并行编程模型的分类 |
21-23 |
|
2．2．2 并行算法设计 |
23-24 |
|
2．3 工作站机群及消息传递接口(MPI) |
24-32 |
|
2．3．1 工作站机群的特点 |
25-26 |
|
2．3．2 MPI |
26-29 |
|
2．3．3 工作站机群算法设计 |
29-32 |
|
第三章 应急系统中最短路径问题描述及算法分析 |
32-47 |
|
3．1 应急系统中最短路径问题定义及分析 |
32-33 |
|
3．2 应急系统中最短路径问题的图论描述 |
33-34 |
|
3．3 并行遗传算法分析 |
34-41 |
|
3．3．1 遗传算法固有的并行性 |
34-35 |
|
3．3．2 并行遗传算法的分类 |
35-41 |
|
3．4 并行遗传算法的改进 |
41-43 |
|
3．4．1 多种群并行遗传算法 |
41-42 |
|
3．4．2 基于模拟退火机制的多种群并行遗传算法 |
42-43 |
|
3．5 工作站机群上构造并行遗传算法考虑的主要问题 |
43-44 |
|
3．6 工作站机群上基于MPI求解最短路径算法 |
44-47 |
|
第四章 工作站机群上基于MPI求解最短路径算法的设计与实现 |
47-62 |
|
4．1 并行遗传算法设计步骤 |
47-50 |
|
4．1．1 划分 |
47-49 |
|
4．1．2 通讯 |
49 |
|
4．1．3 组合 |
49-50 |
|
4．1．4 映射 |
50 |
|
4．2 应急系统中最短路径遗传算法的实现 |
50-55 |
|
4．2．1 编码表示 |
50 |
|
4．2．2 适应度函数 |
50-51 |
|
4．2．3 遗传操作实现 |
51-55 |
|
4．2．4 控制参数设定 |
55 |
|
4．2．5 算法停止准则 |
55 |
|
4．3 工作站机群上基于MPI求解最短路径算法的实现 |
55-62 |
|
4．3．1 并行遗传算法主程序的实现 |
56-57 |
|
4．3．2 并行遗传算法的主进程部分的程序实现 |
57-59 |
|
4．3．3 并行遗传算法的从进程部分的程序实现 |
59-62 |
|
第五章 实验结果与分析 |
62-68 |
|
5．1 并行平台的实施 |
62-64 |
|
5．2 实验方案与结果 |
64-66 |
|
5．2．1 实验方案一与结果 |
64-65 |
|
5．2．2 实验方案二与结果 |
65-66 |
|
5．3 实验结果分析 |
66-68 |
|
总结 |
68-70 |
|
参考文献 |
70-74 |
|
致谢 |
74-76 |
|
攻读硕士学位期间发表的论文 |
76 |
|
| 【DOI】 | LunWen.ID:2.2008.387548 |
