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

论文题目: 并行遗传算法求解应急系统最短路径的研究

论文类型: 硕士论文

论文专业: 计算机应用技术

作者: 张晓波

导师: 谢红薇

关键词: 并行遗传,应急系统,最短路径,工作站机群

文献来源: 太原理工大学

发表年度: 2005

论文摘要: 近年来突发事件频繁爆发,我国格外重视危机管理、突发事件的预警与应急决策系统的建设。现有应急系统大多通过专家系统和方法库进行知识的搜索和定位,以辅助决策。而决策系统知识的准确性与系统反应的时效性是衡量应急决策系统性能的两个重要指标。为加速决策的时效性和准确性,本文以应急系统中的救援物资调度为背景,对实现并行遗传算法求解应急系统中的最短路径问题进行了研究。 首先,本文对应急决策支持系统和并行遗传算法的发展和特点进行综述,并介绍并行处理的硬件系统及其并行环境下的支撑软件,其中主要叙述工作站机群平台上所采用的高效的编程环境MPI。在此基础上针对应急系统中的救援物资调度决策过程,对原始道路图进行预处理,建立其相应的网络拓扑关系,将应急决策支持系统中最短路径问题用图论术语描述。 其次,论文重点分析遗传算法固有的隐式并行性,结合主从并行程序设计特点,提出了工作站机群环境中基于MPI求解最短路径的并行遗传算法,并将模拟退火算法和多种群并行遗传算法相结合,对并行算法加以改进,即利用Boltzmann机制接收交叉和变异后的个体,避免遗传算法中存在的早熟收敛问题,增强算法的全局收敛性。在该算法并行设计的划分、通讯、组合和映射四个过程中,提出遗传算法初始种群的划分原则;利用MPI消息传递的六个基础通信子集在各种群间进行通信和传播各子种群的最优解;运用组合法,以保持灵活性,减

论文目录:

第一章 绪论

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 实验结果分析

总结

参考文献

致谢

攻读硕士学位期间发表的论文

发布时间: 2005-11-14

参考文献

• [1].基于申威众核处理器的混合并行遗传算法的设计和实现[D]. 赵瑞祥.华东师范大学2018
• [2].基于并行遗传算法的多目标优化问题研究[D]. I NOIATOV RUSTAM.兰州交通大学2018
• [3].基于并行遗传算法的驾驶员排班问题研究[D]. 郭亚茹.北京交通大学2017
• [4].改进的并行遗传算法在知识库中的应用研究[D]. 赵戈.大连交通大学2008
• [5].并行遗传算法骨架的研究与实践[D]. 朱咸坤.江西师范大学2009
• [6].基于分布式并行遗传算法的网格任务调度研究[D]. 陈然.湖南科技大学2009
• [7].迁移式并行遗传算法求解支持向量机反问题[D]. 马晓晨.河北大学2008
• [8].一种改进的异步并行遗传算法在物流配送路径的研究[D]. 张翰.吉林大学2013
• [9].一种基于自适应迁移策略的并行遗传算法[D]. 郭肇禄.江西理工大学2010
• [10].基于混合并行遗传算法的文本分类及聚类研究[D]. 戴文华.华中师范大学2007

相关论文

• [1].基于遗传算法的应急物资运输调度[D]. 陈杰.哈尔滨工业大学2006
• [2].应急系统选址的模型与算法研究[D]. 宁艳梅.西安电子科技大学2007
• [3].应急物流系统若干关键技术的研究与实现[D]. 黄金虎.上海交通大学2007
• [4].应急物流配送车辆调度优化研究[D]. 张斌.大连海事大学2007
• [5].救灾物流中的物资调运模型研究[D]. 王杏.北京交通大学2007
• [6].基于鲁棒优化的应急管理下的车辆路线问题的研究[D]. 孙华.河南大学2007
• [7].应急响应过程可靠性建模及调度方法研究[D]. 安金朝.南昌大学2007
• [8].时间约束下的应急资源调度模型及算法研究[D]. 车颍涛.河南大学2007
• [9].交通网络中最短路径算法的研究[D]. 戴文舟.重庆大学2004
• [10].应急物流系统研究[D]. 黄洪涛.大连海事大学2006

标签：并行遗传论文;  应急系统论文;  最短路径论文;  工作站机群论文;