基于自適應免疫算法的配送中心選址問題研究

文/李紀魯 張曉 朱杰

關鍵字：自適應；免疫算法；選址；配送中心

引言

物流配送中心的選址理論最初由Alfred Weber于1929年提出[1]，他們研究如何設置一個配送中心到達各個需求點的距離最短。這種交通問題一提出便得到了各位學者的廣泛關注，從此，配送中心的選址和優化問題越來越重要。近幾年的研究成果也越來越多。費騰[2]等人在配送中心的選址中引入基于DNA改進的魚群算法，豐富了魚群的多樣性，促進魚群算法跳出最優解，使選址有了更好的尋優能力。唐煒[3]為解決配送中心的選址問題，提出基于層次分析法的優化方法，為實際操作提供了新思路。徐小平[4]在解決配送中心選址問題中，提出一種改進的狼群算法，通過引入擾動操作、不確定的奔襲和攻擊步長提高算法的精確度。王辛巖[5]等人通過AHP和人工免疫算法結合來求解物流中心的選址問題，驗證了免疫算法的收斂性和魯棒性。

李爽[6]等人針對物流中心的選址問題提出一種融合DEA和AHP的混合模型，比傳統的物流配送中心選址模型有更強的可行性和實用性。胡利利[7]等人把節點需求量和輻射半徑納入約束條件，并以需求量作為距離的權重放入目標函數中，建立配送中心選址模型，并通過實驗找出了交叉和變異概率的事宜取值，為后續的研究提供了方向。

淦艷[8]等人將配送時間作為目標函數中的權值進行模型構建，并通過免疫算法進行多次實驗，驗證了模型的可行性。倪衛紅[9]等人在配送中心選址中對免疫算法的交叉和變異概率進行自適應改進，并通過實驗驗證了改進的可行性。姜婷[10]針對配送中心選址的研究提出改進的螢火蟲算法，通過對螢火蟲算法的李算話處理來解決選址問題，驗證了算法的穩定性和運行效率。殷月[11]建立考慮多方面成本因素影響的配送中心模型，并通過免疫算法對模型求解，驗證了免疫算法在配送中心選址中的可行性和實用性。本文主要在上述文獻的基礎之上，綜合考慮物流配送中的位置因素和需求量因素，并通過數學建模的方式對目標函數和約束條件進行定義，構建一個帶有需求量權重的配送中心選址模型，并通過自適應的方法改進免疫算法，應用到配送中心模型中進行求解。

1.配送中心選址模型的建立

本文是根據總成本最小為目標的物流配送中心選址問題[12]，在建立配送中心選址模型時考慮到滿足需求節點約束和配送中心到需求點的最大距離約束等，在已知的多個備選點中設定一定數量的配送中心，并構成以配送中心和需求點為基本單元的網絡，實現總成本最小。本文中的距離采用歐氏距離，并采用單位需求運輸費率為1，即運輸費用等于運輸距離。在物流配送中心選址模型中做如下假設：

（1）配送中心的規模容量滿足需求點的需求；

（2）一個配送中心可以對多個需求點進行配送，但一個需求點只能由一個配送中心進行配送；

（3）不考慮運輸費用之外的其他費用。

基于以上假設，根據成本最小化為目標來建立配送中心的選址模型，在配送中心選址模型中，在不超過距離上限的基礎上，需要從n個需求點中找出設定個數的配送中心向各需求點配送貨物。目標函數是各配送中心到需求點單位需求量的運輸成本和需求量的乘積最小。符合就近分配和容量約束原則。

目標函數為：

約束條件為：

2.自適應免疫算法

免疫算法是一種仿生學的算法，它旨在區分有害抗原和自身組織，從而保持有機體的穩定。免疫系統不僅有交叉變異保證種群的多樣性，而且有種群經營保留策略，全局尋優能力較好，同時精英保留策略可以維持免疫系統平衡機制，對于今后侵入相同的抗原，相應的記憶細胞會迅速激發產生大量的抗體。免疫系統在產生抗體時，可以借助克隆選址、免疫記憶、疫苗接種等方式對抗體的產生進行促進和抑制，體現了免疫系統有較好的自我調節能力。參考文獻[7]中的免疫系統改進策略對算法的各部分進行定義描述，同時引進根據抗體與抗原之間的親和力對變異概率進行計算，親和力越高，變異概率越小。

2.1 產生初始抗體群

采用實數編碼的方式對初始抗體群進行編碼，如果記憶庫非空，則從記憶庫中產生初始抗體群，否則，隨機產生初始抗體群。每個可行方案均形成一個長度為q的抗體，即設定的物流配送中心個數。

2.2 親和力計算

在抗體的適應度方面考慮配送中心對需求點的配送最大距離上限約束條件，設置違反距離約束的懲罰函數。抗體親和力包括抗體與抗原之間的親和力和抗體與抗體之間的親和力，抗體與抗原之間的親和力表示抗體對抗原的識別程度，抗體與抗體之間的親和力表示抗體與抗體之間的相似程度。本文中抗體與抗原之間的親和力用Cu表示。

其中，對于配送中心到需求點距離超過規定上限的解給予懲罰，其中Y取一個比較大的正數。

抗體與抗體之間的親和力計算方法主要根據文獻[8]中α位連續方法，即根據兩個抗體中相同位數所占總長度的比重來判斷量抗體的相似程度。兩抗體的親和度定義如下：

其中，ku,v表示抗體u和抗體v之間的相同位數數量，q為抗體的長度。

2.3 抗體濃度的計算

抗體濃度即抗體群中相似抗體所占的比例，為了保證進化過程中種群的多樣性，免疫系統需要對抗體的產生進行促進和抑制，若抗體群中相似抗體所占的比重過大，即抗體間的相似程度較高會影響抗體群的多樣性，因此需要設定一個閾值φ來控制抗體濃度。本文中設定抗體濃度的閾值為0.7，其中N為抗體總數，抗體濃度定義如下：

2.4 期望繁殖概率

每個個體的期望繁殖概率由抗體與抗原之間的親和力Cu和抗體濃度C'u兩部分共同決定，是免疫選擇操作中的重要依據。在期望繁殖概率中不僅體現了適應度高的促進，而且體現了抗體濃度高時的抑制，從而保證整個抗體群的多樣性。與此同時，為了避免出現抗體濃度高時受到抑制而丟失最優解的情況出現，采用了精英保留策略，設置記憶庫容量為overbest的容量庫，先將抗體育抗原親和度的抗體存進記憶庫中，再按照期望繁殖概率選擇優秀的抗體放進記憶庫中。本文設置多樣性評價參數ε對抗體與抗原之間的親和度起到促進作用，同時對抗體高濃度情況起到抑制作用。期望繁殖概率定義如下：

2.5 選擇操作

本文采用輪盤賭的方法，基于適應度權重和濃度權重的選擇策略。個體被選擇的概率與上述期望繁殖的概率一致。

2.6 交叉操作

交叉概率越大，新的抗體產生的速度越快，搜索的范圍越大，但是交叉概率過小時，容易導致搜索速度過慢，影響計算的時間長度，因此，采用自適應交叉概率可以保證較優的解進入下一代，減少計算時間復雜度。交叉概率公式如下，其中Pc0為初始的交叉概率，Fm為最大的適應度值，Fa為平均適應度值，F為進行交叉的兩個個體中較大的適應度值。

2.7 變異操作

本文變異算子基于適應度的大小，主要思想是當適應度較大時，應該抑制變異行為，當適應度較小時，應促進變異行為。對需要變異的個體采用多變異位自適應的方法進行變異，即根據適應度值選擇變異概率及變異位。變異概率定義如下，其中為'F變異個體的適應度值。

2.8 自適應免疫算法求解配送中心選址問題

（1）本初始化抗體種群。隨機產生N個個體并從記憶庫中提取m個個體構成初始抗體種群，其中m為記憶庫中個體的數量。

（2）對上述種群中的抗體進行評價，按照期望繁殖概率對父代進行評價選擇，找出適應度值較大且抗體濃度適當的抗體作為父代并根據精英保留策略存入記憶庫中。

（3）判斷是否滿足終止條件，如果是則輸出結果，如果不是則進行下一步操作。

（4）采用輪盤賭的方式對抗體種群進行選擇操作。

（5）根據自適應公式對抗體群體進行交叉操作、變異操作，并從記憶庫中取出記憶的個體，共同構成新一代群體。

（6）轉到執行步驟（2）。

改進后的自適應免疫算法流程如下：

3.實驗對比設計

該為了驗證算法的可行性，數據采用文獻[11]城市位置坐標和需求量信息如表所示。表中（x，y）代表城市坐標，Wi表示需求點的需求量。本文采用MATLAB2014a編程，并在HP450，CPU為2.60GHz，內存為4GB的ARM筆記本上測試改進的自適應免疫算法，算法參數設置為：種群規模為50，記憶庫容量為10，最大迭代次數為100，交叉改路初始值為0.5，變異改路初始值設置為0.4，求得配送中心的選址方案為[12 28 9 5 20 17] ，距離和為5.49X105 ， 運行對比如下：

圖2 配送中心選址圖

圖3 對比分析

與未設定交叉變異算子的免疫算法對比，收斂速度較快，最終收斂到最小值。

4.結語

考慮到免疫算法容易受精英解的影響，設定自適應的交叉和變異算子，構建路徑和最小為目標函數，設定相應的約束條件，實例驗證得出自適應的免疫算法由較好的全局搜索能力，收斂速度快，可以跳出局部最優解。