改进的粒子群算法在ＶＲＰ中的应用

摘 要：运输调度问题在理论和实践方面都是一个难题。粒子群算法是一种可以解决复杂组合优化问题的有效求解算法。提出了改变惯性权重的粒子群算法，并应用该方法用于求解典型的运输调度问题，结果表明，所提出的方法不仅能得到理想的结果，而且减少运算时间。
　　关键词：粒子群算法;运输调度;惯性权重
　　中图分类号：O24文献标识码：A文章编号：1672-3198（2008）08-0393-02
　　
　　1 VRP的数学模型
　　
　　一般运输调度问题的文字描述：已知需求点的位置坐标和货物需求量，一个车队（有多个车辆）从一个供应点（配送中心）出发，每个需求点只被一辆车访问，且该车所访问需求点的需求量总和不能超过车辆的负载能力，应如何安排车辆的行走路线使得总路线最短。要求：每辆车运输完毕后回到出发点（供应点）。设供应点有K辆车，每辆车的载重为Qk（k=1，2…K），需求点个数为L，每个需求点的需求量为qi（i=1，2...，L）;需求点i到j的距离为qi（i，j=0，1，2...，L，其中i=0或j=0表示该点为供应点）；第k辆车访问的需求点个数为nk(nk=0表示未使用第k辆车)；用集合Rk表示第k辆车的行驶路线，rki代表Rk中一个需求点，它在路线Rk中的顺序为i，rk0表示供应点。借鉴的数学模型：
　　minZ=∑kk=1nk-1i=0drkirk(i+1)+drknkrk0（1）
　　∑nki=1qrn≤Qk，0≤nk≤L（2）
　　0kk=1nk=L（3）
　　Rk=rki｜rki∈1，2…，L，i=1，2 …nk，Rk1∩Rk2=，k1≠k2(4)
　　sign(nk)=1nk≥10其他(5)
　　其中式（1）为目标函数；式（2）保证每条路径上各需求点需求量之和不超过汽车的重量并表明每条路径上的需求点数不超过总需求点数；式（3）表明每个需求点都得到配送服务；式（4）为每条路径的需求点的组成并且限制每个需求点仅能由一辆汽车送货；式（5）表明当第K辆汽车服务的客户数大于或等于1时。该车参加了配送，此时取sign(nk)=1，当第K辆汽车服务的客户数小于1时，表示未使用该车，取sign(nk)=0。
　　上述数学模型的最终优化目标就是：在满足以上各种约束条件的情况下，使得所有车辆路径之和Z最小。
　　
　　2 粒子群优化算法
　　
　　2.1 标准粒子群算法
　　设在一个n维的搜索空间中，由m个粒子组成的种群X={x1，…x2，…xm}，其中第i个粒子位置为xi=(xi1，xi2，…，xim)T，其速度为vi=(vi1，vi2，…，vin)T。它的个体极值为pi=(pi1，pi2，…，pin)T，种群的全局极值为pg=(pg1，pg2，…，pgn)T。按追随当前最优粒子的原理，粒子xi将按(6)、(7)式改变速度和位置。
　　vik+1=vik+c1r1(pik-xik)+c2r2(pgk-xik)（6）
　　xik+1=xik+vik+1（7）
　　其中，k为迭代次数，vik及xik分别为粒子i在第k次迭代的速度与位置，而pik则是粒子i在第k次迭代的自身最佳解，pgk为第k次迭代的整体最佳解，其更新后粒子i在第k+1次迭代的速度为vik+1，xik+1则是粒子i在第k+1次迭代的位置，r1、r2为介于0~1之间的随机数，c1和c2为学习因子，建议将c1和c2取值为2。在上式中的第二部分被称为粒子本身的认知模式，而第三部分是粒子群中的群体模式。每个粒子的速度以及移动的位置，均受最大速度vmax和最大位置xmax的限制。一旦粒子更新后的速度和位置超出所限定的最大极限时，则需将其分别设定为vmax和xmax。
　　主要针对速度更新公式(6)中的第一部分，期望给予vik一个惯性权重w，测量出粒子本身搜索最佳解的能力，加入惯性权重w之后速度更新公式如下所示：
　　vik+1=wvik+c1r1pik-xik+c2r2(pgk-xik)（8）
　　式中w为一常数，为提供各粒子速度vik的一个移动比例，对于各粒子而言，该权重可以调整速度vik的移动速度大小。当惯性权重w较大时，决定粒子下一次搜索方向的主要影响因素为vik，所以粒子会呈现较稳定的搜索路径，进而表现出较好的全局搜索特性。反之，如果惯性权重w较小时，则会受到vik、自身最佳解pbest与整体最佳解gbest等三种因素的影响，出现搜索路径不稳定的现象，仅能发挥出局部搜索的能力。 转贴于
　　2.2 改进的粒子群算法
　　为了解决不易选取合理的惯性权重的困难，本文提出将惯性权重以线性递减方式加以考虑的方法，即将式(8)中的w由下列式子决定：
　　w=wmax-wmax-wminkmax×k(9)
　　式中wmax为使用者设定的惯性权重上限值，wmin为惯性权重下限值，一般惯性权重w的范围为0.8~1.4。通过添加线性惯性权重使得初始搜索阶段具有较高的惯性权重值，从而保证搜索初期全局搜索的灵活性，随着迭代过程的进行逐渐降低惯性权重，转入局部搜索，加强粒子局部搜索能力。
　　为了避免各粒子在使用式(7)后产生过大移动步幅，给各粒子最大移动速度进行限制，其最大速度计算公式如下所示：
　　vmaxγ(xub-xlb)(10)
　　式中xub及xlb分别为搜索空间中变量的上、下限值，γ式用于取决搜索空间中最大速度的移动距离。采用最大速度限制加以约束后，使得粒子的搜索效果更好，并且可以减少不必要的计算时间。
　　2.3 改进粒子群算法流程
　　第一步：设定初始值：最大迭代次数kmax，学习因子c1、c2，动态周期递减周期h，惯性权重以及最大速度动态系数α、β，初始最大速度vmax0，γ，惯性权重上限值wmax，惯性权重下限值wmin，以及其它初始值。在搜索空间中，随机产生初始粒子群的速度v0及位置x0。
　　第二步：对各粒子进行分析计算，根据所设定的目标函数与限制，进一步计算各粒子的适应值。初始阶段的自身最佳解pi0即为各粒子的初始解xi0，而所有粒子自身最佳解中适应值最好的解即为整体最佳解pg0。
　　第三步：利用自身最佳解pik以及整体最佳解pgk修正各粒子下一次搜索的速度，速度更新公式如式（8），其中惯性权重采用动态调整策略。并根据该调整策略更新搜索速度，进一步更新各粒子的所处位置，其位置更新公式如式（7）所示。
　　第四步：将更新后各粒子的适应值与自身最佳解的适应值进行比较，产生下一次迭代的自身最佳解pik+1。将整体最佳解与自身最佳解中适应值最佳的解进行比较，一旦自身最佳解中适应值最好的解优于整体最佳解，则需将下一次迭代的整体最佳解pgk+1加以更新。
　　第五步：若经过h次迭代后，整体最佳解的适应值仍然无法改善，则需根据将惯性权重和最大速度调整策略进行调整，如式（9）、（10）所示。
　　第六步：若是满足终止条件则迭代停止，否则重复第三步，终止条件则是取决于最大迭代次数kmax。
　　
　　3 实验分析
　　
　　引用一个常用的运输调度问题为例来测试算法。有8个需求点和一个供应点的系统，各个需求点对应供应点的需求量为qi(i=1，2，…，8)（单位为t）。供应点只有两辆车用于配送，每辆车的载重均为8吨，已知供应点与各个需求点之间的距离（单位为km）。算法由Matlab 7.1仿真，运行环境为Pentium 4，2.0GHZ，内存为2G的微机上进行。用文献的遗传算法与本文的改进粒子群算法相比较，两种算法在结论上的差异是很明显的，另外达到最优路径的迭代时间，改进粒子群算法为4.52S ；遗传算法为5.68S。实验证明本算法的可行性。