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

[摘要] 電子商務(wù)環(huán)境下的物流配送中心選址問(wèn)題是近年來(lái)物流研究中的熱點(diǎn)。由于它是一個(gè)NP難題，較難得到最優(yōu)解和滿意解。本文將混沌免疫進(jìn)化算法用于解決該問(wèn)題。混沌免疫進(jìn)化算法具有較好的全局搜索能力和收斂性，能夠較好的解決該類復(fù)雜系統(tǒng)的優(yōu)化問(wèn)題。

[關(guān)鍵詞] 物流 配送中心 選址 混沌免疫進(jìn)化算法 多目標(biāo)優(yōu)化

一、物流配送中心選址多目標(biāo)優(yōu)化模型

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

令A(yù)=A1∪A2為所有物流中心地點(diǎn)的集合，A1為已有物流中心的集合，A2為新增物流中心的集合。

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

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

M為充分大的正數(shù)，ε為充分小的正數(shù)，sj為j地的物流中心的供應(yīng)能力，Wi為客戶點(diǎn)i的總需求量。

一般來(lái)說(shuō)，求解雙層規(guī)劃問(wèn)題是非常困難的，原因之一就是由于雙層規(guī)劃問(wèn)題是一個(gè)NP-hard問(wèn)題，解答這類問(wèn)題需要相當(dāng)長(zhǎng)的計(jì)算時(shí)間，這里采用混沌免疫算法來(lái)求解。

二、混沌免疫進(jìn)化算法

本文在結(jié)合混沌優(yōu)化算法和免疫進(jìn)化算法各自特點(diǎn)的基礎(chǔ)上，提出一種混沌免疫進(jìn)化算法。該算法不僅能更好地保持種群的多樣性，而且收斂速度快，搜索能力強(qiáng)。

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

(3)

式中，0≤t(k)≤1，當(dāng)取μ＝4時(shí)，系統(tǒng)完全處于混沌狀態(tài)，其混沌空間為[0，1]。不動(dòng)點(diǎn)為0．25，0．5，0．75。

對(duì)于隨機(jī)擾動(dòng)的確定，令 (4)

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

2.混沌免疫算法描述，采用混沌免疫算法求解約束優(yōu)化問(wèn)題的具體實(shí)現(xiàn)步驟如下：

(1)參數(shù)設(shè)置：設(shè)定種群進(jìn)化代數(shù)為Ngen，種群規(guī)模為No，記憶細(xì)胞數(shù)量為NM，克隆選擇數(shù)量為Ns，克隆倍數(shù)為Nη，免疫補(bǔ)充數(shù)量為NR，混沌變量序列長(zhǎng)度為mc。

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

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

(3)進(jìn)化開(kāi)始：載入抗原，根據(jù)目標(biāo)函數(shù)計(jì)算每個(gè)抗體的聚合適應(yīng)度(聚合適應(yīng)度的具體計(jì)算見(jiàn)公式，并按升序排列，令進(jìn)化代數(shù)T=1。

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

(5)克隆擴(kuò)增操作：對(duì)種群Xs中的每個(gè)個(gè)體，按照Nη倍進(jìn)行克隆擴(kuò)增，得到種群Xc。

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

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

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

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

(10)混沌優(yōu)化：對(duì)種群XM中的每個(gè)記憶細(xì)胞進(jìn)行混沌優(yōu)化操作。

終止條件判斷：判斷進(jìn)化是否到達(dá)指定代數(shù)，若到達(dá)，輸出記憶細(xì)胞種群中最小親和度作為最優(yōu)解，對(duì)應(yīng)的個(gè)體為最優(yōu)點(diǎn)，算法結(jié)束；否則T＝T+1，并執(zhí)行步驟?

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

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

三、混沌免疫算法的求解算法設(shè)計(jì)

算法的基本要素如下：

1.編碼選擇和生成初始種群，采用實(shí)數(shù)編碼。

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

3.抗體擴(kuò)增算子設(shè)計(jì)。模擬克隆擴(kuò)增和超突變過(guò)程。群體B中任一個(gè)體的小鄰域構(gòu)造為：

擴(kuò)展操作相當(dāng)于在優(yōu)秀個(gè)體的小鄰域內(nèi)搜索更優(yōu)秀的個(gè)體。個(gè)體評(píng)價(jià)值越高，其鄰域內(nèi)存在優(yōu)秀個(gè)體的概率越大。

4.抗體突變算子設(shè)計(jì)。在該算子操作中，構(gòu)造一個(gè)較大鄰域。其較大鄰域構(gòu)造為：

MN(vj)在解空間中是以vj為中心，以R為半徑的球形區(qū)域，定義R為突變半徑。突變半徑應(yīng)遠(yuǎn)大于擴(kuò)展半徑。

5.混沌優(yōu)化算子設(shè)計(jì)。用混沌優(yōu)化方法進(jìn)行局部搜索，步驟如下：

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

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

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

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

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

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

四、結(jié)語(yǔ)

提出用混沌免疫算法求解物流配送中心選址的多目標(biāo)優(yōu)化模型。該算法是類似于遺傳算法的全新的全局隨機(jī)搜索算法，該算法比常規(guī)的線性規(guī)劃法簡(jiǎn)單，還可以處理一些傳統(tǒng)方法不能處理的NP完全問(wèn)題。還可以克服傳統(tǒng)遺傳算法的爬山能力差與早熟問(wèn)題。

參考文獻(xiàn):

[1]孫會(huì)君高自友:一類有競(jìng)爭(zhēng)的物流配送中心選址模型[J].交通運(yùn)輸工程學(xué)報(bào)，2002，2(4):54.57

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

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。