李 哲，王嘉瑋，呂 萌，梁德禹

(1.唐山市交通運輸局，河北省唐山市路北區(qū)大里路125號 063000；(2.北京科技大學 自動化學院，北京市海淀區(qū)學院路30號 100083)

在現(xiàn)代智能交通系統(tǒng)中，根據(jù)起點、終點為駕駛員規(guī)劃可行、有效的行車路線是極為重要的工作。高質(zhì)量的行車路線一方面能夠協(xié)助駕駛員快速駛達目的地，另一方面對緩堵保暢、節(jié)約能源、環(huán)境保護具有重要意義。

城市道路網(wǎng)絡是極為復雜的拓撲結(jié)構(gòu)。對行車路線進行規(guī)劃時，不易建立精準的數(shù)學表達式。在復雜道路網(wǎng)絡中，隨著節(jié)點的增加，運算規(guī)模呈指數(shù)增長，大幅度提高了路徑規(guī)劃問題的求解難度。

近年來，對智能優(yōu)化算法的研究取得了長足的進步。以遺傳算法[1]、蟻群算法[2]、粒子群算法[3]為代表的經(jīng)典生物啟發(fā)式算法被廣泛應用于復雜問題的優(yōu)化求解。研究人員嘗試采用這類算法求解路徑規(guī)劃問題，并取得一定成果。梅偉等將噴涂機器人路徑規(guī)劃問題抽象為廣義旅行商問題，并提出一種改進的離散灰狼算法實現(xiàn)路線設計，提高噴涂機器人效率[4]。趙杰等對物流車輛配送路線規(guī)劃問題進行建模，并設計了一種改進的果蠅優(yōu)化算法，引入多種遺傳算子，提高算法性能[5]。徐飛等設計了基于魚群算法的車載導航系統(tǒng)模型，實現(xiàn)城市交通路線的智能規(guī)劃[6]。

文中對近年來較為新穎的果蠅優(yōu)化算法[7][8]進行分析，設計了一種改進算法，并將其集成于車載導航路徑規(guī)劃系統(tǒng)中。在對唐山市人大附近街區(qū)進行建模的基礎(chǔ)上，設置不同的起點、終點，利用該算法為智能車規(guī)劃行車路線，開展仿真實驗并對比分析。實驗結(jié)果表明，文中所提算法能夠高效構(gòu)建復雜路網(wǎng)環(huán)境中的合理行車路線，規(guī)劃質(zhì)量較高。

1 道路建模及分析

選取唐山市唐山市第四幼兒園—市人大/政協(xié)—市教育局地塊進行建模，共選取38個節(jié)點，用經(jīng)緯度標記這些節(jié)點的位置。節(jié)點信息如表1所示。

表1 唐山市人大/政協(xié)附件區(qū)域的行車節(jié)點(部分)Tab.1 Nodes in the area of Municipal People's Congress of Tangshan City(part)

圖1 該區(qū)域的節(jié)點分布Fig.1 Node distribution in the area

設定起點、終點后，在該區(qū)域規(guī)劃行車路線可被視為尋求最優(yōu)“節(jié)點序列”的過程。該序列最長不超過節(jié)點總數(shù)，起點、終點確定，并規(guī)定每個節(jié)點僅可通過一次。尋優(yōu)過程中，一條待選序列的構(gòu)建以達到終點為止。如構(gòu)建過程中出現(xiàn)當前點周圍無可走節(jié)點的情況，則該路線構(gòu)建不成功。節(jié)點間的代價簡單規(guī)定為距離，即優(yōu)先選擇距離較短的下一節(jié)點，后續(xù)可根據(jù)路況等因素進行改進。為規(guī)劃區(qū)域設定環(huán)線，即車輛不會駛離城市，僅能夠在環(huán)線上或環(huán)線區(qū)域內(nèi)進行搜尋。

根據(jù)該環(huán)境設計鄰接矩陣A，如節(jié)點[i，j]間存在直接連接，則對應位置Aij為節(jié)點間距離值；如節(jié)點間不存在直接連接，則Aij=∞。由于該區(qū)域面積不大，文中近似將地表視作平面，通過2維歐式距離計算節(jié)點間距離。

2 基于果蠅算法的車載導航路徑規(guī)劃

生物啟發(fā)式智能算法在非線性優(yōu)化問題、NP完全問題(Non-deterministic Polynomial Complete)的求解中具有一定優(yōu)勢。這些智能算法啟發(fā)自自然界中不同物種種群的特點和行為，如生物體的遺傳進化[1]與免疫[9]，鳥群[3]、蟻群[2]、魚群[6]等種群的覓食行為等。一般而言，這類方法通過種群的多次迭代進化，逐漸向適應度更高的解靠攏，同時適當引入隨機性以避免算法陷入局部最優(yōu)。與自然界中生物的多樣性相一致，不同生物啟發(fā)式算法的流程中也參考了不同的生物行為。

文中主要采用了近年來較為新穎的果蠅優(yōu)化算法求解車載導航路徑規(guī)劃問題。

2.1 果蠅算法

果蠅優(yōu)化算法由臺灣學者潘文超于2011年提出。該算法啟發(fā)自果蠅的覓食行為，因其較低的計算復雜度與較好的性能，被廣泛應用于最優(yōu)化問題的求解。在果蠅算法中，“味道濃度”信息判定值S和“味道濃度”值Smell被用作啟發(fā)式信息，近似不同變量在尋優(yōu)過程中對適應度函數(shù)的影響。

果蠅算法的基本步驟可總結(jié)如下：

Step 1超參數(shù)確定，即種群大小N、最大迭代代數(shù)Max等；

Step 2以隨機形式初始化果蠅種群；果蠅利用其嗅覺，進行搜索并飛行至相應位置；假定果蠅在二維空間(X，Y)中搜尋最優(yōu)解，果蠅種群的位置確定公式如(1)所示；

(1)

式中，n∈[1,2,…，N];Xaxis、Yaxis為以隨機方式初始化的果蠅群體位置；R為隨機數(shù)；

Step 3為每只果蠅計算味道濃度判定值Si，如式(2)，式(3),

(2)

(3)

式中，Dn即為該果蠅距原點的距離；

Step 4將Step 3中求得的味道濃度判定值Sn帶入適應度函數(shù)，計算味道濃度值Smell(n)，據(jù)此判斷每只果蠅(第n只果蠅)位置的優(yōu)劣；如對2維函數(shù)f=-5+x2進行最小化優(yōu)化，則有：

(4)

Step 5依據(jù)優(yōu)化目標確定位置最佳的果蠅，記錄濃度值，如式(5)所示；

[bestSmell， bestIndex]=min(Smell(n))

(5)

對應地，對于最大化問題，式(5)中的min替換為max；

Step 6根據(jù)Step 5中求得的bestIndex選取位置最佳果蠅，即其位置[X(bestIndex),Y(bestIndex)]；

利用果蠅的“視覺”感知，蠅群整體飛向該最優(yōu)位置，如式(6)、(7)、(8)所示；

Smellbest=bestSmell

(6)

Xaxis=X(bestIndex)

(7)

Yaxis=Y(bestIndex)

(8)

Step 7在迭代代數(shù)N內(nèi)重復執(zhí)行Step 2至Step 5；判斷該代蠅群中有無位置更佳的果蠅；如有，則執(zhí)行Step 6；算法在最大迭代代數(shù)N時跳出，此時的[X(bestIndex),Y(bestIndex)]即為所求得的解。

在上述優(yōu)化中，果蠅算法將待優(yōu)化的參數(shù)x轉(zhuǎn)化為具有兩個參量的“味道濃度判定值”，從而分散了優(yōu)化過程中陷入局部最優(yōu)的風險。這一特性使果蠅算法在對某些模型的超參數(shù)進行優(yōu)化時具有優(yōu)勢，如GRNN中的spread[10]。

2.2 用于車載導航路徑規(guī)劃的果蠅算法

上述經(jīng)典果蠅優(yōu)化算法可被用于函數(shù)優(yōu)化、模型超參數(shù)優(yōu)化等連續(xù)優(yōu)化問題。而在現(xiàn)實生活中，需處理的實際問題往往更為多樣化。根據(jù)問題建模形式的不同，果蠅算法也被賦予了不同的意義。國內(nèi)外學者結(jié)合不同場景，對果蠅算法做出了不同的改進。

對于實數(shù)優(yōu)化問題，果蠅算法中的蠅群可被看作一組位置，位置的變化影響數(shù)值的變化[7]。在離散、組合優(yōu)化問題，如TSP、車輛調(diào)度等問題中，果蠅種群常被處理為一組序列[11]。此外，對于機器人路徑規(guī)劃問題，在采用柵格法[12]、基于圖的方法[13]等方式構(gòu)建的地圖環(huán)境中，果蠅可被視作位置，也可被視作序列。這些算法遵循了果蠅算法的基本思想，即通過果蠅的“嗅覺搜索”和“味道濃度判定值”帶入隨機變化，發(fā)現(xiàn)味道濃度更佳的個體；通過“視覺”信息，在每次迭代中實現(xiàn)在最佳位置的聚集。

文中所求解的車載導航路徑規(guī)劃問題是典型的離散、組合優(yōu)化問題。遺傳算法[1]是求解該問題的常用方法。為便于對路徑整體而非單一位置進行評價，同時盡可能減小局部最優(yōu)風險，本文將果蠅建模為一組序列，也就是道路環(huán)境中一組路口節(jié)點的組合。

結(jié)合車載導航路徑規(guī)劃實際環(huán)境，本文算法基于果蠅算法思想，主要進行了以下3點改進。

(1)面向離散優(yōu)化問題，在果蠅序列的構(gòu)建過程中，為地圖中的每一個節(jié)點設計味道濃度判定值，如式(9)、(10)所示。

(9)

(10)

式中，n∈[1,2,…，N]，為種群大小；t為可供選擇的節(jié)點編碼，d為目標節(jié)點編碼；Dnt為當前點[xnt,ynt]到目標點[xnd,ynd]的距離。

這一設計使得節(jié)點離目標點越近，味道濃度判定值越大。在果蠅構(gòu)建路線的過程中，依據(jù)Snt的大小，按照賭輪法選取下一個節(jié)點。利用“嗅覺搜索”和味道濃度判定機制引入啟發(fā)式信息(距離)和隨機變化(賭輪選擇)，是優(yōu)化種群的重要步驟。

(2)進一步設計了與路徑規(guī)劃問題相一致的味道濃度計算函數(shù)，如式(11)所示。

Smell(n)=D1+D2+…+DD

(11)

式中，D為一條路線中兩個相鄰節(jié)點間的距離。

(3)引入交叉算子，進一步豐富種群多樣性以發(fā)現(xiàn)性能更優(yōu)的解。本文中采用比較基礎(chǔ)的單點交叉形式。如對兩條路徑：

A：[1,3,6,5,7,11,4,10]

(12)

B：[1,2,8,9,5,4,10]

(13)

判斷路徑間是否有重合點，如本例中[5,4]，隨機選擇節(jié)點[5]，則交叉后路徑為：

C：[1,3,6,5,4,10]

(14)

相較于經(jīng)典遺傳算法，本文所設計的改進果蠅算法利用了蠅群的“視覺搜尋”、“聚集”機制，即對參與交叉的果蠅進行篩選，僅對當前最優(yōu)序列和部分次優(yōu)序列進行交叉操作。

2.3 算法步驟

文中設計的改進果蠅算法基本步驟如下。

Step 1超參數(shù)確定，即種群大小N、最大迭代代數(shù)Max等；

Step 2按照2.2所述，構(gòu)建初始種群即N只果蠅、N條路徑；

Step 3依據(jù)式(11)計算味道濃度，選取味道最佳的路徑序列；

Step 4種群向味道最佳序列聚集，在最佳序列、與最佳序列存在共同節(jié)點的次優(yōu)序列、與最佳序列存在共同節(jié)點的隨機某一條序列間進行交叉操作；

Step 5按照10%的概率進行變異操作，即對味道濃度不佳的10%的果蠅進行變異，按照2.2所述，利用嗅覺搜索重新構(gòu)建序列；

Step 6采用基于味道濃度的輪盤賭方法選取N只果蠅，重復Step 3至Step 6，直至達到Max。

需要說明的是，文中構(gòu)建待選序列時，需達到終點。規(guī)定每個節(jié)點僅可通過一次。如構(gòu)建過程中出現(xiàn)當前點周圍無可走節(jié)點的情況，則該路線構(gòu)建不成功。規(guī)定城市存在環(huán)路，即汽車能夠以繞城一周的形式抵達終點，不會出現(xiàn)駛離城市的情況。

3 實驗分析

結(jié)合第1節(jié)中構(gòu)建的唐山市某街區(qū)道路環(huán)境，開展仿真實驗。實驗中果蠅規(guī)模為10，最大迭代代數(shù)為200，變異概率為10%，采用單點交叉的形式。

文中采用車載導航路徑規(guī)劃的常用算法，遺傳算法[1]作為對比，其種群規(guī)模為10，最大迭代代數(shù)為200，選擇60%的個體進行交叉，變異概率為10%。采用基于適應度的輪盤賭方法進行個體選擇。變異概率為10%。變異操作為將某點替換為可行駛點，需檢查變異操作后新節(jié)點是否能夠與變異前的路徑相連接。

在所選街區(qū)環(huán)境中，分別設定不同的起點—終點，算法運行5次進行規(guī)劃，其規(guī)劃結(jié)果如表2所示。

表2 不同起點-終點情況下兩種算法的規(guī)劃結(jié)果Tab.3 Length of the routes with different starting points and terminus

由表2中的數(shù)據(jù)可以看出，在5組實驗中，文中所設計的果蠅算法與遺傳算法在3組實驗中取得了一致的最優(yōu)規(guī)劃路線。在起點為14、終點為22，起點為29、終點為12的實驗中，果蠅算法取得了優(yōu)于遺傳算法的解。

起點為4，終點為22時，果蠅算法所得最優(yōu)路線為4-3-2-1-38-18-36-35-21-22，如圖2中黑色路線；遺傳算法所求得的最優(yōu)路線為4-5-7-15-14-17-19-21-22，如圖2中紅色路線。

圖2 起點為4終點為22時兩種算法所得路線Fig.2 Route obtained by 2 algorithms from node 4 to node 22

起點為29，終點為12時，果蠅算法所得最優(yōu)路線為29-28-27-26-25-35-36-18-17-14-13-12，如圖3中黑色路線；遺傳算法所得最優(yōu)路線為29-28-27-26-34-36-18-17-14-13-12，如圖3中紅色路線。

圖3 起點為29終點為12時兩種算法所得路線Fig.4 Route obtained by 2 algorithms from node 29 to node 12

4 結(jié)束語

文中結(jié)合車載導航路徑規(guī)劃問題，設計了一種改進的果蠅算法。對唐山市人大/政協(xié)街區(qū)進行建模后，采用該改進果蠅算法求解路徑規(guī)劃問題。在本文試驗中，選取了多組起點-終點，并進行規(guī)劃，對結(jié)果進行統(tǒng)計。實驗結(jié)果表明，該算法能夠高效地為車輛構(gòu)建從起點到終點的行車路線，降低行車成本。