基于改進(jìn)遺傳算法的國內(nèi)旅行交通規(guī)劃研究*

于 雁 李小光

（青島大學(xué)自動化學(xué)院 青島 266071）

1 引言

隨著中國全面進(jìn)入小康社會，人們不再局限于物質(zhì)消費，越來越重視精神文化滿足。隨著旅游業(yè)的快速發(fā)展，人們對已有的地域空間和距離的認(rèn)識不斷健全，時間距離和成本距離逐漸替代傳統(tǒng)的空間距離被廣泛應(yīng)用于研究中［1］，在“四縱四橫”客運專線建設(shè)全面展開形勢下［2］，中國游客對于交通路線和外出成本的需求在逐漸提高。從黑龍江到海南島，上海到烏魯木齊這種長時間和多地點的外出旅行，進(jìn)行合理的旅行交通規(guī)劃，使得所需總費用最少，具有重要的現(xiàn)實和研究意義。

旅行交通規(guī)劃與旅行商問題具有一定的內(nèi)在聯(lián)系，旅行商問題是一個典型的數(shù)學(xué)組合優(yōu)化問題，已經(jīng)被廣泛應(yīng)用到許多實際問題中［3～7］，如物流配送、飛機(jī)航線安排和產(chǎn)品的生產(chǎn)安排問題等。這些問題都可以通過數(shù)學(xué)變換轉(zhuǎn)化為旅行商問題進(jìn)行求解［8］。求解旅行商問題的方法有簡單插值算法、模擬退火算法、蟻群算法和遺傳算法等，其中，最受歡迎的是遺傳算法［9］。傳統(tǒng)的遺傳算法存在易早熟收斂、后期收斂速度慢的缺陷，許多學(xué)者針對此問題對傳統(tǒng)遺傳算法進(jìn)行改進(jìn)并與其他算法相結(jié)合，滿足了自身對不同問題的具體解決方法需求。羅金亮等［10］利用擇向交叉遺傳算法對遠(yuǎn)距支援干擾部署問題進(jìn)行了研究；Sonmez A等［11］利用遺傳算法對無人機(jī)的路徑規(guī)劃做了優(yōu)化；王勇臻等［12］利用改進(jìn)分組遺傳算法求解了多旅行商問題；許宏志等［13］提出了一種仿細(xì)粒度的粗粒度并行模型，實現(xiàn)了雙層并行的遺傳算法在旅行商問題中的應(yīng)用；易云飛等［14］通過將牛頓力學(xué)中的加速度因子映射到粒子群算法的慣性權(quán)重，改進(jìn)粒子群算法對旅行商問題進(jìn)行了研究；李敏等［15］利用遺傳算法、蟻群算法和模擬退火算法對中國旅行商問題進(jìn)行了仿真。

自然界中動植物的生老病死是固有的規(guī)律，當(dāng)動物達(dá)到一定的年齡后，便會死亡。本文將動物會自然死亡的規(guī)律應(yīng)用于遺傳算法中，對個體編碼時賦予年齡操作，將此改進(jìn)遺傳算法進(jìn)行國內(nèi)旅行交通規(guī)劃，為人們的外出旅行提供最優(yōu)化的旅行路線和旅行總費用。

2 旅行交通規(guī)劃

旅行交通規(guī)劃與旅行商問題相類似［16］，旅行商問題是以地點之間的距離總和為優(yōu)化目標(biāo)，使得距離總和最小。由于我國國內(nèi)各個城市之間的距離相隔較遠(yuǎn)，必須要乘坐一定的交通工具前往。旅行交通規(guī)劃是指推銷員乘坐交通工具代替步行到達(dá)多個地點，并在到達(dá)地點無重復(fù)的情況下找到最終點再回到起點的總路徑，使得所需費用最低。

旅行交通規(guī)劃問題用數(shù)學(xué)語言描述為尋找一條巡回路徑，目標(biāo)函數(shù)為

其中vi為城市號，i∈N，1 ≤vi≤n，p(vi,vj)表示城市i與城市j 之間乘坐交通工具所需費用，對于對稱旅行交通規(guī)劃問題有p(vi,vj)=p(vj,vi)。

3 遺傳算法

對于旅行交通規(guī)劃問題，通常應(yīng)用遺傳算法中的選擇操作、交叉操作和變異操作。本文針對傳統(tǒng)遺傳算法存在的問題，對其進(jìn)行改進(jìn)，即在選擇操作和交叉操作后加入年齡操作，最后進(jìn)行變異操作。

改進(jìn)遺傳算法的流程圖見圖1。

圖1 改進(jìn)遺傳算法流程圖

各個操作的具體內(nèi)容如下。

選擇操作：按個體適應(yīng)度大小，從舊群體中選擇部分個體到新群體。

交叉操作：根據(jù)適應(yīng)度大小，利用輪盤賭注方法選擇兩個個體，交叉產(chǎn)生新個體。

變異操作：確定個體基因兩個位置，將其對換。

年齡操作：判斷個體年齡是否達(dá)到各種動物死亡年齡范圍，若年齡進(jìn)入死亡年齡范圍，則刪除該個體，并利用交叉操作，產(chǎn)生新個體，同時賦予該新個體年齡為0，以保證種群數(shù)量不變。

4 仿真實驗與結(jié)果分析

以乘坐火車為旅行主要交通工具，在國內(nèi)31個省會城市間，進(jìn)行旅行交通路線規(guī)劃。城市與城市之間有多趟和多種列車運行，具體交通工具按照以下規(guī)則進(jìn)行選擇。

1）城市之間有直達(dá)車，優(yōu)先選擇高鐵；若無高鐵，選擇軟臥。

2）城市之間無直達(dá)車，進(jìn)行換乘，優(yōu)先選擇高鐵；若無高鐵，選擇軟臥。

3）前往臺北，選擇飛機(jī)。

將31個省會城市進(jìn)行編號，見表1。

表1 編號與城市對應(yīng)表

查閱中國運輸系統(tǒng)價格表，獲得各個城市之間的交通運輸所需費用，費用表如表2所示。

表2 城市間交通運算所需費用表

本實驗將種群大小設(shè)置為200，最大遺傳代數(shù)為1000，代溝為0.9，變異概率為0.05，對有年齡操作和無年齡操作分別進(jìn)行5 次計算，變化曲線圖見圖2～7，其中圖2 為有無年齡操作后的種群最優(yōu)解所需費用變化曲線圖，圖3 為有無年齡操作后的種群平均所需費用變化曲線圖，圖4 為有年齡操作種群最優(yōu)解所需費用變化曲線圖，圖5 為無年齡操作種群最優(yōu)解所需費用變化曲線圖，圖6 為有年齡操作種群平均所需費用變化曲線圖，圖7 為無年齡操作種群平均所需費用變化曲線圖。

圖2 種群最優(yōu)解所需費用變化曲線圖

圖3 種群平均所需費用變化曲線圖

圖4 有年齡操作種群最優(yōu)解所需費用變化曲線圖

圖5 無年齡操作種群最優(yōu)解所需費用變化曲線圖

圖6 有年齡操作種群平均所需費用變化曲線圖

圖7 無年齡操作種群平均所需費用變化曲線圖

從圖2～7 可以看出，對傳統(tǒng)遺傳算法添加年齡操作具有很好的可實踐性，當(dāng)參數(shù)設(shè)置相同的情況下，對有年齡操作和無年齡操作分別進(jìn)行5 次計算，有年齡操作得到的最優(yōu)巡回路徑比無年齡操作得到的最優(yōu)巡回路徑更優(yōu)，所需旅行總費用更低。當(dāng)添加年齡操作，強(qiáng)制淘汰達(dá)到死亡年齡且適應(yīng)能力高的優(yōu)秀個體，可以有效避免種群的多樣性受到破壞，使遺傳算法過早地出現(xiàn)早熟和收斂現(xiàn)象。

表3為有年齡操作計算5次后的所需費用統(tǒng)計表，表4 為無年齡操作計算5 次后的所需費用統(tǒng)計表。

表3 有年齡操作計算5次費用統(tǒng)計表

表4 無年齡操作計算5次費用統(tǒng)計表

從表3和表4可以得到，進(jìn)行年齡操作后，平均種群最優(yōu)解所需費用比無年齡操作所得到的總費用消費更少，相應(yīng)的種群平均所需費用也比無年齡操作所消費的總費用更少。由此可得，添加年齡操作，對于國內(nèi)的旅行交通規(guī)劃可以實現(xiàn)更好的巡回路徑，能夠為人們的旅行提供更優(yōu)、更合理化的建議，節(jié)約旅行資金。

對各城市旅行解碼前得到的最優(yōu)路線為

解碼后的最優(yōu)路線為

上述最優(yōu)路徑所需總費用為10464.5 元，圖8為最優(yōu)解巡回路徑圖，圖9 為文獻(xiàn)［15］遺傳算法所獲得的最優(yōu)巡回路徑圖。

圖8 最優(yōu)解巡回路徑圖

圖9 文獻(xiàn)［15］遺傳算法巡回路徑圖

將本文改進(jìn)遺傳算法所獲得的最優(yōu)巡回路線需要的總費用與文獻(xiàn)［15］優(yōu)化路徑所需費用進(jìn)行對比，結(jié)果見表5。

表5 與文獻(xiàn)［15］優(yōu)化路徑所需費用對比表

如表5 所示，文獻(xiàn)［15］利用遺傳算法、蟻群算法和模擬退火算法所獲得的優(yōu)化路徑全都比有年齡操作遺傳算法優(yōu)化的路徑總距離少，但所需費用都更高，改進(jìn)遺傳算法獲得最優(yōu)路徑的所需總費用比文獻(xiàn)［15］三種算法所需費用分別省527 元、564元和502.5 元，為人們的外出旅行節(jié)約了一定的資金。

5 結(jié)語

對國內(nèi)旅行外出進(jìn)行旅行交通規(guī)劃，可以為人們出行路線安排提供合理化的建議，使人們對出行安排進(jìn)行理性分析，節(jié)約外出消費資金，做出更正確的路線規(guī)劃和決策，滿足了人們的精神文化追求和享受。在國內(nèi)旅行交通規(guī)劃研究中，對傳統(tǒng)遺傳算法中添加年齡操作相比無年齡操作遺傳算法，能夠更好地求得巡回路線最佳解，得到更優(yōu)的旅行路線以及更少的所需費用，提供合理化的旅行線路圖。改進(jìn)遺傳算法以所需費用為優(yōu)化目標(biāo)，可能會增加部分總距離，但是在限定的資金范圍內(nèi)，能夠緩解經(jīng)濟(jì)壓力，減輕成本負(fù)擔(dān)，讓出行更加的輕松享受。