改進(jìn)的遺傳算法在物流配送中的應(yīng)用

[摘 要] 我們在物流配送系統(tǒng)的研究中，對物流配送的數(shù)學(xué)模型以及所采用的算法進(jìn)行了深入的探討，并取得了一定的成果。遺傳算法的改進(jìn)，一定程度上避免了早熟現(xiàn)象的發(fā)生，提高了遺傳算法用于求解物流配送問題的效率。

[關(guān)鍵詞] 物流配送 遺傳算法 早熟 種群

物流配送是指按客戶的訂貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)送達(dá)客戶手中。目前我國大部分物流配送企業(yè)，仍依賴人工經(jīng)驗(yàn)采用人工安排的方式，從而導(dǎo)致企業(yè)運(yùn)輸資源無法充分利用，增加了企業(yè)的運(yùn)行成本或者根本無法滿足客戶的要求，從而限制了物流配送企業(yè)的進(jìn)一步發(fā)展。對物流配送優(yōu)化問題進(jìn)行深入研究，建立即時(shí)反映客戶需求的自動(dòng)化車輛調(diào)度及路線安排系統(tǒng)，是提升服務(wù)質(zhì)量、提高資源利用率、降低企業(yè)成本的重要課題。

對一個(gè)大型配送中心來講，客戶數(shù)量往往很多，要精確計(jì)算最優(yōu)配送路徑是一件非常困難的事，現(xiàn)在有人利用遺傳算法來求解配送路徑優(yōu)化問題，已經(jīng)取得了一些研究成果，但實(shí)際應(yīng)用卻不是十分的理想，究其原因，主要是由于傳統(tǒng)的遺傳算法，存在著局部搜索能力不強(qiáng)，容易出現(xiàn)早熟而造成的。為了提高遺傳算法的搜索能力，避免在算法進(jìn)化的早期出現(xiàn)收斂，文章對傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，經(jīng)大量的實(shí)驗(yàn)表明:改進(jìn)的遺傳算法較傳統(tǒng)的遺傳算法在物流配送優(yōu)化中，求解效率有了非常明顯的提高，完全能適應(yīng)網(wǎng)絡(luò)配送的要求。

一、數(shù)學(xué)模型

設(shè)配送中心有m臺相同的配送車輛要向n個(gè)客戶配送貨物，客戶i到客戶j的距離為dij，客戶i到配送中心的距離為di0，客戶i的需求量為qi，車輛的最大載重量為Z，最大行駛距離為D，最大裝載體積為V，成本為C0+kx(其中x為距離），按費(fèi)用最低為優(yōu)化目標(biāo)，其數(shù)學(xué)模型為：。

約束條件:(1)每臺配送車輛的最大行駛距離不能超過D;(2)每臺配送車輛的最大裝載體積不能超過V;(3)配送車輛總數(shù)不能超過m。

二、改進(jìn)的遺傳算法

1.遺傳算法

將每個(gè)客戶按十進(jìn)制從1到n進(jìn)行編號，隨機(jī)對換編號的位置，組成初始群體，計(jì)算適應(yīng)度時(shí)，需要在編碼的開始和結(jié)束位置插入0，并在編碼之間按車輛的載重量插入若干0，其中0表示配送中心。遺傳運(yùn)算分別采用聯(lián)賽選擇，循環(huán)交叉(CX)和對換變異。

2.遺傳算法的改進(jìn)

定義1:進(jìn)化的初期，算法的主要任務(wù)是全局尋優(yōu)，稱這個(gè)時(shí)期為尋優(yōu)期。進(jìn)化的后期，算法的主要任務(wù)是局部收斂，稱這個(gè)時(shí)期為收斂期。尋優(yōu)期一般為總進(jìn)化代數(shù)的三分之二，收斂期一般為總進(jìn)化代數(shù)的三分之一。

定義2:設(shè)個(gè)體A=X1，X2，…，Xn-1，Xn，稱A’=Xn，Xn-1，…，X2，X1為A的逆序。

改進(jìn)的遺傳算法在尋優(yōu)期采用較大的交叉和變異概率，在收斂期采用較小的交叉和變異概率。由于交叉和變異概率只與遺傳代數(shù)有關(guān)，因此不會影響算法的效率，同時(shí)也能較好的抑制早熟現(xiàn)象的發(fā)生。

交叉運(yùn)算前，先要對種群兩兩配對，如果將兩個(gè)相同的個(gè)體進(jìn)行配對，那么交叉運(yùn)算就失去了作用。改進(jìn)的遺傳算法為了避免這種情況的發(fā)生，先對種群進(jìn)行試配對，若在某次試配中，經(jīng)幾次試配對均不成功，可重新產(chǎn)生一個(gè)新個(gè)體，從新個(gè)體以及新個(gè)體的逆序中選擇一個(gè)適應(yīng)度高的個(gè)體來替代其中的一個(gè)個(gè)體，這樣可以保證每對個(gè)體它們的基因物質(zhì)不會完全相同。

出現(xiàn)早熟的原因往往是由于種群中出現(xiàn)了某些超級個(gè)體，隨著模擬生物演化過程的進(jìn)行，這些超級個(gè)體的基因物質(zhì)很快占據(jù)了種群的統(tǒng)治地位，導(dǎo)致種群中由于缺乏新鮮的基因物質(zhì)而不能找到全局最優(yōu)值。改進(jìn)的遺傳算法在進(jìn)化的過程中不斷用一些新鮮的個(gè)體來替代適應(yīng)度低的個(gè)體，使得種群中始終含有新鮮的基因物質(zhì)，不至于算法過早收斂，每個(gè)新個(gè)體可從隨機(jī)產(chǎn)生的個(gè)體及它的逆序中選擇一個(gè)適應(yīng)度高的個(gè)體。在尋優(yōu)期增加的新個(gè)體的數(shù)量可適當(dāng)多些（一般為種群的20%左右)，促使算法盡快收斂，在收斂期加入的新個(gè)體的數(shù)量可適當(dāng)少些(一般為種群的5%左右）或不再增加新個(gè)體。

三、仿真實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)來自文獻(xiàn)的實(shí)例2，變異概率為0.01，交叉概率為0.8，初始群體規(guī)模為80，總進(jìn)化代數(shù)為200，共進(jìn)行了100次實(shí)驗(yàn)。

從表中可以看到，改進(jìn)的遺傳算法，在不降低速度的前提下，每次實(shí)驗(yàn)基本都可以求出優(yōu)秀解，說明經(jīng)改進(jìn)的遺傳算法對物流配送問題的求解能力有了很大程度的提高。

四、結(jié)束語

遺傳算法作為一種優(yōu)化算法有著廣泛應(yīng)用前景，但同時(shí)也存在著很多有待解決的問題。文章針對傳統(tǒng)的遺傳算法提出的幾項(xiàng)改進(jìn)措施，一定程度上克服了早熟現(xiàn)象，增強(qiáng)了對物流配送問題的求解能力。文章作為基本遺傳算法的改進(jìn)設(shè)計(jì)，他的優(yōu)劣性還需要在實(shí)踐中進(jìn)一步的檢驗(yàn)。

參考文獻(xiàn):

[1]閻 慶 鮑遠(yuǎn)律:新型遺傳模擬退火算法求解物流配送路徑問題[J].計(jì)算機(jī)應(yīng)用， 2004，24(S1) 261～263

[2]郎茂祥 胡思繼:用混和遺傳算法求解物流配送路徑優(yōu)化問題的研究[J].中國管理科學(xué)，2002，10(5).51～56

[3]陳國良 王熙法等:遺傳算法及其應(yīng)用[M].北京:人民郵電出版社，2001年2月76～143

[4]何 信:多目標(biāo)物流配送路經(jīng)優(yōu)化聚類-遺傳混合算法[J].商場現(xiàn)代化，2006 8(上旬刊)總第475期120～121

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”