改進(jìn)遺傳算法在應(yīng)急物資調(diào)運(yùn)模型中的應(yīng)用

1、改進(jìn)遺傳算法在應(yīng)急物資調(diào)運(yùn)模型中的應(yīng)用-科技創(chuàng)新論文改進(jìn)遺傳算法在應(yīng)急物資調(diào)運(yùn)模型中的應(yīng)用 宋樹(shù)洋 （北京航空航天大學(xué)經(jīng)濟(jì)管理學(xué)院，中國(guó) 北京 100000） 【摘要】在考慮了應(yīng)急物資調(diào)運(yùn)的特殊性后，改進(jìn)了VRP問(wèn)題求解的遺傳算法，并將其應(yīng)用于應(yīng)急物資調(diào)運(yùn)問(wèn)題的求解。通過(guò)仿真計(jì)算表明改進(jìn)后的算法在收斂速度等方面有很大改善。 關(guān)鍵詞遺傳算法；應(yīng)急物流；VRP 應(yīng)急物資的運(yùn)輸與配送問(wèn)題是應(yīng)急物流主要研究的問(wèn)題之一，它也是應(yīng)急物流中最為關(guān)鍵的一個(gè)環(huán)節(jié)，而在一般情況下，應(yīng)急物資調(diào)運(yùn)問(wèn)題就會(huì)轉(zhuǎn)化成一般的車(chē)輛路徑問(wèn)題。車(chē)輛路徑問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，求解十分困難，截至當(dāng)下，僅有一些相對(duì)較小規(guī)模的問(wèn)題

2、能夠保證被求解到精確的最優(yōu)解。各國(guó)的學(xué)者通過(guò)大量的實(shí)踐和理論證明得出結(jié)論，精確算法在求解大規(guī)模VRP問(wèn)題時(shí)非常不適合，而啟發(fā)式算法在求解這類(lèi)問(wèn)題時(shí)顯示出非常大的優(yōu)勢(shì)，并成為近年來(lái)此領(lǐng)域應(yīng)用最多的方法。其中遺傳算法以其優(yōu)秀的尋優(yōu)能力為眾多學(xué)者所青睞。 1遺傳算法 遺傳算法(Genetic Algorithm，簡(jiǎn)稱(chēng)GA) 是由Holland教授首先提出的，它是一種建立在群體遺傳學(xué)基礎(chǔ)和自然選擇上的隨機(jī)、并行搜索算法。求解車(chē)輛調(diào)度問(wèn)題，使用GA搜索算法十分理想，但使用GA算法時(shí)面臨的一個(gè)難以解決的問(wèn)題就是如何防止其“早熟”收斂。 在遺傳算法提出以來(lái)，來(lái)自世界各地的眾多學(xué)者提出了多種方法提高GA的性能

3、：Rudolhp G 提出為保證算法的收斂性，使用精英選擇策略保持群體中最好個(gè)體的方法1；馬欣等提出了PEGA算法，即使用單親進(jìn)化的遺傳算法，它提高算法收斂速度的方法，是利用來(lái)自父體有效邊的信息，保留使用最小邊，這樣來(lái)進(jìn)行個(gè)體的進(jìn)化2；馬均水等提出大變異策略，這個(gè)策略可以表述為，如果某一代里的大多數(shù)個(gè)體集中在了一起，此時(shí)使用一個(gè)較大的變異概率（遠(yuǎn)大于通常）執(zhí)行一次變異操作，這樣使之獨(dú)立產(chǎn)生多個(gè)新個(gè)體，可以讓整個(gè)群體脫離早熟3；以上方法只解決了算法部分問(wèn)題，而且采取的改進(jìn)方式比較復(fù)雜，一般以高運(yùn)算量并降低算法效率為代價(jià)解決遺傳算法過(guò)早收斂的問(wèn)題。 遺傳算法優(yōu)化分析： 早熟收斂一直是遺傳算法中存在

4、的主要問(wèn)題，算法一旦出現(xiàn)早熟收斂，將無(wú)法得到問(wèn)題的最優(yōu)解，這個(gè)問(wèn)題主要原因是遺傳算法自身的優(yōu)化能力有限，不得不需要多次迭代才能夠找到最優(yōu)解，迭代過(guò)程中發(fā)生早熟將很難跳出。本文主要研究如何避免早熟收斂問(wèn)題，下面將在交叉概率一定的(pc=0.8)的前提下進(jìn)行研究討論。 1）變異算子的改進(jìn) 對(duì)于遺傳算法易“早熟”的問(wèn)題，其中主要原因之一是遺傳算法中最重要的遺傳算子交叉算子使群體中的染色體具有局部相似性，從而會(huì)導(dǎo)致搜索停滯不前，因此變異算子的存在就變成克服算法早熟的最有效手段。 2）傳統(tǒng)變異算子的缺陷 定義1在優(yōu)化問(wèn)題求解過(guò)程中得到的最優(yōu)解，其對(duì)應(yīng)染色體上的每個(gè)基因稱(chēng)為這個(gè)染色體基因位上的有效基因。

5、定義2種群中，染色體同一個(gè)基因位上的等位基因具有多樣性，即染色體相同的基因位上既有“1”又有“0”，或者說(shuō)在某一個(gè)基因位上，基因全為“1”(或“0”)的概率P(“1”)(或P(“0”)為： P（“0”）或（“”）（1） J.Craig Potts 等人的研究得出結(jié)論，在GA搜索中，在遺傳算法運(yùn)行過(guò)程中發(fā)生早熟收斂的原因主要是有效等位基因缺失4。選擇策略的目的是在于加快基因的收斂過(guò)程，但是交叉算子作用于個(gè)體卻不可能產(chǎn)出新的基因，所以這無(wú)法避免地會(huì)使得在特定基因位上的某一類(lèi)基因比例下降，最終會(huì)導(dǎo)致這個(gè)基因位上可能的有效基因的缺損。因此，為了預(yù)防早熟收斂，在不知道有效基因位的情形下，如果變異算子可以

6、讓染色體統(tǒng)一基因位上保持等位基因的高多樣性，那么將極大地防止有效基因的缺失，進(jìn)而在最大程度上避免遺傳算法運(yùn)行過(guò)程中的早熟收斂。 定理 一般方法使用的變異算子沒(méi)有辦法保證保持染色體同一基因位上等位基因的多樣性。 證明：在一個(gè)種群規(guī)模為N的種群中，如果假設(shè)在染色體的第j個(gè)基因位上有n1個(gè)“0”和n2(n2=N-n1)個(gè)“1”，那么這個(gè)基因位上的全部基因經(jīng)過(guò)變異操作（取反操作）后變?yōu)橥粋€(gè)基因的概率為： （2） 此式與式（1）矛盾。 ）二元變異算子 一般來(lái)說(shuō)，一般的變異算子作用是進(jìn)行的是一元操作（取反操作），即是操作數(shù)需要且僅需要一個(gè)基因。如果染色體是由二進(jìn)制字符串組成的，對(duì)于此類(lèi)染色體，我們可以在

7、遺傳算法搜索中引入數(shù)字技術(shù)里的二元邏輯算子，優(yōu)化傳統(tǒng)的變異方式，即產(chǎn)生了二元的變異算子：同或/異或。 此種變異操作與傳統(tǒng)的取反變異有所不同，這種變異操作中需要兩個(gè)個(gè)體（染色體）參與，例如： 從邏輯上容易知道，在這個(gè)運(yùn)算之后得到的兩種邏輯狀態(tài)是互補(bǔ)關(guān)系，即如果一個(gè)為“0”，另一個(gè)一定為“1”。換句話說(shuō)在一個(gè)基因位上的基因經(jīng)過(guò)變異操作之后，這個(gè)基因位上至少有一個(gè)“0”和一個(gè)“1”同時(shí)存在，但是并不會(huì)出現(xiàn)都是“0”或者都是“1”的情況。 基于二元變異算子的遺傳算法流程與原遺傳算法流程相同，只在變異操作時(shí)有所區(qū)別。 2應(yīng)急物資調(diào)度模型 2.1問(wèn)題的提出 應(yīng)急資源的調(diào)度需要考慮的問(wèn)題有很多，其中包括運(yùn)輸

8、工具的調(diào)度、運(yùn)輸路線的設(shè)計(jì)，還有資源調(diào)度的速度和效率。突發(fā)事件發(fā)生后，如果造成了大面積的受災(zāi)，救災(zāi)物資需求點(diǎn)的數(shù)量很多，那么在短時(shí)間內(nèi)制定出合理的物資配送計(jì)劃將會(huì)十分困難。 應(yīng)急資源調(diào)度問(wèn)題可以抽象為圖所示： 2.2問(wèn)題情景描述 假設(shè)中國(guó)西南部某地發(fā)生了一定強(qiáng)度的地震，地震地帶處于山地丘陵地形內(nèi)，震后造成交通線路阻斷，圍繞震中形成了幾個(gè)受災(zāi)較為嚴(yán)重的區(qū)域，區(qū)域內(nèi)交通能力恢復(fù)迅速，區(qū)域與區(qū)域之間處于半隔離狀態(tài)。處于各受災(zāi)區(qū)域的政府救助力量迅速組織人員和工具分別進(jìn)行難民的搜尋和治療，并以最快的速度恢復(fù)通信能力，與上一級(jí)政府組織取得聯(lián)系并發(fā)出求救信息。上級(jí)地震災(zāi)害救助領(lǐng)導(dǎo)組織匯集各區(qū)域需求，利用空中

9、設(shè)備(直升機(jī))將救災(zāi)物資空投至各區(qū)域，其中包括醫(yī)藥、食物、飲用水、救災(zāi)車(chē)輛及工具等具體物資，另各救災(zāi)區(qū)域內(nèi)的救災(zāi)應(yīng)急小組抓緊組織收集可利用的機(jī)動(dòng)性運(yùn)輸工具，在各區(qū)域內(nèi)形成配送中心，根據(jù)各需求點(diǎn)需求進(jìn)行救災(zāi)物資配送和傷員運(yùn)輸。 2.3模型的建立 2.3.1模型的假設(shè)條件 假設(shè)一：應(yīng)急資源調(diào)度中心與各物資需求點(diǎn)、各物資需求點(diǎn)之間的運(yùn)輸距離已知，可以作為常數(shù)。 假設(shè)二：受災(zāi)地點(diǎn)及各應(yīng)急資源調(diào)度中心根據(jù)其地理位置及交通便利情況完成最優(yōu)區(qū)域劃分，形成局部地震救災(zāi)單元，單元區(qū)域內(nèi)可以以最快速度進(jìn)行物資分配及救災(zāi)響應(yīng)。各單元地震災(zāi)區(qū)資源運(yùn)輸費(fèi)用有限可加，總和為地震總災(zāi)區(qū)資源調(diào)度費(fèi)用。 假設(shè)三：救災(zāi)物資運(yùn)送車(chē)

10、輛所在停車(chē)場(chǎng)與應(yīng)急物資調(diào)度中心之間的距離可以忽略不計(jì)。 假設(shè)四：所有的需求點(diǎn)之間都可以相互通行，即此路徑網(wǎng)絡(luò)是完全路網(wǎng)。 假設(shè)五：所有的受災(zāi)地點(diǎn)的資源需求，在時(shí)間和數(shù)量方面都能夠得到滿足。 假設(shè)六：物資從調(diào)運(yùn)車(chē)輛上卸載的時(shí)間忽略，不予計(jì)算。 2.3.2問(wèn)題的數(shù)學(xué)模型描述 應(yīng)急資源車(chē)輛調(diào)度問(wèn)題的數(shù)學(xué)模型可以概述如下：對(duì)于單一地震災(zāi)害救助單元，把各物資需求節(jié)點(diǎn)和應(yīng)急資源調(diào)度中心組成一個(gè)圖G(V,E)，其中V是圖中所有節(jié)點(diǎn)的集合，VoV是應(yīng)急資源調(diào)度中心，其余節(jié)點(diǎn)為物資需求節(jié)點(diǎn)；E為圖中所有邊的集合，eijE為節(jié)點(diǎn)i，j之間的邊，圖G為無(wú)向圖，即邊eij是無(wú)方向的。有n個(gè)受災(zāi)地向救災(zāi)指揮中心請(qǐng)求物資

11、配送，物資儲(chǔ)備中心與受災(zāi)節(jié)點(diǎn)、受災(zāi)節(jié)點(diǎn)之間的廣義運(yùn)輸費(fèi)用(距離)為Cij(i，j=0，1，2，n)，物資儲(chǔ)備中心編號(hào)為0，受災(zāi)節(jié)點(diǎn)編號(hào)為1到n，要求為各地震應(yīng)急救助區(qū)域指派運(yùn)輸車(chē)輛k，并確定車(chē)輛運(yùn)輸路線，使得總運(yùn)輸費(fèi)用最低。 對(duì)于模型圖中的每條弧(i，j)(ij)和車(chē)輛k定義變量Xijk： 以上數(shù)學(xué)模型中各表達(dá)式含義如下： 式（）此式為目標(biāo)函數(shù)，其表示總的路徑代價(jià)(運(yùn)輸費(fèi)用、距離或時(shí)間)最低； 式（）保證了有且僅有一輛物資配給車(chē)輛從物資配送中心出發(fā)； 式（）保證了每個(gè)物資需求點(diǎn)凈流量為0； 式（）保證了有且只有一輛物資配給車(chē)輛最終回到調(diào)度中心。 2.4模型求解 根據(jù)前面已經(jīng)建立的應(yīng)急物流車(chē)輛調(diào)

12、度數(shù)學(xué)模型，可將此問(wèn)題進(jìn)一步描述如下：在各地震救災(zāi)單元區(qū)域內(nèi)，從配送中心派出車(chē)輛進(jìn)行救災(zāi)，每一輛車(chē)可為若干受災(zāi)點(diǎn)載送物資，車(chē)輛行駛路徑應(yīng)保證是距離最短的那條，最終要求出總消耗最低的路徑線路和最低費(fèi)用(距離)。 2.4.1求解步驟描述 遺傳算法優(yōu)化算法(GA-plus)在求解應(yīng)急資源調(diào)度問(wèn)題時(shí)的基本步驟如下： Step1：設(shè)定初始參數(shù)。主要是遺傳迭代次數(shù)、初始種群大小、交叉和變異概率； Step2：隨機(jī)產(chǎn)生初始種群，利用適應(yīng)度函數(shù)計(jì)算種群適應(yīng)度； Step3：根據(jù)適應(yīng)度按輪盤(pán)賭方法和最佳個(gè)體復(fù)制選擇下一代染色體； Step4：根據(jù)交叉概率，對(duì)染色體（候選解）進(jìn)行順序交叉操作； Step5：根據(jù)變

13、異概率，對(duì)染色體（候選解）進(jìn)行變異操作(二元變異)； Step6：產(chǎn)生新的種群，利用適應(yīng)度函數(shù)計(jì)算種群適應(yīng)度，記錄新種群中的最佳個(gè)體； Step7：判斷是否滿足遺傳算法迭代次數(shù)，若滿足則停止并輸出優(yōu)化結(jié)果，否則轉(zhuǎn)Step2對(duì)新種群繼續(xù)操作。 2.4.2案例分析 本文采用Matlab編程，對(duì)有30個(gè)節(jié)點(diǎn)、50個(gè)節(jié)點(diǎn)和75個(gè)節(jié)點(diǎn)三種情況進(jìn)行試驗(yàn)分析。 （1）30節(jié)點(diǎn)時(shí) 各算法參數(shù)設(shè)置為： GA迭代步數(shù)為2000，種群規(guī)模為100，交叉概率為0.8，變異概率為0.2； GA-plus迭代步數(shù)為2000，種群規(guī)模為100，交叉概率為0.8，變異概率為0.2。 （2）50節(jié)點(diǎn)時(shí) 各算法參數(shù)設(shè)置為： GA

14、迭代步數(shù)為3000，種群規(guī)模為150，交叉概率為0.8，變異概率為0.2； GA-plus迭代步數(shù)為3000，種群規(guī)模為150，交叉概率為0.8，變異概率為0.2。 （3）75節(jié)點(diǎn)時(shí) 各算法參數(shù)設(shè)置為： GA迭代步數(shù)為7000，種群規(guī)模為200，交叉概率為0.8，變異概率為0.2； GA-plus迭代步數(shù)為7000，種群規(guī)模為200，交叉概率為0.8，變異概率為0.2。 運(yùn)行環(huán)境： 操作系統(tǒng)：Windows 7 32bit 硬件信息： 處理器Intel(R) Core(TM)2 Duo CPU E8400 內(nèi)存2G 運(yùn)行平臺(tái)：Matlab 2013a 運(yùn)行時(shí)間： （）30個(gè)需求點(diǎn) GA4min

15、 23s 53ms GA-plus4min 42s 34ms （）50個(gè)需求點(diǎn) GA10min 30s 51ms GA-plus11min 52s 12ms （）75個(gè)需求點(diǎn) GA19min 45s 19ms GA-plus25min 28s 42ms 3結(jié)束語(yǔ) 通過(guò)實(shí)驗(yàn)過(guò)程以及以上圖示結(jié)果，可以對(duì)GA-plus優(yōu)化方法得出以下結(jié)論： （）GA-plus的全局優(yōu)化度相對(duì)較高，最終解顯示出更優(yōu)水平，并且平均優(yōu)化度也比較高； （）GA-plus的魯棒性強(qiáng)，趨于優(yōu)化解的概率較高； （）GA-plus的計(jì)算時(shí)間較長(zhǎng)，在算法效率上有待提高，但在一定程度上克服了過(guò)早收斂的早熟問(wèn)題。 本文針對(duì)應(yīng)急物資調(diào)運(yùn)問(wèn)

16、題建立了數(shù)學(xué)模型，對(duì)模型求解過(guò)程中使用的啟發(fā)式算法進(jìn)行了優(yōu)化和改進(jìn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法增強(qiáng)了對(duì)問(wèn)題的求解能力，一定程度上克服了算法過(guò)早收斂的問(wèn)題。同時(shí)本文對(duì)于應(yīng)急物資調(diào)運(yùn)問(wèn)題的研究對(duì)于實(shí)際問(wèn)題也具有借鑒意義。 參考文獻(xiàn) Rudolph G. Convergence analysis of canonical genetic algorithmsJ. Neural Networks, IEEE Transactions on, 1994,5(1):96-101. 馬欣,朱雙東,楊斐.旅行商問(wèn)題 (TSP) 的一種改進(jìn)遺傳算法J.計(jì)算機(jī)仿真,2003,4:36-37. 馬鈞水,劉貴忠.改進(jìn)遺傳算法搜索性能的大變異操作J.控制理論與應(yīng)用,1998,1