基于多種群搜索的PSO的物流配送中心尋址求解

李 磊, 楊愛峰, 唐 娜, 陳亞波

(1.合肥工業(yè)大學(xué) 管理學(xué)院,安徽 合肥 230009; 2.過程優(yōu)化與智能決策教育部重點實驗室,安徽 合肥 230009)

基于多種群搜索的PSO的物流配送中心尋址求解

李 磊1,2, 楊愛峰1,2, 唐 娜1,2, 陳亞波1,2

(1.合肥工業(yè)大學(xué) 管理學(xué)院,安徽 合肥 230009; 2.過程優(yōu)化與智能決策教育部重點實驗室,安徽 合肥 230009)

物流配送中心選址不僅影響運輸?shù)瘸杀?而且也影響顧客的服務(wù)水平,在現(xiàn)代物流中具有重要的現(xiàn)實意義。針對物流配送中心選址問題,文章提出了一種基于改進粒子算法的智能求解方法，建立了物流配送中心選擇模型,根據(jù)模型特點設(shè)計出了與免疫優(yōu)化算法混合的粒子群算法、多種群搜索策略、混沌初始化方法、多樣性評價方法。通過合理地設(shè)置算法參數(shù),對物流配送中心選址問題進行實驗比較,實驗結(jié)果表明,該文算法的求解效果良好,并且求解的速度較快。

物流配送中心選址;粒子群算法;多種群;混沌;精英子群

粒子群優(yōu)化算法[1](particle swarm optimization,PSO)是1995年美國學(xué)者Eberhart E C和Kennedy J提出的一種群智能優(yōu)化算法。PSO算法具有參數(shù)少、收斂速度快的優(yōu)點[2],但是同時也具有容易陷入局部解的缺點,而且基本PSO算法主要是用來解決連續(xù)性問題的一種算法,要應(yīng)用到離散問題或者組合優(yōu)化問題則要進行相應(yīng)的設(shè)置和改進。目前主要用于解決離散化問題的PSO算法主要有如下3種:① 對PSO算法解的表現(xiàn)形式和更新公式進行重新定義,如二進制PSO算法[3]等;② 不改變PSO算法的形式,仍然使用基本PSO算法進行求解,只是在求解的最后將所得解取整;③ 將PSO算法與離散化的算法進行混合求解,如與遺傳算法混合的PSO算法[4]、與蟻群算法混合的PSO算法[5]、模擬退火粒子群優(yōu)化算法[6]、基于粒子群優(yōu)化的電動汽車再生制動模糊控制[7]等。

物流配送中心選址問題[8]是典型的組合優(yōu)化問題,由于它是一個整數(shù)規(guī)劃,且變量及相關(guān)約束非常多,屬于典型的NP難問題,找到多項式計算時間內(nèi)的解非常困難。傳統(tǒng)的求解方法有重心法、拉格朗日松弛法、分支定界法等。其中重心法主要用于單一配送中心選址模型;拉格朗日松弛法往往可以獲得中等規(guī)模問題的次優(yōu)解,但其性能依賴于問題本身結(jié)構(gòu);分支定界法能獲得問題的全局最優(yōu)解,但隨著問題規(guī)模增加求解效率低下,適合一些小規(guī)模簡單模型。近年來由于啟發(fā)式隨機優(yōu)化方法在復(fù)雜優(yōu)化問題中的廣泛應(yīng)用,為物流配送中心選址問題提供了新的思路,比如遺傳算法、免疫優(yōu)化算法、粒子群算法等。

1 免疫優(yōu)化算法

生物免疫系統(tǒng)是一個高度進化的生物系統(tǒng),旨在區(qū)分外部有害抗原和自身組織,從而保持有機體的穩(wěn)定。從計算角度看,生物免疫系統(tǒng)是一個高度并行、分布、自適應(yīng)和自組織的系統(tǒng),具有很強的學(xué)習(xí)、識別和記憶能力。

免疫優(yōu)化算法[9](immune optimization algorithm,IOA)是在遺傳算法的基礎(chǔ)上發(fā)展起來的。它模擬生物免疫系統(tǒng)對外來抗原的排除,借鑒免疫系統(tǒng)的自組織學(xué)習(xí)、自適應(yīng)調(diào)節(jié)的特點,在保留遺傳算法優(yōu)良特性的前提下,力圖有選擇、有目的地利用待求問題中的一些特征信息或知識來抑制其優(yōu)化過程中出現(xiàn)的退化現(xiàn)象,具有免疫記憶特性、抗體自我識別能力和免疫多樣性的特點,但與遺傳算法一樣,它仍不能充分利用求解問題的特征信息指導(dǎo)全局搜索,搜索是盲目的、隨機的,在小區(qū)域仍不能克服不成熟收斂現(xiàn)象,在小空間搜索效率并不顯著。免疫算法與遺傳算法類似,采用群體搜索策略,并且強調(diào)群體中個體間的信息交換。但免疫算法評價個體的標準不是適應(yīng)度,而是親和度,因此免疫算法對個體的評價更加合理。

免疫優(yōu)化算法的優(yōu)化過程如下:

(1) 分析問題。對問題及其解的特性進行分析,設(shè)計解的合適表達形式。

(2) 產(chǎn)生初始抗體群。隨機產(chǎn)生N個個體并從記憶庫中提取m個個體構(gòu)成初始群體,其中,m為記憶庫中個體的數(shù)量。

(3) 對上述群體中各個抗體進行評價。在本算法中對個體的評價是以個體的期望繁殖概率為標準的。

(4) 形成父代群體。將初始群體按期望繁殖概率進行降序排序,并取前N個個體構(gòu)成父代群體;同時取前m個個體存入記憶庫中。

(5) 判斷是否滿足結(jié)束條件,是則結(jié)束;反之,則繼續(xù)下一步操作。

(6) 新群體的產(chǎn)生。基于步驟(4)的計算結(jié)果對抗體群進行選擇、交叉、變異操作得到新群體,再從記憶庫中取出記憶的個體,共同構(gòu)成新一代群體。

2 基于多種群搜索的粒子群算法

2.1 基本粒子群算法

粒子群算法[10]中每個潛在解都代表一個粒子,每個粒子對應(yīng)一個適應(yīng)度值,每個粒子都有一個表示移動方向的速度和位置。粒子在解空間中運動,通過跟蹤個體極值Pbest和群體極值Gbest更新個體位置。

設(shè)在一個D維搜索空間中,n個粒子組成的種群X=(X1,X2,…,Xn),其中Xi=(xi1,xi2,…,xiD)T,代表第i個粒子在D維搜索空間中的位置,即一個潛在解。Vi=(vi1,vi2,…,viD)T,代表第i個粒子在D維搜索空間中的移動速度,其個體極值為pi=(pi1,pi2,…,piD)T,種群的群體極值為g=(g1,g2,…,gD)T。粒子的速度位置更新公式如下:

(1)

(2)

其中,c1、c2為非負的常數(shù),稱為學(xué)習(xí)因子;r1、r2為分布于[0,1]的隨機數(shù)。

2.2 基于多種群搜索的粒子群算法

2.2.1 粒子群的初始化

本文算法(MSPSO)用粒子的位置變量來表示離散問題的可行解,采用整數(shù)編碼的方式,每個粒子用length維向量表示?；煦鏪11]是自然界廣泛存在的一種非線性現(xiàn)象,具有隨機性、遍歷性和規(guī)律性的特點,現(xiàn)在已被廣泛地運用到隨機優(yōu)化問題中。

為了提高算法搜索的效率,在粒子群初始化時將粒子均勻分布在解空間中,可以擴展可行解的搜索范圍,有助于提高求解的效率和質(zhì)量,因此,本文將混沌引入到粒子的初始化當中。Logistic混沌映射模型的定義如下:

(3)

(4)

其中,maxAk、minAk為區(qū)間Ak的最大值和最小值；[]為取整符號。

2.2.2 粒子的多樣性評價

粒子的多樣性評價反映了粒子之間的相似程度,主要吸取了免疫優(yōu)化算法中抗體間親和度的計算方法。

定義1(粒子間的相似度) 粒子間的相似度反映了2個粒子之間的相似程度,此處借鑒免疫優(yōu)化算法中抗體間親和度的計算方法。粒子采用整數(shù)編碼的方式,假設(shè)粒子是length維空間上的點,則粒子間的相似度表示為:

Sij=lij/length

(5)

其中,i=1,2,…,N,j=1,2,…,N,N為種群中粒子的數(shù)目;Sij為粒子i與粒子j的分量取值相等的個數(shù)lij占粒子維數(shù)length的比例。

定義2(粒子與種群的相似程度) 粒子與種群的相似程度指的是粒子分別與種群中其余粒子之間的相似度大于某個閾值的個數(shù)與種群大小的比例,即

(6)

其中,T為預(yù)先設(shè)定的某個值;i=1,2,…,N,j=1,2,…,N,N為種群中粒子的數(shù)目。

定義3(粒子的多樣性參數(shù)) 粒子在種群中的多樣性評價參數(shù)是由粒子的適應(yīng)度值和粒子與種群的相似程度共同決定的,即

(7)

其中,i=1,2,…,N,j=1,2,…,N,N為種群中粒子的數(shù)目;fi為粒子i的適應(yīng)度值的倒數(shù);α∈(0,1)。

(7)式表明：若粒子的適應(yīng)度值越好,則多樣性越好;若粒子與群體相似程度越高,則多樣性越低。這樣就促進了適應(yīng)度好的粒子,同時也抑制了多樣性不好的粒子。

2.2.3 種群搜索策略

在初始化種群后,將種群分成pop1和pop2 2個子群,子群pop2進行精確搜索,而子群pop1則輔助pop2進行探索式搜索。

子群pop1中的每個粒子分別與自身的極值pbest交叉,這樣每個粒子都分別跟蹤不同的歷史極值進行更新,不僅能夠保持該子群的多樣性,而且還能進行全局的搜索,之后通過適當?shù)倪x擇進行變異操作以進行局部的搜索,確保更加準確的搜索。

子群pop2中的粒子與精英子群中隨機選擇的粒子best進行交叉操作,這樣可以產(chǎn)生更多優(yōu)秀的粒子,之后同樣進行適當?shù)淖儺惒僮?確保對優(yōu)秀個體的局部進行搜索。而精英子群elite的形成是將適應(yīng)度值較好的粒子和根據(jù)(7)式計算得到的粒子組合成的一個子群。

2個子群間的信息交流是單向交流,pop1通過在搜索過程中得到的種群極值保留在elite中來向pop2傳遞信息,算法搜索策略及子群間的信息交流方式如圖1所示。

圖1 算法的搜索策略及子群間的信息交流

粒子與歷史極值和優(yōu)秀個體進行交叉分別表示為:

p(t)=p(t)?pbest(t)

(8)

(9)

其中,p(t)為群體中的一個粒子;pbest(t)為這個粒子的歷史極值;best(t)為隨機從子群elite中選中的一個粒子,這樣每個粒子追求不同的極值進行迭代,能維持種群的多樣性加快收斂速度;?為交叉操作,這里采用單點交叉法。

為了在迭代過程中保留較好的粒子,對子群elite主要進行局部的精確搜索,這里采用隨機變異位變異的方法。

2.2.4 算法流程

(1) 分析問題。對問題及其解的特性進行分析,設(shè)計解的合適表達形式。

(2) 參數(shù)設(shè)置。設(shè)置種群大小N、子群大小n1和n2、最大迭代次數(shù)Maxiter、精英子群大小m、解的長度length和多樣性評價參數(shù)D。

(3) 產(chǎn)生初始解。利用(3)式與(4)式混沌初始化粒子群。

(4) 分群。首先,把種群中適應(yīng)度值最優(yōu)的粒子加入到精英子群中,然后利用(5)～(7)式將多樣性較好的粒子加入到精英子群中。其次,將群體劃分為2個子群pop1和pop2。

(5) 子群更新。在子群pop1中,粒子分別與自身極值交叉,然后進行選擇變異,最后計算適應(yīng)度值;在子群pop2中,粒子與在精英子群中隨機選擇的優(yōu)秀粒子進行交叉,然后進行選擇變異,最后計算適應(yīng)度值。

(6) 精英子群搜索操作。對精英子群進行局部變異搜索是為了精確地搜索優(yōu)秀個體的局部潛在的最優(yōu)解。

(7) 合群。將子群pop1與子群pop2重新組合成一個群體。

(8) 判斷是否滿足結(jié)束條件,是則結(jié)束;否則跳到步驟(4)繼續(xù)執(zhí)行。

3 物流配送中心選址問題求解

3.1 物流配送中心選址模型

物流配送中心選址模型[12]中有如下假設(shè):

(1) 配送中心的規(guī)模容量總可以滿足需求點的需求,并由其配送輻射范圍內(nèi)的需求量確定。

(2) 一個需求點僅由一個配送中心供應(yīng)。

(3) 不考慮工廠到配送中心的運輸費用。

基于以上假設(shè)建立模型，該模型是一個選址/分配模型,在滿足距離上限的情況下,需要從M個備選配送中心中找出m個配送中心向n個需求點配送物品。目標函數(shù)是各配送中心到需求點的運費與配送中心固定建設(shè)費用之和最小。規(guī)劃模型如下:

(10)

(11)

(12)

(13)

(14)

(15)

其中,N={1,2,…,n}為所有需求點的序號集合;Mi為到需求點i的距離小于s的備選配送中心集合;s為新建配送中心離由其服務(wù)的需求點的距離上限;v為單位產(chǎn)品單位距離的運輸費用(即運費率);wi為需求點的需求量;dij為從需求點i到離其最近的配送中心j的距離;Cj為配送中心的固定建設(shè)成本;p為從候選點選出的配送中心總和;Zij為0-1決策變量,表示用戶和物流中心的服務(wù)需求分配關(guān)系,當其為1時,表示需求點i的需求量由配送中心j供應(yīng),否則Zij=0;hj為0-1決策變量,當其為1時,表示候選點j被選為配送中心,否則hj=0。

(10)式表示各配送中心到需求點的運費與配送中心固定建設(shè)費用之和;(11)式表示每個需求點只能由一個配送中心送貨;(12)式表示若候選的配送中心沒有被選中,則從該配送中心不能供應(yīng)任何需求點,否則可以供應(yīng);(13)式表示從配送中心到需求點運輸距離不超過s;(14)式表示從候選點選出的配送中心總和等于p;(15)式表示決策變量的0-1約束。

3.2 問題求解

本文算法采用整數(shù)編碼的方式,根據(jù)實際問題的需要,每個粒子都是維數(shù)為length(配送中心的數(shù)目)的可行解,代表被選為配送中心的需求點序列,例如:粒子[3 2 8 12 5 9]代表序號為3、2、8、12、5和9的城市被選為配送中心。針對上述配送中心選址模型得到的粒子適應(yīng)度值函數(shù)為:

(16)

現(xiàn)在要從12個候選配送中心城市中選取出6個城市作為配送中心來給需求點城市配送物資,使得總的運輸成本最小。為了簡化實驗,將城市間的距離作為運輸費用,單位物資的成本為1。

21個需求點城市的空間位置和物資需求量見表1所列。

候選配送中心城市的空間位置和建設(shè)費用見表2所列。

表1 需求點位置及其物資需求量 t

表2 候選配送中心城市的位置坐標及建設(shè)成本 萬元

3.3 實驗結(jié)果分析

本文的實驗環(huán)境為:硬件環(huán)境采用32位Windows7操作系統(tǒng)、I5CPU、4GB內(nèi)存;軟件環(huán)境采用matlabr2012a。

本文的實驗參數(shù)設(shè)置為:種群規(guī)模為80、2個子群大小均為40、精英子群的大小為10、最大迭代次數(shù)為200。

在實驗參數(shù)相同的條件下,將本文算法與PSO[13]、IOA[14](internetofficeautomation)和HPSO[15](harmonionsparticleswarmoptimizer)進行仿真實驗得到的結(jié)果進行比較。

問題模型的最優(yōu)解方案為[1 8 6 4 2 7],該方案表示候選配送中心城市序號分別為1、8、6、4、2和7的6個候選配送城市被選為配送中心,作為給需求點配送物資的配送點,且這個方案的最小的配送費用為581 663.859 450 40,該最優(yōu)配送方案如圖2所示。

圖2中25個空心圓圈表示的是25個需求點城市,12個實心圓是候選配送中心城市,而正方形中間的實心圓圈是選中的配送中心城市,與各個配送點有連線的空心圓圈表示圓圈所代表的需求點由這個配送中心配送物資。

在實驗過程中,4種算法通過迭代尋優(yōu)都能夠找到這個模型的最優(yōu)解,因此得到的最優(yōu)方案與圖2中的方案一致。

圖2 最優(yōu)配送方案

4種算法迭代的收斂曲線如圖3所示。從圖3中可以看出4種算法都能收斂到最優(yōu)解。其中,本文算法MSPSO收斂速度比IOA和HPSO算法的收斂速度快,但是要比PSO算法的收斂速度慢。

圖3 4種算法的收斂曲線

程序獨立運行20、30、50次時算法得到的最優(yōu)解次數(shù)折線圖如圖4所示。

從圖4a中可以看出,基本粒子群算法PSO得到最優(yōu)解的次數(shù)最少,其次是免疫優(yōu)化算法IOA、混合粒子群算法與本文算法得到的最優(yōu)解次數(shù)是最多的。

從圖4b中可以看出,本文算法得到最優(yōu)解的次數(shù)要比PSO、IOA和MPSO算法得到最優(yōu)解次數(shù)都要多。

從圖4c中可以看出本文算法得到的最優(yōu)解次數(shù)是最多的,比PSO、IOA和MPSO算法得到的最優(yōu)解次數(shù)都要多。

圖4 程序獨立運行20、30、50次時算法得到的最優(yōu)解次數(shù)

綜上所述,PSO算法在求解該問題時最不穩(wěn)定、尋優(yōu)的概率最低,IOA算法和HPSO算法在尋優(yōu)的過程中得到最優(yōu)的概率則比較穩(wěn)定,但是得到最優(yōu)解的概率也沒有本文算法的高,而本文算法MSPSO尋找最優(yōu)解的概率是最大的,從而證明了本文算法在求解物流配送中心選址問題時具有良好的效果及穩(wěn)定性。

4 結(jié) 論

針對物流配送中心選址問題,本文提出了基于多種群搜索策略的混合粒子群優(yōu)化算法。結(jié)果表明，本文算法在求解物流配送中心選址問題中具有較好的搜索能力,并且搜索的性能也較優(yōu),證明了本文算法在求解離散化的問題方面有著較好的能力。在本文算法中,提出了一種利用混沌初始化種群個體的方法,使粒子能夠均勻分布在問題空間中,提高了搜索到最優(yōu)解的概率,同時把混沌引入到解決離散問題的算法更新中將是下一步的研究工作。

[1] LABAL N,ZERGUINE A,AL-DHAHIR N.Decision feedback equalization using particle swarm optimization[J].Signal Processing,2015,108:1-12.

[2] 李麗,牛奔.粒子群優(yōu)化算法[M].北京:冶金工業(yè)出版社,2010:123-124.

[3] 王志剛,夏慧明,王明剛,等.求解多維背包問題的改進二進制粒子群算法[J].數(shù)學(xué)的實踐與認識,2013,43(19):129-137.

[4] 劉快,紀志成.基于混合粒子群的RFID網(wǎng)絡(luò)的優(yōu)化部署[J].計算機應(yīng)用研究,2012,29(4):1326-1328.

[5] 徐青鶴,劉士榮,呂強.基于蟻群混沌行為的離散粒子群算法及其應(yīng)用 [J].計算機科學(xué),2010,37(5):178-180.

[6] 劉志峰,楊德軍,顧國剛.基于模擬退火粒子群優(yōu)化算法的拆卸序列規(guī)劃[J].合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2011,34(2):163-165,179.

[7] 周云鵬,趙韓,江昊.基于粒子群優(yōu)化的電動汽車再生制動模糊控制[J].合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2014,37(7):771-772.

[8] 王志剛,王明剛,尚旭東.基于人工蜂群算法的配送中心選址問題求解[J].數(shù)學(xué)的實踐與認識,2014, 44(17):170-175.

[9] 戚玉濤,劉芳,常偉遠,等.求解多目標問題的Memetic的免疫優(yōu)化算法[J].軟件學(xué)報,2013,24(7):1529-2544.

[10] 朱大林,詹騰,張屹,等.多策略差分進化的元胞多目標粒子群算法[J].電子學(xué)報,2014,42(9):1831-1838.

[11] YANG Zuyuan,YANG Huafen,YANG You,et al.An improved particle swarm optimization method based on chaos.[C]//2014 10th International Conference on Natural Computation.[S.l.]:IEEE,2014:209-213.

[12] 史峰,王輝,郁磊,等.Matlab 智能算法30個案例分析[M].北京:北京航空航天大學(xué)出版社,2011:118-120.

[13] 趙莉,董玉民.基于量子遺傳的混合粒子群優(yōu)化算法[J].計算機工程與設(shè)計,2014,35(7):2566-2571

[14] 李貞雙,李爭艷.基于云模型的量子免疫優(yōu)化算法[J].計算機工程與應(yīng)用,2011,47(21):123-125.

[15] GHAMISI P,BENDIKTSSON J A.Feature selection based on hybridization of genetic algorithm and particle swarm optimization[J].IEEE Geoscience and Remote Sensing Letters,2015,12(2):309-313.

(責(zé)任編輯 張 镅)

Solution for logistics distribution center location based on multi-population search PSO algorithm

LI Lei1,2, YANG Aifeng1,2, TANG Na1,2, CHEN Yabo1,2

(1.School of Management, Hefei University of Technology, Hefei 230009, China; 2.Key Laboratory of Process Optimization and Intelligent Decision Making of Ministry of Education, Hefei 230009, China)

Logistics distribution center location not only decides the cost such as transportation cost, but also impacts the customer service level. It has important practical significance in modern logistics. For solving this logistics distribution center location problem, an improved particle swarm optimization(PSO) based intelligent optimization algorithm is proposed. Firstly, the mathematical model of the logistics distribution center location is set up. And for solving it, the PSO hybridized with immune optimization algorithm(IOA), multi-population search strategy, chaos initialization method and diversity evaluation method are designed. By setting parameters reasonably, the experiments are conducted and the results show that the proposed algorithm has better solving performance and rapid solving speed.

logistics distribution center location; particle swarm optimization(PSO); multi-population; chaos; elite-subgroup

2015-11-16；

2016-01-14

國家自然科學(xué)基金青年科學(xué)基金資助項目(71301038;71301041)

李 磊(1990-),男,湖北武漢人,合肥工業(yè)大學(xué)碩士生; 楊愛峰(1976-),女,河南濮陽人,博士,合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師.

10.3969/j.issn.1003-5060.2017.02.024

TP18

A

1003-5060(2017)02-0266-06