潘志安

摘要：該文將交通網(wǎng)絡(luò)抽象為不確定性圖模型，并用概率圖的方式研究了不確定交通網(wǎng)絡(luò)中的top-k路徑查詢，給出了求解概率圖中top-k路徑查詢的數(shù)學(xué)模型，提出了一種基于遺傳算法的不確定性交通網(wǎng)絡(luò)top-k路徑查詢算法，并對算法進(jìn)行了測試，得到了較好的結(jié)果。

關(guān)鍵詞：不確定性交通網(wǎng)絡(luò)；概率圖；top-k路徑查詢；遺傳算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）04-0066-04

從一個(gè)地點(diǎn)出發(fā)到達(dá)目的地通常有多條路徑，一般情況下人們希望選擇一條能快速到達(dá)的路徑，比如“查詢從某賓館到機(jī)場的用時(shí)最短的路徑”。目前的地理信息系統(tǒng)GIS的一項(xiàng)主要功能——路徑分析便是用來解決這類問題的[1]。這種問題本質(zhì)上屬于圖論中的兩點(diǎn)之間最短路徑問題。早在GIS建立之前，最短路徑問題已經(jīng)被廣泛和大量地研究。

然而現(xiàn)實(shí)中的交通網(wǎng)絡(luò)狀態(tài)處于不斷變化中，不同時(shí)段的車流量存在差異，不同車輛的行駛速度也不同，這導(dǎo)致經(jīng)過某一段路徑的時(shí)間具有不確定性。用確定的圖模型難以描述交通網(wǎng)絡(luò)的這種不確定性。于是，我們經(jīng)常會(huì)用這樣的表述方式：

1） 查詢能在30分鐘內(nèi)以至少90%的可能性從某賓館到達(dá)機(jī)場的所有路徑。

2） 查詢能在30分鐘內(nèi)從某賓館到達(dá)機(jī)場的可能性最高的[k]條路徑；

3） 查詢至少能以90%的可能性從某賓館到達(dá)機(jī)場的用時(shí)最短的[k]條路徑。這就表示，交通網(wǎng)絡(luò)固有的不確定性可以用概率圖的方法描述[2]。

3 不確定性交通網(wǎng)絡(luò)中的[top-k]路徑查詢算法

傳統(tǒng)的最短路徑算法Dijstra、A*等不能直接用于概率圖中top-k路徑查詢。該文提出了一種基于遺傳算法的改進(jìn)算法，用于求解概率圖中的[top-k]路徑查詢。

遺傳算法是一種仿生優(yōu)化算法，它模仿的機(jī)制是‘一切生命與智慧的產(chǎn)生與進(jìn)化過程。它通過模擬達(dá)爾文“優(yōu)勝劣汰、適者生存”的原理激勵(lì)的結(jié)構(gòu)：通過模擬孟德爾遺傳變異理論在迭代過程中保持已有的結(jié)構(gòu)，同時(shí)尋求更好的結(jié)構(gòu)。

3.1 染色體編碼

遺傳算法使用的染色體編碼方式通常有二進(jìn)制編碼方式和實(shí)數(shù)編碼方式。二進(jìn)制編碼方式下，染色體用一個(gè)長度為n的二進(jìn)制串表示，其中n為圖中頂點(diǎn)個(gè)數(shù)，每條染色體代表一條路徑，染色體的第i位為1表示編號(hào)為i的頂點(diǎn)在此路徑中。

3.2 初始化種群

遺傳算法的魯棒性建立在初始種群的多樣性基礎(chǔ)上，因此，在種群的初始化過程中加入隨機(jī)因素能保證初始種群的多樣性。

3.3 適應(yīng)度函數(shù)

進(jìn)化論中的適應(yīng)度，是表示某一個(gè)體對環(huán)境的適應(yīng)能力，也表示該個(gè)體繁殖后代的能力。遺傳算法的適應(yīng)度函數(shù)也叫評價(jià)函數(shù)，是用來判斷群體中的個(gè)體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估的。

5 創(chuàng)新點(diǎn)

雖然目前在交通網(wǎng)絡(luò)最短路徑方面國內(nèi)外已經(jīng)有了大量研究，但是考慮到交通網(wǎng)絡(luò)的不確定性因素的研究卻很少。智能算法應(yīng)用于不確定性交通網(wǎng)絡(luò)的研究還沒有。

本文在以上研究的基礎(chǔ)上對不確定性交通網(wǎng)絡(luò)中top-k路徑查詢進(jìn)行了研究，并給出了解決這類問題的思路，進(jìn)一步，提出了一種基于遺傳算法的改進(jìn)算法，實(shí)現(xiàn)了不確定性交通網(wǎng)絡(luò)中的top-k路徑查詢。

參考文獻(xiàn)：

[1] 劉學(xué)軍，徐鵬.交通地理信息系統(tǒng)[M].北京：科學(xué)出版社，2006：28-54.

[2] M. Hua，J. Pei. Probabilistic Path Queries in Road Networks： Traffic Uncertainty Aware Path Selection[C].Proceedings of the 13th International Conference on Extending Database Technology （EDBT'10）， Lausanne， Switzerland， 2010 March ：22-26.

[3] Fu L.Heuristic shortest path algorithms for transportation applications： State of the art[J].Computers and Operations Research，2006，33（11）：3324-3343.

[4] 康曉軍，王茂才.基于遺傳算法的最短路徑問題求解[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（23）：22-23，35.

[5] 鄒亮，徐建閩.基于遺傳算法的動(dòng)態(tài)網(wǎng)絡(luò)中最短路徑問題算法[J].計(jì)算機(jī)應(yīng)用，2005，4（25）：742-744.