改进的粒子群算法在ｖｒｐ中的应用论文

《改进的粒子群算法在ｖｒｐ中的应用论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、改进的粒子群算法在ＶＲＰ中的应用论文摘要：运输调度问题在理论和实践方面都是一个难题。粒子群算法是一种可以解决复杂组合优化问题的有效求解算法。提出了改变惯性权重的粒子群算法，并应用该方法用于求解典型的运输调度问题，结果表明，所提出的方法不仅能得到理想的结果，而且减少运算时间。关键词：粒子群算法;运输调度;惯性权重中图分类号：O24文献标识码：A：1672-3198（2008）08-0393-021VRP的数学模型一般运输调度问题的文字描述：已知需求点的位置坐标和货物需求量，一个车队（有多个车辆）从一个供应点（配送中心）出发，每个需求点只被一辆车

2、访问，且该车所访问需求点的需求量总和不能超过车辆的负载能力.freelinZ=∑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,.freel个粒子组成的种群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，种

3、群的全局极值为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之间的随机数

4、，c1和c2为学习因子，建议将c1和c2取值为2。在上式中的第二部分被称为粒子本身的认知模式，而第三部分是粒子群中的群体模式。每个粒子的速度以及移动的位置，均受最大速度vmax和最大位置xmax的限制。一旦粒子更新后的速度和位置超出所限定的最大极限时，则需将其分别设定为vmax和xmax。主要针对速度更新公式(6)中的第一部分，期望给予vik一个惯性权重ax-ax-inkmax×k(9)式中ax为使用者设定的惯性权重上限值，in为惯性权重下限值，一般惯性权重axγ(xub-xlb)(10)式

5、中xub及xlb分别为搜索空间中变量的上、下限值，γ式用于取决搜索空间中最大速度的移动距离。采用最大速度限制加以约束后，使得粒子的搜索效果更好，并且可以减少不必要的计算时间。2.3改进粒子群算法流程第一步：设定初始值：最大迭代次数kmax，学习因子c1、c2，动态周期递减周期h，惯性权重以及最大速度动态系数α、β，初始最大速度vmax0，γ，惯性权重上限值ax，惯性权重下限值in，以及其它初始值。在搜索空间中，随机产生初始粒子群的速度v0及位置x0。第二步：对各粒子进行分析计算，根据所设定的目标函数与限制，进一步计

6、算各粒子的适应值。初始阶段的自身最佳解pi0即为各粒子的初始解xi0，而所有粒子自身最佳解中适应值最好的解即为整体最佳解pg0。第三步：利用自身最佳解pik以及整体最佳解pgk修正各粒子下一次搜索的速度，速度更新公式如式（8）,其中惯性权重采用动态调整策略。并根据该调整策略更新搜索速度，进一步更新各粒子的所处位置，其位置更新公式如式（7）所示。第四步：将更新后各粒子的适应值与自身最佳解的适应值进行比较，产生下一次迭代的自身最佳解pik+1。将整体最佳解与自身最佳解中适应值最佳的解进行比较，一旦自身最佳解中适应值最好的解优于整体最佳解，则需将下一

7、次迭代的整体最佳解pgk+1加以更新。第五步：若经过h次迭代后，整体最佳解的适应值仍然无法改善，则需根据将惯性权重和最大速度调整策略进行调整，如式（9）、（10）所示。第六步：若是满足终止条件则迭代停止，否则重复第三步，终止条件则是取决于最大迭代次数kmax。3实验分析引用一个常用的运输调度问题为例来测试算法。有8个需求点和一个供应点的系统，各个需求点对应供应点的需求量为qi(i=1,2,…,8)（单位为t）。供应点只有两辆车用于配送，每辆车的载重均为8吨，已知供应点与各个需求点之间的距离（单位为km）。算法由Matlab7.1仿

8、真，运行环境为Pentium4,2.0GHZ，内存为2G的微机上进行。用文献的遗传算法与本文的