基于城市道路網(wǎng)的遺傳最短路徑算法研究.pdf

1、最短路徑問題是交通網(wǎng)絡分析中的一個重要問題，也是路徑規(guī)劃、資源分配等優(yōu)化問題的基礎。從網(wǎng)絡模型的角度看，最短路徑分析就是在指定網(wǎng)絡中的兩結點間找出一條阻礙強度最小的路徑，根據(jù)阻礙強度的不同定義，最短路徑可以指一般意義上的距離最短，也可以引申到其它的量度，如時間、費用、油耗等。針對最短路徑問題，多年來產(chǎn)生了大量相關領域的研究成果，其中遺傳算法是近年來的研究熱點。論文在相關研究的基礎上，以提高算法搜索效率為出發(fā)點，對遺傳算法的原理和改進方法

2、進行了深入研究，提出一系列改進措施。本文的主要研究成果包括：
　　 ⑴根據(jù)南京市電子地圖，通過提取道路網(wǎng)數(shù)據(jù)信息，構建拓撲結構，完成了適于最短路徑搜索的實驗平臺。
　　 ⑵基于上述實驗平臺，對基本遺傳算法的操作方式進行了調(diào)整與部分改進，如采用實數(shù)編碼，利用改進的鄰接矩陣結合先驗知識產(chǎn)生初始種群等。通過與Dijkstra算法得到的最優(yōu)結果進行比較，發(fā)現(xiàn)上述算法存在易產(chǎn)生局部收斂、搜索過程易產(chǎn)生不良個體等缺陷。