遺傳算法解決物流中心選址的問題

韓秀梅，王欣大連科技學(xué)院

遺傳算法解決物流中心選址的問題

韓秀梅，王欣
大連科技學(xué)院

摘要：隨著經(jīng)濟(jì)的發(fā)展，網(wǎng)絡(luò)技術(shù)的應(yīng)用，物流中心的數(shù)量越來越多，在城市經(jīng)濟(jì)發(fā)展中的作用越來越重要。本文為解決物流中心選址問題采取了遺傳算法，通過對物流中心位置的建模，選取適當(dāng)?shù)倪m應(yīng)值函數(shù)，對物流中心的位置進(jìn)行合理分配，使得選址建址過程中花費(fèi)的費(fèi)用最低。

注：項(xiàng)目名稱：大連科技學(xué)院科學(xué)技術(shù)研究一般項(xiàng)目（編號(hào)：KJY201410）。

1　分析問題

對于物流中心選址問題，簡言之，就是在產(chǎn)地和需求地點(diǎn)之間找一點(diǎn)，使從產(chǎn)地到物流中心和從物流中心道需求地點(diǎn)這兩個(gè)過程中花費(fèi)的費(fèi)用最低。這個(gè)費(fèi)用和運(yùn)輸量及運(yùn)輸距離成正比。這是個(gè)類似于TSP的問題，TSP即旅行商問題，它的解決辦法是應(yīng)用遺傳算法。因此，物流中心選址問題，也應(yīng)用遺傳算法。首先對其進(jìn)行建模。

式中：Fc總運(yùn)輸成本，vi為i點(diǎn)的運(yùn)輸量，fi為到i點(diǎn)的運(yùn)輸費(fèi)率，di從待定的物流中心到i點(diǎn)的距離。

距離可由下式獲得

2　算法總體設(shè)計(jì)

2.1根據(jù)遺傳算法的流程和步驟，針對物流中心選址問題的總體設(shè)計(jì)作如下說明：

（1）本算法制定了一定的迭代次數(shù)來作為算法的結(jié)束準(zhǔn)則，當(dāng)達(dá)到一定的迭代次數(shù)時(shí)，算法結(jié)束，輸出最優(yōu)解。

（2）根據(jù)適應(yīng)值函數(shù)進(jìn)行選擇時(shí)，記錄當(dāng)前最優(yōu)解，在經(jīng)過交叉變異更新群體后，保證新的迭代循環(huán)中的群體越來越好。

（3）本例是按照適應(yīng)值函數(shù)值來選擇種群的，并使數(shù)目減少，當(dāng)每次變異操作后，產(chǎn)生隨機(jī)路徑補(bǔ)充群體的個(gè)數(shù)不變，再次循環(huán)，這樣在一定程度上防止了因?yàn)槌跏既后w的選擇問題而陷入局部最優(yōu)致使無法得到最優(yōu)解。

2.2設(shè)計(jì)詳情

（1）編碼和隨機(jī)初始群體的生成

（2）和適應(yīng)值函數(shù)

在求解該問題時(shí)，適應(yīng)值函數(shù)為費(fèi)用的和，費(fèi)用的和越大，說明花費(fèi)的越多，適應(yīng)度就越小，反之，則適應(yīng)度大。通過每次選擇適應(yīng)度大的個(gè)體，來逐步找到最優(yōu)解。

每個(gè)個(gè)體（每條距離路徑）總和計(jì)算的編程實(shí)現(xiàn)為：

式中，Cmax是當(dāng)前F(X)的最大值，此時(shí)，Cmax會(huì)隨著代數(shù)有變化。

2.3選擇操作

按照某種選擇策略從群體中選擇出若干個(gè)體進(jìn)入交配池，交配池只不過的個(gè)體通過遺傳算子的作用產(chǎn)生新一代群體。選擇策略應(yīng)遵循的基本原則是：適應(yīng)值越大的個(gè)體被選中的概率應(yīng)該越大[27]。即選擇策略應(yīng)遵循自然界“優(yōu)勝劣汰、適者生存”的自然選擇規(guī)律。

本文中使用適應(yīng)值函數(shù) fitness為：

利用 fitness>rand來選擇個(gè)體，將費(fèi)用較大（適應(yīng)值大）的個(gè)體選擇下來，但是這種算法的群體變少，并且優(yōu)秀個(gè)體的數(shù)目較少，使可能收斂的數(shù)目變慢，在算法的調(diào)試的過程中證明了這一點(diǎn)。

2.4交叉操作

選擇操作雖然能夠從舊種群中選擇則出優(yōu)秀者，但不能創(chuàng)造新的染色體。交叉操作模擬生物進(jìn)化過程中的繁殖現(xiàn)象，通過兩個(gè)染色體的交換組合，來產(chǎn)生新的優(yōu)良品種，從而檢測到搜索空間中新的點(diǎn)。因此，交叉操作時(shí)遺傳算法的核心操作部分，通過交叉，能生成具有更多模式的個(gè)體，使個(gè)體的多樣化能促進(jìn)算法搜索到全局最優(yōu)解。

本文中的交叉采用部分匹配策略，其基本實(shí)現(xiàn)步驟如下：

（1）隨機(jī)選擇兩個(gè)交叉點(diǎn)；

（2）將兩個(gè)交叉點(diǎn)中間的基因互換；

（3）將互換的基因段以外的部分中與互換后基因段中元素沖突的用另一附帶的相應(yīng)位置代替，直到?jīng)]有沖突為止。

過程實(shí)例如圖所示，交叉點(diǎn)為2、7，交換匹配段后，A中沖突的有7、6、5，在B的匹配段中找出與A匹配段中對應(yīng)為止的值7-3、6-0、5-4，繼續(xù)檢測沖突直到?jīng)]有沖突。對B做同樣的操作，得到最后結(jié)果。

圖4.1匹配段交換圖例

2.5變異操作

從遺傳運(yùn)算過程中產(chǎn)生新個(gè)體的能力方面來說，交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法，它決定了遺傳算法的全局搜索能力，而變異運(yùn)算知識(shí)產(chǎn)生新個(gè)體的輔助方法，但它也是必不可少的一個(gè)運(yùn)算步驟，因?yàn)樗鼪Q定了遺傳算法的局部搜索能力。交叉算子與變異算子的相互配合，共同完成對搜索空間的全局搜索和局部搜索，從而使遺傳算法能夠以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。

本文中變異操作使用互換操作算子，也就是隨機(jī)交換染色體中的兩個(gè)不同基因編碼的位置，互換操作相對于逆序操作和插入操作更有利于算法的大范圍搜索

例如，變異交換位置為2和8。

2.6更新群體和停止準(zhǔn)則

種群中的個(gè)體經(jīng)過交叉、變異操作后，將種群的最優(yōu)個(gè)體直接保留作為下一代，以防止因交叉或變異而失去最優(yōu)解，出現(xiàn)退化現(xiàn)象。同時(shí)，為保持種群數(shù)目不變，變異后產(chǎn)生隨機(jī)解加入群體。

停止準(zhǔn)則一般為求出最優(yōu)解或者迭代次數(shù)達(dá)到設(shè)定的最大值，滿足終止條件則停止。本文中采用設(shè)置迭代終止次數(shù)的方法。

參考文獻(xiàn)：

[1]陳志平,徐宗本.計(jì)算機(jī)數(shù)學(xué)——計(jì)算復(fù)雜性理論與NPC, NP難問題的求解[M].北京:科學(xué)出版社,2001.

[2]馬立肖,王江晴.遺傳算法在組合優(yōu)化問題中的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)，2005,27(7):114-117.