基于改進遺傳算法的動態(tài)路徑優(yōu)化研究

肖自乾，陳經(jīng)優(yōu)

(海南軟件職業(yè)技術(shù)學(xué)院 軟件工程系，海南 瓊海 571400)

基于改進遺傳算法的動態(tài)路徑優(yōu)化研究

肖自乾，陳經(jīng)優(yōu)

(海南軟件職業(yè)技術(shù)學(xué)院 軟件工程系，海南 瓊海 571400)

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

遺傳算法；動態(tài)優(yōu)化；路權(quán)

1 最優(yōu)路徑主要影響因素

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

(1)道路是否暢通。在靜態(tài)路網(wǎng)模型中，可以直觀地將路段長度作為最優(yōu)路徑的判斷依據(jù),只需將其轉(zhuǎn)換為經(jīng)典的TSP問題即可求解。而實際情況中，往往一些道路因為維修或天氣原因?qū)е聼o法通行，在最優(yōu)路徑的搜索中應(yīng)避開這樣的路段，尋找其它最優(yōu)路徑。

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

2 改進遺傳算法基本思想

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

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

圖1 兩種算法路徑尋優(yōu)過程曲線

3 路徑動態(tài)優(yōu)化探討

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

圖2 初始化模擬地點

基于改進遺傳算法的最優(yōu)路徑優(yōu)化搜索結(jié)果如圖3所示。

圖3 最優(yōu)路徑搜索結(jié)果(長度3537.2014)

路徑搜索結(jié)果為：

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

3.1 路徑連通情況

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

其中，數(shù)字1表示兩點可通行，數(shù)字0表示不能通行。由圖4可以看出，坐標(biāo)點13和20之間不能通行，在當(dāng)前情況下最優(yōu)搜索結(jié)果如圖5所示。

路徑動態(tài)搜索結(jié)果為：

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

3.2 交通流參數(shù)

3.2.1 參數(shù)介紹

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

圖4 各點相互連接情況

圖5 道路狀況發(fā)生變化后最優(yōu)路徑(長度3681.1895)

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

(1)

其中，q為交通流量(輛/小時)，N為車輛數(shù)，T為單位時間。由于單從交通流量上很難準(zhǔn)確反應(yīng)整個交通運行狀態(tài)，所以，在實際應(yīng)用中不作為單獨指標(biāo)，需要結(jié)合其它參數(shù)綜合考慮。

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

3.2.2 優(yōu)化策略

當(dāng)兩個點之間發(fā)生擁堵，通行特別緩慢時，以平均行駛速度、交通流量作為判定標(biāo)準(zhǔn)。

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

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

4 結(jié)語

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

[1] 李云.基于遺傳算法的動態(tài)路徑優(yōu)化[D].太原：太原理工大學(xué),2013.

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

[3] 梁旭，黃明.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2011.

(責(zé)任編輯：杜能鋼)

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

肖自乾(1982-)，男，四川自貢人，海南軟件職業(yè)技術(shù)學(xué)院軟件工程系副教授，研究方向為軟件開發(fā)、算法研究；陳經(jīng)優(yōu)(1983-)，女，海南東方人，海南軟件職業(yè)技術(shù)學(xué)院軟件工程系副教授，研究方向為軟件開發(fā)。

10.11907/rjdk.162864

TP319

A

1672-7800(2017)003-0108-02