粒子群算法优化研究

丁艳 管燕明

[提要] 粒子群算法控制参数较少、使用简单，受到很多专家学者的关注。但是，传统粒子群算法在求解非线性规划问题时，比较容易陷入局部最优而找不到全局最优解。本文在算法设计过程中，对传统的粒子群算法进行改进，以提高求解效果。

关键词：非线性规划；粒子群算法；回收网络

中图分类号：F27 文献标识码：A

收录日期：2017年11月28日

一、引言

粒子群算法（Particle Swarm Optimization，PSO）为常见优化算法，是一种模拟鸟类觅食过程来寻求最优解的算法，很多问题的优化都可以使用，如核动力、车辆调度、巡回旅行等。因控制参数少、使用简单、易实现，粒子群算法受到很多专家学者的关注。但是传统粒子群算法在求解非线性规划问题时，比较容易陷入局部最优而找不到全局最优解，本文在传统的粒子群算法上进行了改进，以提高求解效果。

二、粒子群算法介绍

粒子群算法（PSO）是一种基于群体的随机优化方法。传统的粒子群算法思路如下：

设S在维目标搜索空间中，有m个微粒组成一个群体，那么其中粒子i可以表示为一个S维的向量xi=（xi1，xi2，…，xis），i=1，2，…，m。同理，群体中的每个粒子都可以以同样的方式表示，每个粒子的位置就是一个可行解。将其预先设定的目标函数来计算每一个粒子的适应值，并根据适应值大小来衡量粒子所在位置的优劣程度。在搜索空间中第i个粒子的飞翔速度也是一个S维向量，记为V=（v1，v2，…，vs）。除了粒子的飞行位置和飞行速度以外，还需要记录两个重要的信息：第i个粒子迄今为止搜索到的最优位置为PbestiS=（Pbesti1，Pbesti2，…，Pbesti3）；整个粒子群迄今为止搜索到的最优位置为GbestS=（Gbest1，Gbest2，…，Gbest3）。设f（x）为目标函数，则微粒当前最好位置由下式确定：

p（t+1）=pi（t） 若f（xi（t+1））≥f（pi（t））xi（t+1） 若f（xi（t+1））≤f（pi（t））

在基础上进行微粒飞行迭代为两步操作：位置移动和速度变化，基本迭代公式分别为：

v（t+1）=v（t）+c1·（Gbest[]-present[]）+c2·（Pbest-p（t）） （1）

x（t+1）=x（t）+v（t+1） （2）

其中，学习因子c1、c2为非负常数，c1调节粒子飞向自身最好位置方向的步长，c2调节粒子飞向全局最好位置方向的步长。r1、r2为相互独立的伪随机数，服从[0，1]上的均匀分布。

经典的PSO算法步骤如下：

Step1：初始化一个规模为m的粒子群，并设定各个微粒的初始位置和速度。

Step2：设置适应度函数并计算每个微粒的适应值。

Step3：把每个微粒的适应值与其经历过的最好位置时的适应值作比较，若当前微粒所在位置的适应值较好，则将其作为微粒当前的最好位置。

Step4：把每个微粒的适应值与整个粒子群经历过的最好位置时的适应值作比较，若当前微粒所在位置的适应值较好，则将其作为当前的粒子群全局的最好位置。

Step5：根据方程（1）、（2）分别对粒子的速度和位置进行更新。

Step6：如果满足终止条件，则输出最优解；否则返回Step2。

三、改进的粒子群算法设计

基本粒子群算法在求解非线性规划问题时，比较容易陷入局部最优而找不到全局最优解，因此，本文在算法设计过程中，对传统的粒子群算法进行了改进，以提高求解效果。改进的算法分别采用强引导型粒子群算法和自适应粒子群算法对原有位置、速度迭代公式进行优化，对式（1）、（2）进行改进，使改进的位置迭代公式为：

x（t+1）=x（t）+（rand（）+k）·v（t）+10-6·rand（）

其中，rand（）为0～1之间的随机数，k为调节系数，随着迭代次数的增加，调节系数逐渐降低，可取k=kmax-·iter，其中iter表示迭代次数。速度更新采用自适应速度更新公式，在传统的速度更新公式中随迭代次数改变？棕，例如迭代100次，可取：

？棕=0.5 1≤gen≤400.1 40≤gen≤600.001 60≤gen≤100

速度更新公式可表示为：

v（）=？棕·v（）+c1·rand（）·（Gbest[]-present[]）+c2·rand（）（Pbest-present[]）

其中，学习因子c1和c2为常数，避免粒子陷入局部最优并实现信息共享，以保证粒子的空间搜索能力，数值大小设置具体应视情况而定。

（一）粒子的编码形式。编码过程是整个算法设计过程中的难点之一，高效的编码方式能够大大减轻模型运算的难度，提高模型求解效率，因此编码的设计十分关键。再制造物流网络中参数较多，编码过程需要把每个变量进行合理编码，以保证在交叉迭代过程中解得可行性，并保证迭代效率。主要的编码设计思路为：分派过程中对粒子进行实数编码，根据分派比例设定粒子的每一个分向量，如对I个回收点、J个仓储点、K个分拣点的编码可采用如下形式：

（x1，1…xi，j…xI，J||y1，1…yj，k…yJ，K||z1，1…zk，s…zK，S||v1，1…vi，j…vI，J||u1，1…uj，k…uJ，K||w1，1…wk，s…wK，S）x代表从回收点到仓库段粒子的位置，y代表从仓库到分拣中心段粒子的位置，z代表从分拣中心到再制造中心段粒子的位置，v代表x的变化速度，u代表y的变化速度，w代表z的变化速度，分拣中心到再利用中心的费用另外计算。

选址过程对粒子进行实数编码，每一项代表各后选点建立仓库或分拣中心的大小，若为0，表示此处将不建立物流节点。因此，J个仓库备选点和K个分拣中心备选点的编码为：

（x1，x2…xJ||y1，y2…yK||v1，v2…vJ||u1，u2…uK）

（二）粒子群规模和终止条件。由于粒子群算法有较强的收敛性和全局搜索能力，理论上粒子群规模较大能提高搜索效率，但考虑到计算机运算的复杂度，把粒子群体规模范围设置在50～100之间可以达到理想效果。终止条件以迭代次数达到预先给定值时程序终止，一般可以设置迭代次数为100次。

四、实例验算

假设某第三方企业需要建立一条废旧物品回收再制造网络。该企业回收3种废旧物品，建立5个废旧物品回收中心，有2个存储中心候选点，拥有3家再制造客户企业和2个分拣中心候选点。其中新建存储中心10元/m2的单位维修费，15元/单位的分拣中心单位维修费，3种废旧物在5个回收点的回收数量分别为：1（260，240，360），2（290，370，380），3（380，260，380），4（270，390，280），5（270，300，340）；客户企业回收各种物品的数量：C1（20，68，30），C2（18，28，20），C3（89，12，54）；各个物流节点之间的运输费率：回收点至存储/分拣点运输费率为：H1（0.13，0.21，0.06）/（0.10，0.07，0.06），H2（0.14，0.12，0.16）/（0.24，0.22，0.19），H3（0.24，0.18，0.09）/（0.13，0.07，0.24），H4（0.12，0.1，0.05）/（0.13，0.07，0.07），H5（0.22，0.23，0.19）/（0.17，0.16，0.18）；分拣点至客户企业运输费率：1-1（0.09，0.08，0.16），1-2（0.07，0.04，0.15），2-1（0.17，0.05，0.08），2-2（0.17，0.22，0.09），3-1（0.05，0.13，0.09），3-2（0.21，0.08，0.14）；存储点至分拣点运输费率：1-1（0.19，0.08，0.16），1-2（0.07，0.14，0.5），2-1（0.17，0.08，0.08），2-2（0.05，0.22，0.19）；其他各种费率：3种废旧物品的利润率（元/件）分别为（150，130，100），（4，3，1）为分拣中心废弃率（%），（1，7，3）为存储中心物品废弃率（%）。

（一）目标函数

maxh（X）=Q+O-T-W-B+A+C+D+P

（二）约束条件。约束条件可表示为：

可得各物流节点的容量为：2924和2201为存储点I的存储容量（m3），1636和1082为分拣点J的分拣量。

五、结论

鉴于传统粒子群算法在求解非线性规划问题时，比较容易陷入局部最优而找不到全局最优解，因此，本文在算法设计过程中，对传统的粒子群算法进行了改进，对第三方废旧物品回收企业建立一条物品再制造回收网络进行求解，结果显示改进的粒子群算法具有更好的效果。

主要参考文献：

[1]刘建华.粒子群算法的基本理论及其改进研究[D].长沙：中南大学，2009.

[2]刘成洋，阎昌琪.粒子群遗传算法及其应用[J].核动力工程，2012.33.4.

[3]李雅琼.基于粒子群算法的遗传算法优化研究[J].兰州文理学院学报（自然科学版），2017.31.1.

[4]黄太安，生佳根.一种改进的简化粒子群算法[J].计算机仿真，2013.30.2.

[5]蒲兴成.基于改进粒子群算法的移动机器人多目标点路径规划[J].智能系统学报，2017.12.6.