发布时间 : 星期五 文章进化粒子群算法在TSP中的应用更新完毕开始阅读
第13页
? 有一个随机初始化过程，在这个过程中，群体中的个体被赋值为一些随机产生的
随机解
? 通过产生更好的新一代群体来搜索空间 ? 新一代群体产生在前一代的基础上
在粒子群优化算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解灵活应用，以及进一步研究开发。
2.3.1 PSO的关键术语
表2-1 描述PSO的关键术语
粒子/组织 位置 群 适应值 局部最佳位置 全局最佳位置 最大速度
1）粒子：群中的个体比喻为粒子或组织。群中的所有粒子在相同组织原则下独立运行，不停地检查目前位置的同时朝着最优的局部和全局位置加速。
2）位置：N维空间是将被优化的问题的解空间。在设置PSO中，需要把优化问题化解为一组能代表解空间中位置的值。
3）适应值：在进化计算技术中有许多用于评估位置好坏的函数或方法。适应函数必须代替解空间中的位置并返回表示位置值的数字。适应值函数反映了实际问题和算法优化之间的联系。
4）局部最优位置：个体独自发现的有着最高适应值的位置称为个体最优或局部最优
pi。在路径上的每个点，粒子将目前位置的适应值与局部最优值比较。若当前位
群内的单独个体
用来表示问题解的一个组的n维坐标 所有粒子的集合
用来表示给定解的优劣的数目（由解空间中的位置表示） 为具体组织返回的最优适应值参数空间中的位置 为整个群体返回的最优适应值参数空间中的位置 给定方向上的最大允许速度
置的适应值更高，则pi由当前位置代替。
5）全局最优位置：整个群发现的最高的适应值称为全体最优或全局最优pg。在路径上的每个点，粒子将目前位置的适应值与全局最优值比较。若粒子所处位置有更高适应值，则pg由当前位置代替。
2.3.2 PSO算法的基本步骤和流程
1） 初始化粒子群，即随机设定各粒子的初始位置x和初始速度v； 2） 计算每个粒子的适应度值；
第14页
3） 对每个粒子，比较它的适应度值和它经历的最好位置Pid的适应度值；若更好，
更新Pid；
4） 对每个粒子，比较它的适应度值和群体所经历的最好位置Pgd的适应度值；若更
-好，更新Pgd；
5） 根据位置和速度的更新公式调整粒子的位置和速度；
6） 若达到结束条件（足够好的位置或最大迭代次数），结束；否则，转步骤2。
图2-2为基本PSO算法的流程图
生成初始种群Xi=(Xi,Vi),i＝1,20评估个体适应值Fi(Xi)YFi(Xi)
图2-2 PSO算法流程图
2.3.3 应用PSO算法步骤
应用粒子群优化算法的基本步骤可归纳如下：
1）定义解空间：第一步是挑选需要优化的参数并赋予其搜索最优解的范围。在N维优化中每一维都要求确定最大最小值。
2）定义适应值函数：这个重要步骤提供了优化算法和实际问题的接口。选择一个函
第15页
数能较为准确地用一个数表示解的最优值。适应值函数和解空间必须是针对该优化算法而定；剩余的实现部分独立于被优化的实际问题之外。
3）随机初始化群的位置和速度：为了在解空间开始优化搜索，每个粒子以随机位置 和速度开始运动，该速度的方向和大小也是随机的。因为其初始位置也是每个粒子在运动初期的第一个位置，所以该位置也是每个粒子自身的局部最优位置。从而全局最优位置也是从这些位置中选取。
4）粒子在解空间中的飞行：该算法在每个粒子身上起作用。具体实现步骤如下： a) 评估粒子适应值，对比全局、局部最优值：适应值函数根据粒子在解空间中的坐标，返回赋给当前位置的适应值。若该值大于此时粒子的局部或全局最优值，则当前位置要由更恰当的位置代替。
b) 更新粒子速度：粒子速度的控制是整个优化的核心。通过对粒子速度更新公式的研究，粒子速度随着局部和全局最优位置的改变而改变，朝着适应值更大的方向加速。公式（2-1）中，加速因子c1、c2：决定局部最优位置pi和全局最优位置pg的相对“牵引力”。
5）循环反复：这些过程都在群中的粒子执行一遍后，重新从步骤4开始。对所有粒子的位置进行评估并根据局部、全局位置更新粒子位置。如此反复直至满足终止条件。
2.3.4 PSO参数设置
应用PSO解决优化问题的过程中有两个重要的步骤：问题解的编码和适应度函数。
PSO的一个优势是采用实数编码，不需要像遗传算法一样是二进制编码（或
22?x3)求解，粒子可以直接者采用针对实数的遗传操作）。例如对于问题f(x)= (x12?x222?x3)，而适应度函数就是f(x)。接着就可以利用前面的过程去寻优。编码为(x12?x2这个寻优过程是一个迭代过程，中止条件一般设为达到最大循环数或者最小错误。 PSO中并没有许多需要调节的参数，下面列出了这些参数以及经验设置：
● 粒子数：较小的群能充分探索解空间，避免了过多的适应值评估和计算时间。
一般取20－40。其实对于大部分的问题10个粒子已经足够可以取得好的结果，不过对于比较难的问题或者特定类别的问题，粒子数可以取到100或200。
● 粒子的长度：这是由优化问题决定，就是问题解的长度。 ● 粒子的范围：由优化问题决定,每一维可以设定不同的范围。
● Vmax：最大速度，决定粒子在一个循环中最大的移动距离，通常设定为粒子
的范围宽度，例如，粒子(x1,x2,x3)，xi属于[－10，10]，那么Vmax的大小
第16页
就是10。
● 加速因子：c1和c2通常等于2。不过在资料中也有其他的取值。但是一般c1等
于c2并且范围在0和4之间。
● 中止条件：最大循环数以及最小错误要求。例如，最小错误可以设定为1个
错误分类，最大循环数设定为2000，这个中止条件由具体的问题确定。 ● 全局PSO和局部PSO：两种版本的粒子群优化算法：全局版和局部版。前者
速度快不过有时会陷入局部最优。后者收敛速度慢一点不过很难陷入局部最优。在实际应用中，可以先用全局PSO找到大致的结果，再用局部PSO进行搜索。
● 惯性权值：w控制着速度前一变化量对当前变化量的影响，如果w较大，则
影响较大，能够搜索以前所未能达到的区域，整个算法的全局搜索能力加强，有利于跳出局部极小点；而w值较小，则前一动量项的影响较小，主要是在当前解的附近搜索，局部搜索能力较强，有利于算法收敛。