基于改进的鸟群算法求解农产品冷链物流配送路径优化问题

王进成 高岳林

摘要鸟群算法（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.