基于改進遺傳算法的動態路徑優化研究

肖自乾，陳經優

(海南軟件職業技術學院 軟件工程系，海南 瓊海 571400)

基于改進遺傳算法的動態路徑優化研究

肖自乾，陳經優

(海南軟件職業技術學院 軟件工程系，海南 瓊海 571400)

日常出行中，由于道路養護、天氣變化等原因，導致部分路段交通受阻甚至禁止通行，這種情況下需要避開此路段。在基于改進遺傳算法查找最優路徑的基礎上，對如何根據路況變化動態尋找更為合適的最優路徑進行了探討。

遺傳算法；動態優化；路權

1 最優路徑主要影響因素

本文探討的最優路徑主要影響因素包括道路是否暢通和道路通行緩慢兩方面[1]。最優路徑定義不同意義也不同，路權的標定方法有5種：①將車輛行駛距離作為優化目標；②將行駛時間作為優化目標；③將行駛費用作為優化目標；④將是否選擇高速路、減少費用等作為優化目標；⑤將實際交通情況如擁擠程度作為優化目標。本文主要將行駛路徑作為優化目標，在此基礎上考慮實際交通狀況，將這些因素轉換后納入路權進行路徑分析。

(1)道路是否暢通。在靜態路網模型中，可以直觀地將路段長度作為最優路徑的判斷依據,只需將其轉換為經典的TSP問題即可求解。而實際情況中，往往一些道路因為維修或天氣原因導致無法通行，在最優路徑的搜索中應避開這樣的路段，尋找其它最優路徑。

(2)通行時間。如果通行時間非常緩慢，則考慮搜索其它更優路徑。

2 改進遺傳算法基本思想

改進遺傳算法相比傳統遺傳算法具有收斂快、較好的全局最優搜索能力等特點。最優路徑搜索以經典TSP問題作為研究模型，其主要實現思想是：①將遺傳過程分階段進行，設定相應的交叉、變異參數，后階段進行自適應參數設定；②在后期先將種群中所有個體進行適應度排序，計算適應度平均值；再根據個體適應度與平均值的關系執行自適應參數的交叉和變異操作，即在交叉操作中，比較適應度值fc：當fc|favg時，執行固定的交叉概率k1；當fc>favg時，執行自適應的交叉概率。在變異操作中，選取兩個個體，找出較大適應度值fm，當fm|favg時，執行固定的變異概率k4；當fm>favg時，執行自適應變異概率，同時引入精英保留策略來保留優良個體[2-3]。

對普通遺傳算法(Rank)和改進的自適應遺傳算法進行仿真比較，發現傳統的遺傳算法存在求解速度較慢問題，子代適應度低于父代適應度的情況也時有出現，而改進的自適應遺傳算法尋優速度較快，能得到較為理想的結果，具有較好的收斂性[2]，如圖1所示。

圖1 兩種算法路徑尋優過程曲線

3 路徑動態優化探討

首先隨機模擬出20個坐標點(模擬地點)，其坐標如圖2所示。

圖2 初始化模擬地點

基于改進遺傳算法的最優路徑優化搜索結果如圖3所示。

圖3 最優路徑搜索結果(長度3537.2014)

路徑搜索結果為：

1→7→6→4→11→14→18→8→12→17→16→5→20→13→9→3→10→19→15→2→1

3.1 路徑連通情況

實際交通環境中，一些路段往往因為道路養護、天氣等原因暫時不能通行，此時要另外尋找合適路徑。為驗證算法，根據設定條件進行動態路徑優化。首先假設任意點之間都是連通的，且不考慮方向因素，據此構造各點相互連接情況如圖4所示。

其中，數字1表示兩點可通行，數字0表示不能通行。由圖4可以看出，坐標點13和20之間不能通行，在當前情況下最優搜索結果如圖5所示。

路徑動態搜索結果為：

1→7→6→4→11→14→18→8→12→17→16→5→20→10→13→9→3→19→15→2→1

3.2 交通流參數

3.2.1 參數介紹

實際交通中需要考慮交通流量、行駛速度、排隊長度、占有率、交通流密度以及車頭間距、時距等交通參數。這些參數在一定程度上反映了實際的交通運行狀態。下面將交通流量和行駛速度參數作為路徑動態優化條件進行介紹[1]。

圖4 各點相互連接情況

圖5 道路狀況發生變化后最優路徑(長度3681.1895)

(1)交通流量：機動車交通流量指在單位時間內通過道路上某節點、路段或某條車道的車輛數。

(1)

其中，q為交通流量(輛/小時)，N為車輛數，T為單位時間。由于單從交通流量上很難準確反應整個交通運行狀態，所以，在實際應用中不作為單獨指標，需要結合其它參數綜合考慮。

(2)行駛速度：道路上行駛的車輛速度有幾種描述，如即時速度、平均行駛速度以及平均行程速度。其中平均行駛速度指路程與行駛時間之比，這個時間包含行駛時間和行駛過程中的等待時間，這個指標并不能很好地反映實際交通情況；平均行程速度指行駛路程與行駛時間(不含等待時間)之比，能更好地體現車輛在道路上的運行狀態。

3.2.2 優化策略

當兩個點之間發生擁堵，通行特別緩慢時，以平均行駛速度、交通流量作為判定標準。

(1)間斷交通流情況：在間斷交通流情況下，設定平均行駛速度小于每小時5公里為“慢”，大于每小時10公里小于每小時15公里為“較慢”，大于每小時20公里小于每小時25公里為“中”，可將平均行駛速度小于每小時15公里作為變換路徑的判定條件，以搜索其它更為快捷的路徑。

(2)連續交通流：在連續交通流情況下，設定平均行駛速度小于每小時10公里為“慢”，大于每小時30公里小于每小時40公里為“較慢”，可將平均行駛速度小于每小時30公里作為變換路徑的判定條件，以搜索其它更為快捷的路徑。

4 結語

本文在改進遺傳算法的基礎上，探討了如何結合實際交通因素進行動態路徑優化問題，并以兩點之間道路不可通行以及在可通行情況下考慮其它交通因素為例，闡述了具體的動態路徑優化策略。

[1] 李云.基于遺傳算法的動態路徑優化[D].太原：太原理工大學,2013.

[2] 肖自乾,陳經優.基于改進的自適應遺傳算法路徑優化研究[J].蘇州職業大學學報,2016(3):123-125.

[3] 梁旭，黃明.現代智能優化混合算法及其應用[M].北京：電子工業出版社，2011.

(責任編輯：杜能鋼)

海南省自然科學基金項目(20156248)

肖自乾(1982-)，男，四川自貢人，海南軟件職業技術學院軟件工程系副教授，研究方向為軟件開發、算法研究；陳經優(1983-)，女，海南東方人，海南軟件職業技術學院軟件工程系副教授，研究方向為軟件開發。

10.11907/rjdk.162864

TP319

A

1672-7800(2017)003-0108-02