基于改進(jìn)的鳥群算法求解農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化問題

王進(jìn)成 高岳林

摘要鳥群算法（BSA）在求解高維復(fù)雜的優(yōu)化問題時(shí)，很容易陷入局部極值，尤其在鳥群覓食過程中總會(huì)出現(xiàn)“早熟”現(xiàn)象。 針對(duì)原鳥群算法的不足，提出一種改進(jìn)的鳥群優(yōu)化算法（WBSA）。 通過仿真試驗(yàn)，結(jié)果表明，提出的算法具有較好的收斂速度和尋優(yōu)精度。 最后，通過對(duì)農(nóng)產(chǎn)品冷鏈物流配送優(yōu)化路徑模型的簡(jiǎn)化，構(gòu)建求解農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化問題的WBSA優(yōu)化算法，利用數(shù)值實(shí)例表明WBSA算法對(duì)此類問題具有可行性和有效性。

關(guān)鍵詞鳥群算法;自適應(yīng)隨機(jī)慣性權(quán)重;農(nóng)產(chǎn)品冷鏈物流配送;路徑優(yōu)化

中圖分類號(hào)S11文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)0517-6611（2018）25-0001-04

Optimization Problem of Cold Chain Logistics Distribution Path of Agricultural Products Based on Improved Algorithm of Bird Swarm Optimization

WANG Jincheng1， GAO Yuelin2

（1.School of Mathematics and Statistics， Ningxia University， Yinchuan，Ningxia 750021;2.Research Institute of Information and System Computation Science， North Minzu University， Yinchuan，Ningxia 750021）

AbstractBirds algorithm （BSA） is easy to fall into local extremum in solving the problem of optimization of highdimensional complex， especially it always appeared a “premature” phenomenon in the process of the flock foraging. Aiming at the shortcomings of the original algorithm of the flock， and an improved optimization algorithm （WBSA） birds was put forward. Based on the simulation experiment，results showed that the presented algorithm had better convergence speed and searching precision. In the end，through simplifying agricultural products cold chain logistics distribution optimization path model， WBSA optimization algorithm of agricultural products cold chain logistics distribution route optimization problem was built. The numerical examples showed that WBSA algorithm had the feasibility and validity of such problem.

Key wordsBird swarm algorithm;Adaptive random inertial weight;Cold chain logistics distribution of agricultural products;Path optimization

鳥群算法（BSA）是由Meng等[1-2]于2015年提出的一種新的基于群體智能的啟發(fā)式算法，具有運(yùn)算速度快、魯棒性好等優(yōu)點(diǎn)，因此，對(duì)于算法的改進(jìn)是一個(gè)重要的研究領(lǐng)域[3-5]，針對(duì)BSA算法的不足，提出一種改進(jìn)的鳥群優(yōu)化算法（WBSA）。通過將自適應(yīng)隨機(jī)慣性權(quán)重引入覓食過程，以增強(qiáng)個(gè)體全局尋優(yōu)能力和平衡種群全局搜索與局部搜索能力。冷鏈物流[6-7]是指新鮮冷凍類產(chǎn)品從生產(chǎn)到被消費(fèi)前的每個(gè)流通環(huán)節(jié)都需要在特定低溫環(huán)境下保存，從而保證產(chǎn)品新鮮度，降低產(chǎn)品變質(zhì)和損耗程度。所以如何科學(xué)地制定配送方案、合理地規(guī)劃配送路徑，從而保證農(nóng)產(chǎn)品的配送效率、產(chǎn)品的新鮮程度和低損耗率，這些對(duì)于冷鏈物流商來說尤為重要，也是農(nóng)產(chǎn)品在發(fā)展道路上需要解決的難題之一。為了驗(yàn)證所提出的WBSA算法的有效性和可行性，通過使用8個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)進(jìn)行數(shù)值試驗(yàn)，將WBSA算法與CSO、PSO和BSA算法進(jìn)行比較，結(jié)果表明，WBSA算法具有較好的收斂速度和尋優(yōu)精度。最后，通過對(duì)農(nóng)產(chǎn)品冷鏈物流配送優(yōu)化路徑模型的簡(jiǎn)化，運(yùn)用WBSA優(yōu)化算法求解農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化問題，通過數(shù)值實(shí)例表明WBSA算法對(duì)農(nóng)產(chǎn)品冷鏈物流配送優(yōu)化路徑模型具有可行性和有效性。

1標(biāo)準(zhǔn)鳥群算法

在現(xiàn)實(shí)世界中，大量的鳥類都是群居的，它們一起棲息、覓食以及成群地飛行。鳥群算法是模仿鳥類的飛行、覓食和警戒行為，這些行為都包含著一些簡(jiǎn)單的規(guī)則。假設(shè)鳥群中個(gè)體的數(shù)目為N，所有的鳥都在D維空間中覓食和飛行。第t時(shí)刻第i只鳥所在的位置表示為xti（i∈[1，2，3，…，N]）。

規(guī)則1：每只鳥的選擇依賴于一個(gè)0～1上的隨機(jī)數(shù)，在此同時(shí)設(shè)定一個(gè)常量p，當(dāng)隨機(jī)數(shù)小于p時(shí)，該鳥將尋找食物，否則，繼續(xù)保持警戒。

規(guī)則2：鳥群的覓食行為遵從自身的經(jīng)驗(yàn)及整個(gè)種群的經(jīng)驗(yàn)來尋找食物，則覓食行為的更新公式為：

xt+1i，j=xti，j+（pi，j-xti，j）×C×rand（0，1）+（gj-xti，j）×S×rand（0，1）（1）

式中，j∈[1，2，3，…，D]，rand（0，1）表示一個(gè)0～1之間均勻分布的隨機(jī)數(shù)，C和S為2個(gè)正數(shù)，分別稱為認(rèn)知加速系數(shù)和社交加速系數(shù)，pi，j表示第i只鳥先前的最優(yōu)位置，gi表示種群先前的最優(yōu)位置。

規(guī)則3：鳥群在保持警戒時(shí)，個(gè)體鳥會(huì)嘗試移動(dòng)至群體中心，鳥群之間并伴隨著與同類的競(jìng)爭(zhēng)，因而不會(huì)直接向中心移動(dòng)，則警戒行為的更新公式為：

xt+1i，j=xti，j+A1（meanj-xti，j）×rand（0，1）+A2（pk，j-xti，j）×rand（-1，1）（2）

A1=a1×exp（-pFitisumFit+ε×N）（3）

A2=a2+exp（（pFiti-pFitk|pFitk-pFiti|+ε）N×pFitksumFit+ε）（4）

式中，k（k≠i）是從1到N中隨機(jī)選取的正整數(shù)，a1和a2是[0，2]中的2個(gè)正常數(shù)，pFiti表示第i只鳥的最佳適應(yīng)度值，sumFit表示整個(gè)種群的最佳適應(yīng)度值之和，ε是計(jì)算機(jī)產(chǎn)生的最小常量，用來避免分母為零，meanj表示整個(gè)種群平均位置的第j個(gè)元素。A1描述的是每只鳥向鳥群中心移動(dòng)過程中由環(huán)境引發(fā)的間接作用，A2描述為由某個(gè)具體沖突而引發(fā)的直接作用。

規(guī)則4和5：鳥類可能飛到另一地點(diǎn)來響應(yīng)天敵威脅、覓食等。當(dāng)其飛行到一個(gè)新的位置，將在生產(chǎn)者和乞討者之間選擇，自行覓食或跟隨生產(chǎn)者獲取食物。飛行行為中生產(chǎn)者和乞討者的更新公式分別為：

xt+1i，j=xti，j+randn（0，1）×xti，j（5）

xt+1i，j=xti，j+（xtk，j-xti，j）×FL×rand（0，1）（6）

式中，randn（0，1）表示服從均值為0、標(biāo)準(zhǔn)差為1的高斯隨機(jī)分布，k∈[1，2，…，N]，k≠i，F(xiàn)L（FL∈[0，2]）表示乞討者跟隨生產(chǎn)者尋找食物。FQ表示鳥群飛行的時(shí)間間隔，F(xiàn)Q是一個(gè)正整數(shù)。

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

在BSA算法中當(dāng)鳥群處于覓食狀態(tài)時(shí)，很容易陷入局部極值點(diǎn)，為了更好地提高算法的搜索性能，將（0，1）均勻分布的隨機(jī)慣性權(quán)重引用于BSA算法中鳥類的覓食行為，使得個(gè)體既能在迭代初期能夠獲得較小的值，又能在迭代后期獲得較大的ω值。但是當(dāng)全局最優(yōu)解gj沒有發(fā)生變化時(shí)，希望隨機(jī)取得的ω值較大一些，加強(qiáng)搜索能力，如果取得較小的ω值，則可能會(huì)陷入局部最優(yōu)解。由以上對(duì)ω的分析，均勻分布的隨機(jī)ω取值應(yīng)該由gj的變化情況來確定。在該研究中，當(dāng)全局最優(yōu)解gj等于0時(shí)，ω取值為[0.4，0.9]，否則ω取值為[0，0.9]，表示如下：

ifΔgj=0ω=0.4+（0.9-0.4）×rand（0，1）（7）

elseω=0.9×rand（0，1）;（8）

在自適應(yīng)隨機(jī)慣性權(quán)重的BSA算法中，觀察位置x的變化情況，如果出現(xiàn)xi（t）=0，則方程（1）變?yōu)閤t+1i，j=（pi，j-xti，j） ×C×rand（0，1）+（gj-xti，j）×S×rand（0，1），即少了第1項(xiàng)，可以得出當(dāng)前位置與歷史位置無關(guān)，此時(shí)成為|pi-xi|和|gj-xi|的隨機(jī)組合，如果這兩項(xiàng)值很小，則xt+1i，j的值也很小，這使得個(gè)體的搜索范圍變小，容易陷入局部極值。為了避免這種情況的發(fā)生，當(dāng)個(gè)體的每維位置都為0時(shí)，以一定的概率隨機(jī)選擇其中某維，改變其位置值，表示如下：

ifxi=0&rand（0，1）

j=rand（0，1）×maxnum;xij=rand（0，1）×maxxj（10）

通過以上分析可得，改進(jìn)后的覓食公式為：

xt+1i，j=ω×xti，j+（pi，j-xti，j）×C×rand（0，1）+（gj-xti，j）×S×rand（0，1）（11）

3結(jié)果與分析

為驗(yàn)證WBSA算法的性能，選取8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)[8-10]，其中Sphere model、Schwefels problem2.22、Schwefels problem 1.2、Schwefels problem 2.21和GeneralizedRosenbroc -ks function均為高維單峰函數(shù)，Generalized Rastrigins function、Ackleys function和Generalized Griewank function均為高維多峰函數(shù)，將WBSA算法與CSO、PSO和BSA算法進(jìn)行對(duì)比，每個(gè)測(cè)試函數(shù)分別在4種算法上獨(dú)立運(yùn)行30次，種群個(gè)體數(shù)設(shè)置為40，CSO、PSO、BSA和WBSA算法相關(guān)參數(shù)設(shè)置如表1所示，記錄試驗(yàn)結(jié)果如表2所示，試驗(yàn)都是在win7系統(tǒng)matlab 2012a中完成的。

3.1尋優(yōu)結(jié)果比較

將每個(gè)測(cè)試函數(shù)分別在4種算法上獨(dú)立運(yùn)行30次，記錄每次運(yùn)行結(jié)果的最差解、最佳解、平均值和方差（表2），表中的加粗字體為4種算法得到的最好結(jié)果。對(duì)于函數(shù)F1、F2、F3和F4，CSO和PSO算法所得的結(jié)果遠(yuǎn)遠(yuǎn)大于BSA和WBSA算法，而WBSA算法在BSA算法的基礎(chǔ)上進(jìn)一步提高了解的質(zhì)量;在函數(shù)F5和F6上，由于測(cè)試函數(shù)本身的復(fù)雜性，4個(gè)算法都很難收斂到全局最優(yōu)解且CSO、PSO和BSA算法都未能很好地找到全局最優(yōu)解，而WBSA比其他3種算法的尋優(yōu)精度都要高;對(duì)于函數(shù)F7和F8，CSO和PSO算法的尋優(yōu)精度遠(yuǎn)遠(yuǎn)大于BSA和WBSA算法的尋優(yōu)精度，并且BSA和WBSA算法都找到了較好的全局最優(yōu)解。綜上所述，WBSA算法在8個(gè)測(cè)試函數(shù)上的搜索能力顯著優(yōu)于CSO、PSO和BSA算法。

4運(yùn)用WBSA算法求解農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化模型

4.1模型簡(jiǎn)化

假設(shè)配送貨物中心有載重量為Q的輛車向L個(gè)需求點(diǎn)進(jìn)行送貨，已知需求點(diǎn)的需求量qi（i=1，2，…，L）、運(yùn)送距離dij以及每一輛車一次配送的距離D，d0，j（i，j=1，2，…，L）表示配送中心到需求點(diǎn)的距離，再設(shè)nk表示第k輛車配送的顧客數(shù)（nk=0表示未使用第k輛汽車），令rk0表示配送中心，rki表示需求點(diǎn)在路徑k中的順序?yàn)閕，通過以上模型的簡(jiǎn)化可以建立以下農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化問題的數(shù)學(xué)模型：

minZ=Kk=1[nki=1drk（i-1）rki+drnkrk0×f（nk）]（12）

約束條件如下：

nki=1qrki≤Q（13）

nki=1Drk（i-1）rki+drnkrk0×f（nk）≤D（14）

0≤nk≤L（15）

Kk=1nk=L（16）

f（nk）=1nk≥10其他（17）

在上述模型中，式（12）表示該模型的目標(biāo)函數(shù)，以配送線路最短為優(yōu)化目標(biāo);式（13）表示每輛車載重量的約束;式（14）表示每車輛配送中最大行駛距離的約束;式（15）表示每條路徑上需求點(diǎn)數(shù)的約束;式（16）表示每個(gè)需求點(diǎn)都被服務(wù);式（17）表示為當(dāng)nk≥1時(shí)，取f（nk），當(dāng)nk<1時(shí)，取f（nk）=0。

4.2農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化問題的WBSA算法步驟

Step1：采用實(shí)數(shù)編碼初始化，將20個(gè)需求點(diǎn)使用4輛車進(jìn)行配送，用1到20的實(shí)數(shù)排列來表示個(gè)體的位置，隨機(jī)生成初始化種群，產(chǎn)生20個(gè)隨機(jī)數(shù)，由4輛車分別給4組需求點(diǎn)進(jìn)行送貨。

Step2：計(jì)算適應(yīng)度和約束條件，對(duì)于每條線路，使用最鄰近法優(yōu)化配送線路。根據(jù)式（12）計(jì)算個(gè)體的目標(biāo)函數(shù)值Z，在約束條件中每輛車的載量不超過8 t，配送的距離不超過60 km。

Step3：初始化局部最優(yōu)值和全局最優(yōu)值，若當(dāng)前各個(gè)體的適應(yīng)度值是初始化局部最優(yōu)值和所有局部最優(yōu)值中適應(yīng)度值最優(yōu)的適應(yīng)度值是全局最優(yōu)值，則所對(duì)應(yīng)的個(gè)體為最優(yōu)解。

Step4：根據(jù)公式（11）、（2）、（5）和（6）更新個(gè)體的位置。

Step5：判斷迭代終止條件。若滿足則輸出最優(yōu)路徑和適應(yīng)度值，否則，返回步驟Step4繼續(xù)更新位置。

4.3數(shù)值實(shí)例

某城市農(nóng)產(chǎn)品冷鏈物流配送中心，需要向其20個(gè)需求點(diǎn)進(jìn)行配送貨物，配送中心的配送車輛的裝載質(zhì)量不超過8 t;每一輛車一次配送的距離不超過60 km;共4輛車來完成20個(gè)需求點(diǎn)的配送任務(wù)。根據(jù)上述實(shí)例的特點(diǎn)，利用win7系統(tǒng)matlab 2012a進(jìn)行編程，最大迭代次數(shù)設(shè)置為1000次和WBSA算法的相關(guān)參數(shù)，隨機(jī)產(chǎn)生需求點(diǎn)的需求量和運(yùn)送距離，得到計(jì)算結(jié)果見表3。

經(jīng)過10次仿真試驗(yàn)，得到該問題的最優(yōu)解為182.4 km，其對(duì)應(yīng)的配送路徑分別為：路徑1：1-2-4-6-11;路徑2：5-7-8-10-13-19;路徑3：3-9-14-15-17;路徑4：12-16-18-20。結(jié)果表明，WBSA算法具有較好的優(yōu)化能力，能夠很好地對(duì)農(nóng)產(chǎn)品冷鏈物流配送路徑進(jìn)行優(yōu)化，為解決此類問題提供了方便。

5結(jié)論

在求解高維復(fù)雜的優(yōu)化問題時(shí)，鳥群算法很容易陷入局部極值，并且在鳥群覓食的過程中總會(huì)出現(xiàn)“早熟”現(xiàn)象，針對(duì)原鳥群算法存在的缺陷，提出一種改進(jìn)的鳥群優(yōu)化算法。將自適應(yīng)隨機(jī)慣性權(quán)重引入覓食過程，從而平衡種群全局搜索與局部搜索能力。通過對(duì)8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試，結(jié)果表明，WBSA算法可以有效地增強(qiáng)收斂速度，提高尋優(yōu)精度。最后，對(duì)農(nóng)產(chǎn)品冷鏈物流配送優(yōu)化路徑模型的簡(jiǎn)化，運(yùn)用WBSA優(yōu)化算法求解農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化問題。通過數(shù)值實(shí)例表明WBSA算法對(duì)農(nóng)產(chǎn)品冷鏈物流配送優(yōu)化路徑模型具有可行性和有效性。因此，WBSA算法對(duì)解決此類問題具有很好的現(xiàn)實(shí)意義。

參考文獻(xiàn)

[1] MENG X B，LIU Y，GAO X Z，et al.A new bioinspired algorithm：Chicken swarm optimization[C]//5th international conference on swarm intelligence.Hefei：SpringerInternational Publishing，2014：74-85.

[2] MENG X B，GAO X Z，LU L H，et al.A new bioinspired optimisation algorithm：Bird swarm algorithm[J].Journal of experimental & theoretical artificial intelligence，2016，28（4）：673-687.

[3] MENG X B，LIU Y，GAO X Z，et al.A new bioinspired algorithm：Chicken swarm optimization[C]//TAN Y，SHI Y H，COELLO C A.Advances in swarm intelligence：5th international conference.Heifei，China：ICSI，2014：86-94.

[4] 崔東文，金波.鳥群算法-投影尋蹤回歸模型在多元變量年徑流預(yù)測(cè)中的應(yīng)用[J].人民珠江，2016，37（11）：26-30.

[5] LENIN K，REDDY D B R，KALAVATHI M S.Snow finch bird swarm optimization algorithm for solving reactive power problem [C]//International journal of mathematical engineering & management sciences.[s.l.]：[s.n.]，2016.

[6] 向敏，袁嘉彬，于潔.電子商務(wù)環(huán)境下鮮活農(nóng)產(chǎn)品物流配送路徑優(yōu)化研究[J].科技管理研究，2015，35（18）：166-171.

[7] 蔡浩原，潘郁.基于人工蜂群算法的鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化[J]. 江蘇農(nóng)業(yè)科學(xué)，2017，45（15）：318-321.

[8] 高宏進(jìn)，王力.一種基于動(dòng)態(tài)慣性權(quán)重的鳥群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2019，36（5）[2018-04-28].http：//www.arocmag.com/article/02-2019-05-020.html.

[9] 肖海軍，盧常景，何凡.基于鳥群算法的SVM參數(shù)選擇[J].中南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，36（3）：90-94.

[10] 劉曉龍，寧芊，趙成萍，等.基于萊維飛行的鳥群優(yōu)化算法 [J].計(jì)算機(jī)測(cè)量與控制，2016，24（12）：194-197.