基于改進(jìn)遺傳算法的動態(tài)路徑規(guī)劃研

董小帥 ，毛政元

1.福州大學(xué) 福建省空間信息工程研究中心，福州 350002

2.福州大學(xué) 空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室，福州 350002

3.福州大學(xué) 地理空間信息技術(shù)國家地方聯(lián)合工程研究中心，福州 350002

1 引言

按照對時變性因素的不同處理，路徑規(guī)劃模型分為靜態(tài)和動態(tài)兩種類型[1]，前者指在靜態(tài)路網(wǎng)模型上迭加各路段權(quán)重，再采用規(guī)劃與優(yōu)化算法求解最佳路徑，同一問題只需求解一次；后者指綜合考慮路網(wǎng)中各路段的通行能力和路網(wǎng)不斷變化的路況信息采用優(yōu)化算法求解最優(yōu)路徑[2-3]。動態(tài)路徑規(guī)劃相比靜態(tài)路徑規(guī)劃更具實用價值[4]，同時，由于其采用的動態(tài)路網(wǎng)模型加入了實時、復(fù)雜、多變的路網(wǎng)信息，經(jīng)典規(guī)劃算法難以高效、魯棒地完成路徑規(guī)劃與優(yōu)化，目前相關(guān)研究中一般采用仿生智能算法實現(xiàn)動態(tài)路徑規(guī)劃[5-9]。

遺傳算法是一種采用種群搜索機制的全局性尋優(yōu)算法，該搜索策略使求得最優(yōu)解的可能性和效率大大提高[10]，該算法因此被廣泛應(yīng)用于包括路徑規(guī)劃在內(nèi)的眾多問題的求解研究。但是傳統(tǒng)的遺傳算法存在“早熟收斂”、種群多樣性逐漸降低和局部搜索能力差等缺陷[11-14]。對此，相關(guān)研究文獻(xiàn)中提出了一系列的改進(jìn)，比如，采用啟發(fā)式算法生成初始種群[15-17]，提出以相同節(jié)點作為交叉點的交叉策略和變異策略等[18-19]，提高收斂速度，避免“早熟收斂”；采用多種群協(xié)同進(jìn)化策略[20]，優(yōu)良基因以一定概率在不同種群間橫向傳遞，降低“早熟收斂”的可能性；自適應(yīng)交叉概率和變異概率的提出，動態(tài)調(diào)整交叉，變異操作[21]，使得隨著迭代次數(shù)增加，種群多樣性不會大幅降低；引入模擬退火思想[22]以一定的概率接受比當(dāng)前解更差的新解，混合禁忌搜索算法[23]、爬山算法[24]、融入復(fù)合型操作[25]等提高局部搜索能力。這些改進(jìn)能夠在一定程度上克服傳統(tǒng)遺傳算法的缺陷，但在處理大規(guī)模實時交通數(shù)據(jù)時，求解精度與效率仍不能滿足實時路徑規(guī)劃的需求。

本文針對傳統(tǒng)遺傳算法應(yīng)用于動態(tài)路徑規(guī)劃求解的局限性提出以下三方面的改進(jìn)：（1）結(jié)合隨機選擇和趨于終點方向提出一種控制全局搜索方向的種群初始化策略，在保持初始種群多樣性的同時提高初始種群個體質(zhì)量，加快收斂。（2）提出一種根據(jù)空間距離的鄰近大小選擇交叉位置點的交叉策略，有效保留父代優(yōu)良基因，同時避免“早熟收斂”。（3）提出一種基于節(jié)點適應(yīng)度的局部搜索策略，通過建立節(jié)點選擇概率與節(jié)點適應(yīng)度的正相關(guān)關(guān)系，有效提高局部搜索能力，加快收斂。設(shè)計與實現(xiàn)了改進(jìn)的遺傳算法，并以福州市部分路網(wǎng)數(shù)據(jù)為樣本，驗證改進(jìn)后的遺傳算法在求解精度、效率與穩(wěn)定性三方面的進(jìn)步。

2 動態(tài)交通網(wǎng)絡(luò)規(guī)劃模型

2.1 動態(tài)路網(wǎng)模型

在城市交通網(wǎng)絡(luò)中，同一路段的交通狀況一般會隨時間而改變，動態(tài)路網(wǎng)模型不僅是對現(xiàn)實世界中路網(wǎng)的簡單抽象表達(dá)，同時還包含路況的實時變化信息[26-28]。比如，某些路段在上下班高峰時段更擁擠，采用傳統(tǒng)的靜態(tài)路阻函數(shù)進(jìn)行時間最短的路徑規(guī)劃時，不能有效規(guī)避擁堵路段，時間成本較高。動態(tài)路網(wǎng)模型是靜態(tài)路網(wǎng)模型添加各路段時態(tài)信息后的擴(kuò)展，其數(shù)學(xué)表達(dá)式如下：

式中，G表示有向帶權(quán)的動態(tài)城市交通路網(wǎng)；V表示路網(wǎng)中節(jié)點集合，V={vi|i=1,2,…,n}；E表示路網(wǎng)中各個節(jié)點連通的有向路段集合，vj∈V}，vi、vj分別是路段e的起點、終點；T表示時間閉區(qū)間[t0,tm]，t0是起點時刻，tm是到達(dá)終點時刻，在實際交通網(wǎng)絡(luò)中，Δt為間隔時長，其值越小越能實時反應(yīng)路況信息的變化，一般取5 min，并忽略在該間隔時長內(nèi)的路況變化；表示節(jié)點v在時刻t的時延集合；W(e,t)表示路段e在時刻t的路阻系數(shù)集合。

圖1為路網(wǎng)示意圖，其中節(jié)點包括轉(zhuǎn)向延誤節(jié)點和分流節(jié)點兩種類型，后者不產(chǎn)生轉(zhuǎn)向延誤（如V2）；路段具有方向性，在同一時間間隔內(nèi)，同一路段可能由于方向不同而具有不同的路阻系數(shù)。

圖1 交通路網(wǎng)示意圖

2.2 路徑規(guī)劃模型

如圖1所示，設(shè)vO、vD分別是始節(jié)點、終節(jié)點，ROD是vO到vD所有合格路徑的集合，r=(vO,v2,v4,v5,vD)是其中一條路徑，r∈ROD，時間最優(yōu)路徑規(guī)劃是指根據(jù)時刻t所在時間段的路況信息，分別計算ROD中每個路徑的行程時間Z(r)，從中選擇一條時間最短的路徑作為該時間段內(nèi)的最優(yōu)路徑，目標(biāo)函數(shù)如下：

3 改進(jìn)遺傳算法理論

3.1 編碼和初始化

遺傳算法包括三種常用的編碼實現(xiàn)方式，即二進(jìn)制編碼、符號編碼與實數(shù)編碼。在動態(tài)路徑規(guī)劃問題中，一條路徑相當(dāng)于一個染色體，路網(wǎng)節(jié)點相當(dāng)于染色體中的基因，由于這些節(jié)點的排列順序正好就是所要求的路徑，所以采用實數(shù)編碼方式更能直接表達(dá)路徑的實際意義，同時也有利于適應(yīng)值函數(shù)的選取和適應(yīng)值的計算。由于城市交通路網(wǎng)中的節(jié)點數(shù)較大，滿足相同起點和終點之間的不同連通路徑一般具有不同的節(jié)點數(shù)，因此采用變長度染色體編碼策略比定長度策略更適合求解動態(tài)路徑規(guī)劃這一問題。

遺傳算法與其他搜索算法最大的區(qū)別之一就是其面向種群進(jìn)行搜索的并行性，初始種群的設(shè)定對整個遺傳算法的運行性能具有決定作用。傳統(tǒng)的遺傳算法采用隨機的方式生成初始種群，這樣雖能提高種群的多樣性，但整個搜索過程缺乏方向性的引導(dǎo)，同時會出現(xiàn)斷路或環(huán)路現(xiàn)象，使得遺傳的進(jìn)化操作復(fù)雜化甚至無意義。為了保證種群的多樣性、避免出現(xiàn)斷路與環(huán)路現(xiàn)象，同時又提高初始種群個體的質(zhì)量，本文采用半隨機方式生成初始種群，即引入控制全局搜索方向的啟發(fā)式搜索策略。具體操作步驟如下：（1）以起節(jié)點O作為染色體的第一個基因，以終節(jié)點D作為染色體的最后一個基因。（2）為了規(guī)避斷路或環(huán)路現(xiàn)象，當(dāng)一個節(jié)點被選中后，就標(biāo)記該節(jié)點，若當(dāng)前節(jié)點無未標(biāo)記的鄰接節(jié)點可用于選擇時，退回當(dāng)前節(jié)點的上一節(jié)點重新進(jìn)行選擇并標(biāo)記當(dāng)前節(jié)點禁止下一次被搜索到。（3）以當(dāng)前節(jié)點C的所有未被標(biāo)記的鄰接節(jié)點作為下一個節(jié)點N的候選節(jié)點，從中按照一定的選擇概率使用隨機方式或最優(yōu)夾角方式確定下一個節(jié)點，若選擇最優(yōu)夾角方式，計算有向路段的夾角，選擇夾角最小的節(jié)點作為下一個節(jié)點。（4）重復(fù)步驟（2）和（3）直到當(dāng)前節(jié)點C 為終節(jié)點D，即為一個初始染色體。（5）按照此方式求解下一個染色體，直至達(dá)到初始種群規(guī)模的要求。（6）為了進(jìn)一步提高初始種群個體的平均質(zhì)量，本文確定初始種群規(guī)模為設(shè)定種群規(guī)模數(shù)的1.2倍，最后按表現(xiàn)排名依次舍去最差的多余個體。

3.2 選擇操作

定義適應(yīng)度函數(shù)的值為每個個體所包含路段和中間節(jié)點的交通時間阻抗之和，根據(jù)第二章得出的動態(tài)路網(wǎng)模型和動態(tài)最優(yōu)路徑模型可知，個體適應(yīng)度函數(shù)為：

式中，Z(r)越小，染色體的適應(yīng)值越小，所對應(yīng)的路徑所花費的行程時間越少，越接近于路徑最優(yōu)解。

選擇操作是指從當(dāng)代種群中選擇優(yōu)秀個體以生成交配池遺傳給下一代的過程，聯(lián)賽選擇、最佳個體保留、適應(yīng)值比例選擇是目前最常用的三種選擇策略。本文選擇聯(lián)賽選擇與最佳個體保留相結(jié)合的策略，前者的基本思想為：從當(dāng)代群體中隨機選擇一定規(guī)模的個體，比較后選擇適應(yīng)值小的個體放入交配池；可通過調(diào)整聯(lián)賽規(guī)模動態(tài)控制群體選擇壓力，一般聯(lián)賽規(guī)模取2。同時采用最佳個體保留策略將當(dāng)代種群中最優(yōu)的個體直接復(fù)制進(jìn)入子代，使得子代種群中的最優(yōu)個體不會出現(xiàn)比父代種群中的最優(yōu)個體差的可能，從而保證進(jìn)化方向，加快收斂速度。

3.3 交叉操作

交叉算子是模仿自然界染色體基因交叉重組將父代的優(yōu)良基因遺傳給下一代個體的操作。采用隨機確定交叉點對或選擇相同節(jié)點作為交叉點對的傳統(tǒng)方式進(jìn)行交叉操作存在明顯的局限性，前者需對子代個體進(jìn)行連通化處理，從而使父代的優(yōu)良基因發(fā)生劇變；后者會因為兩父代個體在此節(jié)點的前后基因片段相同而產(chǎn)生等同于父代的個體，使得交叉操作無效。因此本文采用啟發(fā)式鄰近交叉算子操作，主要步驟如下：（1）從其中一個雙親中隨機選擇待交叉點（除去O、D點）。（2）計算另一雙親中的節(jié)點與該節(jié)點的空間距離，選取距離最小的節(jié)點作為交叉點。（3）在交叉點連通生成子代個體，使子代表示的路徑合格化。此策略把需要連通處理的路段降到最小，同時保留了父代雙親的優(yōu)良基因。

3.4 變異操作

傳統(tǒng)的單點、多點變異等策略在路徑規(guī)劃問題中不能有效地維持種群的多樣性，容易導(dǎo)致個體向更壞的方向變異，本文采用多向變異策略，主要步驟如下：（1）按照變異概率選擇變異個體，隨機選擇變異個體的變異點（除去O、D點）。（2）以該點為起點，O點為終點，逆向搜索獲得變異個體。（3）以D節(jié)點為起點，該變異點為終點，逆向搜索求得變異個體。（4）對兩個變異個體進(jìn)行去環(huán)路處理。（5）比較兩種方式下變異個體的適應(yīng)度，選擇適應(yīng)度大的個體作為子代個體。（6）為保證種群多樣性，每隔五代重新生成一個新的個體取代其中一個待變異個體。

3.5 局部搜索策略

前人引入模擬退火、爬山與禁忌搜索等思想設(shè)計的混合遺傳算法雖在一定程度上能提高遺傳算法的局部搜索能力，但由于局部搜索過程中多次隨機生成若干路段，然后比較擇優(yōu)替代舊局部路段，而沒有考慮或者利用局部路段中鄰接節(jié)點的路況、轉(zhuǎn)向等已知信息的綜合影響，從而導(dǎo)致經(jīng)過大量時間解算得到的最優(yōu)路徑中的部分路段為次優(yōu)而非最優(yōu)，因此本文引入節(jié)點適應(yīng)度這一新的局部搜索策略對各代種群個體的隨機部分基因片段進(jìn)行自學(xué)習(xí)，以替代適應(yīng)度差的舊基因片段，且每次自學(xué)習(xí)只需搜索一次。根據(jù)路段的實時路況Traffic、路段的道路等級類型Type、轉(zhuǎn)彎類型Turn，以及與基因片段終點的夾角Angle四個影響因子對當(dāng)前節(jié)點的鄰接節(jié)點進(jìn)行適應(yīng)度評價，定義為節(jié)點適應(yīng)度，按照適應(yīng)度所占比例選取下一節(jié)點。節(jié)點適應(yīng)度與節(jié)點選擇概率定義為：

式中，f(xj)為當(dāng)前節(jié)點的鄰接節(jié)點xj的適應(yīng)度；根據(jù)路段的路阻系數(shù)，分為通暢、較通暢、擁擠和擁堵四種類型，分別對應(yīng)的 Traffic值為1、0.75、0.5、0；根據(jù)城市交通道路的等級類型，分為主干路和支路兩種類型，分別對應(yīng)的Type值為1和0.5；通過判斷通往下一節(jié)點的行駛轉(zhuǎn)向，分為直行、右轉(zhuǎn)、左轉(zhuǎn)和掉頭四種類型，對應(yīng)的Turn值分別為1、0.75、0.5和0.25；Angle為有向路段----CN與------

ND的夾角所對應(yīng)弧度值（C為當(dāng)前節(jié)點，N為待選鄰接節(jié)點，D為所選基因片段的終點），由于其與適應(yīng)度呈為負(fù)相關(guān)，需要進(jìn)行倒數(shù)處理。P(xj)為鄰接節(jié)點xj的選擇概率，節(jié)點適應(yīng)度越大，選擇概率就越大。

3.6 算法步驟

改進(jìn)的動態(tài)路徑規(guī)劃算法的主要步驟如下：（1）設(shè)定遺傳參數(shù)以及動態(tài)路阻系數(shù)。（2）采用啟發(fā)式策略獲得初始種群。（3）計算個體適應(yīng)度，判斷是否滿足算法終止條件，滿足則算法終止輸出實時路徑轉(zhuǎn)步驟（6），不滿足轉(zhuǎn)步驟（4）。（4）進(jìn)行選擇算子、交叉算子、變異算子操作，對遺傳算子操作生成的子代個體進(jìn)行局部搜索，并通過篩選生成子代種群。（5）轉(zhuǎn)步驟（3）。（6）按照最優(yōu)路徑行駛，每隔5 min更新動態(tài)路阻系數(shù)，并判斷當(dāng)前最優(yōu)行車路線上是否出現(xiàn)某一個或幾個路段發(fā)生擁堵等嚴(yán)重影響正常通行的現(xiàn)象，若不發(fā)生繼續(xù)原定路線行駛，若發(fā)生轉(zhuǎn)步驟（7）。（7）定位當(dāng)前位置的下一節(jié)點，若其為終點，結(jié)束行程，若不為終點則以該節(jié)點為起點重新進(jìn)行路徑規(guī)劃。如圖2為算法流程。

4 實驗與分析

4.1 數(shù)據(jù)處理

圖2 改進(jìn)后的算法流程

有向交通路網(wǎng)向量數(shù)據(jù)主要包括節(jié)點圖層和路段圖層，依據(jù)時間最短的路徑規(guī)劃需求，先設(shè)計節(jié)點與路段的字段屬性表：前者包括RoadID、FromNodeID、ToNodeID、Road_Type、Speed、Length與Real_Traffic字段，分別表示路段編號、路段起節(jié)點編號、路段終節(jié)點編號、路段等級、通暢時速度、長度、擁堵系數(shù)；后者包括NodeID、X、Y與Node_Type字段，分別表示節(jié)點編號、X坐標(biāo)值、Y坐標(biāo)值、節(jié)點是否為轉(zhuǎn)向節(jié)點；二者通過路段屬性表中的FromNodeID、ToNodeID字段與節(jié)點屬性表中的NodeID字段關(guān)聯(lián)。為了模擬路網(wǎng)的動態(tài)性，采用時間離散化方法對路段擁堵系數(shù)進(jìn)行每隔5 min的變化處理，結(jié)合路段長度以及通暢時路段速度求解路段行駛時間。本文采用的福州市部分路網(wǎng)數(shù)據(jù)共包含3 757個節(jié)點（包括轉(zhuǎn)向時延節(jié)點和轉(zhuǎn)向非時延節(jié)點），5 981個路段（包括單向路段和雙向路段），228個時段的擁堵系數(shù)。

鄰接矩陣和鄰接鏈表是路網(wǎng)資料常用的兩種存儲結(jié)構(gòu)，由于城市有向路網(wǎng)的大規(guī)模性和稀疏性，采用鄰接矩陣表達(dá)路網(wǎng)數(shù)據(jù)需要消耗大量存儲空間與搜索時間，而鄰接鏈表充分利用了路網(wǎng)中路段的鄰接特性進(jìn)行存儲，存儲空間和搜索時間的消耗均遠(yuǎn)遠(yuǎn)小于鄰接矩陣。因此，本文選用鄰接鏈表數(shù)據(jù)結(jié)構(gòu)，在.NET平臺下，利用ArcEngine組件庫進(jìn)行仿真實驗。

4.2 結(jié)果分析

種群規(guī)模是遺傳算法的一個重要參數(shù)，對求解精度和求解效率都存在較大影響，如圖3顯示了種群規(guī)模與收斂適應(yīng)值、收斂代數(shù)的關(guān)系：當(dāng)種群規(guī)模較小時，需要較多收斂代數(shù)，同時求解的收斂適應(yīng)值較大不能滿足路徑規(guī)劃的精度要求；隨著種群規(guī)模增大，收斂次數(shù)減少，同時求解的收斂適應(yīng)值逐漸減低，最終收斂次數(shù)和收斂適應(yīng)值趨于平穩(wěn)；當(dāng)種群規(guī)模為20～60時，收斂適應(yīng)值和收斂代數(shù)皆滿足最優(yōu)路徑規(guī)劃的精度要求，但隨著種群規(guī)模的增加，同樣的收斂代數(shù)，種群規(guī)模越小，收斂計算時間越少。通過多次模擬分析，綜合考慮求解精度和效率，本文設(shè)定種群規(guī)模為30，交叉率為0.9，變異率為0.05，迭代終止條件為最優(yōu)適應(yīng)值連續(xù)5代保持不變或達(dá)到最大迭代次數(shù)100。

圖3 種群規(guī)模對收斂適應(yīng)值和收斂代數(shù)影響

為便于比較分析算法的性能，選取傳統(tǒng)遺傳算法（GA）、文獻(xiàn)[22]中基于模擬退火的混合遺傳算法（SAGA），以及本文改進(jìn)的遺傳算法（IGA）進(jìn)行實驗對比，隨機選取一對OD點對，同時進(jìn)行100代進(jìn)化操作實驗，分析對比進(jìn)化過程中每代種群中最優(yōu)適應(yīng)值的變化情況。如圖4所示，IGA在進(jìn)化至13代時已達(dá)到收斂適應(yīng)值，求解收斂速度快于GA和SAGA，同時IGA所求得的收斂適應(yīng)值明顯優(yōu)于GA和SAGA。分析可知，本文所采用的局部搜索策略通過利用鄰接節(jié)點自身的先驗知識，構(gòu)建節(jié)點適應(yīng)度，然后根據(jù)各節(jié)點選擇概率進(jìn)行搜索，強化了局部搜索的目的性，進(jìn)化過程中每一代種群最優(yōu)值都有所提高，直至達(dá)到收斂適應(yīng)值，從而提高了算法的局部搜索能力，使其具有更好的收斂性。

圖4 進(jìn)化過程中最優(yōu)適應(yīng)值變化

進(jìn)一步對該OD點對進(jìn)行20次實驗，并利用第100代最優(yōu)適應(yīng)值的均值對之前每一代種群中最優(yōu)適應(yīng)值的均值做標(biāo)準(zhǔn)化處理，其值越趨近于1對應(yīng)路徑越優(yōu)，結(jié)果如圖5。IGA在前20代中具有很快的收斂速度，在進(jìn)化至20代左右時的標(biāo)準(zhǔn)化適應(yīng)值已達(dá)到0.9，即20次實驗中有若干次已十分逼近收斂結(jié)果，而GA和SAGA進(jìn)化緩慢，直到40代之后才達(dá)到0.9，說明本文提出的改進(jìn)算法IGA的收斂性和穩(wěn)定性均優(yōu)于GA和SAGA。

圖5 進(jìn)化過程中標(biāo)準(zhǔn)化適應(yīng)值變化

為避免偶然性，選取10對OD點對分別進(jìn)行20次實驗，實驗結(jié)果如表1。精度上：IGA搜索到的最優(yōu)個體所對應(yīng)路徑的行程時間更少，相較于GA縮短約38%，相較于SAGA縮短約6%；效率上：IGA收斂時所需計算時間平均值為1.232 s，相較于GA降低約30%，比SAGA降低約20%。本文提出的算法IGA具有更好的局部搜索能力，求解精度和求解效率均有明顯提升，能更好地滿足動態(tài)路徑規(guī)劃需求。

表1 不同OD點對實驗結(jié)果

為檢驗本文提出的算法的動態(tài)性與優(yōu)越性，選擇錦繡大廈為起點，光明港公園為終點，采用三種算法分別進(jìn)行動態(tài)路徑規(guī)劃誘導(dǎo)，結(jié)果如圖6、7、8所示，其中紅色代表擁堵路段，黃色代表擁擠路段，淡綠色代表較通暢路段，綠色代表通暢路段。初始時刻IGA所規(guī)劃的最優(yōu)路徑避免不必要的轉(zhuǎn)向等次優(yōu)行駛決策，具有更好的局部搜索效果，行程時間為19.69 min，優(yōu)于GA的34.68 min，和SAGA的22.56 min；5 min后規(guī)劃路徑中剩余部分未出現(xiàn)擁堵路段，不需要重新進(jìn)行路徑規(guī)劃；10 min后規(guī)劃路徑中剩余部分出現(xiàn)擁堵路段，重新規(guī)劃后得到規(guī)避了擁堵路段的新路徑。對比可知，本文提出的算法IGA能更好地處理動態(tài)路徑規(guī)劃問題。

圖6 GA動態(tài)路徑規(guī)劃

圖7 SAGA動態(tài)路徑規(guī)劃

圖8 IGA動態(tài)路徑規(guī)劃

5 結(jié)論

本文針對城市路網(wǎng)中動態(tài)路徑規(guī)劃問題，提出一種改進(jìn)的遺傳算法，該算法采用啟發(fā)式策略控制全局搜索方向確定初始種群；采用空間鄰近交叉策略完成交叉操作；使用前向、逆向的多向變異和重新生成新個體變異相結(jié)合的變異策略實施變異操作；引入節(jié)點選擇概率的局部搜索策略進(jìn)行局部搜索，能有效克服傳統(tǒng)遺傳算法存在的“早熟收斂”，局部搜索能力差等問題，同時有著更高的收斂效率與更穩(wěn)定的收斂性。實驗結(jié)果表明，提出的算法在搜索最優(yōu)路徑的過程中具有更優(yōu)的局部搜索能力，能有效地規(guī)避交通擁堵路段，滿足行進(jìn)中的動態(tài)最優(yōu)路徑規(guī)劃對求解精度和效率的要求。