遺傳算法基于路徑優化問題應用的改進探索研究

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

關鍵詞：路徑優化；遺傳算法；禁忌搜索算法

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

引言

隨著經濟快速發展、信息化時代的來臨，尤其是網絡購物等新型購物方式的發展壯大使得物流業迅速成為人們日常所不可缺少的行業。與此同時物流業之間的競爭也迅速加劇。而物流業也與其他服務業一樣除了服務質量的競爭以外關鍵在于成本的競爭。物流企業成本絕大部分在于運輸過程中產生，有效地路徑優化能夠幫助物流企業很好的解決成本節約問題。從而遺傳算法等高效簡潔的優化算法成為人們越來越關注的對象。

一、研究背景

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

二、遺傳算法

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

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

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

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

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

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

三、問題描述

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

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

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

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

四、算法改進

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

為了避免上述缺點，本文提出一種新的雙層染色體編碼方案Double Layers Chromos Coding Shema，DLCCS）。標準遺傳算法中染色體是單層的。而在DLCCS中，染色體是兩層的，其構成為：第一層是n維向量L1，代表n個客戶的一種排列。第二層是一個維數可變的向量L2，在L2中存放的元素代表每輛車所服務的第一個客戶在Ll中的順序號，需根據車輛的能力限制計算得出。以上節的例為例，用自然數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開始，這便于編程實現，因為在很多編程語言中，都將數組的起始編號設為0。（2）繼續讓0號車服務后面的客戶，直到超出車輛的能力約束，在本例中，0號車可以服務前5個客戶，到第6個客戶，由于違反車輛的能力約束，需派出1號車（第二輛車）。1號車所服務的第一個客戶為客戶6，其在Ll中的順序號為5，將其加入LZ，第二層染色體變成L2（0，5）。（3）繼續應用步驟2，直到所有的客戶都得到服務為止。

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

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

參考文獻：

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

[2]榮耀華.傳統物流與現代物流[M].北京:中國物資出版社，2007.

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

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

[5]王凌.智能優化算法及其應用[M].北京:清華大學出版社，施普林格出版社，2001.

[6]邢文訓，謝金星，等.現代優化計算方法:第2版[M].北京:清華大學出版社，2005.

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

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

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