概念隐喻与大学英语写作教学

新万博体育网址首页

2019-05-18 15:53

   针对标准粒子群算法在求解车辆调度问题中存在的易陷入局部最优、早熟等缺陷,从粒子群算法本身出发,引入粒子个体与群体的平均信息,出一种基于平均最优信息的粒子群算法(AVGPSO),该算法利用粒子个体最优信息和全局最优信息的平均值来高全局搜索能力。将该算法应用到车辆调度问题中,并与标准粒子群算法进行比较。实验结果表明,该算法在解决车辆调度问题中表现出了更优的性能,是解决车辆调度问题的有效方法。    关键词车辆调度问题;粒子群算法;平均最优信息;组合优化    中图分类号U116.2 文献标识码A    车辆调度问题(Vehicle Routing Problem, VRP)是一个层次目标优化问题,最早由学者Dantzig和Ramser于1959年    出1,自出以来一直都是组合优化领域的热点和前沿问题。车辆调度问题是典型的NP-hard问题,当问题所涉及的规模很小时可采用精确算法进行求解,但随着问题规模的增大,精确算法的计算量呈指数增长,实际应用范围非常有限。因此,如何通过少量计算并以较快速度得到一个相对满意的解成为学者们研究的重点内容。在解决大规模VRP时通常采用启发式算法或现代优化算法,现阶段已有不少研究将启发式算法应用到车辆调度问题中,其中神经网络、模拟退火算法、蚁群算法以及遗传算法尤为居多2-5。但这些算法均存在一定的局限性,如遗传算法在寻优过程中早熟且收敛慢;禁忌搜索全局性差;模拟退火搜索速度慢等。因此寻求性能更优的启发式算法,对于解决VRP具有十分重的意义。    粒子群优化算法(Particle Swarm Optimization,PSO)6是目前国内外研究的热点,它在大规模问题寻优过程中表现出比其他经典启发式算法更大的优势和可行性7-8。PSO算法虽具有自身优势,但在实际寻优过程中仍会出现陷入局部最优值,早熟停滞进化现象。针对这些不足,本文利用基于粒子个体最优值与全局最优值的均值信息,将平均粒子群算法(Average PSO,AVGPSO)应用到车辆调度问题中。通过仿真实验,验证了该算法的有效性,并与标准粒子群算法进行性能对比,实验结果表明改进的算法在解决车辆调度问题中表现出了更优的性能。    1 车辆调度问题描述    式(1-4)是容量约束,限制每条路线上的客户需求量之和不超过车辆的最大承载量;    式(1-5)表示每个客户需求点被访问一次并且只能被访问一次;    式(1-6)、(1-7)表示每个客户需求点的需求只能由一辆车完成;    式(1-8)表示所有配送车辆均从配送中心出发,最后返回到配送中心;    式(1-9)、(1-1)为变量取值约束。    2 粒子群优化算法及改进    2.1 标准粒子群算法    2.2 基于平均最优信息的粒子群算法(AVGPSO)    标准粒子群算法中,速度更新公式中的第二项和第三项分别利用了粒子的个体极值和全局极值。该算法虽然在解决车辆路径问题上已表现出较好的性能,但由于算法自身的粒子间信息共享机制可能会导致粒子在寻优过程中过分集中而易陷入局部最优值,从而过早地成熟收敛。文献9在标准粒子群算法的基础上引入了粒子个体极值的平均值,出一种改进的粒子群优化算法,即在标准粒子 AVGPSO 算法过程如表2-1所示    3 基于AVGPSO的车辆调度问题    3.1 构造粒子编码    车辆调度问题是组合优化问题,其编码方式和初始解的设定对问题的求解都有很大影响。本文根据文献1的编码思想,采用一种基于实数向量的编码方式,即在不增加维数的前下,将车辆和车辆中客户的排序在编码中表示出来。对于有N个客户的VRP问题,粒子的状态由N维的实数向量X表示。对于向量的每一维,其整数部分表示客户所在的车辆,整数部分相同的,表示在同一辆车中;其小数部分表示客户在该车辆中配送的次序。假设有8个客户的VRP问题,需的车辆数为3,采用该编码方式表示如下    客户编号 1 2 3 4 5 6 7 8    X 2.1 3.9 1.51 1.34 1.21 1.76 3.35 3.17    按照上述描述的编码思想,先将X取整,整数部分相同的划为一个组,即得到如下三组2.1,1.51,1.34,1.21,1.76,3.9,3.35,3.17。在得到的三组数中,按照小数部分的值从小到大进行排序,即有2.1,1.21,1.34,1.51,1.76,3.9,3.17,3.35。将上述粒子的状态映射成对应的客户,即得到车辆的配送路径    车辆1-5-4-3-6-    车辆2-1-    车辆3-2-8-7-    在该编码方式中,粒子的维数与客户的数目相对应,解码时只需进行一次排序和取整运算,粒子状态更新操作简单,并能发挥粒子群算法的固有特点。    3.2 算法步骤    为验证AVGPSO算法相对于标准PSO算法的优越性,同样针对该车辆调度问题采用标准PSO算法进行优化,并将两种算法进行性能分析比较。标准PSO算法的相关参数设置与AVGPSO算法一样。最大迭代次数为5,每种算法独立运行2次,每次优化得到的最优适应度值结果及运行时间如表4-3所示。其中,AVGPSO算法有19次搜索到最优解,而标准PSO只有14次,即AVGPSO的成功率为95%,标准PSO的成功率为7%,而且在运行时间上AVGPSO也快于标准PSO。图4-2给出了AVGPSO与标准PSO算法的平均适应度值的进化曲线,由于所求目标函数指标为距离最短,即求最小值,所以适应度值曲线越往下越优。从图中可看出,标准PSO算法与AVGPSO算法均达到了最优值,但AVGPSO算法的收敛速度明显快于标准PSO算法。   根据上述仿真结果可知,AVGPSO算法在搜索精度上比标准PSO算法高,收敛速度快,并且在找到最优值时的平均收敛步数更短,寻优性能远远胜于标准PSO算法。由图4-2可知,在标准PSO算法陷入局部最优解时,AVGPSO算法能够有效跳出局部最优,更好地保持了种群的多样性,从而高算法的优化能力。    5 结束语    本文针对标准粒子群算法在解决车辆调度问题时易陷入局部最优的缺陷,考虑结合粒子的个体最优值与全局最优值,将平均性能指标引入到算法的更新策略中,出了一种基于平均最优信息的粒子群算法。通过实验结果表明,该算法能快速有效地解决车辆调度问题。改进的算法编码简单,并且在种群进化过程中保持了种群的多样性,增强了算法的全局搜索能力,是解决此类问题一种简单易行的优化方法。    参考文献    1 DANTZING G, RAMSER J. The truck dispatching problemJ. Management Science, 1959,1(6)8-91.    2 郭耀煌,李军. 车辆优化调度M. 成都成都科技大学,1994.    3 Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant coloniesC // In Proc of 1st European conf Artificial Life, Pans, France Elsevier, 1991134-142.    4 张翠军,张敬敏,王占峰. 基于车辆路径问题的蚁群遗传融合优化算法J. 计算机工程与应用,28,44(4)233-235.    5 刘之硕,申金升,柴跃延. 基于自适应蚁群算法的车辆路径问题研究J. 控制欲决策,25,2(5)562-566.    6 曾建潮. 微粒群算法M. 北京科学出版社,24.    7 丰伟,李雪芹. 基于粒子群算法的多目标车辆调度模型求解J. 系统工程,27,4(25)16-19.    8 李宁,等. 带时间窗车辆路径问题的粒子群算法J. 系统工程理论与实践,24,4(4)13-135.    9 苏晋荣,李兵义,王晓凯. 一种利用种群平均信息的粒子群优化算法J. 计算机工程与应用,27,43(1)58-59.    1 Salmen A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problemJ. Microprocessors and Microsystems, 22,26367-371.    11 李军,谢秉磊,郭耀煌. 非满载车辆调度问题的遗传算法J. 系统工程理论与实践,2,2(3)235-239.   

发表评论

全部评论:0条

LittleBlack

爱生活,爱音乐,爱电影,爱编程