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

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

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