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

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

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

中圖分類(lèi)號(hào)：F25文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1673-291X（2011）04-0199-02

引言

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

一、研究背景

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

二、遺傳算法

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

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

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

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

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

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

三、問(wèn)題描述

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

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

表1 各需求點(diǎn)對(duì)貨物需求量 單位：噸

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

四、算法改進(jìn)

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

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

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

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

參考文獻(xiàn)：

[1]張遠(yuǎn)昌.物流運(yùn)輸與配送管理[M].北京:中國(guó)紡織出版社，2004.

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

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

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

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

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

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

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

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