优秀研究生学位论文题录展示

并行遗传算法求解应急系统最短路径的研究

专 业: 计算机应用技术
关键词: 并行遗传 应急系统 最短路径 MPI 工作站机群
分类号: TP301
形 态: 共 69 页 约 45,195 个字 约 2.162 M内容
阅 读: 全文阅读说明

内容摘要


近年来突发事件频繁爆发,我国格外重视危机管理、突发事件的预警与应急决策系统的建设。

现有应急系统大多通过专家系统和方法库进行知识的搜索和定位,以辅助决策。

而决策系统知识的准确性与系统反应的时效性是衡量应急决策系统性能的两个重要指标。

为加速决策的时效性和准确性,本文以应急系统中的救援物资调度为背景,对实现并行遗传算法求解应急系统中的最短路径问题进行了研究。

首先,本文对应急决策支持系统和并行遗传算法的发展和特点进行综述,并介绍并行处理的硬件系统及其并行环境下的支撑软件,其中主要叙述工作站机群平台上所采用的高效的编程环境MPI。

在此基础上针对应急系统中的救援物资调度决策过程,对原始道路图进行预处理,建立其相应的网络拓扑关系,将应急决策支持系统中最短路径问题用图论术语描述。

其次,论文重点分析遗传算法固有的隐式并行性,结合主从并行程序设计特点,提出了工作站机群环境中基于MPI求解最短路径的并行遗传算法,并将模拟退火算法和多种群并行遗传算法相结合,对并行算法加以改进,即利用Boltzmann机制接收交叉和变异后的个体,避免遗传算法中存在的早熟收敛问题,增强算法的全局收敛性。

在该算法并行设计的划分、通讯、组合和映射四个过程中,提出遗传算法初始种群的划分原则;利用MPI消息传递的六个基础通信子集在各种群间进行通信和传播各子种群的最优解;运用组合法,以保持灵活性,减少通信开销;将该算法映射为主从式工作站机群上的粗粒度并行遗传算法,并使用静态负载平衡任务调度技术改善映射质量。

最后,在实验部分作者通过配置工作站机群并行环境,在Linux和MPI平台上,使用C语言编程实现该并行算法,通过分析对比多组实验数据,计算该算法加速比性能,结果表明:

算法适应度高,寻优速度快。

但该并行算法求解问题规模较小、遗传参数设置和消息传递内容与时机固定,这些都有待进一步完善..……

全文目录


文摘
英文文摘
第一章 绪论
1.1引言
1.2本文的写作背景及现状
1.2.1国内外应急系统研究现状
1.2.2最短路径问题
1.2.3遗传算法分析
1.2.4并行遗传算法的设计与研究动态
1.3本文的主要内容
第二章 并行计算机结构与并行算法基础
2.1并行处理的硬件系统
2.1.1并行计算机系统的发展
2.1.2并行计算机结构模型及存储组织
2.2并行算法的设计基础
2.2.1并行算法的定义和并行编程模型的分类
2.2.2并行算法设计
2.3工作站机群及消息传递接口MPI
2.3.1工作站机群的特点
2.3.2 MPI
2.3.3工作站机群算法设计
第三章 应急系统中最短路径问题描述及算法分析
3.1应急系统中最短路径问题定义及分析
3.2应急系统中最短路径问题的图论描述
3.3并行遗传算法分析
3.3.1遗传算法固有的并行性
3.3.2并行遗传算法的分类
3.4并行遗传算法的改进
3.4.1多种群并行遗传算法
3.4.2基于模拟退火机制的多种群并行遗传算法
3.5工作站机群上构造并行遗传算法考虑的主要问题
3.6工作站机群上基于MPI求解最短路径算法
第四章 工作站机群上基于MPI求解最短路径算法的设计与实现
4.1并行遗传算法设计步骤
4.1.1划分
4.1.2通讯
4.1.3组合
4.1.4映射
4.2应急系统中最短路径遗传算法的实现
4.2.1编码表示
4.2.2适应度函数
4.2.3遗传操作实现
4.2.4控制参数设定
4.2.5算法停止准则
4.3工作站机群上基于MPI求解最短路径算法的实现
4.3.1并行遗传算法主程序的实现
4.3.2并行遗传算法的主进程部分的程序实现
4.3.3并行遗传算法的从进程部分的程序实现
第五章 实验结果与分析
5.1并行平台的实施
5.2实验方案与结果
5.2.1实验方案一与结果
5.2.2实验方案二与结果
5.3实验结果分析
总结
参考文献

相似论文

  1. 遗传算法研究及在航运船舶配载系统中的应用,63 页,TP301.6 TP319 U692.32
  2. 支持向量机集成学习算法研究, 11页,TP301.6 TP181
  3. 海量数据可视化方法的研究,58 页,TP301.6 TP393.08
  4. 改进型人工鱼群算法及其在数值方法中的应用,53 页,TP301.6 O241
  5. 求解QoS路由优化的蚁群算法研究,37 页,TP301.6 TN913.11
  6. 协作型协进化算法及其应用,46 页,TP301.6
  7. 微粒群优化算法的改进研究与应用,90 页,TP301.6
  8. 基于模糊聚类与多生境排挤的小生境遗传算法研究,61 页,TP301.6
  9. 基于群智能算法的聚类分析方法研究,63 页,TP301.6 O242.23
  10. 基于规则的委托授权研究,55页,TP309
  11. 视频数字双水印技术研究,68页,TP309.7 TP391.41
  12. SOAP消息传递安全性技术研究与SOAP加密的实现,64页,TP309.7 TP393.08
  13. CCIPS的分布实时容错一体化研究,72页,TP302.8 TP311.52 V57
  14. UML图的Petri网建模,70页,TP302 TP393.11
  15. 基于J2EE平台的益智类游戏开发中安全问题的研究,61页,TP309 TP393.08
  16. 航天分布式实时容错平台研究,74页,TP302.8 TP393
  17. 非负矩阵分解算法理论及其应用研究,53页,TP301.6
  18. 工作流的Petri网建模及模型分析,49页,TP302 TP391.78
  19. 访问控制模型RBAC中时间约束特性的研究,44页,TP309
  20. 公钥基础设施中证书路径构造方法研究,57页,TP309
中图分类: > TP301 > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法

© 2012 book.hzu.edu.cn