改进粒子群算法求解TSP问题.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流改进粒子群算法求解TSP问题毕 业 论 文(设计)论文(设计)题目：改进粒子群算法求解TSP问题系 别：计算机与信息科学系 专 业：网络工程学 号：2008107407姓 名：李良良指导教师：易云飞讲师时 间：2012年6月河 池 学 院毕 业 论 文（设 计） 开 题 报 告系别:计算机与信息科学系 专业:网络工程学 号2008107407姓 名李良良论文（设计）题目改进粒子群算法求解TSP问题命题来源教师命题 学生自主命题 教师课题选题意义(不少于300字): 旅行商问题 (TSP)又名货郎担问题，是一个典型的NP难题。其数学描述非常简单，但却无法找到一个确定的算法在多项式时间内求解TSP 问题，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP问题加以求解，因此找到能够有效解决TSP 问题的方法,在理论上和实际应用中都很有价值。本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义，使粒子群算法适合于求解TSP问题，并采用贪心算法的思想每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解TSP问题的基于球隙迁移的改进措施，克服了PSO算法易陷入局部最优的缺陷。作为一类组合优化问题的代表，TSP问题在实际工程中有许多应用，如计算机联网、物流等行业中的车辆调度优化、电力系统配电网络重构、城市管道铺设优化、交通导航、电气布线、电子地图、VLSI单元布局、X射线结晶学问题等。研究综述(前人的研究现状及进展情况，不少于600字):在我国，在粒子群优化算法的研究则是刚刚起步，深入的研究和应用还很少， PSO算法的研究还有大量的研究工作要做。主要的研究方向有下面几个方面：(l)粒子群算法的改进标准粒子群算法主要适用于连续空间函数的优化问题，如何将粒子群算法应用于离散空间优化问题，特别是一类非数值优化问题，将是粒子群算法的主要研究方向。另外，充分吸引其他进化类算法的优势，以改进PSO算法存在的不足也是值得研究的问题。(2)粒子群算法的理论分析到目前为止，PSO算法的分析方法还很不成熟，存在许多不完善之处。如何利用有效的数学工具对PSO算法的运行行为、收敛性以及计算复杂性进行分析也是目前的研究热点之一。(3)粒子群算法与其他进化算法的比较研究目前，进化算法的研究在理论和应用两方面都得到迅速发展，效果显著。其中研究的比较成熟的有遗传算法、蚁群算法等，而粒子群算法是一个新兴的群体智能算法，目前己成为进化算法的一个重要分支，如何从多方面比较各种算法从而得到各自的特长和不足，如何吸引其他进化类算法的优势来弥补PSO算法的不足也是当前研究的热点之一。(4)粒子群算法的应用算法研究的目的是应用，如何将PSO算法应用于更多领域，同时研究应用中存在的问题也是值得关注的热点。研究的目标和主要内容（不少于400字）基本粒子群算法的速度进化方程由认识和社会两部分组成，如何实现全局搜索能力与局部搜索能力的平衡是一个重要的研究方向。PSO算法极易陷入局部极值，如何保证其在陷入局部最优时，能够及时“跳出”，继续进行全局搜索，对于提高其寻优性能有着至关重要的影响。球隙迁移算法中，发现局部极小（开采）和克服局部极小（勘探）这两个过程互不影响，并能防止其陷入已经发现的局部极小，这样就避免了不必要的重复探索，提高了性能。在解决TSP问题时，基于球隙迁移的策略克服了易陷入局部最优的缺陷，它不但能保证及时的“跳出”，同时，还能有效地回避历史上已经发现的多个局部极小。初始种群的产生借鉴贪心算法（Greedy Algorithm）的思想，每一步都取局部最优。由于旅行商问题为一个循环回路，所以可以选择任意一个城市作为起始城市。采用贪心算法的思想，随机选择一个城市作为出发城市，并始终选择距离当前城市最近的城市作为下一个遍历城市，直到所有城市均被遍历后直接连接到出发城市即可。可以利用这个贪心算法得到近似最优循环序列，产生一定规模的初始种群。PSO算法在连续空间优化问题上已经取得了很好的效果，但是将其应用在TSP等离散优化问题中还是一种尝试。因此用改进的PSO算法有效的求解TSP问题，在整个组合优化领域和实际工程中都有着重要影响和实际意义。拟采用的研究方法a）查找并阅读相关资料，了解基本的内容，利用需求分析文档，对整个系统有个初步的架构。b）搜寻实验用的文件文档集和研究过程中用到的各种工具软件。c）根据已有的资料形成基本的思想。d）采用MyEclipse 8.5开发工具完成整个程序的编写并在Windows上进行测试。研究工作的进度安排2011年11月29日12月15日 与指导老师沟通交流，完成毕业论文选题；2011年12月16日12月30日 搜集资料，查阅文献，完成开题报告；2012年01月01日01月08日 通过阅读大量文献了解粒子群算法的基本思想；2012年01月09日02月25日 定出参考以及详细研究的文档；2012年02月26日04月25日 整理相关资料并完成概要，形成基本思想；2012年04月26日05月01日 进行编码工作；2012年05月02日05月16日 完善算法思想并对结果进行分析；2012年05月17日05月31日 总结毕业设计的整个过程，完成毕业设计论文。参考文献目录（作者、书名或论文题目、出版社或刊号、出版年月日或出版期号）1 曾建潮.微粒群算法M.北京：科学出版社,2004.2 胡劲松，郑启伦.球隙迁移算法实现全局优化J.计算机学报,2012,35(2):193-201.3 沈庆涛，张振宇.高效的求解TSP问题的近似算法J.计算机工程与应用,2008,44(35):46-49.4 牛永洁.一种新型的混合粒子群算法J.信息技术,2010,10:94-97.5 李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研究J.重庆邮电大学学报,2008,20(5):624-626.6 吴骏, 吴俊. 改进型免疫量子粒子群算法求解TSP问题J.微电子学与计算机,2011,28(8):222-224.7 熊伟清，郭举良，魏平.一种快速求解TSP问题的遗传算法J.微电子学与计算机,2004:19-22.8 张煜东，吴乐南，韦耿.智能算法求解TSP问题的比较J.计算机工程与应用,2009,45(11):11-15.9 熊伟,张江维,张火林.求解TSP问题的增强型自探索粒子群算法J.华北电力大学学报,2009,36(6):69-85.10 Siqueira P H， Steiner MTA，Scheer S.A new approach to solve the traveling salesman problemJ.Neurocomputing，2007，70 （4/6）：1013-1021.指导教师意见该生对于所开课题进行了较为详尽的研究，参考了许多文献，最后确定的课题具有一定的实用价值。论文是通过粒子群算法的研究，以提出一种粒子群算法的改进措施，具有较大的研究价值和应用价值。同意该课题开题。 签名： 年 月 日教研室主任意见同意指导老师意见，同意该课题开题。 签名： 年 月 日目 录摘 要1关键词1引言11 粒子群优化算法的研究现状21.1粒子群算法的起源21.2粒子群算法在国内的发展22 基本粒子群算法32.1粒子群优化算法的关键术语32.2粒子群优化算法的原理32.3基本粒子群算法的流程如下：42.4粒子群优化算法的参数设置52.5 粒子群算法与其它进化算法的比较研究62.5.1进化算法62.5.2 粒子群优化算法（PSO）与遗传算法(GA)的比较72.5.2 各进化算法的优劣82.5.3 粒子群算法的缺陷82.6 小结83粒子群优化算法的改进措施83.1调整惯性权重93.2 添加收缩因子93.3引入领域算子93.4离散化处理9小结104 TSP问题概述105 球隙迁移算法105.1球隙迁移算法的定义105.2球隙迁移算法的原理115.3基于球隙转移的改进措施125.4算法主要流程126改进的粒子群算法求解TSP问题136.2概念更新136.3公式更新147 实验结果与分析147.1实验结果147.2结论168 结束语16参考文献16Abstract17Keyword17致 谢17.精品文档.粒子群算法的改进及其在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）等。本文研究了标准粒子群优化算法的算法流程、参数设置以及其存在的缺陷，并对球隙迁移算法的原理进行了分析。通过对目前几种不同类型的改进PSO算法的比较，将球隙迁移算法与粒子优化算法(PSO)相结合，提出了一种新的基于球隙迁移的粒子群优化算法。最后将该算法应用于求解TSP一类离散的组合优化问题。1 粒子群优化算法的研究现状1.1 粒子群算法的起源自然界中各种生物体均具有一定的群体行为，鸟类的群集行为，如大雁飞行时可以自动排成人字形、鸽子在飞行中几乎可以同时转弯、蝙蝠在洞穴中快速飞行却可以保证互不相碰等，这些复杂的行为引起了广大研究者的普遍关注。受上述鸟群运动模型的影响，社会心理学博士 James Kennedy和电子工程学博士 Russell Eberhart在1995年提出了粒子群算法。粒子群算法是一种演化计算技术，该算法中将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置，通过个体的信息传递，导引整个群体向可能解的方向移动，在求解过程中逐步增加发现较好的解的可能性。群体中的鸟被抽象为没有质量和体积的“粒子”，通过这些“粒子”间的相互协作和信息共享，使其运动速度受到自身和群体的历史运动状态信息的影响，以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响，较好的协调微粒本身群体运动之间的关系，以利于群体在复杂的解空间中进行寻优操作。1.2 粒子群算法在国内的发展在我国，粒子群优化算法的研究刚刚起步，深入的研究和应用还很少。主要的研究方向有下面几个方面：(l)粒子群算法的改进标准粒子群算法主要适用于连续空间函数的优化问题，如何将粒子群算法应用于离散空间优化问题，特别是一类非数值优化问题，将是粒子群算法的主要研究方向。另外，充分吸引其他进化类算法的优势，以改进PSO算法存在的不足也是值得研究的问题。(2)粒子群算法的理论分析到目前为止，PSO算法的分析方法还不成熟，存在许多不完善之处。如何利用有效的数学工具对PSO算法的运行行为、收敛性以及计算复杂性进行分析也是研究热点之一。(3)粒子群算法与其他进化算法的比较研究目前，进化算法的研究在理论和应用两方面都得到迅速发展，效果显著。其中研究的比较成熟的有遗传算法、蚁群算法等，而粒子群算法是一个新兴的群体智能算法，目前己成为进化算法的一个重要分支，如何从多方面比较各种算法从而得到各自的特长和不足，如何吸引其他进化类算法的优势来弥补PSO算法的不足也是当前研究的热点之一。(4)粒子群算法的应用算法研究的目的是应用，如何将PSO算法应用于更多领域，同时研究应用中存在的问题也是值得关注的热点。目前的发展状况表明，通过对粒子群优化算法进行深入研究，与其它进化算法进行比较，发现其缺陷所在并针对其缺陷提出有效的改进方法是研究的重要方向之一。本文针对粒子群优化算法易陷入局部最优的缺陷，提出了基于球隙迁移的改进措施。基于球隙迁移的思想，“开采”和“勘探”的过程不会相互干扰，这种对粒子群优化算法的改进，目的在于提高算法搜索全局最优解的能力，避免其陷入局部最优解，以获得更高性能的PSO算法。2 基本粒子群算法2.1 粒子群优化算法的关键术语表2-1 描述 PSO 的关键术语术 语关键术语含义粒 子群内的单独个体位 置用来表示问题解的一个组的 n 维坐标群所有粒子的集合适应值用来表示给定解的优劣的数目（由解空间中的位置表示）局部最佳位置为具体组织返回的最优适应值参数空间中的位置全局最佳位置为整个群体返回的最优适应值参数空间中的位置最大速度给定方向上的最大允许速度2.2 粒子群优化算法的原理粒子群算法通过种群中个体间的协作与竞争，实现在搜索空间内寻找最优解。算法首先在搜索空间内随机初始化一群粒子，每个粒子就代表该空间内的一个可行解，对应于目标函数它就有了相应的适应度值。寻优的过程中由速度决定粒子移动的方向和距离，速度除了要借鉴粒子自身曾经到达过的最好位置外，还需借鉴种群曾经到达过的最好位置；这里就用个体极值和全局极值来分别代表它们曾经到达过的最好位置。我们可以用数学形式描述整个过程，设在一个搜索空间内有 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：根据方程对微粒的速度和位置进行进化；Step6：如未达到结束条件通常为足够好的适应值或达到一个预设最大代数（） ，则返回step2。 图2-2 基本粒子群算法的流程图2.4 粒子群优化算法的参数设置PSO算法一个最大的优点就是不需要进行太多的参数调节，但是算法中的少数几个参数却直接影响着算法的性能以及收敛性。目前，PSO算法的理论研究尚处在初级阶段，所以算法参数设置在很大程度上还依赖于经验。PSO参数包括: 群体规模m，微粒长度l，微粒范围-，微粒最大速度，惯性权重w。加速常数，。下面是这些参数的作用及其设置经验。群体规模m: 即微粒数目，一般取2040。试验表明，对于大多数问题来说，30个微粒就可以取得很好的结果，不过对于比较难的问题或者特殊类别的问题，微粒数目可以取到100或200。微粒数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也越长。微粒长度l: 即每个微粒的维数，由具体优化问题而定。微粒范围-，: 微粒范围由具体优化问题决定，通常将问题的参数取值范围设置为微粒的范围。同时，微粒每一维也可以设置不同的范围。微粒最大速度: 微粒最大速度决定了微粒在一次飞行中可以移动的最大距离。如果太大，微粒可能会飞过好解；如果太小，微粒不能在局部好区间之外进行足够的探索，导致陷入局部最优值。惯性权值：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问题时通常用一条周游路径来表示“染色体”，在执行算法之前，随机地给出一群初始“染色体”，即假设解。然后把这些假设解置于问题的“环境”中，并按适者生存，劣者淘汰的原则，从中选择出较适应环境的“染色体”，进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，经过一代一代的进化，最终收敛到最适应环境的一个“染色体”上，它是问题的最优解。2.5.2 粒子群优化算法（PSO）与遗传算法(GA)的比较大多数演化计算技术都使用同样的过程：1) 种群随机初始化。2) 对种群内的每一个个体计算适应值，适应值与最优解的距离直接有关。3) 种群根据适应值进行复制。4) 如果终止条件满足的话，就停止，否则转步骤 2。PSO 和 GA 有很多共同之处，结合我们地理解，可以归纳如下：l 两者都随机初始化种群l 两者都是基于群体进行搜索，即并行地爬多个山峰l 都使用适应值来评价系统l 都根据适应值来进行一定的随机搜索l 两个系统都不能保证能找到最优解粒子群优化算法具有和遗传算法某些相似的特征，所以 Kennedy 也称之为一类进化算法。但是，PSO 没有遗传操作如交叉(Crossover)和变异(Mutation)操作，而是根据自己的速度来决定搜索。PSO 除维护位置信息外，还维护飞行矢量，其好的结果往往来自于搜索中飞过局部最优点而探索到新的解。PSO 还有一个重要的特点，就是有记忆，每个粒子可以保存各自飞过的最好点，新的全局最优的出现会对飞行矢量产生影响，但对历史记录无影响，即搜索和记忆在一定程度上分离了。与遗传算法比较，PSO 的信息共享机制是很不同的。在遗传算法中，染色体(Chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中，只有gBest(或 pBest)给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，在大多数的情况下，所有的粒子可能更快地收敛于最优解。在种群数目为20，最大迭代次数为50，最优未更新最大次数20的条件下，参数=2，=2，w=1，将程序运行30次，统计得到以下结果，并和PSO以及GA两种算法在相同条件下的结果进行了比较。表2-2 16节点三种算法性能分析算法全局最优次数寻优概率平均消耗时间（秒）平均迭代次数GA2480%31.4811.9PGA30100%63.784.5PSO2893.3%21.256.42.5.2 各进化算法的优劣模拟退火算法的实现过程简单，但算法中参数的选择往往和过程中所遵循的准则和亟待解决的问题性质有关。基本蚁群算法存在三方面的缺陷：算法容易早熟收敛，不容易求得全局最优解；算法所用的参数较多使搜索过程较为复杂，影响时间效率；算法适用范围较窄，仅适用于解决TSP、QAP等组合优化问题。遗传算法的交叉、变异操作是一种随机选择的过程，没有确定性；当所要求的问题较为复杂时，个体的染色体过长从而使搜索的空间加大，此时算法的收敛的速度变的很慢，同时种群还容易陷入到局部最优。粒子群优化算法的优势在于所需参数较少，计算过程简单且易于实现；但是还要看到其缺点也是易陷入局部最优。2.5.3 粒子群算法的缺陷通过与其它算法进行比较，我们发现粒子群算法也有很多缺陷，这些缺陷也是随机搜索算法比较普遍的不足之处，粒子群算法很容易陷入局部最优解，导致了其全局搜索能力不足。基本PSO算法依靠的是群体之间的合作和竞争，粒子本身没有变异机制，因而单个粒子一旦受某个局部极值约束后本身很难跳出局部极值的约束，此时需要借助其它粒子的成功发现。比如：粒子群优化算法容易陷入局部极小点，导致优化结果得不到全局最优解。基本粒子群算法的速度进化方程由认识和社会两部分组成，如何实现全局搜索能力与局部搜索能力的平衡。2.6 小结本部分的内容首先对粒子群算法做了简单的介绍，同时也阐述基本粒子群算法的思想、原理，然后给出了粒子群算法的参数设置、详细流程。最后指出了粒子群算法的一些缺陷及需要改进的方面。3 粒子群优化算法的改进措施我们可以将（2.1）式改写为= + （3.1）微粒速度的进化方程的第一项是用于保证算法具有一定的全局搜索能力，第二项和第三项用于保证算法的局部搜索能力，故 、 使得微粒群算法具有局部收敛能力，而则是用于保证算法的全局收敛性能。因此，我们可以通过改变进化方程的一项或是同时改变几项来调整粒子群算法的性能。以下是几种改进策略：3.1调整惯性权重当粒子速度较大时算法的全局搜索能力较强，相反地当粒子速度变小时算法的局部搜索能力就加强了。为了使算法在进化的初期阶段尽可能地搜索到更加广阔的区域，而在进化的后期阶段提高算法的收敛性，Shi Y.等人用线性递减的方法来动态调整惯性权重值，而用来控制先前速度对当前速度的影响。在进化的初期算法注重的是全局搜索能力，大的值能避免种群总是在某个局部区域进行搜索而陷入到局部最优点；而到了进化的后期算法注重的则是进一步搜索到更加精确解的能力，此时的值随着线性递减已经变的很小，因而算法的局部搜索能力也就加强了。此版本的粒子群优化算法称为标准粒子群优化算法。3.2 添加收缩因子通过给粒子的速度添加收缩因子来限定它的大小，该方法认为如果粒子速度过大，会使算法不能很好的进行局部搜索，从而影响搜索到精确解的能力。它从机理上和调整惯性权重的方法是一样的，也是通过动态速度来平衡算法的全局搜索能力和局部搜索能力。此版本的粒子群优化算法称为收缩因子粒子群优化算法。3.3 引入领域算子前面介绍的基本粒子群优化算法中粒子的速度变化除了要借鉴自身曾经到达过的最好位置外，还需借鉴所有种群粒子到达过的最好位置。然而Kennedy等人在后来的研究中又发现粒子往往无需借鉴所有粒子的经验而只需借鉴与它比邻的粒子经验，由此就引入了一种邻域算子，改进算法求出的解更加精确，但时间效率却没有原算法高。3.4 离散化处理传统的粒子群优化算法中，粒子都是在某个连续的空间内随机地进行搜索，其位置向量是该连续空间内的任意一个状态，此状态并不是预先设定的状态集中的某一种。相反地离散型粒子群优化算法则预先设定了一系列离散状态，搜索过程中采用一种趋近的方式使粒子在连续空间内的状态转化为对预定状态的趋近程度。小结 “没有免费午餐”的理论认为：不包含领域知识的算法不一定有效，但包含过多的问题领域知识也会因此导致算法对其它问题的脆弱性。从上面可以发现，当前已经有多种对PSO 算法的改进，然而正如“没有免费午餐”的理论所认为的，这些改进算法需要针对具体问题的特点，根据领域知识对算法参数进行设置，在提高某种性能的同时也为此付出相应代价。粒子群算法容易陷入局部最小，因此，如何实现全局搜索能力和局部搜索能力的平衡是改进的重点。4 TSP问题概述TSP是运筹学、图论和组合优化中的NP难问题。问题的具体如下：给定N个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的弧集，已知各顶点间连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点一次且仅一次的最短回路。设为城市i与j 之间的距离，即弧(i,j)的长度。引入决策变量： = (4.1)则TSP的目标函数为 (4.2)TSP 问题描述非常简单，但最优化求解很困难，若用穷举法搜索，则要考虑所有可能情况，并两两对比，找出最优,其算法复杂性呈指数增长, 即所谓的“组合爆炸”。所以，寻求和研究TSP 的有效启发式算法,是问题的关键。5 球隙迁移算法5.1球隙迁移算法的定义球隙：设维空间中由个点围成的一个唯一确定的超球G，这个点都在球面上，则称球G为一个球型的空隙（空心球），简称球隙。从极值域 中一点B出发做贪心搜索，轨迹必趋向极点，称BA为起极对。图5-1 球隙、极值域示意图5.2球隙迁移算法的原理球隙迁移法包括贪心搜索和球隙转移两个过程。贪心搜索为单一的开采，球隙转移为纯粹的勘探。把每一个局部极小点A都看成一个吸引子，A所在的极值域称作其吸引域，在搜索得到极小点A之后如何摆脱它就成为最大的难点。解决策略是在搜索得到A点之后，为了摆脱它的吸引，应将接下来的搜索转移到其吸引域之外，且不能是原来老的吸引域，并转移到新的极值域进行搜索，发现新的极值，不断地找到新极值，这样就成功克服了局部最小，并有效地回避历史上已经发现的多个局部极小，避免重复搜索。当所有极值都发现了，从中选取最好的则为全局极值。启发式策略1：离已找到的极小点越远越不容易落入其极值域。启发式策略2：离已使用过的转移点越远越不容易落入老极值域 老转移点表明该区域已被开采过。启发式策略3：如果形成球隙G的点都是起极对 则G的大小应当减半考虑。其中关键的一步是求下一个转移点，设已知当前k个点形成球隙序列，新增加第k+1个点 判断新点落入的那个Voronoi多边形体内，同时修改该Voronoi多边形体及相应Voronoi多边形体的边与顶点。如新球隙符合启发式策略3 还需对新球隙的大小进行修正，于是得到新的球隙序列。此处Voronoi法不是用于逼近目标函数的极小点，反而是远离之。5.3基于球隙转移的改进措施基本粒子群算法的速度进化方程由认识和社会两部分组成，如何实现全局搜索能力与局部搜索能力的平衡是一个重要的研究方向。PSO算法极易陷入局部极值，如何保证其在陷入局部最优时，能够及时“跳出”，继续进行全局搜索，对于提高其寻优性能有着至关重要的影响。球隙迁移算法中，发现局部极小（开采）和克服局部极小（勘探）这两个过程互不影响，并能防止其陷入已经发现的局部极小，这样就避免了不必要的重复探索，提高了性能。在解决TSP问题时，基于球隙迁移的策略克服了易陷入局部最优的缺陷，它不但能保证及时的“跳出”，同时，还能有效地回避历史上已经发现的多个局部极小。5.4算法主要流程Step1：用贪婪算法产生两个初始种群A群和B群，随机产生两个基本交换序作为两个种群的初始速度，设定惯性权重w及，；Step2：计算粒子适应度，确定个体极值和全局极值；Step3：利用球隙迁移算法对粒子的历史最优解进行分析，确定每个粒子的球隙序列，并在极值域内进行贪心搜索；Step4：对搜索到的每个粒子，比较它的适应度值和邻域局部最优位置的适应度值，如果更好，更新；Step5：对搜索到的每个粒子，比较它的适应度值和种群的最好位置的适应度值，如果更好，更新；Step6：利用球隙迁移算法进行球隙转移，在新的极值域进行贪心搜索，发现新的局部极小值点，并确定下一个转移点，继续进行搜索；Step7：如未满足终止条件（连续多次没有发现新的极小点），则返回Step2。改进算法的流程图如图5-1所示： 图5-1 改进算法的流程图初始种群的产生借鉴贪心算法（Greedy Algorithm）的思想，每一步都取局部最优。由于旅行商问题为一个循环回路，所以可以选择任意一个城市作为起始城市。采用贪心算法的思想，随机选择一个城市作为出发城市，并始终选择距离当前城市最近的城市作为下一个遍历城市，直到所有城市均被遍历后直接连接到出发城市即可。可以利用这个贪心算法得到近似最优循环序列，产生一定规模的初始种群。6改进的粒子群算法求解TSP问题6.2概念更新TSP问题为离散问题，用PSO求解TSP问题需要对基本PSO算法中粒子的位置、速度以及操作进行重新定义： （1）粒子的位置粒子的位置可以定义为一个具有所有节点的哈密尔顿圈，设所有与之间的弧存在，粒子的位置可表示为序列,其中，E为状态空间。（2）粒子的速度 速度定义为粒子位置的变换集，表示一组置换序列的有序列表。可以表示为：,其中，表示该速度所含交换的数目，式(3.1)表示先交换粒子中、的位置，然后交换、的位置，依此类推。（3）粒子位置与速度的加法操作 该操作表示将一组置换序列依次作用于某个粒子位置，其结果为一个新的位置，即一个新的节点的排列。例如：位置为X=l，5，2，4，3，l，速度为V=(1，3)，(2，4),则其相加X+V后结果为X=2，4，1,5,3,2。 （4）粒子位置与位置的减法操作 粒子位置与位置相减后结果为一组置换序列，即速度。例如X=2，4，1，5，3，2，Y=1，5，2，4，3，1，由于X(1)=Y(3)=2,)=2，所以第一个交换为，因此第二个交换为，作用到粒子的位置X1后得，所以位置X与位置Y相减后得到一组置换序列，即X-Y=(1,3),(2,4)。 （5）粒子速度与速度的加法操作 粒子速度与速度的加法操作为两个置换序列的合并，结果为一个新的置换序列，即一个新的速度。例如：速度,相加后得。6.3公式更新粒子的速度、位置及其各种操作重新定义后，离散粒子群算法的速度更新公式表示如下： = w（-）（-） （6.1） = + （6.2）其中，、仍为加速常数，在02之间取值，r1、r2为（0，1）上均匀分布的两个相互独立的随机数；为两交换序的合并算子，表示速度与速度的加法操作；表示粒子位置与位置的减法操作；表示粒子位置与速度的加法操作。7 实验结果与分析7.1实验结果表6-1 14 节点的 TSP 标准问题节点1234567X 16.4716.4720.0922.3925.2322.0020.47Y 96.1094.4492.5493.3797.2496.0597.02表6-1 14 节点的 TSP 标准问题节点891011121314X17.2016.3014.0516.5321.521