基于改進的鳥群算法求解農產品冷鏈物流配送路徑優化問題

王進成 高岳林

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

關鍵詞鳥群算法;自適應隨機慣性權重;農產品冷鏈物流配送;路徑優化

中圖分類號S11文獻標識碼A文章編號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年提出的一種新的基于群體智能的啟發式算法，具有運算速度快、魯棒性好等優點，因此，對于算法的改進是一個重要的研究領域[3-5]，針對BSA算法的不足，提出一種改進的鳥群優化算法（WBSA）。通過將自適應隨機慣性權重引入覓食過程，以增強個體全局尋優能力和平衡種群全局搜索與局部搜索能力。冷鏈物流[6-7]是指新鮮冷凍類產品從生產到被消費前的每個流通環節都需要在特定低溫環境下保存，從而保證產品新鮮度，降低產品變質和損耗程度。所以如何科學地制定配送方案、合理地規劃配送路徑，從而保證農產品的配送效率、產品的新鮮程度和低損耗率，這些對于冷鏈物流商來說尤為重要，也是農產品在發展道路上需要解決的難題之一。為了驗證所提出的WBSA算法的有效性和可行性，通過使用8個標準的測試函數進行數值試驗，將WBSA算法與CSO、PSO和BSA算法進行比較，結果表明，WBSA算法具有較好的收斂速度和尋優精度。最后，通過對農產品冷鏈物流配送優化路徑模型的簡化，運用WBSA優化算法求解農產品冷鏈物流配送路徑優化問題，通過數值實例表明WBSA算法對農產品冷鏈物流配送優化路徑模型具有可行性和有效性。

1標準鳥群算法

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

規則1：每只鳥的選擇依賴于一個0～1上的隨機數，在此同時設定一個常量p，當隨機數小于p時，該鳥將尋找食物，否則，繼續保持警戒。

規則2：鳥群的覓食行為遵從自身的經驗及整個種群的經驗來尋找食物，則覓食行為的更新公式為：

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）表示一個0～1之間均勻分布的隨機數，C和S為2個正數，分別稱為認知加速系數和社交加速系數，pi，j表示第i只鳥先前的最優位置，gi表示種群先前的最優位置。

規則3：鳥群在保持警戒時，個體鳥會嘗試移動至群體中心，鳥群之間并伴隨著與同類的競爭，因而不會直接向中心移動，則警戒行為的更新公式為：

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中隨機選取的正整數，a1和a2是[0，2]中的2個正常數，pFiti表示第i只鳥的最佳適應度值，sumFit表示整個種群的最佳適應度值之和，ε是計算機產生的最小常量，用來避免分母為零，meanj表示整個種群平均位置的第j個元素。A1描述的是每只鳥向鳥群中心移動過程中由環境引發的間接作用，A2描述為由某個具體沖突而引發的直接作用。

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

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、標準差為1的高斯隨機分布，k∈[1，2，…，N]，k≠i，FL（FL∈[0，2]）表示乞討者跟隨生產者尋找食物。FQ表示鳥群飛行的時間間隔，FQ是一個正整數。

2改進的鳥群優化算法

在BSA算法中當鳥群處于覓食狀態時，很容易陷入局部極值點，為了更好地提高算法的搜索性能，將（0，1）均勻分布的隨機慣性權重引用于BSA算法中鳥類的覓食行為，使得個體既能在迭代初期能夠獲得較小的值，又能在迭代后期獲得較大的ω值。但是當全局最優解gj沒有發生變化時，希望隨機取得的ω值較大一些，加強搜索能力，如果取得較小的ω值，則可能會陷入局部最優解。由以上對ω的分析，均勻分布的隨機ω取值應該由gj的變化情況來確定。在該研究中，當全局最優解gj等于0時，ω取值為[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）

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

ifxi=0&rand（0，1）

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

通過以上分析可得，改進后的覓食公式為：

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

3結果與分析

為驗證WBSA算法的性能，選取8個標準測試函數[8-10]，其中Sphere model、Schwefels problem2.22、Schwefels problem 1.2、Schwefels problem 2.21和GeneralizedRosenbroc -ks function均為高維單峰函數，Generalized Rastrigins function、Ackleys function和Generalized Griewank function均為高維多峰函數，將WBSA算法與CSO、PSO和BSA算法進行對比，每個測試函數分別在4種算法上獨立運行30次，種群個體數設置為40，CSO、PSO、BSA和WBSA算法相關參數設置如表1所示，記錄試驗結果如表2所示，試驗都是在win7系統matlab 2012a中完成的。

3.1尋優結果比較

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

4運用WBSA算法求解農產品冷鏈物流配送路徑優化模型

4.1模型簡化

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

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）表示該模型的目標函數，以配送線路最短為優化目標;式（13）表示每輛車載重量的約束;式（14）表示每車輛配送中最大行駛距離的約束;式（15）表示每條路徑上需求點數的約束;式（16）表示每個需求點都被服務;式（17）表示為當nk≥1時，取f（nk），當nk<1時，取f（nk）=0。

4.2農產品冷鏈物流配送路徑優化問題的WBSA算法步驟

Step1：采用實數編碼初始化，將20個需求點使用4輛車進行配送，用1到20的實數排列來表示個體的位置，隨機生成初始化種群，產生20個隨機數，由4輛車分別給4組需求點進行送貨。

Step2：計算適應度和約束條件，對于每條線路，使用最鄰近法優化配送線路。根據式（12）計算個體的目標函數值Z，在約束條件中每輛車的載量不超過8 t，配送的距離不超過60 km。

Step3：初始化局部最優值和全局最優值，若當前各個體的適應度值是初始化局部最優值和所有局部最優值中適應度值最優的適應度值是全局最優值，則所對應的個體為最優解。

Step4：根據公式（11）、（2）、（5）和（6）更新個體的位置。

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

4.3數值實例

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

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

5結論

在求解高維復雜的優化問題時，鳥群算法很容易陷入局部極值，并且在鳥群覓食的過程中總會出現“早熟”現象，針對原鳥群算法存在的缺陷，提出一種改進的鳥群優化算法。將自適應隨機慣性權重引入覓食過程，從而平衡種群全局搜索與局部搜索能力。通過對8個標準測試函數進行測試，結果表明，WBSA算法可以有效地增強收斂速度，提高尋優精度。最后，對農產品冷鏈物流配送優化路徑模型的簡化，運用WBSA優化算法求解農產品冷鏈物流配送路徑優化問題。通過數值實例表明WBSA算法對農產品冷鏈物流配送優化路徑模型具有可行性和有效性。因此，WBSA算法對解決此類問題具有很好的現實意義。

參考文獻

[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] 崔東文，金波.鳥群算法-投影尋蹤回歸模型在多元變量年徑流預測中的應用[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] 向敏，袁嘉彬，于潔.電子商務環境下鮮活農產品物流配送路徑優化研究[J].科技管理研究，2015，35（18）：166-171.

[7] 蔡浩原，潘郁.基于人工蜂群算法的鮮活農產品冷鏈物流配送路徑優化[J]. 江蘇農業科學，2017，45（15）：318-321.

[8] 高宏進，王力.一種基于動態慣性權重的鳥群優化算法[J].計算機應用研究，2019，36（5）[2018-04-28].http：//www.arocmag.com/article/02-2019-05-020.html.

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

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