河池学院2012届本科毕业论文（设计）
Step6：如未达到结束条件通常为足够好的适应值或达到一个预设最大代数（
） ，则返回step2。
开始初始化计算适应度值NO更新个体极值和全局极值更新粒子的速度和位置满足条件？YES结束 图2-2 基本粒子群算法的流程图
2.4 粒子群优化算法的参数设置
PSO算法一个最大的优点就是不需要进行太多的参数调节，但是算法中的少数几个参数却直接影响着算法的性能以及收敛性。目前，PSO算法的理论研究尚处在初级阶段，所以算法参数设置在很大程度上还依赖于经验。
PSO参数包括: 群体规模m，微粒长度l，微粒范围[-，惯性权重w。加速常数
，
]，微粒最大速度
，。下面是这些参数的作用及其设置经验。
群体规模m: 即微粒数目，一般取20~40。试验表明，对于大多数问题来说，30个微粒就可以取得很好的结果，不过对于比较难的问题或者特殊类别的问题，微粒数目可以取到100或200。微粒数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也越长。
微粒长度l: 即每个微粒的维数，由具体优化问题而定。 微粒范围[-，
]: 微粒范围由具体优化问题决定，通常将问题的参数取值
范围设置为微粒的范围。同时，微粒每一维也可以设置不同的范围。
微粒最大速度
: 微粒最大速度决定了微粒在一次飞行中可以移动的最大距离。
5
河池学院2012届本科毕业论文（设计）
如果太大，微粒可能会飞过好解；如果太小，微粒不能在局部好区间之外进行
足够的探索，导致陷入局部最优值。
惯性权值：w控制着速度前一变化量对当前变化量的影响，如果w较大，则影响较大，能够搜索以前所未能达到的区域，整个算法的全局搜索能力加强，有利于跳出局部极小点；而w值较小，则前一动量项的影响较小，主要是在当前解的附近搜索，局部搜索能力较强，有利于算法收敛。
2.5 粒子群算法与其它进化算法的比较研究 2.5.1进化算法 （1）人工神经网络
人工神经网络的基本思想是通过对神经网络引入适当的能量函数，使之与TSP的目标函数相一致来确定神经元之间的联结权，随着网络状态的变化，其能量不断减少，最后达到平衡时，即收敛到一个局部最优解。但是，当城市的数少于30时，在大多数情况下可以求的最优解的近似解，但是当城市大于30时，求解结果并不能令人满意。当规模更大时，易于收敛到非法解或局部极小解。同时，它还具有收敛速度慢、对模型参数和初始条件敏感等缺点。 （2）模拟退火算法
模拟退火算法的基本思想是从一定解开始的，从邻域中随机产生另一个解，接受准则允许目标函数在有限范围内变坏。它由一控制参数t决定，其作用类似于物理过程中的温度T，对于t的每一取值，算法持续进行“产生新解一判断—接受或舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。经过大量的解变换后，可以求得给定控制参数t值时优化问题的相对最优解。然后减小控制参数t的值，重复执行上述迭代过程。当控制参数逐渐减小并趋于零时，系统亦越来越趋于平衡状态，最后系统状态对应于优化问题的整体最优解。模拟退火算法所得解的好坏与初始状态、温度函数等都有一定的联系，降温较快的效果不一定很好；效果好的，其降温过程又极其缓慢。但由于该方法适用范围广，并可以人为控制迭代次数，反复求解，因此具有很强的实用性。
(3）遗传算法（GA）
遗传算法（GA）生物学的自然选择和自然遗传机制模拟生命进化的原理赖寻求问题的最优解，为一种进化算法，自Holland.J等提出以来，获得了广泛的应用。用该算法求解TSP问题的基本思想是：把问题的解表示成“染色体”，在求解TSP问题时通常用
6
河池学院2012届本科毕业论文（设计）
一条周游路径来表示“染色体”，在执行算法之前，随机地给出一群初始“染色体”，即假设解。然后把这些假设解置于问题的“环境”中，并按适者生存，劣者淘汰的原则，从中选择出较适应环境的“染色体”，进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，经过一代一代的进化，最终收敛到最适应环境的一个“染色体”上，它是问题的最优解。
2.5.2 粒子群优化算法（PSO）与遗传算法(GA)的比较 大多数演化计算技术都使用同样的过程： 1) 种群随机初始化。
2) 对种群内的每一个个体计算适应值，适应值与最优解的距离直接有关。 3) 种群根据适应值进行复制。
4) 如果终止条件满足的话，就停止，否则转步骤 2。
PSO 和 GA 有很多共同之处，结合我们地理解，可以归纳如下：
? 两者都随机初始化种群
? 两者都是基于群体进行搜索，即并行地爬多个山峰 ? 都使用适应值来评价系统
? 都根据适应值来进行一定的随机搜索 ? 两个系统都不能保证能找到最优解
粒子群优化算法具有和遗传算法某些相似的特征，所以 Kennedy 也称之为一类进化算法。但是，PSO 没有遗传操作如交叉(Crossover)和变异(Mutation)操作，而是根据自己的速度来决定搜索。PSO 除维护位置信息外，还维护飞行矢量，其好的结果往往来自于搜索中飞过局部最优点而探索到新的解。PSO 还有一个重要的特点，就是有记忆，每个粒子可以保存各自飞过的最好点，新的全局最优的出现会对飞行矢量产生影响，但对历史记录无影响，即搜索和记忆在一定程度上分离了。与遗传算法比较，PSO 的信息共享机制是很不同的。在遗传算法中，染色体(Chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中，只有gBest(或 pBest)给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，在大多数的情况下，所有的粒子可能更快地收敛于最优解。
在种群数目为20，最大迭代次数为50，最优未更新最大次数20的条件下，参数
=2，
=2，w=1，将程序运行30次，统计得到以下结果，并和PSO以及GA两种算法在相同条件下的结果进行了比较。
7
河池学院2012届本科毕业论文（设计）
表2-2 16节点三种算法性能分析
算法 GA PGA PSO
全局最优次数
24 30 28
寻优概率 80% 100% 93.3%
平均消耗时间（秒）
31.48 63.78 21.25
平均迭代次数
11.9 4.5 6.4
2.5.2 各进化算法的优劣
模拟退火算法的实现过程简单，但算法中参数的选择往往和过程中所遵循的准则和亟待解决的问题性质有关。基本蚁群算法存在三方面的缺陷：算法容易早熟收敛，不容易求得全局最优解；算法所用的参数较多使搜索过程较为复杂，影响时间效率；算法适用范围较窄，仅适用于解决TSP、QAP等组合优化问题。遗传算法的交叉、变异操作是一种随机选择的过程，没有确定性；当所要求的问题较为复杂时，个体的染色体过长从而使搜索的空间加大，此时算法的收敛的速度变的很慢，同时种群还容易陷入到局部最优。粒子群优化算法的优势在于所需参数较少，计算过程简单且易于实现；但是还要看到其缺点也是易陷入局部最优。 2.5.3 粒子群算法的缺陷
通过与其它算法进行比较，我们发现粒子群算法也有很多缺陷，这些缺陷也是随机搜索算法比较普遍的不足之处，粒子群算法很容易陷入局部最优解，导致了其全局搜索能力不足。基本PSO算法依靠的是群体之间的合作和竞争，粒子本身没有变异机制，因而单个粒子一旦受某个局部极值约束后本身很难跳出局部极值的约束，此时需要借助其它粒子的成功发现。比如：粒子群优化算法容易陷入局部极小点，导致优化结果得不到全局最优解。基本粒子群算法的速度进化方程由认识和社会两部分组成，如何实现全局搜索能力与局部搜索能力的平衡。 2.6 小结
本部分的内容首先对粒子群算法做了简单的介绍，同时也阐述基本粒子群算法的思想、原理，然后给出了粒子群算法的参数设置、详细流程。最后指出了粒子群算法的一些缺陷及需要改进的方面。
3 粒子群优化算法的改进措施
我们可以将（2.1）式改写为
8
河池学院2012届本科毕业论文（设计）
= ＋+ （3.1）
微粒速度的进化方程的第一项是用于保证算法具有一定的全局搜索能力，第二项和第三项用于保证算法的局部搜索能力，故而
、
使得微粒群算法具有局部收敛能力，
则是用于保证算法的全局收敛性能。因此，我们可以通过改变进化方程的一项或是
同时改变几项来调整粒子群算法的性能。以下是几种改进策略： 3.1调整惯性权重
当粒子速度较大时算法的全局搜索能力较强，相反地当粒子速度变小时算法的局部搜索能力就加强了。为了使算法在进化的初期阶段尽可能地搜索到更加广阔的区域，而在进化的后期阶段提高算法的收敛性，Shi Y.等人用线性递减的方法来动态调整惯性权重ω值，而ω用来控制先前速度对当前速度的影响。在进化的初期算法注重的是全局搜索能力，大的ω值能避免种群总是在某个局部区域进行搜索而陷入到局部最优点；而到了进化的后期算法注重的则是进一步搜索到更加精确解的能力，此时的ω值随着线性递减已经变的很小，因而算法的局部搜索能力也就加强了。此版本的粒子群优化算法称为标准粒子群优化算法。 3.2 添加收缩因子
通过给粒子的速度添加收缩因子χ来限定它的大小，该方法认为如果粒子速度过大，会使算法不能很好的进行局部搜索，从而影响搜索到精确解的能力。它从机理上和调整惯性权重的方法是一样的，也是通过动态速度来平衡算法的全局搜索能力和局部搜索能力。此版本的粒子群优化算法称为收缩因子粒子群优化算法。 3.3 引入领域算子
前面介绍的基本粒子群优化算法中粒子的速度变化除了要借鉴自身曾经到达过的最好位置外，还需借鉴所有种群粒子到达过的最好位置。然而Kennedy等人在后来的研究中又发现粒子往往无需借鉴所有粒子的经验而只需借鉴与它比邻的粒子经验，由此就引入了一种邻域算子，改进算法求出的解更加精确，但时间效率却没有原算法高。 3.4 离散化处理
传统的粒子群优化算法中，粒子都是在某个连续的空间内随机地进行搜索，其位置向量是该连续空间内的任意一个状态，此状态并不是预先设定的状态集中的某一种。相反地离散型粒子群优化算法则预先设定了一系列离散状态，搜索过程中采用一种趋近的方式使粒子在连续空间内的状态转化为对预定状态的趋近程度。
9