7.1实验结果 .......................................................... 14 7.2结论 .............................................................. 16 8 结束语 ................................................................. 16 参考文献 ................................................................. 16 Abstract .................................................................. 17 Keyword ................................................................. 17 致 谢 ................................................................... 17
河池学院2012届本科毕业论文（设计）
粒子群算法的改进及其在TSP问题中的应用
网络工程专业 李良良 指导教师 易云飞
[摘 要] 粒子群优化算法是源于对鸟群捕食行为的研究而发展的一种智能寻优算法，它通过
迭代搜寻最优值，不仅能获得较高的效率而且具有简单、易于操作和通用的特性。而针对粒子群算法易陷入局部最优的缺陷，本文提出了粒子群算法基于球隙迁移的改进措施。基于球隙迁移的思想，发现局部最小（开采）和克服局部最小（勘探）的过程不会相互干扰，优化效果更好。旅行商（TSP）问题是一个著名的NP完全问题，在解决TSP问题时，基于球隙迁移的改进策略不但能保证及时的“跳出”。同时，还能有效地回避历史上已经发现的多个局部极小。
[关键词]粒子群算法；球隙迁移；全局极小；局部极小
引言
粒子群优化（Particle Swarm Optimization，PSO）算法最早是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。粒子群优化算法（PSO）是基于群体的优化工具，粒子在解的共建过程中始终追随最优的粒子进行搜索。它采用种群的方式组织搜索，这使得它可以同时搜索空间内的多个区域，而且这种方式特别适合大规模的并行计算。旅行商问题 (Traveling Salesman Problem，简称TSP)又名货郎担问题，是一个典型的NP-hard完全问题。问题描述：给定N个城市以及两两城市之见的距离，求一条访问各个城市且仅访问一次的最短路线。虽然其数学描述非常简单，但却很难找到一个确定的算法在多项式时间内求解TSP问题，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP问题加以求解，因此找到能够有效解决TSP问题的方法,在理论上和实际应用中都很有价值。对于TSP问题求解的算法主要有模拟退火算法( Simulated Annealing，简称SA)、蚁群算法(Ant Colony Optimization，简称ACO)、遗传算法（Genetic Algorithm，简称GA）、人工鱼群算法（Artificial Fish School Algorithm, 简称AFSA）等。
本文研究了标准粒子群优化算法的算法流程、参数设置以及其存在的缺陷，并对球
1
河池学院2012届本科毕业论文（设计）
隙迁移算法的原理进行了分析。通过对目前几种不同类型的改进PSO算法的比较，将球隙迁移算法与粒子优化算法(PSO)相结合，提出了一种新的基于球隙迁移的粒子群优化算法。最后将该算法应用于求解TSP一类离散的组合优化问题。
1 粒子群优化算法的研究现状
1.1 粒子群算法的起源
自然界中各种生物体均具有一定的群体行为，鸟类的群集行为，如大雁飞行时可以自动排成人字形、鸽子在飞行中几乎可以同时转弯、蝙蝠在洞穴中快速飞行却可以保证互不相碰等，这些复杂的行为引起了广大研究者的普遍关注。
受上述鸟群运动模型的影响，社会心理学博士 James Kennedy和电子工程学博士 Russell Eberhart在1995年提出了粒子群算法。粒子群算法是一种演化计算技术，该算法中将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置，通过个体的信息传递，导引整个群体向可能解的方向移动，在求解过程中逐步增加发现较好的解的可能性。群体中的鸟被抽象为没有质量和体积的“粒子”，通过这些“粒子”间的相互协作和信息共享，使其运动速度受到自身和群体的历史运动状态信息的影响，以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响，较好的协调微粒本身群体运动之间的关系，以利于群体在复杂的解空间中进行寻优操作。 1.2 粒子群算法在国内的发展
在我国，粒子群优化算法的研究刚刚起步，深入的研究和应用还很少。主要的研究方向有下面几个方面： (l)粒子群算法的改进
标准粒子群算法主要适用于连续空间函数的优化问题，如何将粒子群算法应用于离散空间优化问题，特别是一类非数值优化问题，将是粒子群算法的主要研究方向。另外，充分吸引其他进化类算法的优势，以改进PSO算法存在的不足也是值得研究的问题。 (2)粒子群算法的理论分析
到目前为止，PSO算法的分析方法还不成熟，存在许多不完善之处。如何利用有效的数学工具对PSO算法的运行行为、收敛性以及计算复杂性进行分析也是研究热点之一。 (3)粒子群算法与其他进化算法的比较研究
目前，进化算法的研究在理论和应用两方面都得到迅速发展，效果显著。其中研究的比较成熟的有遗传算法、蚁群算法等，而粒子群算法是一个新兴的群体智能算法，目
2
河池学院2012届本科毕业论文（设计）
前己成为进化算法的一个重要分支，如何从多方面比较各种算法从而得到各自的特长和不足，如何吸引其他进化类算法的优势来弥补PSO算法的不足也是当前研究的热点之一。 (4)粒子群算法的应用
算法研究的目的是应用，如何将PSO算法应用于更多领域，同时研究应用中存在的问题也是值得关注的热点。
目前的发展状况表明，通过对粒子群优化算法进行深入研究，与其它进化算法进行比较，发现其缺陷所在并针对其缺陷提出有效的改进方法是研究的重要方向之一。本文针对粒子群优化算法易陷入局部最优的缺陷，提出了基于球隙迁移的改进措施。基于球隙迁移的思想，“开采”和“勘探”的过程不会相互干扰，这种对粒子群优化算法的改进，目的在于提高算法搜索全局最优解的能力，避免其陷入局部最优解，以获得更高性能的PSO算法。
2 基本粒子群算法
2.1 粒子群优化算法的关键术语
表2-1 描述 PSO 的关键术语
术 语 粒 子 位 置 群 适应值 局部最佳位置 全局最佳位置 最大速度
关键术语含义
群内的单独个体
用来表示问题解的一个组的 n 维坐标 所有粒子的集合
用来表示给定解的优劣的数目（由解空间中的位置表示） 为具体组织返回的最优适应值参数空间中的位置 为整个群体返回的最优适应值参数空间中的位置 给定方向上的最大允许速度
2.2 粒子群优化算法的原理
粒子群算法通过种群中个体间的协作与竞争，实现在搜索空间内寻找最优解。算法首先在搜索空间内随机初始化一群粒子，每个粒子就代表该空间内的一个可行解，对应于目标函数它就有了相应的适应度值。寻优的过程中由速度决定粒子移动的方向和距离，速度除了要借鉴粒子自身曾经到达过的最好位置外，还需借鉴种群曾经到达过的最好位置；这里就用个体极值和全局极值来分别代表它们曾经到达过的最好位置。我们可
3
河池学院2012届本科毕业论文（设计）
以用数学形式描述整个过程，设在一个搜索空间内有 m 个粒子，搜索空间的维数为d，即表示粒子的维数也为 d。
粒子的位置向量表示为：＝（粒子的速度向量表示为：＝（粒子搜索到的最优位置：（或
,,
,?,,?,）＝（
）,i=1,2,?,m； ），i=1,2,?,m； ,
,?,
,
），称为个体极值； ,?,
），称为全局极
整个粒子群搜索到的最优位置：（或 ）＝（
值，因为是整个粒子群的最优位置，因此上述 PSO 算法也称为全局版 PSO。
在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和位置：
= w×=
＋＋
×rand()×(
－
)＋
×rand()×(
－
) (2.1)
(2.2)
,
是非负常数，称为加速因子，根据经验
∈[-,
]，
是常数，
其中 w 是非负数，称为惯性权值；通常＝＝2；
是粒子的速度，i=1,2,?,m ，
由用户设定用来限制粒子的速度；和 如前定义，分别是个体极值和全局极值；rand()是介于(0,1)之间的随机数。
：目前搜索到的点
：改进后的搜索点
：当前速度
：改进后的速度 ：基于个体极值的速度 ：基于全局极值的速度
图 2-1 位置向量、速度向量示意图
2.3 基本粒子群算法的流程如下：
Step1：依照初始化过程，对微粒群的随机位置和速度进行初始设定； Step2：计算每个微粒的适应值；
Step3：对于每个微粒，将其适应值与所经历过的最好位置的适应值进行比较，若较好，则将其作为当前的最好位置；
Step4：对每个微粒，将其适应值与全局所经历的最好位置的适应值进行比较，若较好，则将其作为当前的全局最好位置；
Step5：根据方程对微粒的速度和位置进行进化；
4