李漢軒，李志華，呂春生

（1.河海大學 控制理論與控制工程系，江蘇 南京 211100；2.91656部隊 質(zhì)量控制室，上海 200136）

目前，在最短路徑規(guī)劃方面，已經(jīng)出現(xiàn)很多成熟優(yōu)秀的算法。熟知的有Dijkstra算法、Ford算法，以及啟發(fā)式的A*算法。這些算法在路徑規(guī)劃中對于解決只有距離限制的點與點之間最優(yōu)路徑的問題有著良好的時間復雜度[1]。在實際的車輛導航系統(tǒng)中，往往用戶更希望能得到一些帶約束條件的路徑規(guī)劃。在多約束條件的路徑規(guī)劃研究中，目前的確定性解決方法都擁有較高的時間復雜度[2-3]。而遺傳算法、蟻群算法是近年來迅速發(fā)展起來的基于生物進化原理的全局性優(yōu)化算法，在解決多約束路徑規(guī)劃問題中取得了很大成效[4-5]。這種仿生學算法往往具有良好的魯棒性，并有著并行，反饋等特點，但收斂性不強，可能會陷入局部最優(yōu)，無法得到全局最優(yōu)解。文中結(jié)合A*算法和蟻群算法優(yōu)點，提出了一種新的不確定算法。

1 基本算法

1.1 A*算法分析

A*（A-Star）算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。如圖1所示，算法中，將目前位置與目標位置的歐氏距離作為評估值，通過選擇最小路徑評估值，不斷回溯運算，可求出全局最短距離。

公式表示如式（1）。

其中，f（n）是從初始點經(jīng)由節(jié)點n到目標點的估價函數(shù)，g（n）是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h（n）是從n到目標節(jié)點最佳路徑的估計代價。

圖1 A*算法評估值示意Fig.1 A*algorithm assessed value

1.2 蟻群算法分析

蟻群算法（Ant Colony Optimization， ACO），又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。概率轉(zhuǎn)移函數(shù)如式（2）所示：

式中:Pk（r，s）表示螞蟻k從節(jié)點r轉(zhuǎn)移到節(jié)點 s的概率；τ（r，s） 表示螞蟻儲存在邊 V（r，s） 上的生物信息激素強度；η（r，s） 表示節(jié)點 s 相對于節(jié)點 r的可見性，η（r，s） =1/crs，crs表示邊 V（r，s） 的代價；Jk（r） 是第 k 個螞蟻由節(jié)點 r可以到達的所有可行節(jié)點集合。

蟻群算法在路徑規(guī)劃問題中往往根據(jù)兩節(jié)點間的距離和信息素濃度作為節(jié)點轉(zhuǎn)移的參考。不能考慮下個節(jié)點和目標點關(guān)系的信息，導致在尋優(yōu)過程中收斂性不高。

2 多約束條件下的路徑規(guī)劃算法

在實際路徑規(guī)劃時，往往面臨多個約束條件的限制[6]。文中提出一種路徑代價指標，將所有約束條件加權(quán)融合，使多約束問題轉(zhuǎn)化為單約束問題。同時利用A*算法的評估值概念，引入預測代價概念為蟻群在路徑選擇時提供額外的信息來源，最終用加權(quán)的路徑代價和加權(quán)的預測路徑代價作為一種廣義的路徑代價指標，基于這種思想，本文提出了基于A*和蟻群算法融合的新算法。對多約束條件的加權(quán)融合方法如式（3）。

其中L是道路長度，ρ是權(quán)重系數(shù)，γ是轉(zhuǎn)移因子，M為代價均值。其中轉(zhuǎn)移因子γ的作用是在用戶設定完約束意愿后，系統(tǒng)可以根據(jù)系統(tǒng)狀況作動態(tài)的改變規(guī)劃路徑。文中對導航系統(tǒng)的路徑模型作一定簡化，將影響路線規(guī)劃的道路條件設定為路線長度，路線寬度，路線材料3種。

距離在上述路徑代價指標中雖然不能完全決定多約束路徑的方向選擇。但在一般導航中距離都是重要的因素。所以利用A*算法中的評估值概念 （即節(jié)點與目標點的歐氏距離），為路徑規(guī)劃引入預測代價概念-歐式距離。將歐氏距離作為螞蟻在路徑選擇的額外“信息素”，加上蟻群算法本身的機率性可以實現(xiàn)快速、全局的最優(yōu)路徑選擇。

2.1 節(jié)點尋找

根據(jù)文中提出簡化路徑模型，參考代價指標公式，融合多約束條件后的新的轉(zhuǎn)移預測代價可以表示為：

式中: （ρ1M1）γ1表示 r節(jié)點到 s節(jié)點的路線距離指標，（ρ2M2）γ2

表示 r節(jié)點到目標結(jié)點的路線材料指標，（ρ3M3）γ3表示路線寬度的指標，（ρ4M4）γ4表示預測代價指標。

根據(jù)（2）式與（4）式，新的轉(zhuǎn)移公式如下：

2.2 節(jié)點轉(zhuǎn)移

文中采用J.H.Holland教授提出的輪盤方式選擇轉(zhuǎn)移目標結(jié)點[7]，它是一種按轉(zhuǎn)移概率大小隨機選擇優(yōu)良目標的方法。目標被選擇的概率取決于目標轉(zhuǎn)移概率的大小，即：

式中：Pj為目標j被選中的概率；fi為個體j的轉(zhuǎn)移概率；M為群體中個體的數(shù)目。故fi越大，Pj也就越大，則該目標被輪盤選中（擇優(yōu)時）的可能性就越大。

2.3 算法設計與實現(xiàn)

在算法實現(xiàn)時，參照文獻[2]設計了圖的存儲結(jié)構(gòu)，具體流程如圖2所示。

圖2 A*與蟻群結(jié)合算法流程Fig.2 Flow chart of A*combined with ant colony algorithm

步驟1：建立圖形中個頂點到目標頂點的歐氏距離及其他代價值；

步驟2：生成一個螞蟻，從起點開始出發(fā)根據(jù)信息素濃度和預測轉(zhuǎn)移概率選擇路徑；

步驟3：根據(jù)螞蟻的路徑，更新信息素，記錄最優(yōu)路徑。

重復2、3步至迭代次數(shù)完成。

3 仿真結(jié)果

文中實驗時，根據(jù)截取的河海大學附近地圖制作了簡化圖如圖3所示 。截選地圖有28個頂點，46條邊。本次路徑共假定3種約束條件分別為路線長度，耗費時間，所經(jīng)過的道路材料。其中在路況中將道路擁擠度分為4級，從1級到4級擁擠度逐漸增加。具體路線擁擠如表1所示：將道路材料分為3種包括柏油或水泥路面，沙礫路面，土路如表2所示。根據(jù)本次實驗的駕駛意愿，3種約束條件在融合過程中的權(quán)重因子分別為：路線長度0.6，道路擁擠度0.2，道路材料0.4。轉(zhuǎn)移因子均為1。實驗結(jié)果如表3所示。

表1 路線擁擠表Tab.1 The extent of line crowding

表2 路線材料表Tab.2 Line materials

圖3 簡化抽象拓補結(jié)構(gòu)圖Fig.3 Simplify figure of the abstract topology

由于蟻群算法運行結(jié)果的隨機性，單次算法運算的結(jié)果不能客觀反映方案的優(yōu)劣，該研究共進行了5輪測試，每輪生成100只螞蟻最多迭代50次的統(tǒng)計值作為比較。

表3 測試結(jié)果Tab.3 Test result

1）在每輪實驗中均采用了大樣本實驗，即5輪測試共進行5×100次路徑尋找運算，進行實際運算測試。從各項統(tǒng)計指標的絕對值及其方差來看，在同種方案內(nèi)的不同測試中統(tǒng)計數(shù)據(jù)項結(jié)果波動很?。?/p>

2）方案1的總運行時間明顯縮短（僅為前者的3.55%），方案2的總運行時間大部分被無效路徑選擇占用，其原因是常規(guī)蟻群算法有效信息素積累慢，收斂性不強導致；由于是在同一軟硬件平臺上進行方案測試，故統(tǒng)計數(shù)據(jù)具有可比性；

3）兩方案的搜索最優(yōu)解次數(shù)（即每輪大樣本實驗中算法停止時的尋優(yōu)解為全局最優(yōu)解的次數(shù)）相差2.55倍，說明2方案除了在速度上的明顯差異外，在全局最優(yōu)解的搜索成功率上也是效果明顯不同的；

4）由于歐氏距離因子可以為路徑選擇做出非常有效的方向預測，進而提供穩(wěn)定的最優(yōu)路徑獲取成功率。所以方案1的最優(yōu)解次數(shù)方差遠遠低于方案2，證明改進方案在獲得全局最優(yōu)解能力方面有著很好的穩(wěn)定性。

4 結(jié)束語

文中提出了一種基于A*算法和蟻群算法融合的多約束條件最優(yōu)路徑導航算法，能夠保證在路徑規(guī)劃時得到一條具有較小行駛代價的航路?？梢钥闯?，這種路徑規(guī)劃方法具有如下特點：1）保留了蟻群算法具有的動態(tài)性，分布性，協(xié)同性；2）加入A*算法的估計代價因子增加了算法的收斂速度，算法也更容易更穩(wěn)定的得到全局最優(yōu)解。

[1]嚴寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑搜索算法[J].計算機學報，2000， 25（3）:210-215.YAN Han-bing，LIU Ying-chun.A new algorithm for finding shortcut in a city’s road net based on GIS technology[J].Chinese J.Computers，2000，25（3）:210-215.

[2]戴樹貴，潘蔭榮，胡幼華，等.求帶多個限制條件的單源多權(quán)最短路徑算法[J].計算機應用與軟件，2004，21（12）:78-81.DAI Shu-gui，PAN Yin-rong，HU You-hua，et al. An algorithm for the multiple weights shortest-path problem with multiple constraints[J].Computer Applications and Software，2004，21（12）:78-81.

[3]Takaoka T.An O （n3loglogn/log n）time algorithm for the allpairs shortest path problem[J].Information Processing Letter，2005，96:155-161.

[4]Dorigo M，Gambardella L M， Middendorf M，et al.Guest editorial:special section on ant colony optimization[J].IEEE Transactionon Evolutionary Computation，2002，6（4）:317-319.

[5]柳長安，李為吉，工和平.基于蟻群算法的無人機航路規(guī)劃[J].空軍工程大學學報，2004，5（2）:9-12.LIU Chang-an， LI Wei-ji， GONGHe-ping.Path planning for reconnaissance UAV based on ant algorithm[J].Journal of Air Force Engineering University，2004，5（2）:9-12.

[6]王海梅.基于GIS的最優(yōu)路徑算法研究與實現(xiàn)[D].南京:南京理工大學，2008.

[7]HUANG Kai-ming.Analysis and improvement on roulette wheel method of genetic algorithm[J].Computer Engineering and Applications，2009，45（28）：60-63.