郭海峰，張翠玲

融合多種策略的改進(jìn)粒子群算法及其在電子商務(wù)多級(jí)物流中的應(yīng)用研究

*郭海峰，張翠玲

(沈陽理工大學(xué)自動(dòng)化與電氣工程學(xué)院，遼寧，沈陽 110159)

為了提高粒子群優(yōu)化算法（PSO）求解復(fù)雜優(yōu)化問題的能力，本文對(duì)基于細(xì)菌趨化的粒子群優(yōu)化算法（PSOBC）進(jìn)行改進(jìn)。PSOBC算法是PSO算法的一種新思路, 可以有效地克服其易陷入局部最優(yōu)、后期粒子多樣性差的缺點(diǎn)，故將一般反向?qū)W習(xí)策略和自適應(yīng)慣性權(quán)重與PSOBC算法相結(jié)合，得到一種改進(jìn)的粒子群優(yōu)化算法。改進(jìn)的粒子群優(yōu)化算法的開發(fā)能力和勘探能力都得到了很大的提高；在求解復(fù)雜性優(yōu)化問題時(shí)種群能夠在搜索范圍內(nèi)快速收斂到局部最優(yōu)處，并且當(dāng)種群密度足夠小時(shí)，及時(shí)增大種群密度即進(jìn)行去全局尋優(yōu)。最后將改進(jìn)后算法應(yīng)用到電子商務(wù)多級(jí)物流中心選址及路徑規(guī)劃問題上。

粒子群優(yōu)化算法；反向?qū)W習(xí)；自適應(yīng)慣性權(quán)重；物流中心選址；路徑規(guī)劃

粒子群優(yōu)化算法[1](Particle Swarm Optimization, PSO)自提出以來便受到國內(nèi)外學(xué)者的廣泛關(guān)注。PSO算法作為現(xiàn)代群體智能算法，有無限的發(fā)展?jié)摿?，被廣泛應(yīng)用在各個(gè)領(lǐng)域。但傳統(tǒng)PSO存在局部搜索能力差、求解精度低、易陷入局部最優(yōu)和十分依賴各個(gè)參數(shù)的問題。為了解決這些問題，很多學(xué)者從參數(shù)設(shè)置、學(xué)習(xí)策略、領(lǐng)域結(jié)構(gòu)等方面融合其他算法對(duì)PSO算法進(jìn)行改進(jìn)，提出了許多不同的粒子群改進(jìn)算法[2-5]。在傳統(tǒng)PSO中每個(gè)粒子都是一個(gè)候選解，粒子在進(jìn)化過程中是不斷向個(gè)體歷史最優(yōu)和全局最優(yōu)的學(xué)習(xí)過程，導(dǎo)致種群易陷入局部最優(yōu)。所以，要提高算法的全局搜索能力，改進(jìn)學(xué)習(xí)策略是關(guān)鍵。文獻(xiàn)[6]中提出了一種求解大規(guī)模問題的自學(xué)習(xí)協(xié)同粒子群算法，將自學(xué)習(xí)策略引入到協(xié)同粒子群算法中，提高了算法的全局搜索能力，使算法在求解大規(guī)模問題中表現(xiàn)出較大的潛力。

本文將一般反向?qū)W習(xí)策略(GOBL)[7]和自適應(yīng)慣性權(quán)重[8]與基于細(xì)菌趨化的粒子群算法[9]相結(jié)合，提出了新的改進(jìn)算法。反向?qū)W習(xí)策略增加了種群進(jìn)化的多樣性，使種群進(jìn)化方向由單一向個(gè)體歷史最優(yōu)和全局最優(yōu)方向變成多方向，提高了算法的局部尋優(yōu)能力[10]；自適應(yīng)慣性權(quán)重改變了基本PSO中單一慣性，充利用種群信息，增強(qiáng)種群多樣性和算法的全局尋優(yōu)能力。

1 融合多種策略的改進(jìn)粒子群優(yōu)化算法

1.1 PSO存在的問題及改進(jìn)方法

傳統(tǒng)PSO存在局部搜索能力差、收斂速度快，易陷入局部最優(yōu)且搜索精度低；而對(duì)于復(fù)雜優(yōu)化問題，往往存在很多極值點(diǎn)，PSO在求解過程中收斂速度慢、收斂度低且很難得到最優(yōu)解。

針對(duì)PSO易陷入局部最優(yōu)的問題，采用PSOBC[7]算法中以種群密度來度量種群當(dāng)前的狀態(tài)，當(dāng)種群密度過高時(shí)，進(jìn)行“吸引”操作，加快種群的收斂速度，從而得到較優(yōu)解；當(dāng)種群密度過低時(shí)，判斷種群目前已達(dá)到某個(gè)局部最優(yōu)，此時(shí)進(jìn)行“排斥”操作，來增加種群的多樣性，避免種群陷入這個(gè)局部最優(yōu)，以尋找下一個(gè)局部最優(yōu)；最終從多個(gè)局部最優(yōu)選出全局最優(yōu)。針對(duì)種群在“吸引”階段中收斂過快的問題，采用自適應(yīng)慣性權(quán)重[8](如公式(1)所示)，粒子根據(jù)自身所處狀態(tài)來調(diào)節(jié)慣性權(quán)重，而非以統(tǒng)一的慣性權(quán)重不加區(qū)別地對(duì)自身速度予以保持。而“排斥”操作，通過粒子跟隨歷史最差位置和全局最差位置來實(shí)現(xiàn)，速度更新如公式(2)所示。

其中，fitness為當(dāng)前粒子的適應(yīng)值；fitness為當(dāng)前種群中適應(yīng)值的最小值；為當(dāng)代粒子的平均適應(yīng)值。

針對(duì)PSO在求解復(fù)雜優(yōu)化問題時(shí)收斂度慢和收斂度低的問題，將一般反向?qū)W習(xí)策略(GOBL)引入到算法[8]中。因?yàn)楫?dāng)給定一個(gè)隨機(jī)候選解時(shí)，其對(duì)立面′可能更靠優(yōu)化問題的最優(yōu)解，所以在引入反向?qū)W習(xí)策略后，不僅可以加快收斂速度，一定程度上提高了算法的尋優(yōu)能力。

1.2 改進(jìn)后粒子群優(yōu)化算法

改進(jìn)后粒子群優(yōu)化算法偽代碼：

1) initialize P，X，V

2) 更新搜索范圍；

3) for i=1:PopSize

生成反向種群G

4) end

5) fitness(X)；fitness(G) // 計(jì)算適應(yīng)度

6) for i=PopSize+1:2*PopSize

選取前Popsize個(gè)粒子

7) end

8) Pbest，Gbest // 選取種群歷史最優(yōu)和個(gè)體歷史最優(yōu)

10) iter=iter+1;

11) div=div/(sqrt(UB^2+LB^2)*PopSize) // 判斷種群多樣性

12) 根據(jù)種群密度取Mode值

13) if Mode==1

14) w_now=((w_start-w_end)*(Maxiter-iter)/Maxiter)+w_end // 更新慣性權(quán)重

15) V=w_now*V+c1*R1*(Pbest-X)+c2*R2*(Gbest-X) // 更新速度

16) X=X+V;

17) fitness(X)

18) 更新Pbest，Gbest

當(dāng)溫度低于0℃時(shí)，電池內(nèi)的水會(huì)結(jié)成冰，阻止電池的啟動(dòng)。針對(duì)電池的結(jié)冰問題，采取吹掃除水的策略來提高冷啟動(dòng)性能，實(shí)現(xiàn)燃料電池的冷啟動(dòng)。

19) else

20) 反向?qū)W習(xí)生成種群G，并計(jì)算種群適應(yīng)度，選取前PopSize個(gè)粒子

21) end

22) end

23) 輸出最優(yōu)值

2 問題描述與數(shù)學(xué)模型

2.1 問題描述

多級(jí)物流配送中心選址及路徑規(guī)劃問題需要從一級(jí)配送中心M和二級(jí)配送中心H中選擇部分物流中心進(jìn)行建設(shè)，即閉環(huán)供應(yīng)鏈網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的構(gòu)建，然后規(guī)劃供貨商T、一級(jí)物流中心M，二級(jí)物流中心H及城市區(qū)C之間的服務(wù)與被服務(wù)關(guān)系，即完成整個(gè)閉環(huán)供應(yīng)鏈中的網(wǎng)絡(luò)搭建。閉環(huán)供應(yīng)鏈運(yùn)營包括配送、運(yùn)輸、退貨處理、橫向調(diào)度及縱向調(diào)度等操作（如圖1所示）。

圖1 多級(jí)物流中的產(chǎn)品流動(dòng)

當(dāng)某城市客戶區(qū)有產(chǎn)品需求時(shí)，首先由服務(wù)于該客戶區(qū)的二級(jí)物流配送中心提供，若該二級(jí)配送中心缺貨，則優(yōu)先從其他二級(jí)配送中心調(diào)度即縱向調(diào)度，當(dāng)所有二級(jí)配送中心都無法滿足時(shí)，由一級(jí)物流配送中心提供緊急配送服務(wù)即橫向調(diào)度，且每級(jí)配送中都有回收退回產(chǎn)品的能力。

為了方便模擬解決實(shí)際問題，先對(duì)問題做了如下假設(shè)：1) 一級(jí)配送中心M不存在缺貨和容量不足的問題；2) 只有供貨商有鑒定和修復(fù)退回產(chǎn)品的能力；3) 客戶的產(chǎn)品需求單一；4) 暫不考慮運(yùn)輸時(shí)貨車的承載能力。

2.2 數(shù)學(xué)模型

2.1.1 符號(hào)定義

符號(hào)含義符號(hào)符號(hào)含義符號(hào) 供應(yīng)商集T設(shè)施點(diǎn)的建造成本F 一級(jí)備選配送中心集M設(shè)施點(diǎn)的可利用時(shí)長V 二級(jí)備選配送中心集H城市區(qū)的需求D 城市區(qū)集R配送處理成本S 退貨收集成本t設(shè)施點(diǎn)i運(yùn)到j(luò)的產(chǎn)品數(shù)qij 二級(jí)配送中心的庫存量θ設(shè)施點(diǎn)i到j(luò)的距離dij 二級(jí)配送中心橫向調(diào)度單位運(yùn)輸成本f城市區(qū)r的退貨率kr 二級(jí)配送中心單位新產(chǎn)品存儲(chǔ)容量系數(shù)γ二級(jí)配送中心單位退回產(chǎn)品存儲(chǔ)容量系數(shù)β 節(jié)點(diǎn)間的單位產(chǎn)品運(yùn)輸成本Gtm，Gmh，Ghr，Grh，Ghm，Gmr，Ghh二級(jí)配送中心的庫存處理最大容量Q 一級(jí)配送中心是否建設(shè)km∈(0,1)二級(jí)配送中心是否建設(shè)bk∈(0,1) 一級(jí)配送中心m是否服務(wù)于二級(jí)配送中心hcmh∈(0,1)二級(jí)配送中心h是否服務(wù)于城市區(qū)rchr∈(0,1)

2.2.2 數(shù)學(xué)模型

建立數(shù)學(xué)模型，即在保證滿足各個(gè)城市區(qū)產(chǎn)品需求(如公式(6)所示)、二級(jí)物流配送中心庫存處理最大容量(如公式(7)所示)的條件下，使整個(gè)閉環(huán)供應(yīng)鏈的成本最小，即公式(4)所表示含義。

約束條件為：

3 算法設(shè)計(jì)

圖2 粒子解碼過程

本文以問題的目標(biāo)函數(shù)（即公式（4））作為適值函數(shù)，算法流程如圖3所示。

圖3 算法流程圖

4 算例分析

實(shí)驗(yàn)所用數(shù)據(jù)為參考文獻(xiàn)[11]中的實(shí)驗(yàn)數(shù)據(jù)。該組數(shù)據(jù)的供應(yīng)商、一級(jí)備選物流中心、二級(jí)備選物流配送中心和城市區(qū)的個(gè)數(shù)分別為2,2,6,14；它們的位置分布如圖4所示。

圖4 設(shè)施點(diǎn)位置分布

一級(jí)和二級(jí)備選物流中心的配送處理成本S=0.8；一級(jí)備選物流中心的退回處理成本為0.5，可利用月份均為120，建造成本依次為50萬、60萬；二級(jí)備選物流中心的退貨收集成本t=1，產(chǎn)品的儲(chǔ)存容量系數(shù)γ=1，β=2；處理容量Q=1600，庫存量θ=1000，可利用月份均為60，建造成本依次為8萬、10萬、13萬、10萬、11萬、9萬。城市區(qū)的需求量如表1所示。供應(yīng)鏈運(yùn)作的基本數(shù)據(jù)如表2所示。

表1 城市區(qū)的需求量

表2 供應(yīng)鏈運(yùn)作的基本數(shù)據(jù)

采用Matlab R2018b在Windows10 系統(tǒng)中，運(yùn)用改進(jìn)的粒子群優(yōu)化算法對(duì)上述問題進(jìn)行求解，最終結(jié)果為26435。此時(shí)選擇建設(shè)第一個(gè)一級(jí)物流中心，且選擇第一個(gè)供應(yīng)商對(duì)其進(jìn)行供貨；選擇建設(shè)第2、第5、第6三個(gè)二級(jí)配送中心，其中二級(jí)配送中心與城市區(qū)之間的服務(wù)關(guān)系如圖5所示。雖然此時(shí)第6個(gè)城市區(qū)距離第5個(gè)二級(jí)物流配送中心比較近，但是此時(shí)卻選擇了第2個(gè)二級(jí)物流配送中心；與第6個(gè)城市區(qū)情況類似的有第8、第13城市區(qū)。但是此時(shí)這種選擇即沒有橫向調(diào)度也沒有縱向調(diào)度，相比之下成本反而會(huì)降低。

圖5 二級(jí)物流中心與城市區(qū)的服務(wù)關(guān)系

5 結(jié)束語

本文對(duì)基于細(xì)菌趨化的粒子群算法進(jìn)行改進(jìn)，以及針對(duì)多級(jí)物流中心選址和路徑規(guī)劃問題設(shè)計(jì)合適的編碼，能夠有效求解該問題。雖然改進(jìn)算法是有效的，但是無法破解群智能算法求解不唯一的難題，每次都只能找到一個(gè)較優(yōu)解，且無法復(fù)現(xiàn)。在這方面仍需要繼續(xù)改進(jìn)，繼續(xù)提高算法的搜索能力。

[1] Kennedyj, eberhartrc. Particleswarmoptim- ization[C]. IEEEInternationalConferenceonNeuralNetworks. Perth, Australia,1995:1942-1948.

[2] 劉浩然,崔靜闖,盧澤丹,等. 一種改進(jìn)的雁群擴(kuò)展粒子群算法研究[J].計(jì)量學(xué)報(bào),2019,40(03):498-504.

[3] 張?zhí)m勇,孟坤,劉勝,等. 基于改進(jìn)雙粒子群算法的艦船電力系統(tǒng)網(wǎng)絡(luò)故障重構(gòu)[J].電力系統(tǒng)保護(hù)與控制,2019, 47(09):90-96.

[4] 丁芳,宋小靜. 共享適應(yīng)度粒子群在雙機(jī)ETV中的應(yīng)用[J].計(jì)算機(jī)測(cè)量與控制,2018,26(11):228-232+247.

[5] 谷磊. 基于改進(jìn)粒子群算法優(yōu)化的車輛運(yùn)動(dòng)側(cè)傾控制研究[J]. 井岡山大學(xué)學(xué)報(bào):自然科學(xué)版,2018,39(06): 74-78.

[6] 肖根福,劉歡,李東洋,等. 一種求解大規(guī)模問題的自學(xué)習(xí)協(xié)同粒子群算法[J]. 井岡山大學(xué)學(xué)報(bào):自然科學(xué)版,2018(3):32-37.

[7] Angh, wuzj, rahnamay ANS, et al. Enhancing particles- warmoptimizationusing generalizedop- position- based learning[J]. InformationSciences, 2011, 181:4699-4714.

[8] 康嵐蘭,董文永,宋婉娟,等. 無慣性自適應(yīng)精英變異反向粒子群優(yōu)化算法[J].通信學(xué)報(bào),2017,38(08):66-78

[9] 周濤. 基于細(xì)菌趨化的改進(jìn)粒子群算法在電力系統(tǒng)無功優(yōu)化中的應(yīng)用[J].上海電力學(xué)院學(xué)報(bào),2014,30(4): 315-323.

[10] 曹生讓,丁曉群,王慶燕,等. 基于反向云自適應(yīng)粒子群算法的多目標(biāo)無功優(yōu)化[J]. 中國電力,2018,7(51): 21-27.

[11] 李帥. 基于電子商務(wù)的物流與供應(yīng)鏈網(wǎng)絡(luò)優(yōu)化問題研究[D].沈陽:沈陽理工大學(xué).2014.

Improved particle swarm optimization algorithm with multiple strategies and its application in Multi-level Logistics of E-commerce

*GUO Hai-feng, ZHANG Cui-ling

(School of Automation and Electrical Engineering, Shenyang Ligong University, Shenyang, Liaoning 110159, China)

In order to improve the ability of particle swarm optimization (PSO) to solve complex optimization problems, this paper improves the PSO algorithm based on bacterial chemotaxis (PSOBC). Aiming at the problem of slow convergence and low convergence of PSO in solving complexity problems, a general inverse learning strategy and adaptive inertia weight are combined with PSOBC algorithm to obtain an improved particle swarm optimization algorithm. The improved particle swarm optimization algorithm has greatly improved the development and exploration capabilities; it can quickly converge to the local optimum within the search capability when solving the complexity optimization problem, and increase the population density when it is small enough. The large population density is to perform global optimization. Finally, the improved algorithm is applied to the e-commerce multi-level logistics center location and path planning.

particle swarm optimization;reverse learning;adaptive inertia weight;logistics center location;path planning

1674-8085(2020)01-0048-06

TH16;F252

A

10.3969/j.issn.1674-8085.2020.01.010

2019-08-11；

2019-11-14

*郭海峰(1970-)，男，山東萊蕪人，教授，博士，主要從事先進(jìn)控制理論與應(yīng)用、物流與供應(yīng)鏈運(yùn)作技術(shù)等研究(E-mail:ghf_1970@163.com);

張翠玲(1996-)，女，河北省邢臺(tái)市人，碩士生，主要從事粒子群與物流優(yōu)化方面的研究(E-Mail:17363190519@163.com).