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

韓秀梅，王欣大連科技學院

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

韓秀梅，王欣
大連科技學院

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

注：項目名稱：大連科技學院科學技術研究一般項目（編號：KJY201410）。

1　分析問題

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

式中：Fc總運輸成本，vi為i點的運輸量，fi為到i點的運輸費率，di從待定的物流中心到i點的距離。

距離可由下式獲得

2　算法總體設計

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

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

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

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

2.2設計詳情

（1）編碼和隨機初始群體的生成

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

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

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

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

2.3選擇操作

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

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

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

2.4交叉操作

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

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

（1）隨機選擇兩個交叉點；

（2）將兩個交叉點中間的基因互換；

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

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

圖4.1匹配段交換圖例

2.5變異操作

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

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

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

2.6更新群體和停止準則

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

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

參考文獻：

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

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