原文传递
基于城市道路网的遗传最短路径算法研究
| 论文题名： | 基于城市道路网的遗传最短路径算法研究 |
| 关键词： | 城市交通;道路网络;路径规划;遗传算法 |
| 摘要： | 最短路径问题是交通网络分析中的一个重要问题，也是路径规划、资源分配等优化问题的基础。从网络模型的角度看，最短路径分析就是在指定网络中的两结点间找出一条阻碍强度最小的路径，根据阻碍强度的不同定义，最短路径可以指一般意义上的距离最短，也可以引申到其它的量度，如时间、费用、油耗等。针对最短路径问题，多年来产生了大量相关领域的研究成果，其中遗传算法是近年来的研究热点。论文在相关研究的基础上，以提高算法搜索效率为出发点，对遗传算法的原理和改进方法进行了深入研究，提出一系列改进措施。本文的主要研究成果包括： ⑴根据南京市电子地图，通过提取道路网数据信息，构建拓扑结构，完成了适于最短路径搜索的实验平台。 ⑵基于上述实验平台，对基本遗传算法的操作方式进行了调整与部分改进，如采用实数编码，利用改进的邻接矩阵结合先验知识产生初始种群等。通过与Dijkstra算法得到的最优结果进行比较，发现上述算法存在易产生局部收敛、搜索过程易产生不良个体等缺陷。 ⑶针对上述算法存在的问题，论文提出了进一步的改进方案，包括：将轮盘赌选择与精英保护法相结合，采用带基因序列限制的交叉与改进的两点变异方法。算法实例表明，改进方法较原有算法更加有效。 ⑷结合实际应用需求，分析了：道路存在障碍、求k条最佳路径、通过站点最少三种常见情形下的最优路径求解方法，并给出具体搜索实例。 |
| 作者： | 吴莲 |
| 专业： | 控制理论与控制工程 |
| 导师： | 王海梅 |
| 授予学位： | 硕士 |
| 授予学位单位： | 南京理工大学 |
| 学位年度： | 2010 |
| 正文语种： | 中文 |
检索历史
应用推荐
