張禮華，廖聞劍，彭艷兵

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

求解物流路徑優(yōu)化的改進遺傳算法研究

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

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

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

路徑優(yōu)化；遺傳算法；鏈路狀態(tài)算法；自適應(yīng)概率

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

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

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

1　數(shù)學(xué)模型的建立

1.1路徑優(yōu)化問題模型

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

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

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

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

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

1.2遺傳算法簡介

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

約束條件為：

其中U是V的非空子集。

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

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

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

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

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

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

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

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

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

2　算法設(shè)計及改進

2.1算法設(shè)計

2.1.1編碼的選擇和適應(yīng)度函數(shù)的確定

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

適應(yīng)度函數(shù)是評判一個個體好壞的標(biāo)準(zhǔn)。取fitness（X）= 1/F（X），由公式可求得個體X的路徑值F（X）。

2.1.2初始群體的選取

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

2.1.3選擇算子設(shè)定

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

2.1.4融合鏈路狀態(tài)算法的交叉算子

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

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

表1　7座城市的距離矩陣

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

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

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

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

步驟5：假設(shè)現(xiàn)已確定a2=Am+1，把a2作為交叉點，重復(fù)步驟1到5，得到子代a；

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

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

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

在該方法中鏈路狀態(tài)算法的整個搜索空間有原來的整個網(wǎng)絡(luò)拓撲結(jié)構(gòu)縮減為現(xiàn)在的兩個父代個體，極大簡化了每個城市需要存儲的信息量，同時通過交叉算子的實現(xiàn)使整個遺傳算法朝著最優(yōu)解的方向發(fā)展。

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

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

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

2.1.6改進自適應(yīng)概率的設(shè)定

從群體整個進化過程看，在算法初期，由于隨機生成，適應(yīng)度值相對離散，這時交叉概率應(yīng)相對較高以便產(chǎn)生新的個體。在算法中后期，由于適應(yīng)度值逐漸趨于穩(wěn)定，最優(yōu)解也逐漸收斂，這時應(yīng)該降低交叉概率，以保證最優(yōu)解不會被破壞。基于此目的本文設(shè)計的與進化代數(shù)相關(guān)的自適應(yīng)概率，其中交叉概率如下：

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

變異概率如下：

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

2.2算法步驟

算法具體步驟如下：

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

步驟2：通過公式（1）計算種群中每個個體的適應(yīng)度函數(shù)值；

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

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

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

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

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

流程圖如圖1所示。

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

圖1　GBLSA算法流程圖

3　仿真驗證與性能分析

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

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

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

上述實例ei176、o1iver30、rat99和rand75經(jīng)本算法仿真后所得的最優(yōu)路徑圖如圖2～5所示。

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

表2　改進遺傳算法、傳統(tǒng)遺傳算法與TSPLIB提供最優(yōu)路徑值比較表

圖2　實例ei176通過GBLSA得到的最優(yōu)路徑圖

圖3　實例o1iver30通過GBLSA得到的最優(yōu)路徑圖

圖4　實例rat99通過GBLSA得到的最優(yōu)路徑圖

圖5　實例rand75通過GBLSA得到的最優(yōu)路徑圖

4　結(jié)束語

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

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

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

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

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

［4］王銀年，葛洪偉.求解TSP問題的改進模擬退火遺傳算法［J］.計算機工程與應(yīng)用，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］羅勇，陳治亞.基于改進遺傳算法的物流配送路徑優(yōu)化［J］.系統(tǒng)工程，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—），男，湖北武漢人，碩士。研究方向：互聯(lián)網(wǎng)技術(shù)。

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