基于混沌免疫進化算法的物流配送中心選址方案

[摘要] 電子商務環境下的物流配送中心選址問題是近年來物流研究中的熱點。由于它是一個NP難題，較難得到最優解和滿意解。本文將混沌免疫進化算法用于解決該問題。混沌免疫進化算法具有較好的全局搜索能力和收斂性，能夠較好的解決該類復雜系統的優化問題。

[關鍵詞] 物流 配送中心 選址 混沌免疫進化算法 多目標優化

一、物流配送中心選址多目標優化模型

1.上層模型。上層規劃為決策部門在允許的固定投資范圍為，確定最佳的新選物流中心的地點以使總成本最小。具體模型如下：

令A=A1∪A2為所有物流中心地點的集合，A1為已有物流中心的集合，A2為新增物流中心的集合。

式中:Cij(.)—第i個客戶由j地點的物流中心提供服務的單位運量的廣義費用；Xij—第i個客戶在j地點的物流中心得到滿足的需求量；fj—在j(j∈A2)地建物流中心的固定投資；B—修建物流中心的總投資預算；Yj—0-1變量，在j(j∈A2)地建物流中心時，此值為1，否則為零。

2.下層模型。下層規劃(L)描述了在多個物流中心存在的條件下，客戶需求量在不同物流中心之間的分配模式，它的目標是使每個客戶的費用最低。下層規劃為：

M為充分大的正數，ε為充分小的正數，sj為j地的物流中心的供應能力，Wi為客戶點i的總需求量。

一般來說，求解雙層規劃問題是非常困難的，原因之一就是由于雙層規劃問題是一個NP-hard問題，解答這類問題需要相當長的計算時間，這里采用混沌免疫算法來求解。

二、混沌免疫進化算法

本文在結合混沌優化算法和免疫進化算法各自特點的基礎上，提出一種混沌免疫進化算法。該算法不僅能更好地保持種群的多樣性，而且收斂速度快，搜索能力強。

1.混沌映射和混沌撓動方式的確定，本文采用常用的Logistic映射:

(3)

式中，0≤t(k)≤1，當取μ＝4時，系統完全處于混沌狀態，其混沌空間為[0，1]。不動點為0．25，0．5，0．75。

對于隨機擾動的確定，令 (4)

其中；β*為當前最優值映射到[0，1]區間后形成的向量，稱為最優混沌向量；βk為迭代k次后的混沌向量；βk’為施加隨機擾動后的混沌向量；0<α< l，α可以自適應變化。搜索初期希望變量變化較大，α值應較大；隨著搜索的進行，變量逐漸接近最優值，α應逐漸減小。本文算法按下式確定：

2.混沌免疫算法描述，采用混沌免疫算法求解約束優化問題的具體實現步驟如下：

(1)參數設置：設定種群進化代數為Ngen，種群規模為No，記憶細胞數量為NM，克隆選擇數量為Ns，克隆倍數為Nη，免疫補充數量為NR，混沌變量序列長度為mc。

(2)初始化：初始種群X0隨機生成，設個體x＝[x1，x2，…，xn]T，則生成N0個可行解個體的初始種群X0的步驟如下：

①令初始可行解集X0＝，滿足約束條件的可行解個體計數j=0。②個體隨機生成。 ③判斷生成的候選解x是否為可行解，若是可行解，則x并入X0中，即X0←x，且計數器增加1，j←j＋1，轉步驟(4);若不是可行解，則放棄生成的x，轉步驟 。④判斷計數器計數j是否達到N0，若達到，則結束種群初始化，轉步驟③，否則轉步驟(2)繼續。

(3)進化開始：載入抗原，根據目標函數計算每個抗體的聚合適應度(聚合適應度的具體計算見公式，并按升序排列，令進化代數T=1。

(4)克隆選擇：選取序列前N 個個體形成種群Xs，用于克隆。

(5)克隆擴增操作：對種群Xs中的每個個體，按照Nη倍進行克隆擴增，得到種群Xc。

(6)抗體突變操作：對種群Xc中的每個個體進行突變操作，得到種群Xm。

(7)對種群Xm中的個體進行可行解審查，合格的個體組成種群X，m，并計算其親和度。

(8)父代樣本X0和X，m組成新的種群X0←X，m，并按照親和度重新排序。

(9)記憶細胞的形成：重新選擇序列的前N0個個體作為子代種群X0，并把前NM個個體記為記憶細胞種群XM。

(10)混沌優化：對種群XM中的每個記憶細胞進行混沌優化操作。

終止條件判斷：判斷進化是否到達指定代數，若到達，輸出記憶細胞種群中最小親和度作為最優解，對應的個體為最優點，算法結束；否則T＝T+1，并執行步驟?

免疫補充：按式(3)隨機生成NR個個體，代替種群X0中NR個親和度最大的個體，種群按親和度重新排列，并轉步驟(4)。

在上述算法步驟中，除步驟(10)外，其余的步驟構成免疫算法，而步驟(10)為混沌優化方法。容易看出，在步驟(9)中的記憶細胞為免疫算法獲得的全局近似最優解，而步驟(10)是在全局近似最優解的鄰域內進行局部范圍的混沌搜索，以獲得全局精確最優解，這樣免疫算法與混沌優化就有機地結合在一起。

三、混沌免疫算法的求解算法設計

算法的基本要素如下：

1.編碼選擇和生成初始種群，采用實數編碼。

2.抗體聚合適應度的計算，抗體的聚合度的計算步驟如下：(1)分別計算抗體體的子目標函數值；(2)將抗體排序等級作為原始適應度；(3)根據如下公式計算抗體的濃度，Ci=與抗體i的相似度大于λ的抗體數/N;(4)根據如下公式計算抗體的聚合適應度;。

3.抗體擴增算子設計。模擬克隆擴增和超突變過程。群體B中任一個體的小鄰域構造為：

擴展操作相當于在優秀個體的小鄰域內搜索更優秀的個體。個體評價值越高，其鄰域內存在優秀個體的概率越大。

4.抗體突變算子設計。在該算子操作中，構造一個較大鄰域。其較大鄰域構造為：

MN(vj)在解空間中是以vj為中心，以R為半徑的球形區域，定義R為突變半徑。突變半徑應遠大于擴展半徑。

5.混沌優化算子設計。用混沌優化方法進行局部搜索，步驟如下：

(1)對記憶種群中的第k(k＝1，2，… ，NM)個記憶細胞，將其第i個基因變量xi映射到混沌空間[0，1.0]：

把xi，0作為混沌迭代的初始值，按式3生成mc個不同軌跡的混沌變量序列{xi，j }( j＝1，2，…，mc)。

(2)利用選定的混沌變量xi，j分別對原變量進行載波：

式中:△xi，j為xi的鄰域；r為鄰域半徑;p為鄰域半徑系數，取p=0.05；函數randint(a，b)為區間 [a，b]內的隨機整數。

(3)對混沌變量序列的個體進行可行解審查，設有m’c個個體滿足約束條件。

(4)計算這m’c個可行解個體的親和度Gj＝G(x’i，j)( i=1，2，…n，j=1，2，…，m’c)，并進行如下操作:設載波前k個記憶細胞和親和度分別為x(k)、G(k)=G(x(k))，在載波后的可行解個體序列中最小親和度與最優個體分別為G*=min(Gj)、x*，即G*=min(Gj)=G(x*)。進行下列判斷:若G*

四、結語

提出用混沌免疫算法求解物流配送中心選址的多目標優化模型。該算法是類似于遺傳算法的全新的全局隨機搜索算法，該算法比常規的線性規劃法簡單，還可以處理一些傳統方法不能處理的NP完全問題。還可以克服傳統遺傳算法的爬山能力差與早熟問題。

參考文獻:

[1]孫會君高自友:一類有競爭的物流配送中心選址模型[J].交通運輸工程學報，2002，2(4):54.57

[2]肖劍:基于遺傳算法的物流中心選址模型及算法研究[D].碩士學位論文，重慶大學，2005

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。