求解物流路徑優化的改進遺傳算法研究

張禮華，廖聞劍，彭艷兵

（1.武漢郵電科學研究院湖北武漢430074；2.烽火通信科技股份有限公司江蘇南京210019）

求解物流路徑優化的改進遺傳算法研究

張禮華1，2，廖聞劍2，彭艷兵2

（1.武漢郵電科學研究院湖北武漢430074；2.烽火通信科技股份有限公司江蘇南京210019）

為了解決傳統遺傳算法中易早熟和陷入局部最優，造成收斂慢，效率低的問題，提出了一種改進的遺傳算法GBLSA（Genetic Based on Link_State A1gorithm）。對遺傳算法的基本算子進行改進，其中將鏈路狀態算法強大的尋優能力融入交叉算子中，保證個體逐代進化。引入與遺傳代數相關的自適應概率，提高了遺傳算法的搜索效率和收斂速度。仿真實驗表明，與傳統遺傳算法和TSPLIB標準值相比，提出的方法得到的結果路徑更優，效率更高。

路徑優化；遺傳算法；鏈路狀態算法；自適應概率

隨著阿里巴巴在美國的成功上市，網絡購物已成了人們越來越關注的話題，而物流配送業務在當今這個網購的生態圈內起著舉足輕重的作用。作為一個企業追求利益毋庸置疑，因此通過對有限的資源進行適當的調度和優化，為客戶帶來更好的服務成了物流公司爭相討論的一個熱門話題。目前主流物流公司配送流程大都是將貨物發往各地分撥中心后進行人力配送，一個快遞公司的總成本主要由人力配送成本決定。有效降低配送路徑的距離能提高人力配送的效率，這對于公司實現利益最大化有著極大的貢獻作用［2］。

物流配送問題可概括為旅行商問題（Trave1ing Sa1esman Prob1em，TSP），又叫貨郎擔問題，人們通常采取借助大量的公式和約束條件去解決多項式時間內可解決的問題，所以被戲稱為“NP_hard”。對于這類問題普遍通過尋求最優解或者近似最優解的方法來代替全局遍歷搜索求得最優解［1］。目前對于該問題的有效解決手段大體可分為兩類，一類是以仿生學算法為代表，諸如人工魚群算法、蛙跳算法、蟻群算法［2］、螢火蟲算法［3］等；另一類是以啟發式算法為代表，比如模擬退火算法［4］、遺傳算法［5_7］、免疫算法、禁忌搜素算法、爬山算法等。其中以遺傳算法為代表的全局搜索算法解決NP完全問題效果顯著。

但傳統遺傳算法也存在收斂速度緩慢和容易陷入局部最優解的問題。為了加快遺傳算法的收斂速度和防止過早陷入最優解情況的產生，本文提出了一種基于鏈路狀態算法的改進遺傳算法GBLSA（Genetic Based on Link_State A1gorithm），將鏈路狀態算法（Link_State A1gorithm，LSA）強大的尋優能力巧妙地融入遺傳算法的交叉算子中，不僅成功克服了鏈路狀態算法需要較大存儲空間的缺點，而且有效地解決了傳統遺傳算法慢收斂的問題。并提出基于基因值的倒位算子和引入自定義的自適應概率，對物流配送路徑優化問題進行了深入探討和研究，并通過Mat1ab仿真進行了實驗和性能上的分析。同算例仿真不難發現，該算法在路徑優化與時間上都取得了令人滿意的效果，大都提高了物流配送的工作效率，節省了經營成本，為企業創造了巨大的經濟效益。

1　數學模型的建立

1.1路徑優化問題模型

物流配送路徑優化問題可描述為：從某配送中心通過多輛汽車將貨物送到多個客戶手中，每個客戶需求量和地理位置一定，汽車的載重量一定，要求合理安排汽車的行徑軌跡，使總的運送距離最短。同時還應滿足一下條件：

1）每條配送路徑上各需求點的需求量之和不超過汽車載重量；

2）每條配送距離長度不超過汽車的最大行駛距離；

3）每個客戶的需求必須滿足且只能有一輛汽車完成配送任務。

由于多輛車的配送路徑優化問題可以按照一定的策略加以分解成單輛汽車的路徑優化。通過求得單輛車的最短路徑，并加以組合就能得到整個物流配送路徑的最短距離。為了便于問題更進一步地討論與展開，本文將基于上述分析對單輛車的最短路徑優化展開的討論與研究。

1.2遺傳算法簡介

TSP問題具體可以描述為：一個旅行商人即將拜訪n座城市，要求他先后通過這n座城市，并且每座城市有且只能經過一次，最后再回到原來出發的那個城市。路徑選擇的要求是在滿足上述約束條件的情況下，選擇出所有符合條件的路徑中的最小路徑值。定義城市i和城市j之間的距離用d（i，j）表示，城市總數目為n，V包含所有城市的一個集合，即V=｛v1，v2，…，vn｝，則目標路徑為：

約束條件為：

其中U是V的非空子集。

公式（2）表示當該旅行商所走路線經過包含城市i到城市j時變量fij=1，否則為0；公式（3）表明每座城市只能經過一次；公式（4）要求該旅行商在任何一個城市子集中不能形成回路。

TSP問題是一類組合優化問題，其可能路徑隨著城市數目的增多成指數型增長，因此常常利用遺傳算法強大的尋優能力來解決這一類問題。

遺傳算法（Genetic A1gorithm，GA）是一種基于生物進化中的自然選擇和優勝劣汰的游戲規則所產生的一種啟發式算法。該算法通過每一代的適應度（fitness）大小按照適者生存的原則從每一代中選出個體，并通過模擬生物進化中基因雜交和變異的方式來產生下一代種群。遺傳算法在解決TSP問題的運算過程步驟如下：

1）初始化：設置此代進化數g=0，最大進化數為G，隨機產生初始種群P（g），種群中每個個體即表示一條路徑。

2）計算適應度：計算種群P（g）中每個個體的值，即路徑總長，取長度的倒數值為該個體的適應度值。

3）選擇運算：按照步驟2中的方法通過選擇算子對種群P（g）進行篩選，保證盡可能多地將適應度高的個體保留，完成優良基因的延續。

4）交叉運算：對本代種群中任意兩個個體通過交叉算子產生兩個新的個體作為下一代的種群個體。

5）變異運算：對種群中的個體串的基因通過變異算子作局部的變動。

6）截止條件：如果g≤G，則返回步驟2），否則停止運算。此時適應度值最高的個體即為所求的最短路徑。

2　算法設計及改進

2.1算法設計

2.1.1編碼的選擇和適應度函數的確定

遺傳算法的編碼大體分為二進制編碼和實數編碼。由于二進制編碼在城市數過多的情況下會使數據冗長，而且二進制表示還會造成“漢明懸崖”的產生，因此本文采用實數編碼的形式。假設種群中的某一個體X的基因表現型為（3251647），數字i表示編號為i的城市，則該個體所表示含義為從編號為3號的城市出發，按照3→2→5→1→6→4→7的順序依次經過各個城市，此表達方式更為直觀。

適應度函數是評判一個個體好壞的標準。取fitness（X）= 1/F（X），由公式可求得個體X的路徑值F（X）。

2.1.2初始群體的選取

初始群體的選擇是遺傳算法中很重要的一環，初始群體的好壞直接影響著整個算法的收斂速度為了防止個體的好壞過于集中，造成種群個體極端化的產生，本文將首先隨機產生一個規模為初始種群3倍的初始種群集。假設初始種群個體個數為N，則初始種群集個數為3*N，對初始種群集的個體進行量化排序，選出其中名次（N+1，2N）的N個體作為初始種群，一定程度上阻止了個體極端化的產生。

2.1.3選擇算子設定

為了使個體選擇相對均勻，采用一種新的選擇機制，具體操作如下：首先將種群中個體的按照適應度值的大小進行降序排列，如果兩個個體的適應度值大小相同則順序任意。對排序好的N個體按照1，2，…，N的方式對排名第一的個體到排名最后的個體進行編號。該編號作為個體新的適應度值。則個體m被選擇的概率是：

2.1.4融合鏈路狀態算法的交叉算子

遺傳算法中起核心作用的是交叉算子，但單點交叉、多點交叉等交叉算子只是簡單地將父代的基因進行重新排列產生兩個新的子代，在豐富種群多樣性的同時無法保證子代的表現型一定要優于父代，因此會造成慢收斂的現象產生。

鏈路狀態算法則是是每個參與鏈路狀態選路的路由器都具有一份完整的全網拓撲結構圖，通過拓撲圖可以得出與本節點距離最近的下一件點的位置，從而求出最短路徑。但該算法要求節點必須有完整的網絡拓撲信息，因而造成計算工作量巨大。本文將鏈路狀態算法強大的尋優能力融入遺傳算法的交叉算子中，在彌補二者不足的同時也加快了收斂速度。設一個7座城市的距離矩陣如表1所示，父代個體A和B分別為（6574231）和（1372456），具體做法如下：

表1　7座城市的距離矩陣

步驟1：隨機選取一個交叉點的值為i作為子代a的第一位基因值，即a1=i；

步驟2：對父代A和B進行遍歷，找到基因值為i的位置，假設父代A所在基因序列中的位置為m，父代B中為n，即Am=Bn=i；

步驟3：向右依次找到位于父代A和B中交叉點的下一個基因位置，比較d（Am，Am+1）和d（Bn，Bn+1）的大小；

步驟4：根據鏈路狀態算法中求最短路徑的方法求出子代a的第二位基因值，如果d（Am，Am+1）≤d（Bn，Bn+1），則a2=Am+1，如果d（Am，Am+1）＞d（Bn，Bn+1），則a2=Bn+1；

步驟5：假設現已確定a2=Am+1，把a2作為交叉點，重復步驟1到5，得到子代a；

步驟6：隨機選取一個交叉點的值為j（j≠i）作為子代b的第一位基因值，重復步驟1到5得到子代b。

由已知父代A和父代B的基因型，根據表1的距離矩陣表由公式（1）求得相應的表現型為：F（A）=10+24+21+18+16+ 14=103，F（B）=14+17+31+18+23+10=113。

隨機選擇交叉點為1按照上述步驟求得子代a的基因型為（1374256），其表現型為：F（a）=14+17+21+18+11+10=91，不難發現其子代表現型優于父代，加快了種群的收斂速度。

在該方法中鏈路狀態算法的整個搜索空間有原來的整個網絡拓撲結構縮減為現在的兩個父代個體，極大簡化了每個城市需要存儲的信息量，同時通過交叉算子的實現使整個遺傳算法朝著最優解的方向發展。

2.1.5基于基因值倒位的變異算子

變異算子在整個遺傳算法中的作用是改變某些個體的基因值，豐富種群的多樣性，防止未成熟收斂的出現。本文基于此目的提出了一種基于基因值倒位的變異算子。規定城市數為n，首先在1～n之間隨機選擇一個數q作為變異點，其次找到基因值為n+1_q的基因，將該基因與之前基因值為q的基因位置交換即完成變異操作。對于上述子代a而言，如果變異點為1，則變異后a′的基因型為（7314256），相應的表現型為F（a′）=17+14+19+18+11+10=89。

該操作僅能極大豐富種群的多樣性，而且也有效避免了在實數編碼環境下，對于單一基因值進行變異后造成基因值重復的情況。

2.1.6改進自適應概率的設定

從群體整個進化過程看，在算法初期，由于隨機生成，適應度值相對離散，這時交叉概率應相對較高以便產生新的個體。在算法中后期，由于適應度值逐漸趨于穩定，最優解也逐漸收斂，這時應該降低交叉概率，以保證最優解不會被破壞?；诖四康谋疚脑O計的與進化代數相關的自適應概率，其中交叉概率如下：

式中n表示最大迭代次數，x表示進化代數，α∈（0，1］，一般為0.5。fmax為當前種群最大適應度值，favg為當前種群平均適應度值，f′為參與交叉操作的父代個體中較大的適應度值。

變異概率如下：

式中β∈（0，1］，一般為0.01，f為參與變異的個體適應度值。

2.2算法步驟

算法具體步驟如下：

步驟1：隨機產生規模為初始種群3倍的隨機種群，通過量化排序選出初始種群；

步驟2：通過公式（1）計算種群中每個個體的適應度函數值；

步驟3：由公式（5）計算種群中每個個體被選擇的概率，并借助輪盤賭的選擇機制選出相應的個體；

步驟4：對選出的個體進行交叉操作，交叉算子采用基于改進的鏈路狀態算法，保證了算法收斂性的同時提高了算法效率；

步驟5：采用基于基因值倒位的變異算子對個體進行變異操作，交叉和變異操作通過自適應概率對個體進行控制，保證優質個體進入下一代；

步驟6：產生新一代種群，通過終止條件判斷算法是否終止，如果終止則轉入步驟7；反之，則轉入步驟2。

步驟7：輸出最短路徑值。

流程圖如圖1所示。

改進后的遺傳算法流程圖如圖1所示，首先通過對初始種群進行量化排序選出初始種群，利用公式計算每個個體被選擇的概率進行選擇操作。然后通過改進的交叉算子對個體進行交叉操作。利用鏈路狀態算法強大的尋優能力很好地保障了算法那的收斂性。利用基于基因值的倒位算子，極大地豐富了多樣性，破壞了遺傳算法容易陷入局部最優解的局限性，更好地得到了理想值。

圖1　GBLSA算法流程圖

3　仿真驗證與性能分析

為了更好的證明算法可行性和高效性，文中選用國際上通用的TSP測試庫中的多個實例來對算法進行檢驗。

實驗中的參數設置為：最大遺傳代數G=200，種群大小popsize=50，交叉概率Pc和變異概率Pm有自適應概率得出。

使用GBLSA算法那和傳統遺傳算法對TSPLIB中的實例ei176、o1iver30、rat99和rand75進行仿真，經過10測試后算得的最優路徑值與TSPLIB提供的最優路徑值進行比較，對比情況見表2。

上述實例ei176、o1iver30、rat99和rand75經本算法仿真后所得的最優路徑圖如圖2～5所示。

從表2中的實驗數據可以看出經過GBLSA算法仿真所得出的最優路徑值均優于TSPLIB所提供的最優路徑值，這也得益于改進后的交叉算子強大的尋優能力，加上改進的自適應概率，使得能在短時間內尋找到最短路徑值。

表2　改進遺傳算法、傳統遺傳算法與TSPLIB提供最優路徑值比較表

圖2　實例ei176通過GBLSA得到的最優路徑圖

圖3　實例o1iver30通過GBLSA得到的最優路徑圖

圖4　實例rat99通過GBLSA得到的最優路徑圖

圖5　實例rand75通過GBLSA得到的最優路徑圖

4　結束語

通過對遺傳算法和鏈路狀態算法進行了改進，將兩種算法結合到一起，取長補短，形成了一種基于鏈路狀態算法的改進遺傳算法那（GBLSA）。該算法對遺傳算法中起關鍵作用的交叉算子改進明顯，引入鏈路狀態算法中最短路徑優先的原則來產生子代個體，大都提升了算法的收斂速度；對選擇算則進行概率的重新定義，加大了優質個體存活率；提出基于基因值倒位的變異算子豐富了種群的多樣性。經試驗證明GBLSA算法的高效性，能更快更好地找到最優解，有效地結局了傳統遺傳算法中易早熟、收斂慢、耗時長等問題。

同時本文也存在一些問題。改進自適應概率中參數的選擇，以及在城市數目過大的情況下該算法的效率是否與小規模下的效率同樣優秀，這些問題都是值得未來進一步研究的。

［1］Sun H.A Genetic A1gorithm for Trave11ing Sa1esman Prob-1ems［J］.Journa1 of Southwest Jiaotong University，2011（2）：25.

［2］孫力娟，王良俊，王汝傳.改進的蟻群算法及其在TSP中的應用研究［J］.通信學報，2004，25（10）：111_116.

［3］周永權，黃正新，劉洪霞.求解TSP問題的離散型螢火蟲群優化算法［J］.電子學報，2012，40（6）：1164_1170.

［4］王銀年，葛洪偉.求解TSP問題的改進模擬退火遺傳算法［J］.計算機工程與應用，2010（46）：44_47.

［5］Min H，Dazhi P，Song Y.An improved hybrid ant co1ony a1-gorithm and its app1ication in so1ving TSP［C］//Information Techno1ogy and Artificia1 Inte11igence Conference（ITAIC），2014：423_427.

［6］Ye C，Yang Z，Yan T.An efficient and sca1ab1e a1g_orithm for thetrave1ingsa1esmanprob1em［C］//20145thIEEE Internationa1ConferenceonSoftwareEngineeringand Service Science（ICSESS），2014：335_339.

［7］羅勇，陳治亞.基于改進遺傳算法的物流配送路徑優化［J］.系統工程，2012（8）：118_122.

ZHANG Li_hua1，2，LIAO Wen_jian2，PENG Yan_bing2
（1.Wuhan Research Institute of Posts and Telecommunications，Wuhan 430074，China；2.FiberHome Telecommunication Technologies Co.，Ltd.Nanjing 210019，China）

the traditiona1 genetic a1gorithm exists the disadvantage of premature and easy to fa11 into a 1oca1 optimum，so it has 1ow convergence and 1ow efficiency.To address this prob1em，we propose an improved genetic a1gorithm GBLSA（Genetic Based on Link_State A1gorithm）.We improve the basic operation of genetic a1gorit_hm，the main method is making fu11 use of the abi1ity of 1ink_state a1gorithm for g1oba1 optimization of popu1ati_ons into cross_operation，aiming at improving the individua1 generation by generation.Introducing adaptive prob_abi1ity to further improve the searching efficiency and the speed of convergence.The experiment suggested that，GBLSA has better resu1ts and higher efficiency in comparison with traditiona1 genetic a1gorithm and the resu1ts of TSPLIB.

routing optimization；genetic a1gorithm；1ink_state a1gorithm；adaptive probabi1ity

TP301.6

A

1674_6236（2016）10_0013_04

2015_06_09稿件編號：201506089

國家863計劃資助項目（2012AA013002）

張禮華（1989—），男，湖北武漢人，碩士。研究方向：互聯網技術。

Research on lmProVed genetlc algorlthm for solVlng oPtlmlzatlon of loglstlcs dlstrlbutlon route