一種多約束條件下路徑規(guī)劃算法研究

李漢軒，李志華，呂春生

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

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

1 基本算法

1.1 A*算法分析

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

公式表示如式（1）。

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

圖1 A*算法評(píng)估值示意Fig.1 A*algorithm assessed value

1.2 蟻群算法分析

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

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

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

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

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

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

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

2.1 節(jié)點(diǎn)尋找

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

式中: （ρ1M1）γ1表示 r節(jié)點(diǎn)到 s節(jié)點(diǎn)的路線(xiàn)距離指標(biāo)，（ρ2M2）γ2

表示 r節(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路線(xiàn)材料指標(biāo)，（ρ3M3）γ3表示路線(xiàn)寬度的指標(biāo)，（ρ4M4）γ4表示預(yù)測(cè)代價(jià)指標(biāo)。

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

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

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

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

2.3 算法設(shè)計(jì)與實(shí)現(xiàn)

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

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

步驟1：建立圖形中個(gè)頂點(diǎn)到目標(biāo)頂點(diǎn)的歐氏距離及其他代價(jià)值；

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

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

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

3 仿真結(jié)果

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

表1 路線(xiàn)擁擠表Tab.1 The extent of line crowding

表2 路線(xiàn)材料表Tab.2 Line materials

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

由于蟻群算法運(yùn)行結(jié)果的隨機(jī)性，單次算法運(yùn)算的結(jié)果不能客觀(guān)反映方案的優(yōu)劣，該研究共進(jìn)行了5輪測(cè)試，每輪生成100只螞蟻?zhàn)疃嗟?0次的統(tǒng)計(jì)值作為比較。

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

1）在每輪實(shí)驗(yàn)中均采用了大樣本實(shí)驗(yàn)，即5輪測(cè)試共進(jìn)行5×100次路徑尋找運(yùn)算，進(jìn)行實(shí)際運(yùn)算測(cè)試。從各項(xiàng)統(tǒng)計(jì)指標(biāo)的絕對(duì)值及其方差來(lái)看，在同種方案內(nèi)的不同測(cè)試中統(tǒng)計(jì)數(shù)據(jù)項(xiàng)結(jié)果波動(dòng)很小；

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

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

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

4 結(jié)束語(yǔ)

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

[1]嚴(yán)寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑搜索算法[J].計(jì)算機(jī)學(xué)報(bào)，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]戴樹(shù)貴，潘蔭榮，胡幼華，等.求帶多個(gè)限制條件的單源多權(quán)最短路徑算法[J].計(jì)算機(jī)應(yīng)用與軟件，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]柳長(zhǎng)安，李為吉，工和平.基于蟻群算法的無(wú)人機(jī)航路規(guī)劃[J].空軍工程大學(xué)學(xué)報(bào)，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)路徑算法研究與實(shí)現(xiàn)[D].南京:南京理工大學(xué)，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.