原文传递
基于遗传算法的多源多目路径规划问题研究
| 论文题名： | 基于遗传算法的多源多目路径规划问题研究 |
| 关键词： | 交通网络;遗传算法;多源多目标;路径规划;网络拓扑图;仿真实验 |
| 摘要： | 随着人们消费水平的不断提高，汽车数量的快速增加与道路建设迟缓之间的矛盾日益凸显，严重制约着社会与经济的可持续和谐发展，解决交通阻塞问题已经迫在眉睫。合理高效的路径规划是解决交通堵塞问题的有效途径之一。传统的路径规划算法在搜索单源最短路径等简单最优路径时是可行和高效的，但对于解决复杂交通网络问题，进行顾及全局优化的多源多目最优多路径规划时还不能直接应用，存在遍历搜索时间长、效率较低等诸多问题。遗传算法作为一种智能算法具有并行搜索和全局优化的优势，成为快速解决多源多目复杂路径规划问题的潜在有效手段。因此，论文开展了基于遗传算法的复杂路径规划问题研究，研究分析了利用遗传算法解决单源和多源多目标路径规划的算法设计和基本流程，并运用网络拓扑图进行仿真实验，验证遗传算法解决多源多目路径规划问题的可行性和收敛性。主要研究内容如下: (1)基于遗传算法的单源最短路径问题:采用基于路径的编码方式，设计基于遗传算法的单源最短路径算法，对初始种群进行基于路径的选择、交叉、变异等遗传操作，解决网络拓扑图中给定两点的路径（或权值）最短问题，并将轮盘赌选择与最优选择策略模型结合与单纯轮盘赌方式进行分析，解决遗传算法未成熟收敛问题。 (2)基于遗传算法的多源多目标路径规划问题:将遗传算法解决单源最短路径问题的基本思路扩展到解决多源多目路径规划问题上，提出了一种双层遗传算法模式。第一层在忽略通路承载量M的基础上，利用遗传算法针对各个源点到终点找到n条最短路径;第二层引入重选择算子和删除算子对超过通路承载量M的线路进行重选择和删除操作，然后对剩余节点再进行基于路径的遗传运算，依次循环，直到找到多源多目优化路径。 (3)实验平台设计与实验分析:利用Matlab7.0平台，给定网络拓扑图，对上述算法进行仿真实验。重点对算法搜索的结果、效率和收敛性进行了实验和分析，实验分析结果表明本文算法可行有效、收敛速度快。 |
| 作者： | 李晓明 |
| 专业： | 地图制图学与地理信息工程 |
| 导师： | 韩李涛 |
| 授予学位： | 硕士 |
| 授予学位单位： | 山东科技大学 |
| 学位年度： | 2014 |
| 正文语种： | 中文 |
检索历史
应用推荐
