粒子群算法邻域拓扑结构研究.docx

粒子群算法邻域拓扑结构研究 摘要：粒子群算法（PSO算法）是一种启发式全局优化技术。PSO的邻域拓扑结构是决定粒子群优化算法效果的一个很重要的因素，不同邻域拓扑结构的粒子群算法，效果差别很大。文章分析了邻域拓扑结构与PSO算法的关系，阐述了粒子群算法邻域拓扑结构研究现状，提出了未来可能的研究方向。关键词：粒子群算法；PSO算法；邻域拓扑结构；启发式：F235：A：1009-2374（2009）16-0036-02粒子群优化算法PSO（Particle Swarm Optimization，简称PSO）是由Kennedy 和Eberhart于1995年提出的一种启发式全局优化技术。由于PSO概念简单，易于实现，因而短期内得到很大发展，迅速得到了国际演化计算研究领域的认可，并在很多领域得到应用，如电力系统优化、TSP问题、神经网络训练、数字电路优化、函数优化、交通事故探测、参数辨识等。PSO算法在多维空间函数寻优、动态目标寻优等方面有着收敛速度快、解质量高、鲁棒性好等优点。但是，随着迭代次数的增加，其易于陷入局部最优的缺点就暴露无疑，因此，近年来很多学者均致力于PSO算法的改进工作。目前，对粒子群优化算法的改进主要体现在以下几个方面：参数的改进和优化、惯性权值和加速因子的改进、混合PSO、领域拓扑结构等。PSO的拓扑结构是指整个群体中所有粒子之间相互连接的方式，而PSO的邻域结构是指单个粒子如何与其它粒子相连。前者是整体性质，后者是局部性质，邻域结构决定了拓扑结构。潘峰等人的研究表明，邻域结构是决定粒子群优化算法效果的一个很重要的因素，不同邻域结构的粒子群优化算法，效果会有很大的差别。邻域拓扑结构的改进是粒子群优化算法研究的一个很重要的方面。一、邻域拓扑结构与PSO算法的关系目前，对于种群邻域拓扑结构的研究大多基于如下五种模式：1全局（gbest）：种群中所有个体相互通信。该模式中，信息传递的速度比较快，所以收敛速度也比较快，但是也较容易陷入到局部极小点。2局部（lbest）：种群中相邻个体之间通信。局部模式中所有粒子排成一个环状结构，这种结构信息传递得比较慢，收敛速度较慢，但是也较不容易陷入局部极值点。34 类（four clusters）：整个粒子群中有4个类组成，各个类内部相互完全通信，类间通信较少。4金字塔（pyramid）：三角形线框的金字塔结构，即四面体结构，粒子分布在四面体的四个顶点上，然后所有这样的四面体相互连接起来。5冯诺以曼（Von Neumann）：四方网格，顶点相连形成环面，即每个粒子与上下左右四个最邻近的粒子相互连接，形成一种网状的结构。（一）影响拓扑结构的主要因素影响拓扑结构的因素比较多，但是有两个最重要的特征可以量化，一是与单个粒子直接相连的粒子的个数k，k的大小决定了单个粒子的邻域大小，从而影响信息在粒子间传递的速度，通常k值比较大的群体收敛比较快，反之比较慢。第二个影响因素是整个群体中类的个数c，一个类定义为互为邻域的粒子的集合，每个类中的粒子之间相互连接数为k。类的个数与信息在粒子之间的传递通常是减函数关系。根据watts的研究结果，信息在粒子构成的网络中流动时，决定它的传递速度的一个很重要的因素是从一个粒子到另一个相邻粒子的平均最短距离，而平均最短距离和k以及c有高度的相关性。（二）邻域结构和迭代式之间的对应关系邻域结构和粒子群的迭代式之间存在着对应关系，不同的邻域结构影响种群中当前粒子的速度和位置。当前粒子位置的定义随着邻域大小的改变而改变，整个系统的最后输出解为所有当前粒子位置中的最优值。二、邻域拓扑结构的研究进展（一）基于粒子划分的邻域结构局部模式PSO中粒子的邻域是基于粒子序号划分的。每个粒子仅与其附近的两个粒子相互交流信息，从而能有效地保证种群的多样性。此外，这里的邻域仅与粒子的下标有关，而与粒子的真实位置无关，从而可以有效地对搜索空间进行搜索，但有时会影响算法效率。作为该结构的推广，随机环形结构针对环形结构的邻域仅由粒子的下标决定的缺点做了一定调整，其邻域虽然主体仍由下标决定，但存在两个粒子的邻域可以随机选择，从而在一定程度上提高了算法效率。Suganthan提出了基于粒子的空间位置划分的方案。在迭代中，计算每一个粒子与群中其他粒子的距离，记录任何2个粒子间的最大距离为dmax。对每一粒子按照Xa-Xb/dmax计算比值，其中Xa-Xb是当前粒子a到粒子b的距离。而选择阈值e根据迭代次数而变化。当另一粒子b满足Xa-Xb/dmax阈值e时，则b成为当前粒子的邻域。所有满足该条件的粒子组成Ni，其他同原局部版PSO。应用改进的邻域规则，且采用时变的PSO在绝大多数测试中都取得了比全局版PSO更优良的性能。（二）动态的邻域结构Suganthan提出了一种具有可变邻域算子的微粒群算法，该算法初始阶段微粒的邻域为它自身，随着进化代数的增长，邻域逐渐扩大至整个群体。在此基础上，孔丽丹等提出了基于动态邻域的量子行为的粒子群优化算法（NQPSO）。在NQPSO中，为了定义一个邻域，根据粒子的空间位置，在每次迭代中，种群中一个粒子（中心粒子）到其他粒子之间的距离都被计算出来，并且用变量max_dist来标记该中心粒子与其他粒子之间距离的最大值。对于每一个粒子i来说，利用粒子间的距离，可以获得一个比值disti/max_dist，disti是粒子i到中心粒子的距离，这个比值可用来作为选择相邻粒子的依据，利用较大比值或较小比值作为选择依据。在定义好一个邻域后，要确定其局部最优解Lbest，再利用进化方程进行进化，此时进化方程中所有粒子中目前取得的最优解被当前邻域的局部最优解替代。NQPSO算法具有强的全局搜索能力，在解决高维的优化问题中能获得较好的效果。但由于加入了邻域定义，运算量增大。另外Richards和Ventura提出一种邻域结构随算法逐步由局部结构模式向全局结构模式进化的微粒群算法，结果发现该方法对局部极值点较多的函数能起到更好的作用。（三）引入有向图概念的邻域结构模型Mohais等将有向图的概念引入邻域结构模型，提出了两种动态改变邻域结构的方法：1随机边迁移，即随机选择节点度大于1的节点移除一条边，同时选择一个节点度小于N（节点个数）的节点与之建立连接。2邻域重构，该方法每间隔一定时间段就对邻域结构进行完全初始化，整个过程保持邻域大小和节点出度保持不变。实验结果证明这两种方法能够取得较von Neumann等其它邻域模型相当甚至更好的效果。（四）基于小世界的邻域结构模型从社会结构学角度来看邻域结构。社会结构定义为人与人之间的连接关系，小世界（Small world）理论认为，此类关系分为两种基本类型，一是强连接关系，二是弱连接。前者是指个人之间产生的紧密的、稳定的连接，后者是指偶然产生的、不稳定的连接。强连接关系基本决定了群体的结构，而弱连接关系则非常显著的改变群体间信息流动的快慢。在一个具有稳定结构的群体中，随机的加上几个弱连接关系，将大大的提高群体间信息流动和传递的速度，从而也将加快收敛的速度。穆华平和曾建潮提出了基于“小世界”模型的邻域动态演化的微粒群算法（DSWN-PSO）。算法将每个微粒看作一个节点，采用NW模型构造微粒间的邻域关系。算法初始阶段将种群中的每个微粒按照编号构造成为一个环形规则网络，每个节点都与它左右相邻的k/2（k（五）其它改进Kenney提出了混和空间邻域和环形拓扑方法的另一个局部PSO版本，称为社会趋同法。因为生活中人们往往是试图追随一个群体的共同观点，而不是群体中某个人的立场。将该思想应用到PSO中，即不用每个粒子的经验而是用它所属空间聚类的共同经验来更新自己。三、进一步的研究方向种群邻域拓扑结构对PSO算法性能的影响主要有两个层面:其一，可选取不同粒子的局部邻域结构；其二，可定义不同的局部邻域之间的通信方式。PSO算法中粒子分布的邻域拓扑结构的改进，不仅可提高寻优解的精度，而且可加快收敛速度。拓扑结构的研究对PSO的发展具有重要的意义。1在实际的应用中很多问题都是随时间动态变化的，因而将PSO应用到动态问题领域具有重要的现实意义。2不同的粒子群邻域拓扑结构是对不同类型社会的模拟，研究不同拓扑结构的适用范围，对PSO算法推广和使用有重要意义。3使用邻域带来的一个问题是增加了配置算法的难度，可能导致研究者不敢轻易尝试使用PSO算法。一个有前途的研究方法是自动产生不同种群大小的邻域拓扑结构。4引入带权图，研究不同个体粒子所携带的信息对其他粒子的影响程度，从而控制信息流动是值得研究的。5鲁棒性是系统在异常和危险情况下系统生存的关键。如何改进拓扑结构以提高鲁棒性是值得研究的。参考文献1Kennedy J，Eberhart R.CParticle Swarm Optimization.In:Proccedings of the IEEE International Conference on Neural networks，Perth Australia，19952潘峰，陈杰，甘明刚粒子群优化算法模型分析J自动化学报，2006，32（3）3D.J.watts.Small Worlds:The Dynamics of Network Between Oder and Randomness，Princeton university Press，1999.4Baskar S，Suganthan P N.A Novel Concurrent Particle Swarm OptimizationC/ Proceedings of the 2004 Congress on Evolutionary ComputationPiscataway，NJ：IEEE Press，20045Suganthan P N.Particle swarm optimizer with neighborhood operatorCProc Con Evolutionary Computation，Washington DC，1999，（7）6孔丽丹，须文波，孙俊基于动态邻域的QPSO算法J计算机工程与应用，2008，44（13）.7Mohais A S，Mendes R， Ward C，Posthoff C. Neighborhood ReStructuring in Particle Swarm OptimizationCAustralian Conference on Artificial Intelligence. Heidelberg，Germany:Springer Berlin，20058穆华平，曾建潮基于小世界模型动态演化邻域的微粒群算法J系统仿真学报，2008，20（15） -全文完-