翻新时间:2023-03-15
改进的粒子群算法在VRP中的应用
摘 要:运输调度 问题 在 理论 和实践方面都是一个难题。粒子群算法是一种可以解决复杂组合优化问题的有效求解算法。提出了改变惯性权重的粒子群算法,并 应用 该 方法 用于求解典型的运输调度问题,结果表明,所提出的方法不仅能得到理想的结果,而且减少运算时间。
关键词:粒子群算法;运输调度;惯性权重
1 VRP的数学模型
minZ=∑kk=1nk-1i=0drkirk(i+
1)+drknkrk0
(1) 0kk=1nk=L
(3) sign(nk)=1nk≥10其他
(5) 上述数学模型的最终优化目标就是:在满足以上各种约束条件的情况下,使得所有车辆路径之和Z最小。
2 粒子群优化算法
2.1 标准粒子群算法 vik+1=vik+c1r1(pik-xik)+c2r2(pgk-xik)
(6)
xik+1=xik+vik+1
(7) 主要针对速度更新公式
(6)中的第一部分,期望给予vik一个惯性权重w,测量出粒子本身搜索最佳解的能力,加入惯性权重w之后速度更新公式如下所示: 式中w为一常数,为提供各粒子速度vik的一个移动比例,对于各粒子而言,该权重可以调整速度vik的移动速度大小。当惯性权重w较大时,决定粒子下一次搜索方向的主要 影响 因素为vik,所以粒子会呈现较稳定的搜索路径,进而表现出较好的全局搜索特性。反之,如果惯性权重w较小时,则会受到vik、自身最佳解pbest与整体最佳解gbest等三种因素的影响,出现搜索路径不稳定的现象,仅能发挥出局部搜索的能力。
2.2 改进的粒子群算法
为了解决不易选取合理的惯性权重的困难,本文提出将惯性权重以线性递减方式加以考虑的 方法 ,即将式
(8)中的w由下列式子决定:
w=wmax-wmax-wminkmax×k
(9)
式中wmax为使用者设定的惯性权重上限值,wmin为惯性权重下限值,一般惯性权重w的范围为0.8~1.4。通过添加线性惯性权重使得初始搜索阶段具有较高的惯性权重值,从而保证搜索初期全局搜索的灵活性,随着迭代过程的进行逐渐降低惯性权重,转入局部搜索,加强粒子局部搜索能力。
为了避免各粒子在使用式
(7)后产生过大移动步幅,给各粒子最大移动速度进行限制,其最大速度 计算 公式如下所示:
vmaxγ(xub-xlb)
(10)
式中xub及xlb分别为搜索空间中变量的上、下限值,γ式用于取决搜索空间中最大速度的移动距离。采用最大速度限制加以约束后,使得粒子的搜索效果更好,并且可以减少不必要的计算时间。
2.3 改进粒子群算法流程 第二步:对各粒子进行 分析 计算,根据所设定的目标函数与限制,进一步计算各粒子的适应值。初始阶段的自身最佳解pi0即为各粒子的初始解xi0,而所有粒子自身最佳解中适应值最好的解即为整体最佳解pg0。
第三步:利用自身最佳解pik以及整体最佳解pgk修正各粒子下一次搜索的速度,速度更新公式如式
(8),其中惯性权重采用动态调整策略。并根据该调整策略更新搜索速度,进一步更新各粒子的所处位置,其位置更新公式如式
(7)所示。
第四步:将更新后各粒子的适应值与自身最佳解的适应值进行比较,产生下一次迭代的自身最佳解pik+1。将整体最佳解与自身最佳解中适应值最佳的解进行比较,一旦自身最佳解中适应值最好的解优于整体最佳解,则需将下一次迭代的整体最佳解pgk+1加以更新。
第五步:若经过h次迭代后,整体最佳解的适应值仍然无法改善,则需根据将惯性权重和最大速度调整策略进行调整,如式
(9)、
(10)所示。
第六步:若是满足终止条件则迭代停止,否则重复第三步,终止条件则是取决于最大迭代次数kmax。
3 实验分析
引用一个常用的运输调度 问题 为例来测试算法。有8个需求点和一个供应点的系统,各个需求点对应供应点的需求量为qi(i=1,2,…,
8)(单位为t)。供应点只有两辆车用于配送,每辆车的载重均为8吨,已知供应点与各个需求点之间的距离(单位为km)。算法由Matlab 7.1仿真,运行环境为Pentium 4,2.0GHZ,内存为2G的微机上进行。用 文献 的遗传算法与本文的改进粒子群算法相比较,两种算法在结论上的差异是很明显的,另外达到最优路径的迭代时间,改进粒子群算法为4.52S ;遗传算法为5.68S。实验证明本算法的可行性。
下载文档
网友最新关注
- 我长大了
- 我想对老师说
- 放假了
- 给灾区小朋友的一封信
- 通知书拿到了
- 做梦
- 合作
- 小鸟,是我们的朋友
- 明天要考试
- 别问这是为什么
- 废旧扑克做盒子
- 好玩的海洋公园
- 让座
- 我是好孩子
- 借书
- 论民商法的演进性(1)论文
- 计划生育与村民自治制度关系研究
- 论人格权法与侵权责任法的关系(1)论文
- 中国法学会环境资源法学研究会2013年年会综述论文
- 主持人的角色意识
- 电视艺术理论与美学建设随想五题
- 关注百姓命运,珍重平民情感
- 分析中国传统戏剧对中国电影的影响
- 创造性地讲好故事——电视连续剧《大雪无痕》观感
- 美丽新定义——关于李宇春的审美交锋
- 中国电视剧与当代大众文化思潮
- 电影的崛起及人文脉理释解
- 我国民事立法中价值目标的冲突与选择(1)论文
- 当代电视剧批评模式的断想
- 论数字电影对传统电影的冲击
- 《北京》教学设计
- 《葡萄沟》教案
- 《风娃娃》教学设计
- 《称赞》教学设计
- 《我要的是葫芦》第一课时教案
- 《找春天》教案
- 《称赞》
- 《植物妈妈有办法》教学设计
- 《酸的和甜的》教学设计
- 《雷雨》第二课时教案
- 《浅水洼里的小鱼》教学设计
- 《看雪》教学设计
- 《从现在开始》教学设计
- 《蓝色的树叶》教学设计
- 《纸船和风筝》教学设计