发布时间 : 星期六 文章进化粒子群算法在TSP中的应用更新完毕开始阅读
第5页
1.2.3 粒子群优化算法的概述
粒子群优化算法(PSO)的基本概念源于对鸟群觅食行为的研究。设想这样一个场景：一群鸟在随机搜寻食物。在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是他们知道当前的位置距离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前距离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。
在粒子群优化算法中，每个优化问题的潜在解都是搜索空间中的一只“鸟”，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(Fitness Value),每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在空间中搜索。粒子群优化算法初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个极值就是粒子本身所找到的最优解，这个解被称为个体极值。另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。
Kennedy和Eberhart最早提出的PSO算法采用下列公式对粒子操作:
'Vid??Vid?c1rand()(Pid?Xid)?c2rand()(Pgd?Xid) （1-1）
式中vid表示第i个粒子在第d维上的速度；?为惯性权重，控制粒子的每一代速度更新有多少以前的速度保留下来；c1和c2为调节Pid和Pgd相对重要性的参数；
rand()为随机数生成函数。这样可以得到粒子移动的下一个位置:
''?Xid?Vid Xid （1-2）
Pid为粒子i曾达到的最优位置，Pgd为整个粒子群曾达到的最优位置。由此可见
PSO的基本思想就是每个个体充分利用群体与自身的智能,不断地调整学习,最终得到满意解。
算法的迭代终止条件根据具体问题一般选为最大迭代次数或(和)粒子群迄今为止搜索到的最优位置满足预定最小适应阀值。
粒子群优化算法并没有能给出严格的数学证明，但在实际应用中被证明是有效的。粒子群优化算法初期，其解群随进化代数而言表现了更强的随机性，正是由于其产生了下一代解群体的较大随机性，以及每代所有解的“信息”的共享性和各个解的“自我素质”的提高，比如解群体随进化代数的变化过程中存在“掉队”个体的“归队”现象，使得每代种群中的解具有“自我”学习和向“他人”学习提高的双重优点，因此其下代解具有针对性的从“先辈”那里继承的更多的信息。在这种前提下，种群很快就达到了收敛状态，从而能在较少的代数内找到最优解。
第6页
1.2.4 旅行商问题
最优化问题自然而然的被分为两类：一类是连续变量的问题，另一类是离散变量的问题，对于后者，我们称它为组合优化。在组合优化问题里，是从一个无限集或者可数无限集里寻找一个对象，典型的是一个整数，一个集合，一个排列或一个图。这与连续变量问题求一组实数或一个函数有着很大不同，因而求解它们的方法也很大相同。从某种意义上讲，组合优化问题的研究是从它与连续优化问题之间的分界线上入手的。
旅行商问题(Traveling Salesman Problem-TSP)是运筹学、图论和组合优化中的NP难题，旅行商问题描述如下：给定n个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最短路线。其图论描述为：给定图G=(V,A)，其中V为顶点集，A为各顶点相互连接组成的弧集，已知各顶点间连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点一次且仅一次的最短回路。设dij为城市i与j之间的距离，即弧(i,j)的长度。引入决策变量：
ij??xij?1,若旅行商访问城市后访问城市 xij?? （1-3）
??0，否则则TSP的目标函数为
MinZ?i，j?1?xdijnij。 （1-4）
TSP的描述非常简单，但求解最优化解是很困难的。对于N个城市的TSP，存在着(n?1)!/2条可能的路径。随着城市数目N的增长，可能路径的数目以N的指数倍增加，如果使用穷举法搜索，需要考虑所有的可能情况，并两两比较，找出最优解，那么可搜索的路径及其距离之和的计算量将正比于(N!)/2,算法的复杂度呈指数增长，产生所谓的“组合爆炸”，这即使是当今世界上运算最快的计算机也感到无能为力。由于对TSP及与之具有类似复杂性的一些其它最优化问题现在还没有有效的算法，人们把这类问题称为“NP完全问题”。因为所有的NP完全问题在数学上都等价于TSP，因此研究TSP具有很重要的意义。
1.3 粒子群优化算法的国内外研究现状
粒子群优化算法概念简单，实现容易，同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。算法一提出就吸引了广泛的注意，不断涌现了各种关于PSO算法应用研究的成果，有力推动了PSO研究。目前，其研究现状大致分为两个方向：算法的改进，算法的应用。
第7页
由于粒子群算法提出的时间不长，算法缺乏深刻的的理论分析，数学基础相对薄弱，且存在许多不完善和未涉及到的问题。因此，迄今已经出现了很多对粒子群优化算法的改进方法。例如：混合PSO(HPSO)算法、杂交PSO算法、协同PSO算法、基于模拟退火的PSO算法、自适应变异的PSO算法、离散PS0、自适应PSO、耗散的PSO，GA-PSO等多种粒子群优化算法。如何利用有效的数学工具对算法的收敛性，收敛速度的估计，计算的复杂性，以及预防陷入局部最优和参数设置影响等进行分析将是今后的研究热点之一。
由于PSO算法概念简单，易于实现，因而在短期内得到很大发展，迅速得到了国际演化计算研究领域的认可，并在很多领域得到应用：
PSO的第一个应用是神经网络训练。Kennedy和Eberhart的报告说明PSO成功用于正确区分XOR问题，包括13维搜索空间的函数优化问题。Salerno也应用PSO到训练神经网络学习XOR问题，比梯度递减算法更好。另一个神经网络训练的例子中Eberhart和Hu用PSO训练神经网络以正确区分病人的颤抖行为是普通颤动或是患有帕金森氏症。他们在PSO算法中使惯性权值在2000代中从0.9到0.4线性递减，获得很好的效果。
PSO算法也用来优化带权神经网络的连接结构。Zhang和Shao的PSONN算法使用PSO算法优化神经网络，成功地用来评估喷气机燃料的质量。乘法单元神经网络是带误差函数的神经网络，很难训练。多种基于梯度的优化算法在搜索空间陷入多个局部最小值。Engelbrecht和Ismail研究了不同优化算法训练乘法单元神经网络的能力，发现在乘法单元神经网络的训练问题上，PSO比其它随机搜索算法还要好，如GA和LeapFrog算法。
Eberhart等人在文献[7]描述了PSO的一些其他应用。例如用训练神经网络来评估电池充电的状态；PSO用来优化用于促进微生物的生长的化学成分配方，找到的解比之前使用其它优化算法发现的各种解有明显的改进。PSO的优势之一是能更加有效地对搜索空间内的大范围区域进行搜索，这使得PSO能够在搜索空间里发现更好的解，并且该解明显区别于使用其它已知算法发现的解。
另一个与神经网络训练有关的应用是Fukuyama和Yoshida发表的论文。他们表明PSO优化连续和离散变量都非常有效。在速度更新前，通过简单离散值来调整PSO的更新公式，粒子的位置也是如此。只要适当调整，这些离散变量与连续变量可以自由组合，应用到更新公式。他们使用的是惯性权值线性递减的PSO，结果表明比原来使用的RTS算法效率更高。Fukuyama等人把Angeline的混合PSO运用到相同问题，似乎混合PSO算法更有效。进一步的研究还发现相同参数设置的PSO应用在不同电力系统问题上获得了高质量的解。
标准粒子群算法主要适用于连续空间函数的优化问题，如何将算法应用于离散空
第8页
间的优化问题，特别是非数值优化问题，将是粒子群算法的一个重要研究方向。此外，充分利用其他进化算法以改善微粒群算法存在的不足，也是值得研究的问题。
总之，PSO算法的应用十分广泛，有着比较好的发展前景。目前PSO的研究尚处于初期，还有许多问题值得做进一步的研究。
1、PSO算法的理论研究还很缺乏，目前还没有粒子群理论的数学证明。 2、由于实际问题的多样性和复杂性，尽管目前已经有了多种不同版本的PSO改进算法但这些PSO算法不具有通用性，或者参数的设置要求使用者具备较高的经验，否则难以达到理想的效果。
3、开拓PSO算法的新的应用领域是一项很有意义的工作。 4、如何将PSO应用于组合优化问题也是一个重要的研究方向。
1.4 粒子群优化算法的研究意义
粒子群算法自1995年被提出之后，得到了数值优化领域的广泛关注，吸引了大量的研究者。如何加快算法的收敛速度和避免早熟收敛问题，一直是大多数研究者关注的重点，也是所有随机搜索算法共同面临的两个主要难题。这两个问题之间本身就存在很复杂的关系，在很多情况下是互相冲突的两个目标。在避免早熟收敛方面，现有的大量研究涉及如何让算法跳出局部最优点。在加快收敛速度方面，主要的工作集中在如何选择最优的算法参数，以及从其他智能优化算法中借鉴一些思想对PSO算法的主要框架加以修改。
粒子群优化技术的应用领域己扩展到组合优化、数据分类、数据聚类、模式识别、电信Qos管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面。
由此可见，作为一类现代启发式优化算法，粒子群优化算法理论及其应用研究都具有相当重要的学术意义和现实价值。