李茂林

(運(yùn)城職業(yè)技術(shù)學(xué)院 電子信息工程系,山西 運(yùn)城 044000)

0 引言

隨著物聯(lián)網(wǎng)的迅速興起,物流配送產(chǎn)業(yè)也得到了迅猛的發(fā)展。物流配送系統(tǒng)主要分為物流配送中心選址和物流配送路徑規(guī)劃兩個(gè)部分,其中起決策作用的是配送中心選址的優(yōu)化問題[1]。物流配送中心選址模型優(yōu)化主要指從若干個(gè)供應(yīng)點(diǎn)和若干個(gè)需求點(diǎn)中,選擇出幾個(gè)最優(yōu)點(diǎn)作為配送中心,使得配送路徑最合理,配送成本更低。因此,物流配送中心選址模型具有非線性和多約束性,是典型的NP-Hard問題[2]。針對(duì)物流配送中心選址模型優(yōu)化問題,許多國(guó)內(nèi)外的學(xué)者對(duì)該問題進(jìn)行了深入研究。

袁群等人提出一種改進(jìn)遺傳算法的冷鏈物流配送中心選址優(yōu)化策略[3],通過貪婪算子對(duì)算法進(jìn)行改進(jìn),提高了物流配送效率。尚猛等人提出一種改進(jìn)鯨魚優(yōu)化算法的選址優(yōu)化策略[4],通過隨機(jī)正弦控制因子策略提高了算法的全局收斂能力,很大程度降低了配送時(shí)間和配送成本。范榮華提出一種基于直覺模糊數(shù)的物流配送中心選址策略[5],建立了新的評(píng)價(jià)標(biāo)準(zhǔn),降低了配送成本和配送風(fēng)險(xiǎn)。谷淑娟等人提出一種多尺度網(wǎng)格配送方法,通過區(qū)域離散的方式選擇配送中心[6]。此外,還有重心法[7]、改進(jìn)蟻群算法[8]、改進(jìn)粒子群算法[9]以及改進(jìn)煙花算法[10]。以上物流配送中心選址優(yōu)化策略均在一定程度上降低了配送成本,節(jié)約配送時(shí)間,但單一機(jī)制的優(yōu)化算法難以針對(duì)具有多個(gè)配送點(diǎn)和需求點(diǎn)的配送中心選址模型進(jìn)行優(yōu)化,因此本文提出一種改進(jìn)猴群優(yōu)化算法的優(yōu)化策略。

猴群優(yōu)化算法是一種新的群智能優(yōu)化算法[11],算法具有調(diào)整參數(shù)少,結(jié)構(gòu)簡(jiǎn)單易實(shí)現(xiàn)的優(yōu)點(diǎn),但算法全局收斂精度較低,在迭代后期易早熟收斂陷入局部最優(yōu)。本文針對(duì)上述問題通過引入lateral變異和非線性調(diào)節(jié)因子對(duì)算法進(jìn)行改進(jìn),并將改進(jìn)后的算法用于物流配送中心選址模型優(yōu)化。

1 物流配送中心選址模型

物流配送中心選址優(yōu)化問題是指在多個(gè)供應(yīng)點(diǎn)中選取M個(gè)供應(yīng)點(diǎn)作為配送中心,使得從配送中心出發(fā)的配送車輛可以很快地送到配送中心附近的配送點(diǎn),從而節(jié)約配送時(shí)間,降低配送成本。因此,在建立物流配送中心選址模型時(shí),應(yīng)考慮以下幾方面的假設(shè)。

1)假設(shè)任意一個(gè)配送點(diǎn)的需求量應(yīng)小于或等于其匹配的配送中心的貨物總量,此假設(shè)可用以下數(shù)學(xué)式表示:

(1)

式中,M為所選出的全部配送中心地址;ψi,j為第i個(gè)配送點(diǎn)的需求量。

2)假設(shè)所有配送點(diǎn)所需配送貨物均應(yīng)從距其最近的配送中心發(fā)貨。此假設(shè)可用以下數(shù)學(xué)式表示:

(2)

式中,Zi,j為0或1,當(dāng)Zi,j=1時(shí),表示配送點(diǎn)i的貨物由配送中心供應(yīng)。

3)假設(shè)無配送中心的點(diǎn)沒有客戶:

Zi,j≤hjj=1,2,…,N

(3)

式中,hj為0或1,當(dāng)hj=1時(shí),則將第j個(gè)供應(yīng)點(diǎn)選為配送中心,Fj為第j個(gè)配送中心的建設(shè)費(fèi)用。

4)假設(shè)有P個(gè)物流配送中心:

(4)

5)假設(shè),任意一個(gè)配送點(diǎn)都應(yīng)在與其匹配的配送中心可送范圍之內(nèi):

di,j≤t

(5)

式中,di,j為第i個(gè)配送點(diǎn)和與其距離最短的第j個(gè)配送中心之間的距離。

因此基于上述假設(shè),定義帶多約束條件的物流配送中心選址模型的目標(biāo)函數(shù)為:

(6)

2 猴群優(yōu)化算法的改進(jìn)策略

2.1 基本猴群優(yōu)化算法 (Monkey Optimization Algorithm, MOA)

針對(duì)具有數(shù)據(jù)量大,復(fù)雜度高以及多約束條件特性的數(shù)學(xué)模型,猴群優(yōu)化算法有著很好的優(yōu)化效果,其求解過程包含爬、望、跳三個(gè)階段。首先設(shè)猴群優(yōu)化算法的種群規(guī)模為NP,解空間維度為D,因此猴群優(yōu)化算法的種群初始化過程為:

Xi=(xi,1,xi,2,…,xi,D)

(7)

式中,i=1,2,…,NP,xi表示每個(gè)粒子在解空間的初始位置。

其次,猴群優(yōu)化算法在求解過程中,種群中所有粒子會(huì)逐漸向全局極值靠攏,并在迭代過程中不斷更新自己的位置,直到找到目標(biāo)函數(shù)最小解為止,這種位置更新過程被描述為爬過程,其數(shù)學(xué)表達(dá)式如下所示:

(8)

(9)

再次,猴群優(yōu)化算法在迭代過程中,當(dāng)粒子取得局部最優(yōu)解的同時(shí),粒子會(huì)搜索局部極值附近是否存在比當(dāng)前更好的解,如果存在,則向更好的解靠攏,否則粒子停留在局部極值點(diǎn)的位置。這種行為被描述為望過程,其過程如下所示:

1)在當(dāng)前局部極值點(diǎn)附近(xi,j-β,xi,j+β),隨機(jī)選取相鄰點(diǎn),并計(jì)算相鄰點(diǎn)的位置yi′。

2)計(jì)算局部極值點(diǎn)的適應(yīng)度值和相鄰點(diǎn)的適應(yīng)度值,并進(jìn)行比較。若局部極值點(diǎn)的適應(yīng)度值優(yōu)于相鄰點(diǎn)的適應(yīng)度值,則粒子停留在局部極值點(diǎn)位置不變,否則粒子向相鄰點(diǎn)靠攏。

最后,為了在算法尋優(yōu)過程中,將當(dāng)前區(qū)域移動(dòng)到新的搜索區(qū)域當(dāng)中,選擇所有粒子的重心位置作為支點(diǎn),每個(gè)粒子均沿當(dāng)前位置指向支點(diǎn)的方向進(jìn)行移動(dòng)搜索,這個(gè)過程被描述為跳過程,其數(shù)學(xué)表達(dá)式如下所示:

yi=xi,j+θ(pi,j-xi,j)

(10)

式中：θ為[0,1]之間的隨機(jī)數(shù)；pj為支點(diǎn),可表示為:

(11)

2.2 改進(jìn)的猴群優(yōu)化算法(Improved Monkey Optimization Algorithm, IMOA)

首先,根據(jù)大量的數(shù)值實(shí)驗(yàn)表明,整體收斂精度較高的算法在迭代前期,應(yīng)獲得較高的慣性權(quán)重或控制因子,使得算法具有較強(qiáng)的全局搜索能力和搜索范圍,保證全局極值點(diǎn)在搜索范圍內(nèi)。在算法迭代后期,慣性權(quán)重或控制因子應(yīng)迅速減小,保證算法可以獲得較強(qiáng)的局部搜索能力,有助于粒子在小范圍內(nèi)的精確尋優(yōu)。在傳統(tǒng)猴群優(yōu)化算法中,α為搜索步長(zhǎng),同時(shí)也是控制因子,負(fù)責(zé)調(diào)整算法全局搜索能力和局部搜索能力的大小,但傳統(tǒng)猴群算法中,α的取值隨迭代次數(shù)的增加線性減小,而算法全局搜索能力和局部搜索能力之間的平衡呈非線性,α線性減小難以平衡算法的全局勘探能力和局部開發(fā)能力。因此,本文引入非線性調(diào)節(jié)因子對(duì)爬過程進(jìn)行改進(jìn),非線性調(diào)節(jié)因子δ的數(shù)學(xué)表達(dá)式如下所示:

(12)

式中,Tmax為最大迭代次數(shù),t為當(dāng)前迭代次數(shù),λ和ω為調(diào)節(jié)系數(shù)。經(jīng)大量實(shí)驗(yàn)驗(yàn)證,當(dāng)λ=3.75ω=0.01時(shí),算法收斂精度最高。τ為位移量,當(dāng)τ=0.64時(shí),算法取得結(jié)果最優(yōu)。sinh(·)為雙曲正弦函數(shù),由雙曲正弦函數(shù)特性可知,δ隨迭代次數(shù)的增加,非線性減小,在算法迭代初期,減小速率較慢,使得算法具有較強(qiáng)的全局收斂能力。在算法迭代后期,δ值迅速降低,使得算法具有較強(qiáng)的局部開發(fā)能力,使得粒子的搜索精度更高,同時(shí)保證粒子可以在全局極值附迅速收斂,提高算法的收斂速度。因此可將式(8)改為:

(13)

其次,通過算法尋優(yōu)過程中的望過程可知,β的值越小,隨機(jī)生成領(lǐng)域點(diǎn)的范圍越小,使得粒子在迭代過程中易陷入局部最優(yōu),早熟收斂。β的值越大,隨機(jī)生成領(lǐng)域點(diǎn)的范圍越大,使得算法在迭代后期尋優(yōu)速度緩慢,甚至停滯,依然會(huì)導(dǎo)致算法早熟收斂,陷入局部最優(yōu)。因此,為了避免由β取值不合理,導(dǎo)致算法出現(xiàn)早熟收斂的現(xiàn)象,本文引入lateral變異對(duì)算法進(jìn)行改進(jìn),其中l(wèi)ateral變異的數(shù)學(xué)表達(dá)式如下所示:

xi,j=(1-η)xi,j+ηxk,j

(14)

式中,xi,j為當(dāng)前最優(yōu)個(gè)體,xk,j為種群中的隨機(jī)個(gè)體且k≠i;η為學(xué)習(xí)率,在[0,1]之間服從均勻分布。lateral變異主要是通過xk,j個(gè)體的信息特征來指導(dǎo)當(dāng)前xi,j的搜索機(jī)制,可更有效地利用種群的環(huán)境信息,在算法陷入局部最優(yōu)時(shí)給予適當(dāng)大小的擾動(dòng),幫助粒子跳出局部最優(yōu),并提高算法的收斂速度。

改進(jìn)的猴群優(yōu)化算法的尋優(yōu)步驟如下所述。

Step1:初始化猴群的種群規(guī)模NP=100,維數(shù)D=50,最大迭代次數(shù)Tmax=100,λ=3.75,ω=0.01,τ=0.64;

Step2:對(duì)種群中所有粒子的位置進(jìn)行初始化,計(jì)算全部個(gè)體的適應(yīng)度值,并將粒子按適應(yīng)度值大小進(jìn)行排序。找出適應(yīng)度值最小的個(gè)體作為當(dāng)前最優(yōu)解;

Step3:依照式(13)計(jì)算當(dāng)前猴群粒子的位置;

Step4:依照望過程更新當(dāng)前猴群粒子的位置;

Step5:依照式(14)對(duì)當(dāng)前粒子進(jìn)行l(wèi)ateral變異操作,對(duì)更新后的粒子進(jìn)行邊界處理;

Step6:依照式(10)更新當(dāng)前猴群粒子的位置;

Step7:判斷是否達(dá)到最大迭代次數(shù),若達(dá)到最大迭代次數(shù),則輸出全局最優(yōu)解,否則返回Step3。

2.3 基于測(cè)試函數(shù)的性能測(cè)試

為了驗(yàn)證本文所提改進(jìn)猴群算法(IMOA)的收斂精度,選取8個(gè)基準(zhǔn)測(cè)試函數(shù)作為目標(biāo)函數(shù),對(duì)IMOA進(jìn)行數(shù)值實(shí)驗(yàn),并將實(shí)驗(yàn)結(jié)果與改進(jìn)鯨魚優(yōu)化算法(IWOA)、改進(jìn)粒子群算法(DPSO)以及改進(jìn)蟻群算法(ICOA)的數(shù)值實(shí)驗(yàn)結(jié)果相對(duì)比,記錄四種算法求解所得平均值和標(biāo)準(zhǔn)差。為了保證對(duì)比實(shí)驗(yàn)的公平性,四種算法種群規(guī)模均為100,維度均為50,最大迭代次數(shù)均為100,其他參數(shù)設(shè)置詳見文獻(xiàn)[4]、文獻(xiàn)[8]以及文獻(xiàn)[9]。測(cè)試函數(shù)如表1所示。其中f1～f4為單峰測(cè)試函數(shù)。f5～f8為多峰測(cè)試函數(shù)。具體實(shí)驗(yàn)結(jié)果如表2所示,其中最優(yōu)解用加粗字體表示。

表1 測(cè)試函數(shù)Table 1 Test function

表2 12個(gè)測(cè)試函數(shù)測(cè)試結(jié)果Table 2 Test results of 12 test functions

從表2中可知,首先,對(duì)于測(cè)試函數(shù)f1～f4而言,四種算法均可以找到全局極值點(diǎn),說明四種算法的整體性能較高。但本文所提IMOA算法相較其他三種算法而言,取得平均值更小,說明IMOA算法具有更高的局部收斂精度,在迭代后期,可以迅速向全局最優(yōu)解靠攏,收斂速度更快。值得注意的是,對(duì)于測(cè)試函數(shù)f1而言,本文所提IMOA可以求解到理論最優(yōu)值,說明IMOA算法很大程度地減小了算法陷入局部最優(yōu)的概率。此外,IMOA算法可以取得更小的標(biāo)準(zhǔn)差,說明IMOA算法相較其他三種算法而言,算法局部搜索的穩(wěn)定性更高,魯棒性更強(qiáng),對(duì)于處理復(fù)雜度較高的優(yōu)化問題具有很好的收斂精度。

其次,對(duì)于多峰測(cè)試函數(shù)f5～f8而言,IMOA求解的平均值同樣遠(yuǎn)小于其他三種算法,驗(yàn)證了IMOA算法在尋優(yōu)初期具有較高的全局搜索范圍,算法的全局收斂能力要優(yōu)于其他三種算法,搜索成功率也大于其他三種算法。同樣,對(duì)比四種算法的標(biāo)準(zhǔn)差,IMOA求解結(jié)果遠(yuǎn)小于其他三種算法,說明IMOA算法的全局尋優(yōu)穩(wěn)定性優(yōu)于其他三種算法。由此可得,IMOA算法的全局收斂精度遠(yuǎn)優(yōu)于其他三種算法的全局收斂精度。

最后,利用Wilcoxon秩和檢驗(yàn)分析IMOA、DPSO、ICOA和IWOA四種算法的性能差異性。在(D=50)時(shí),在選定5%的顯著性水平下,以IMOA算法為基準(zhǔn),DPSO算法、ICOA算法和IWOA算法所得的pvalue分別為0.02741、0.04873和0.04209。

總體而言,IMOA算法很好地平衡了算法的全局收斂能力和局部搜索能力,對(duì)于求解復(fù)雜的較高的測(cè)試函數(shù)時(shí),具有較高的收斂精度和收斂速度,可以用于求解物流配送中心選址模型。

3 仿真實(shí)驗(yàn)及分析

為了驗(yàn)證本文所提IMOA算法的優(yōu)化性能,本文獲取30個(gè)需要配送貨品的城市地理位置信息,選取式(6)為目標(biāo)函數(shù),建立物流配送中心選址數(shù)學(xué)模型,并將IMOA算法對(duì)模型進(jìn)行優(yōu)化。本文實(shí)驗(yàn)平臺(tái)為MATLAB2014a,實(shí)驗(yàn)所用硬件配置為Intel Core i5 2.70 GHz 8.00 GB運(yùn)行內(nèi)存的處理器。操作系統(tǒng)為Win10操作系統(tǒng)。30個(gè)配送城市的地理位置和貨物量如表3所示。

表3 30個(gè)配送城市地理位置Table 3 Geographical location of 30 distribution cities

為了可以更加直觀地表明IMOA算法具有較高的收斂精度,本文將IMOA算法的優(yōu)化結(jié)果與IWOA算法的優(yōu)化結(jié)果和ICOA算法的優(yōu)化結(jié)果相對(duì)比,三種算法的設(shè)置參數(shù)與數(shù)值實(shí)驗(yàn)中參數(shù)設(shè)置相同。具體實(shí)驗(yàn)結(jié)果如圖1～圖3和表4所示。

圖1 基于IMOA算法的物流配送中心選址Fig.1 Location of logistics distribution center based on IMOA algorithm

圖2 基于IWOA算法的物流配送中心選址Fig.2 Location of logistics distribution center based on IWOA algorithm

圖3 基于ICOA算法的物流配送中心選址Fig.3 Location of logistics distribution center based on ICOA algorithm

表4 三種算法的選址性能比較Table 4 Comparison of location performance of three algorithms

在實(shí)驗(yàn)前應(yīng)對(duì)三種算法進(jìn)行二進(jìn)制編碼處理。將30個(gè)城市的編碼隨機(jī)設(shè)定成0或1,當(dāng)其中任意一個(gè)城市被選中為配送中心時(shí),該城市編碼為1,否則該城市編碼為0。假設(shè)在10個(gè)城市中選擇第1個(gè)、第4個(gè)和第8個(gè)城市作為配送中心,則該編碼為X=(1,0,0,1,0,0,0,1,0,0)。

圖1～圖3分別為基于IMOA算法的優(yōu)化策略、基于IWOA算法的優(yōu)化策略以及基于ICOA算法的優(yōu)化策略所求解的平均適應(yīng)度值和最小適應(yīng)度值。從圖中可知,本文所提基于IMOA算法的優(yōu)化策略相較其他兩種優(yōu)化算法的優(yōu)化結(jié)果,可以求解到更小的平均值和最小適應(yīng)度值,說明基于IMOA算法的優(yōu)化結(jié)果更加精確,搜索精度更高。

從表4可得,經(jīng)IMOA算法優(yōu)化后的物流配送中心選址模型,較大程度地降低了物流配送費(fèi)用,同時(shí)可以更快地得到最優(yōu)解。值得注意的是,IMOA算法相較其他兩種算法迭代次數(shù)明顯更小,說明IMOA算法具有較為平衡的全局收斂能力和局部搜索能力,搜索精度更高?？傮w而言,IMOA算法較其他兩種算法,優(yōu)化速度更快，可以更加精確地選取物流配送中心地址。

4 結(jié)論

本文針對(duì)物流配送中心選址模型難以優(yōu)化的問題,提出一種改進(jìn)的猴群優(yōu)化算法對(duì)模型進(jìn)行求解。首先針對(duì)猴群算法收斂精度低,易早熟收斂陷入局部最優(yōu)的問題,通過非線性調(diào)節(jié)因子和lateral變異對(duì)算法進(jìn)行改進(jìn),提高了算法的收斂精度和收斂速度,平衡了算法的全局搜索能力和局部開發(fā)能力,提高了算法跳出局部最優(yōu)的概率。其次通過數(shù)值對(duì)比實(shí)驗(yàn),驗(yàn)證了本文所提IMOA算法整體收斂性能更強(qiáng),具有較高的收斂精度。最后,將IMOA算法對(duì)物流配送中心選址模型進(jìn)行優(yōu)化,并將實(shí)驗(yàn)結(jié)果與IWOA算法的優(yōu)化結(jié)果和ICOA算法的優(yōu)化結(jié)果相對(duì)比,結(jié)果表明,IMOA算法可以更快求解到最優(yōu)值,很大程度降低了物流配送花費(fèi),提高了配送效率,降低了配送成本。