遺傳算法基于路徑優(yōu)化問題應(yīng)用的改進探索研究

摘要：遺傳算法是一種應(yīng)用很廣泛的智能優(yōu)化算法，對遺傳算法進行了分析研究，針對遺傳算法的一些缺陷提出了相應(yīng)的改進方法。在上述研究基礎(chǔ)上，基于遺傳算法，研究了物流系統(tǒng)中的庫存優(yōu)化問題及車輛路徑問題。將車輛路徑問題看做是組合優(yōu)化問題，并應(yīng)用遺傳算法進行求解。

關(guān)鍵詞：路徑優(yōu)化；遺傳算法；禁忌搜索算法

中圖分類號：F25文獻標志碼：A文章編號：1673-291X（2011）04-0199-02

引言

隨著經(jīng)濟快速發(fā)展、信息化時代的來臨，尤其是網(wǎng)絡(luò)購物等新型購物方式的發(fā)展壯大使得物流業(yè)迅速成為人們?nèi)粘Ｋ豢扇鄙俚男袠I(yè)。與此同時物流業(yè)之間的競爭也迅速加劇。而物流業(yè)也與其他服務(wù)業(yè)一樣除了服務(wù)質(zhì)量的競爭以外關(guān)鍵在于成本的競爭。物流企業(yè)成本絕大部分在于運輸過程中產(chǎn)生，有效地路徑優(yōu)化能夠幫助物流企業(yè)很好的解決成本節(jié)約問題。從而遺傳算法等高效簡潔的優(yōu)化算法成為人們越來越關(guān)注的對象。

一、研究背景

近年來，隨著人工智能應(yīng)用領(lǐng)域的不斷擴大，傳統(tǒng)的基于符號處理的人工智能方法在知識表示、信息處理和解決組合爆炸等方面遇到的困難越來越明顯，從而使得尋求一種適合于大規(guī)模問題并具有自組織、自適應(yīng)、自學(xué)習(xí)能力的算法成為有關(guān)學(xué)科的一個研究目標。遺傳算法（genetic algorithms，簡稱GA）是J.Holland與1975年提出的。GA是基于“適者生存”的一種高度并行、隨機和自適應(yīng)的優(yōu)化算法，它將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷進化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解或滿意解。

二、遺傳算法

GA是一種通用的優(yōu)化算法，其編碼技術(shù)和遺傳操作比較簡單，優(yōu)化不受限制性條件的約束，其兩個顯著性特點是隱含并行性和全局解空間搜索。它是一類隨機優(yōu)化算法，但它不是簡單的隨機比較搜索，而是通過對染色體的評價和對染色體中基因的作用，有效地利用已有信息來指導(dǎo)搜索有希望改善優(yōu)化質(zhì)量的狀態(tài)。

遺傳算法主要借鑒了生物進化的一些特征，它的主要生物進化特征體現(xiàn)在：（1）進化發(fā)生在解的編碼上。這些編碼用生物術(shù)語稱為染色體。由于一開始要進行編碼，優(yōu)化問題的一切性質(zhì)都通過編碼來研究。編碼和解碼是遺傳算法的一個主題。（2）自然選擇規(guī)律決定哪些染色體產(chǎn)生超過平均數(shù)的后代。而在遺傳算法中，通過優(yōu)化問題的目標而人為地構(gòu)造適應(yīng)函數(shù)以達到好的染色體產(chǎn)生超過平均數(shù)的后代。（3）當染色體結(jié)合時，雙親的遺傳基因結(jié)合使得子女保持有父母的特征。（4）染色體結(jié)合以后，隨機的變異會造成子代與父代產(chǎn)生不同的特征。

遺傳算法主要包含以下處理步驟：第一是對優(yōu)化問題的解編碼。此外，稱一個解的編碼為一個染色體，組成編碼的元素成為基因。編碼的目的主要是用于優(yōu)化問題的表現(xiàn)形式和利于之后遺傳算法中的計算。第二是適應(yīng)函數(shù)的構(gòu)造和應(yīng)用。適應(yīng)函數(shù)基本上依據(jù)優(yōu)化問題的目標函數(shù)而定。適應(yīng)函數(shù)確定以后，自然選擇規(guī)律是以適應(yīng)函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰。生存下來的染色體就組成了一個種群，形成一個可以繁衍下一代的種群。第三是染色體的結(jié)合。雙親的遺傳基因之間的結(jié)合是通過編碼之間的交配（crossover）達到下一代的產(chǎn)生。

遺傳算法作為一個全局性優(yōu)化算法具有很大的優(yōu)越性，具體體現(xiàn)在：（1）遺傳算法適合求解那些帶有多參數(shù)、多變量、多目標和在多區(qū)域但連通性較差的NP難（非多項式確定性問題）優(yōu)化問題。對多參數(shù)、多變量的NP難優(yōu)化問題，通過解析求解或計算求最優(yōu)解的可能性很小，主要依賴于數(shù)值求解。遺傳算法就是一種數(shù)值求解的算法，具有普遍性并且對目標函數(shù)的性質(zhì)幾乎沒有要求，并且它可以一次記錄多個解。（2）遺傳算法在求解很多組合優(yōu)化問題時，不需要有很強的技巧和對問題有非常深入的了解。如路線調(diào)度問題、排序等。遺傳算法再給這些問題的決策變量編碼后，起計算過程是比較簡單的，并且可以較快的得到一個滿意解。（3）遺傳算法同求解問題的其他啟發(fā)式算法有較好的兼容性。

當然遺傳算法也不可避免地存在著它的不足之處：（1）存在編碼不規(guī)范及表示不準確等問題。（2）單一的遺傳編碼不能全面地將優(yōu)化問題的約束表示出來。（3）大量研究也表明，GA存在早熟、算法參數(shù)敏感等缺點，取得良好的性能需要依賴較大的種群并對算法進行精心設(shè)計。

采用遺傳算法等智能優(yōu)化算法來求解帶能力約束的車輛路徑問題 （Capacitated Vehicle Routing Problem，即CVRP），一般能在較短的計算時間內(nèi)獲得質(zhì)量較高的近似解。

三、問題描述

CVRP可描述如下:配送中心有m輛貨車，每輛車的能力為q；配送中心需為n個客戶提供貨物配送任務(wù)，每個客戶的需求量為gi（i=1，2，…，n），gi

有1個配送中心和8個商店，商店0表示配送中心，配送中心有兩輛載重量為8噸的貨車，要求合理安排車輛行駛路徑，使總運輸距離最小。商店之間的相互距離及各商店的商品需求量（見表1、表2）：

表1 各需求點對貨物需求量 單位：噸

表2配送中心與各需求點之間的距離單位：KM

四、算法改進

在現(xiàn)有遺傳算法中，個體的染色體編碼還需要用到最優(yōu)車輛數(shù)。這兩種編碼方案有三個缺點:（1）由于染色體維數(shù)變長，使組合空間變大，從而降低了搜索到最優(yōu)解的幾率。（2）由染色體解碼后獲得的子路徑有可能不滿足車輛的能力約束。（3）需要預(yù)先知道最優(yōu)解所需車輛數(shù)。

為了避免上述缺點，本文提出一種新的雙層染色體編碼方案Double Layers Chromos Coding Shema，DLCCS）。標準遺傳算法中染色體是單層的。而在DLCCS中，染色體是兩層的，其構(gòu)成為：第一層是n維向量L1，代表n個客戶的一種排列。第二層是一個維數(shù)可變的向量L2，在L2中存放的元素代表每輛車所服務(wù)的第一個客戶在Ll中的順序號，需根據(jù)車輛的能力限制計算得出。以上節(jié)的例為例，用自然數(shù)1～8代表8個客戶，其需求量分別為（1，2，1，2，1，4，2，2），車輛的能力約束為8個單位。假定某個體的第一層染色體為L1（4，l，3，7，2，6，5，8），第二層染色體的計算過程如下:（1）第一輛車編為0號車，其第一個客戶為客戶4，在L1中的順序號為0，因此第二層染色體暫時為LZ（0）。編號順序都從0開始，這便于編程實現(xiàn)，因為在很多編程語言中，都將數(shù)組的起始編號設(shè)為0。（2）繼續(xù)讓0號車服務(wù)后面的客戶，直到超出車輛的能力約束，在本例中，0號車可以服務(wù)前5個客戶，到第6個客戶，由于違反車輛的能力約束，需派出1號車（第二輛車）。1號車所服務(wù)的第一個客戶為客戶6，其在Ll中的順序號為5，將其加入LZ，第二層染色體變成L2（0，5）。（3）繼續(xù)應(yīng)用步驟2，直到所有的客戶都得到服務(wù)為止。

設(shè)置遺傳算法的種群規(guī)模為60，交叉概率為0.8，變異概率為0.05。在計算機上用MATLAB優(yōu)化軟件求得標準遺傳算法與改進后的遺傳算法結(jié)果（如表3所示）。

由表3可以看出，改進后的遺傳算法比標準的遺傳算法收斂性要好得多，并且在運算速度以及占用內(nèi)存方面也有很大優(yōu)勢。

參考文獻：

[1]張遠昌.物流運輸與配送管理[M].北京:中國紡織出版社，2004.

[2]榮耀華.傳統(tǒng)物流與現(xiàn)代物流[M].北京:中國物資出版社，2007.

[3]葉耀華，陳霖，朱曉梅.一種帶時間窗口和在前約束的車輛路線問題及其算法[J].系統(tǒng)工程理論與實踐，2000，(3).

[4]程世平.物流管理[M].合肥:合肥工業(yè)大學(xué)出版社，2007.

[5]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社，施普林格出版社，2001.

[6]邢文訓(xùn)，謝金星，等.現(xiàn)代優(yōu)化計算方法:第2版[M].北京:清華大學(xué)出版社，2005.

[7]Dantizg G，Ramser J.The truck dispatching problem，Management Science，1959，(6):80-91.

[8]李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社，2001:11.

[9]Holland J H.Adaption in natural and artificial systems.MIT Press，1975.[責(zé)任編輯 安世友]