| 根据上述定义，微粒群算法的进化方程可以表示如下：
vij(t+1)=w*vij(t)+c1*r1*(pij(t)-xij(t))+ c2*r2*(pgj(t)- xij(t))(2.1)
xij(t+1)= xij(t)+ vij(t+1)(2.2)
参数说明：
在上式(2.1)和（2.2）中：下标“i”表示第i个微粒；下标“j”表示微粒的第j维；“t”表示第t代；“w”为权重因子,根据文献[3]，w较大适用于对解空间进行大范围探查，w较小适于进行小范围开挖；c1，c2为加速度常数，可加快收敛且不易陷入局部最优，c1调节微粒飞向自身最好位置方向的步长，c2调节微粒向全局最好位置飞行的步长，通常在0～2之间取值；r1，r2为两个相互独立的随机数，在（0,1）之间满足均匀分布；vij通常将搜索范围限制在一定的空间范围[-Xmax，Xmax] 之内，为了使微粒在搜索空间内飞行而不离开，将vij设定在一定区间内[-vmax，vmax]内变化。
（3） 流程及其流程图
基本微粒群算法的流程可描述为：
Step 1：初始化一群微粒，包括随机位置和速度。
初始化过程：
①设定群体规模为n；
②对任意i，j，在[-Xmax，Xmax]内服从均匀分布产生xij；
③对任意i，j，在[-vmax，vmax]内服从均匀分布产生vij；
④对任意i，设yi = xi。
Step 2：评价每个微粒的适应度。
Step 3：对每个微粒，将其适应值与其经历过的最好位置pbest作比较，如果较好毕业论文提纲，则将其作为当前的最好位置pbest。
Step 4：对每个微粒，将其适应值与全局所经历的最好位置gbest作比较，如果较好，则重新设置gbest。
Step 5：根据式（3.1）、（3.2）变化微粒的速度和位置。
Step 6：如未达到结束条件（通常为足够好的适应值或达到一个预设最大Gmax），则返回Step 2。
根据上文的算法流程步骤，我们可以用图来形象地表示其流程，具体见图2-1：
图2-1 基本微粒群算法的流程图
3 变化路径的PSO求解
（1）表达式
如何将微粒群算法应用于车辆路径问题的关键是要构造一个正确而且合适的微粒表达式，并且要使每个微粒与其每个解对应。如前所述，VRP问题要求每个发货点都必须得到车辆的配送服务，而且每个发货点的服务只能限制一辆车来完成。由参考文献[3]的思想并根据本文所用实例做出适当的调整，可以构造出这样的问题：
首先，假设构造一个N维的空间微粒的位置向量z，使它对应于有N个发货任务点的VRP问题，其中z的数值代表车辆编号。例如，某VRP问题中有8个发货点任务，车辆数为3，某个微粒的位置向量z =[1 2 2 3 3 1 1 2]，表示第1、6、7个任务点由第1辆车配送；第2、3、8个任务点由第2辆车配送；第4、5个任务点由第3辆车配送。
然后再采用整数编码，即对于N个发货点，k辆车的VRP问题，将1～N的整数随机排列并赋给每个发货点，再在发货点序列中插入（k-1）个0，这样把发货点序列分成k段，每一段就代表一辆车的行车路径。由此产生一组新的种群，种群中每个微粒即对应一个（N+k-1）维向量，也就是问题一个解。
例如，设某VRP问题有3辆车运输，6个发货点，若某微粒的位置向量X为：5 3 0 6 1 4 0 2，则表示该粒子对应的路径为：
第1辆车：0→5→3→0；
第2辆车：0→6→1→4→0；
第3辆车：0→2→0。
这样的表达方式有效地解决了车辆的编码, 而且将VRP转成一个TSP问题, 便于采用传统TSP问题处理方法来求解VRP问题。
（2）求解步骤
在第二部分中可知，虽然微粒群算法在求解连续空间的问题上表现出很好的优越性，但是对于离散问题（如VRP问题）就不是很方便了。微粒群算法中，微粒下一个位置是通过速度的更新来进行的，但其难以表达。因而实现过程中，在基本微粒群算法的基础上要对其作相应的改进：微粒的下一个位置是通过与全局极值的交叉，最后再变异产生的，这样不仅能简单表示微粒的位置，而且经过变异后还能防止了算法陷入局部极值的可能。根据上面的表达式并且借鉴文献[4]的思想，具体算法步骤如下：
① 初始化参数：设微粒数为n，随机产生n个初始解（初始路径）C0，给每个变量w、c1、c2赋值，最大迭代次数为T，有N个发货点，每个发货点的需求量为g，车辆数目为k，车辆载重为q。
② 根据当前位置计算每个微粒的适应值（各路径的长度）d，设置当前微粒的适应值为个体极值pbest，取其中最优值为全局极值gbest杂志网。
While(迭代次数 < 最大迭代次数T) do
For j =1:n
③ 对第j个微粒的路径C0(j)与全局极值gbest交叉得到C'(j)，然后与个体极值pbest交叉得到C'(j)。交叉方法是：取微粒某个位置的值，若它与要交叉的对象在该位不相等，则微粒这个位置的值等于要交叉的对象在该位的值，若相等则不交叉；交叉完后微粒会有两个位置的值一样，则将另一个位置的值换为交叉时的那个值。
例如，C0 = 1 2 3 4 5 6 7，取其第2位与7 6 5 4 3 2 1的第2位进行交叉，则C0交叉后的结果为1 6 3 4 5 2 7。
④ 对C'(j)变异得到C1(j)。方法是，从微粒中随机取两个位置，然后将包括这两个位置在内的子序列以反方向插入到原来位置。
例如，C'(j) = 1 6 3 4 5 2 7，取第3位和第6位进行变异，则C'(j)变异后得到的结果为C1(j) = 1 6 2 5 4 3 7。
⑤ 将交叉变异后的微粒进行判断是否满足车辆的载货量毕业论文提纲，若满足条件，则作为微粒的下一个位置，并计算适应值；若不满足则回到步骤(3)。
End For
⑥ 比较每个微粒新适应值与其个体极值的大小，若f(i)
End While
⑦ 最后输出全局极值gbest及取到全局极值时的最优路径。
以上是将微粒群算法应用于车辆路径问题的算法步骤，若要适用于变化路径运输问题，根据本人的理解，只需将受阻的某条（或某几条）路径两点间的距离相对于其他路径设为无穷大，然后按上面的步骤1～步骤7开始计算适应值，由于两点间的距离无穷大其适应值肯定很大，则每个粒子的最优路径肯定不会包含此两点所表示的受阻路径，从而能够得到全局极值，即最优路径值。
（3）实例分析
现根据参考文献[5]举一个有7个发货点任务的车辆路径问题，各任务节点坐标及货运量见下表3-1。其中序号0表示中心仓库，其余序号1～7为发货点，由2辆车来完成所有发货任务，设每辆车的容量都是2。
表3-1 各发货点坐标及货运量
|
序号
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
坐标
|
(18,54)
|
(22,60)
|
(58,69)
|
(71,71)
|
(83,46)
|
(91,38)
|
(24,42)
|
(18,40)
|
|
货运量(gi)
|
-
|
0.89
|
0.14
|
0.28
|
0.33
|
0.21
|
0.41
|
0.57
|
用MATLAB 7.0编写程序，并选取微粒数为40，最大迭代次数为200，随机运行50次，最终得到gbest的最小值（即理想最优值）为196.77，最优行车路径为：第1辆车：0→1→2→0；
第2辆车：0→6→5→4→3→7→0。
两辆车的行车总距离为：75。
在50次的运算中，3次达到理想最优值196.77，达优率为88.87%，可见PSO求解VRP有较高的成功率，值得我们进一步探讨。
结论与小结
通过对课题的研究发现，PSO具有运算速度快、鲁棒性好的特点，是求解离散优化问题(如VRP)的有效算法。但由实验可知PSO算法易陷入局部最优。总而言之PSO对于解决VRP有较高的成功率，对于变化路径的运输具有较大的实际应用价值。
本文对VRP仅做了初步的研究，还存在很多问题，在今后的研究中相信还有大量有意义的工作有待开展。
参考文献
[1]曾建潮，介婧，崔志华.微粒群算法[M].北京：科学出版社.2004.
[2]李宁，邹彤，孙德宝.车辆路径问题的粒子群算法研究[J].系统工程学报, 2004，19(6).
[3]张丽艳，庞小红，夏蔚军.带时间窗车辆路径问题的混合粒子群算法[J]，上海交通大学学报, 2006, 40(11).
[4]高尚，杨静宇，群智能算法及其应用[M]，北京：中国水利水电出版社，2006
[5]谢晓峰，张文俊，杨之廉.微粒群算法综述[J].控制与决策，2003，18(2)：129-134.
2/2 首页 上一页 1 2 |
