具有多种群框架的pso算法

‘壹’ pso的算法结构

对微粒群算法结构的改进方案有很多种，对其可分类为：采用多个子种群；改进微粒学习对象的选取策略；修改微粒更新迭代公式；修改速度更新策略；修改速度限制方法、位置限制方法和动态确定搜索空间；与其他搜索技术相结合；以及针对多模问题所作的改进。
第一类方案是采用多个子种群。柯晶考虑优化问题对收敛速度和寻优精度的双重要求并借鉴多群体进化算法的思想，将寻优微粒分成两组，一组微粒采用压缩因子的局部模式PSO算法，另一组微粒采用惯性权重的全局模式PSO算法，两组微粒之间采用环形拓扑结构。对于高维优化问题，PSO算法需要的微粒个数很多，导致计算复杂度常常很高，并且很难得到好的解。因此，出现了一种协作微粒群算法（Cooperative ParticleSwarm Optimizer, CPSO-H），将输入向量拆分成多个子向量，并对每个子向量使用一个微粒群来进行优化。虽然CPSO-H算法使用一维群体来分别搜索每一维，但是这些搜索结果被一个全局群体集成起来之后，在多模问题上的性能与原始PSO算法相比有很大的改进。Chow使用多个互相交互的子群，并引入相邻群参考速度。冯奇峰提出将搜索区域分区，使用多个子群并通过微粒间的距离来保持多样性。陈国初将微粒分成飞行方向不同的两个分群，其中一分群朝最优微粒飞行，另一分群微粒朝相反方向飞行；飞行时，每一微粒不仅受到微粒本身飞行经验和本分群最优微粒的影响，还受到全群最优微粒的影响。Niu在PSO算法中引入主—从子群模式，提出一种多种群协作PSO算法。Seo提出一种多组PSO算法（Multigrouped PSO），使用N组微粒来同时搜索多模问题的N个峰。Selleri使用多个独立的子群，在微粒速度的更新方程中添加了一些新项，分别使得微粒向子群历史最优位置运动，或者远离其他子群的重心。王俊年借鉴递阶编码的思想，构造出一种多种群协同进化PSO算法。高鹰借鉴生态学中环境和种群竞争的关系，提出一种基于种群密度的多种群PSO算法。
第二类方案是改进微粒学习对象的选取策略。Al-kazemi提出多阶段PSO算法，将微粒按不同阶段的临时搜索目标分组，这些临时目标允许微粒向着或背着它自己或全局最好位置移动。Ting对每个微粒的pBest进行操作，每一维从其他随机确定的维度学习，之后如果新的pBest更好则替换原pBest；该文还比较了多种不同学习方式对应的PSO算法的性能。Liang提出一种新颖的学习策略CLPSO，利用所有其他微粒的历史最优信息来更新微粒的速度；每个微粒可以向不同的微粒学习，并且微粒的每一维可以向不同的微粒学习。该策略能够保持群体的多样性，防止早熟收敛，可以提高PSO算法在多模问题上的性能；通过实验将该算法与其它几种PSO算法的变种进行比较，实验结果表明该算法在解决多模复杂问题时效果很好。Zhao在PSO算法中使用适应值最好的n个值来代替速度更新公式中的gBest。Abdelbar提出一种模糊度量，从而使得每个邻域中有多个适应值最好的微粒可以影响其它微粒。Wang也采用多个适应值最好的微粒信息来更新微粒速度，并提出一种模糊规则来自适应地确定参数。崔志华提出一种动态调整的改进PSO算法，在运行过程中动态调整极限位置，使得每个微粒的极限位置在其所经历的最好位置与整体最好位置所形成的动态圆中分布。与原始PSO算法相反，有一类方法是远离最差位置而非飞向最优位置。Yang提出在算法中记录最差位置而非最优位置，所有微粒都远离这些最差位置。与此类似，Leontitsis在微粒群算法中引入排斥子的概念，在使用个体最优位置和群体最优位置信息的同时，在算法中记录当前的个体最差位置和群体最差位置，并利用它们将微粒排斥到最优位置，从而让微粒群更快地到达最优位置。孟建良提出一种改进的PSO算法，在进化的初期，微粒以较大的概率向种群中其他微粒的个体最优学习；在进化后期，微粒以较大的概率向当前全局最优个体学习。Yang在PSO算法中引入轮盘选择技术来确定gBest，使得所有个体在进化早期都有机会引领搜索方向，从而避免早熟。
第三类方案是修改微粒更新公式。Hendtlass在速度更新方程中给每个微粒添加了记忆能力。He在速度更新方程中引入被动聚集机制。曾建潮通过对PSO算法的速度进化迭代方程进行修正，提出一种保证全局收敛的随机PSO算法。Zeng在PSO算法中引入加速度项，使得PSO算法从一个二阶随机系统变为一个三阶随机系统，并使用PID控制器来控制算法的演化。为了改进PSO算法的全局搜索能力，Ho提出一种新的微粒速度和位置更新公式，并引入寿命（Age）变量。
第四类方案是修改速度更新策略。Liu认为过于频繁的速度更新会弱化微粒的局部开采能力并减慢收敛，因此提出一种松弛速度更新（RVU）策略，仅当微粒使用原速度不能进一步提高适应值时才更新速度，并通过试验证明该策略可以大大减小计算量并加速收敛。罗建宏对同步模式和异步模式的PSO算法进行了对比研究，试验结果表明异步模式收敛速度显着提高，同时寻优效果更好。Yang在微粒的更新规则中引入感情心理模型。Liu采用一个最小速度阈值来控制微粒的速度，并使用一个模糊逻辑控制器来自适应地调节该最小速度阈值。张利彪提出了对PSO算法增加更新概率，对一定比例的微粒并不按照原更新公式更新，而是再次随机初始化。Dioan利用遗传算法（GA）来演化PSO算法的结构，即微粒群中各微粒更新的顺序和频率。
第五类方案是修改速度限制方法、位置限制方法和动态确定搜索空间。Stacey提出一种重新随机化速度的速度限制和一种重新随机化位置的位置限制。Liu在[76]的基础上，在PSO算法中引入动量因子，来将微粒位置限制在可行范围内。陈炳瑞提出一种根据微粒群的最佳适应值动态压缩微粒群的搜索空间与微粒群飞行速度范围的改进PSO算法。
第六类方案是通过将PSO算法与一些其他的搜索技术进行结合来提高PSO算法的性能，主要目的有二，其一是提高种群多样性，避免早熟；其二是提高算法局部搜索能力。这些混合算法包括将各种遗传算子如选择、交叉、变异引入PSO算法，来增加种群的多样性并提高逃离局部最小的能力。Krink通过解决微粒间的冲突和聚集来增强种群多样性，提出一种空间扩展PSO算法（Spatial ExtensionPSO，SEPSO）；但是SEPSO算法的参数比较难以调节，为此Monson提出一种自适应调节参数的方法。用以提高种群多样性的其他方法或模型还包括“吸引—排斥”、捕食—被捕食模型、耗散模型、自组织模型、生命周期模型（LifeCycle model）、贝叶斯优化模型、避免冲突机制、拥挤回避（Crowd Avoidance）、层次化公平竞争（HFC）、外部记忆、梯度下降技术、线性搜索、单纯形法算子、爬山法、劳动分工、主成分分析技术、卡尔曼滤波、遗传算法、随机搜索算法、模拟退火、禁忌搜索、蚁群算法（ACO）、人工免疫算法、混沌算法、微分演化、遗传规划等。还有人将PSO算法在量子空间进行了扩展。Zhao将多主体系统（MAS）与PSO算法集成起来，提出MAPSO算法。Medasani借鉴概率C均值和概率论中的思想对PSO算法进行扩展，提出一种概率PSO算法，让算法分勘探和开发两个阶段运行。
第七类方案专门针对多模问题，希望能够找到多个较优解。为了能使PSO算法一次获得待优化问题的多个较优解，Parsopoulos使用了偏转（Deflection）、拉伸（Stretching）和排斥（Repulsion）等技术，通过防止微粒运动到之前已经发现的最小区域，来找到尽可能多的最小点。但是这种方法会在检测到的局部最优点两端产生一些新的局部最优点，可能会导致优化算法陷入这些局部最小点。为此，Jin提出一种新的函数变换形式，可以避免该缺点。基于类似思想，熊勇提出一种旋转曲面变换方法。
保持种群多样性最简单的方法，是在多样性过小的时候，重置某些微粒或整个微粒群。Lvbjerg在PSO算法中采用自组织临界性作为一种度量，来描述微粒群中微粒相互之间的接近程度，来确定是否需要重新初始化微粒的位置。Clerc提出了一种“Re-Hope”方法，当搜索空间变得相当小但是仍未找到解时（No-Hope），重置微粒群。Fu提出一种带C-Pg变异的PSO算法，微粒按照一定概率飞向扰动点而非Pg。赫然提出了一种自适应逃逸微粒群算法，限制微粒在搜索空间内的飞行速度并给出速度的自适应策略。
另一种变种是小生境PSO算法，同时使用多个子种群来定位和跟踪多个最优解。Brits还研究了一种通过调整适应值计算方式的方法来同时找到多个最优解。Li在PSO算法中引入适应值共享技术来求解多模问题。Zhang在PSO算法中采用顺序生境（SequentialNiching）技术。在小生境PSO算法的基础上，还可以使用向量点积运算来确定各个小生境中的候选解及其边界，并使该过程并行化，以获得更好的结果。但是，各种小生境PSO算法存在一个共同的问题，即需要确定一个小生境半径，且算法性能对该参数很敏感。为解决该问题，Bird提出一种自适应确定niching参数的方法。
Hendtlass在PSO算法中引入短程力的概念，并基于此提出一种WoSP算法，可以同时确定多个最优点。刘宇提出一种多模态PSO算法，用聚类算法对微粒进行聚类，动态地将种群划分成几个类，并且使用微粒所属类的最优微粒而非整个种群的最好微粒来更新微粒的速度，从而可以同时得到多个近似最优解。Li在PSO算法中引入物种的概念，但是由于其使用的物种间距是固定的，该方法只适用于均匀分布的多模问题；为此，Yuan对该算法进行扩展，采用多尺度搜索方法对物种间距加以自适应的调整。
此外，也有研究者将PSO算法的思想引入其他算法中，如将PSO算法中微粒的运动规则嵌入到进化规划中，用PSO算法中的运动规则来替代演化算法中交叉算子的功能。

‘贰’ pso的拓扑结构

通过设计不同类型的拓扑来提高PSO算法的性能，也是一个活跃的研究方向。
既然是研究拓扑结构，一定会涉及到邻域的概念。邻域可以是静态的，也可以是动态确定的。邻域的确定有两种方式，一种为根据微粒的标志（或索引）来确定，与距离无关；而另一种为根据微粒之间的拓扑距离来确定。显然，按照拓扑距离动态确定邻域的计算量会比较大。
大多数研究针对静态拓扑来展开。Kennedy分析了各种各样的静态邻域结构以及它们对算法性能的影响，认为星形、环形和Von Neumann拓扑适用性最好，并宣称小邻域的PSO算法在复杂问题上性能较好，但是大邻域的PSO算法在简单问题上性能会更好。Kennedy还基于K均值聚类算法提出混合空间邻域和环形拓扑方法的另一个局部PSO算法版本，称为社会趋同法，不用每个微粒的经验而是用它所属空间聚类的共同经验来更新自己。Engelbrecht研究了基本的PSO算法定位并维持多个最优点的能力，发现全局邻域PSO（gBest PSO）算法对此根本无能为力，而局部邻域PSO（nBest PSO）算法则是效率很低。
Peram发展了一种基于适应值距离比的PSO算法（FDR-PSO），使用近邻的交互。在更新速度的每一维分量时，FDR-PSO算法选择一个其他微粒的nBest，该微粒应具有更高的适应值，并且与待更新的微粒距离更近。该算法在每一维速度更新中选取不同邻域微粒，比在所有速度维只选取一个邻域微粒更有效。Peer用不同的邻域拓扑来研究保证收敛PSO（GCPSO）算法的性能。Parsopoulos将全局版本和局部版本组合在一起，构建了一个统一微粒群算法（Unified ParticleSwarm Optimizer, UPSO）。与此有异曲同工之效的是Xu提出的扩展PSO算法，同时使用个体最优、全局最优以及邻域中的局部最优来更新速度。Mendes介绍了一种完全通知（Fully informed）的PSO算法，使用微粒的所有邻居信息来更新速度，每个微粒对其邻居的影响基于它的适应值大小和邻域大小进行加权。在此基础上，方峻发展出一种基于加权有向拓扑的的改进算法，体现微粒之间影响的不平衡性。
也有少部分研究工作是关于动态拓扑的。Suganthan使用了一个动态调整的邻域，微粒的邻域逐渐增大，直到包含所有的微粒为止。Hu研究了一种动态邻域，在每一代的性能空间中m个最近的微粒被选作新的邻居。Mohais研究了两种随机动态邻域拓扑。Binkley提出一种带影响范围的PSO算法，最优微粒对其余各微粒的影响能力取决于它们之间的距离。分层PSO算法使用基于种群中每个微粒的性能得到的动态树分层概念来定义邻域结构。
上述邻域拓扑均用于确定群体经验gBest，而Jian使用邻域拓扑来确定个体经验pBest。

‘叁’ pso的并行算法

与大多数随机优化算法相似，当适应值评价函数的计算量比较大时，PSO算法的计算量会很大。为了解决该问题，研究者提出了并行PSO算法。与并行遗传算法类似，并行PSO算法也可以有三种并行群体模型：主从并行模型、岛屿群体模型和邻接模型。
Schutte采用同步实现方式，在计算完一代中所有点的适应值之后才进入下一代。这种并行方法虽然实现简单，但常常会导致并行效率很差。故而有人提出异步方式的并行算法，可以在对数值精度影响不大的条件下提高PSO算法的并行性能。这两种方式采用的都是主从并行模型，其中异步方式在求解上耦合性更高，更容易产生通信瓶颈。
Baskar提出一种两个子种群并行演化的并发PSO算法，其中一个子种群采用原始的PSO算法，另一个子种群采用基于适应值距离比的PSO算法（FDR-PSO）；两个子种群之间频繁地进行信息交换。而El-Abd研究了在子种群中采用局部邻域版本的协作PSO算法，并研究了多种信息交换的方式及其对算法性能的影响。黄芳提出一种基于岛屿群体模型的并行PSO算法，并引入一种集中式迁移策略，提高了求解效率，同时改善了早收敛现象。
Li提出延迟交换信息的并行算法属于邻接模型，该算法可以提高速度，但可能使得解的质量变差。

‘肆’ 粒子群优化算法（PSO）的应用

这个属于多目标优化问题，你可以把参考价格、外观样式、网络类型、屏幕参数和摄像头像素等分别给予不同的权重值，作为一个目标函数，目标函数值就是综合评价得分，然后用微粒群算法求解。

‘伍’ 粒子群优化算法

姓名：杨晶晶  学号：21011210420  学院：通信工程学院

【嵌牛导读】

传统的多目标优化方法是将多目标问题通过加权求和转化为单目标问题来处理的,而粒子算法主要是解决一些多目标优化问题的（例如机械零件的多目标设计优化）,其优点是容易实现,精度高,收敛速度快。

【嵌牛鼻子】粒子群算法的概念、公式、调参以及与遗传算法的比较。

【嵌牛提问】什么是粒子群算法？它的计算流程是什么？与遗传算法相比呢？

【嵌牛正文】

1. 概念

        粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation），源于对鸟群捕食的行为研究。

        粒子群优化算法的基本思想：是通过群体中个体之间的协作和信息共享来寻找最优解。

        PSO的优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。

2. 算法

2.1 问题抽象

        鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子i在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)。每个粒子都有一个由目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)，这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

2.2 更新规则

      PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest，gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。

      公式(1)的第一部分称为【记忆项】，表示上次速度大小和方向的影响；公式(1)的第二部分称为【自身认知项】，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式(1)的第三部分称为【群体认知项】，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

      以上面两个公式为基础，形成了PSO的标准形式。

      公式(2)和 公式(3)被视为标准PSO算法。

2.3 标准PSO算法流程

    标准PSO算法的流程：

    1）初始化一群微粒(群体规模为N)，包括随机位置和速度；

    2）评价每个微粒的适应度；

    3）对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest；

    4）对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest；

    5）根据公式(2)、(3)调整微粒速度和位置；

    6）未达到结束条件则转第2）步。

        迭代终止条件根据具体问题一般选为最大迭代次数Gk或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值。

      公式(2)和(3)中pbest和gbest分别表示微粒群的局部和全局最优位置。

    当C1＝0时，则粒子没有了认知能力，变为只有社会的模型(social-only)：

被称为全局PSO算法。粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题

比标准PSO 更易陷入局部最优。

    当C2＝0时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型：

      被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。

2.4 参数分析

        参数：群体规模N，惯性因子 ，学习因子c1和c2，最大速度Vmax，最大迭代次数Gk。

        群体规模N：一般取20～40，对较难或特定类别的问题可以取到100～200。

        最大速度Vmax：决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点；如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。

        权重因子：包括惯性因子和学习因子c1和c2。使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。c1和c2代表将每个粒子推向pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。

        参数设置：

        1)如果令c1＝c2＝0，粒子将一直以当前速度的飞行，直到边界。很难找到最优解。

        2)如果＝0，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。较大时，具有较强的全局搜索能力；较小时，具有较强的局部搜索能力。

        3)通常设c1＝c2＝2。Suganthan的实验表明：c1和c2为常数时可以得到较好的解，但不一定必须等于2。Clerc引入收敛因子(constriction factor) K来保证收敛性。

      通常取为4.1,则K＝0.729.实验表明，与使用惯性权重的PSO算法相比，使用收敛因子的PSO有更快的收敛速度。其实只要恰当的选取和c1、c2，两种算法是一样的。因此使用收敛因子的PSO可以看作使用惯性权重PSO的特例。

        恰当的选取算法的参数值可以改善算法的性能。

3. PSO与其它算法的比较

3.1 遗传算法和PSO的比较

  1)共性：

  (1)都属于仿生算法。

  (2)都属于全局优化方法。

  (3)都属于随机搜索算法。

  (4)都隐含并行性。

  (5)根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。

  (6)对高维复杂问题，往往会遇到早熟收敛和收敛 性能差的缺点，都无法保证收敛到最优点。

    2)差异：   

    (1)PSO有记忆，好的解的知识所有粒子都保 存，而GA（Genetic Algorithm），以前的知识随着种群的改变被改变。

    (2)PSO中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单共享项信息机制。而GA中，染色体之间相互共享信息，使得整个种群都向最优区域移动。

    (3)GA的编码技术和遗传操作比较简单，而PSO相对于GA，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。

    (4)应用于人工神经网络(ANN)

    GA可以用来研究NN的三个方面：网络连接权重、网络结构、学习算法。优势在于可处理传统方法不能处理的问题，例如不可导的节点传递函数或没有梯度信息。

    GA缺点:在某些问题上性能不是特别好；网络权重的编码和遗传算子的选择有时较麻烦。

    已有利用PSO来进行神经网络训练。研究表明PSO是一种很有潜力的神经网络算法。速度较快且有较好的结果。且没有遗传算法碰到的问题。

‘陆’ pso的多目标优化

在多目标优化问题中，每个目标函数可以分别独立进行优化，然后为每个目标找到最优值。但是，很少能找到对所有目标都是最优的完美解，因为目标之间经常是互相冲突的，只能找到Pareto最优解。
PSO算法中的信息共享机制与其他基于种群的优化工具有很大的不同。在遗传算法（GA）中，染色体通过交叉互相交换信息，是一种双向信息共享机制。但是在PSO算法中，只有gBest（或nBest）给其他微粒提供信息，是一种单向信息共享机制。由于点吸引特性，传统的PSO算法不能同时定位构成Pareto前锋的多个最优点。虽然通过对所有目标函数赋予不同的权重将其组合起来并进行多次运行，可以获得多个最优解，但是还是希望有方法能够一次同时找到一组Pareto最优解。
在PSO算法中，一个微粒是一个独立的智能体，基于其自身和同伴的经验来搜索问题空间。前者为微粒更新公式中的认知部分，后者为社会部分，这二者在引导微粒的搜索方面都有关键的作用。因此，选择适当的社会和认知引导者（gBest和pBest）就是MO-PSO算法的关键点。认知引导者的选择和传统PSO算法应遵循相同的规则，唯一的区别在于引导者应按照Pareto支配性来确定。社会引导者的选择包括两个步骤。第一步是建立一个从中选取引导者的候选池。在传统PSO算法中，引导者从邻居的pBest之中选取。而在MO-PSO算法中更常用的方法是使用一个外部池来存储更多的Pareto最优解。第二步就是选择引导者。gBest的选择应满足如下两个标准：首先，它应该能为微粒提供有效的引导来获得更好的收敛速度；第二，它还需要沿Pareo前锋来提供平衡的搜索，以维持种群的多样性。文献中通常使用两种典型的方法：（1）轮盘选择模式，该方式按照某种标准进行随机选择，其目的是维持种群的多样性；（2）数量标准：按照某种不涉及随机选择的过程来确定社会引导者。
Moore最早研究了PSO算法在多目标优化中的应用，强调了个体和群体搜索二者的重要性，但是没有采用任何维持多样性的方法。Coello在非劣最优概念的基础上应用了一个外部“容器”来记录已找到的非支配向量，并用这些解来指导其它微粒的飞行。Fieldsend采用一种称为支配树的数据结构来对最优微粒进行排序。Parsopoulos应用了权重聚合的方法。Hu应用了动态邻域，并在此基础上利用扩展记忆，按词典顺序依次优化各个目标。Ray使用聚集机制来维持多样性，并用一个多水平筛来处理约束。Lu使用了动态种群策略。Bartz-Beielstein采用归档技术来提高算法性能。Li在PSO算法中采用NSGA-II算法中的主要机制，在局部最优微粒及其后代微粒之间确定局部最优微粒；并此基础上又提出一种新的算法，在适应值函数中使用最大最小策略来确定Pareto支配性。张利彪使用多个目标函数下各最优位置的均值来指导微粒飞行。Pulido使用多个子种群并采用聚类技术来求解多目标规划问题。Mahfouf采用加权聚合方法来计算微粒的适应值，并据此确定引导微粒的搜索。Salazar-Lechuga使用适应值共享技术来引导微粒的搜索。Gong提出微粒角度的概念，并使用最小微粒角度和微粒密度来确定局部最优和全局最优微粒。基于AER模型，Zhang提出一种新的智能PSO模型，来将种群驱向Pareto最优解集。Ho提出一种新的适应值分配机制，并使用寿命（Age）变量来保存和选择最优历史记录。Huang将CLPSO算法应用到多目标规划中。Ho提出另一种基于Pareto的与尺度无关的适应值函数，并使用一种基于正交试验设计的智能运动机制（IMM）来确定微粒的下一步运动。Branke系统研究了多种个体最优微粒的选择方法对MOPSO算法性能的影响。张勇考虑储备集更新策略在多目标PSO算法中的关键作用，提出一种两阶段储备集更新策略。
原萍提出一种分布式PSO算法—分割域多目标PSO算法（DRMPSO），并将其应用到基站优化问题。向量评价PSO算法（VEPSO）是一种受向量评价遗传算法（VEGA）的启发提出的一种算法，在VEPSO算法中，每个种群仅使用多个目标函数之一来进行评价，同时各种群之间互相交互经验。将每个种群分配到一台网络PC上，即可直接使VEPSO算法并行化，以加速收敛。Vlachogiannis应用并行VEPSO算法来确定发电机对输电系统的贡献。熊盛武利用PSO算法的信息传递机制，在PSO算法中引入多目标演化算法常用的归档技术，并采用环境选择和配对选择策略，使得整个群体在保持适当的选择压力的情况下收敛于Pareto最优解集。
由于适应值的计算非常消耗计算资源，为了减少计算量，需要减少适应值评价的次数。Reyes-Sierra采用适应值继承和估计技术来实现该目标，并比较了十五种适应值继承技术和四种估计技术应用于多目标PSO算法时的效果。
保持MOPSO中的多样性的方法主要有两种：sigma方法和ε-支配方法。Villalobos-Arias在目标函数空间中引入条块划分来形成聚类，从而保持多样性。

‘柒’ pso的来源背景

为了说明粒子群优化算法的发展和形成背景，首先介绍一下早期的简单模型，即Boid（Bird-oid）模型。这个模型是为了模拟鸟群的行为而设计的，它也是粒子群优化算法的直接来源。
一个最简单的模型是这样的：每一个鸟的个体用直角坐标系上的点表示，随机地给它们赋一个初速度和初位置，程序运行的每一步都按照“最近邻速度匹配”规则，很快就会使得所有点的速度变得一样。因为这个模拟太简单而且远离真实情况，于是在速度项中增加了一个随机变量，即在迭代的每一步，除了满足“最近邻速度匹配”之外，每一步速度还要添加一个随机变化的量，这样使得整个模拟看起来更为真实。
Heppner设计了一个“谷地模型”来模拟鸟群的觅食行为。假设在平面上存在一个“谷地”，即食物所在地，鸟群开始时随机地分散在平面上，为了寻觅食物所在地，它们按照如下规则运动：
首先假设谷地的位置坐标为(x0,y0)，单个鸟的位置和速度坐标分别为和(x,y)，用当前位置到谷地的距离s：来衡量当前位置和速度的“好坏程度”，离谷地的距离越近，则越“好”，反之越“坏”。假设每一个鸟具有记忆能力，能够记住曾经达到的最好位置，记作pBest，并记a为系统规定的速度调节常数，rand为一个[0,1]间的随机数，设定速度项按照下述规则变化：
然后假设群体之间可以以某种方式通讯，每个个体能够知道并记住到当前为止整个群体的最好位置，记为gBest，记b为系统规定的速度调节常数，Rand为一个[0,1]间的随机数，则速度项在经过以上调整后，还必须按照下述规则变化：
在计算机上模拟的结果显示：当a/b较大时，所有的个体很快地聚集到“谷地”上；反之，粒子缓慢地摇摆着聚集到“谷地”的四周。通过这个简单的模拟，发现群体能很快地找到一个简单函数（2-1）的最优点。受该模型启发，Kennedy和Eberhart设计出了一种演化优化算法，并通过不断的试验和试错，最后将此算法的基本型固定为：
其中符号的意义同上。研究者认为每个个体被抽象为没有质量和体积，而仅仅具有速度和位置的微粒，故将此方法称为“粒子群”优化算法。
据此，可对粒子群算法小结如下：粒子群算法是一种基于种群的搜索过程，其中每个个体称作微粒，定义为在D维搜索空间中待优化问题的潜在解，保存有其历史最优位置和所有粒子的最优位置的记忆，以及速度。在每一演化代，微粒的信息被组合起来调整速度关于每一维上的分量，继而被用来计算新的微粒位置。微粒在多维搜索空间中不断改变它们的状态，直到到达平衡或最优状态，或者超过了计算限制为止。问题空间的不同维度之间唯一的联系是通过目标函数引入的。很多经验证据已经显示该算法是一个非常有效的优化工具。微粒群优化算法的流程图见图2-1。
以下给出微粒群算法的比较完整的形式化表述。在连续空间坐标系中，微粒群算法的数学描述如下：设微粒群体规模为N，其中每个微粒在D维空间中的坐标位置向量表示为，速度向量表示为，微粒个体最优位置（即该微粒经历过的最优位置）记为，群体最优位置（即该微粒群中任意个体经历过的最优位置）记为。不失一般性，以最小化问题为例，在最初版本的微粒群算法中，个体最优位置的迭代公式为：
群体最优位置为个体最优位置中最好的位置。速度和位置迭代公式分别为：
由于初始版本在优化问题中应用时效果并不太好，所以初始算法提出不久之后就出现了一种改进算法，在速度迭代公式中引入了惯性权重ω，速度迭代公式变为：
虽然该改进算法与初始版本相比复杂程度并没有太大的增加，但是性能却有了很大的提升，因而被广泛使用。一般的，将该改进算法称为标准微粒群算法，而将初始版本的算法称为原始微粒群算法。
通过分析PSO算法的收敛行为，Clerc介绍了一种带收缩因子的PSO算法变种，收缩因子保证了收敛性并提高了收敛速度。此时的速度迭代公式为：
显然，迭代公式（2-7）和（2-8）并无本质区别，只要适当选取参数，二者完全相同。
微粒群算法有两种版本，分别称为全局版本和局部版本。在全局版本中，微粒跟踪的两个极值为自身最优位置pBest和种群最优位置gBest。对应的，在局部版本中，微粒除了追随自身最优位置pBest之外，不跟踪种群最优位置gBest，而是跟踪拓扑邻域中的所有微粒的最优位置nBest。对于局部版本，速度更新公式（2-7）变为：
其中为局部邻域中的最优位置。
每一代中任意微粒迭代的过程见图2-2所示。从社会学的角度来看速度迭代公式，其中第一部分为微粒先前速度的影响，表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动，因此参数ω称为惯性权重（Inertia Weight）；第二部分取决于微粒当前位置与自身最优位置之间的距离，为“认知（Cognition）”部分，表示微粒本身的思考，即微粒的运动来源于自己经验的部分，因此参数c1称为认知学习因子（也可称为认知加速因子）；第三部分取决于微粒当前位置与群体中全局（或局部）最优位置之间的距离，为“社会（Social）”部分，表示微粒间的信息共享与相互合作，即微粒的运动来源于群体中其他微粒经验的部分，它通过认知模拟了较好同伴的运动，因此参数c2称为社会学习因子（也可称为社会加速因子）。
自从PSO算法被提出以来，由于它直观的背景，简单而容易实现的特点，以及对于不同类型函数广泛的适应性，逐渐得到研究者的注意。十余年来，PSO算法的理论与应用研究都取得了很大的进展，对于算法的原理已经有了初步的了解，算法的应用也已经在不同学科中得以实现。
PSO算法是一种随机的、并行的优化算法。它的优点是：不要求被优化函数具有可微、可导、连续等性质，收敛速度较快，算法简单，容易编程实现。然而，PSO算法的缺点在于：（1）对于有多个局部极值点的函数，容易陷入到局部极值点中，得不到正确的结果。造成这种现象的原因有两种，其一是由于待优化函数的性质；其二是由于微粒群算法中微粒的多样性迅速消失，造成早熟收敛。这两个因素通常密不可分地纠缠在一起。（2）由于缺乏精密搜索方法的配合，PSO算法往往不能得到精确的结果。造成这种问题的原因是PSO算法并没有很充分地利用计算过程中获得的信息，在每一步迭代中，仅仅利用了群体最优和个体最优的信息。（3）PSO算法虽然提供了全局搜索的可能，但是并不能保证收敛到全局最优点上。（4）PSO算法是一种启发式的仿生优化算法，当前还没有严格的理论基础，仅仅是通过对某种群体搜索现象的简化模拟而设计的，但并没有从原理上说明这种算法为什么有效，以及它适用的范围。因此，PSO算法一般适用于一类高维的、存在多个局部极值点而并不需要得到很高精度解的优化问题。
当前针对PSO算法开展的研究工作种类繁多，经归纳整理分为如下八个大类：（1）对PSO算法进行理论分析，试图理解其工作机理；（2）改变PSO算法的结构，试图获得性能更好的算法；（3）研究各种参数配置对PSO算法的影响；（4）研究各种拓扑结构对PSO算法的影响；（5）研究离散版本的PSO算法；（6）研究PSO算法的并行算法；（7）利用PSO算法对多种情况下的优化问题进行求解；（8）将PSO算法应用到各个不同的工程领域。以下从这八大类别着手，对PSO算法的研究现状作一梳理。由于文献太多，无法面面俱到，仅捡有代表性的加以综述。

‘捌’ 如何用粒子群优化（PSO）算法实现多目标优化

粒子群算法，也称粒子群优化算法（ParticleSwarmOptimization），缩写为PSO，是近年来发展起来的一种新的进化算法(EvolutionaryAlgorithm-EA)。PSO算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。

‘玖’ PSO优化方向

1. PSO收敛快，特别是在算法的早期，但存在着精度较低，易发散等缺点。加速系数、最大速度等参数太大，粒子可能错过最优解--------------->不收敛； 收敛的情况下，由于所有粒子都向最优的方向飞去，所有粒子趋向同一化（失去多样性）--------->使得 后期收敛速度明显变慢，搜索能力变弱 ，同时算法收敛到一定精度时，无法继续优化。

2. 缺乏数学理论支持，PSO算法本质上是一种随机搜索算法，因此可靠性上让人存疑；

3. 寻找一种好的拓扑结构，加强PSO算法的泛化能力；

4. 平衡全局搜索和局部搜索能力；

（1）粒子群初始化：粒子群初始化对算法性能有一定的影响，分为粒子位置初始化和速度初始化。

         粒子群 位置 初始化的理想效果：初始种群尽可能 均匀覆盖整个 搜索空间。

         一、不推荐的初始化 ：a. 均匀分布随机数

                                          缺点：1. 对搜索空间的覆盖不够好；

                                                     2. 当维度D增大时候，所有的粒子都倾向于靠近搜索空间的边缘：

                                     b. 伪随机数初始化：造成粒子在参数空间的不均匀分布和聚集效应；

          二、推荐的初始化 ：a. 基于centroidal voronoi tessellations (CVTs)的种群初始化方法（这东西是啥没搞懂）；

                                   b. 采用正交设计方法对种群进行初始化；

                                   c. 类随机采样方法中的sobol序列：使得粒子群在参数空间更加均匀；

                                   d. Hammersley方法：感觉这个类似于类随机采样方法（具体我也没搞清楚）；

                                   e. 将粒子建立为带电（positive charged）的模型，通过建立一个平衡方程，求解该方程的最小解获得粒子初始化位置；

                                   f. 设置偏向的随机分布（推荐） ：即：我们通过对评价函数等一系列先验信息进行分析，得出最优解的可能存在空间范围，然后在这些范围内，着重撒点。就算再不济，也可以根据评价函数遵循Nearer is Better class（最优解更加可能在搜索空间的中心位置准则），在搜索空间的中心位置着重撒点。比如：

粒子群 速度 初始化：主要有如下五种方式：（根据实验表明，One-rand的效果最好。喂！！！这里One-rand的表达式是不是写错了啊？）

（2）领域拓扑：粒子的拓扑，决定了粒子所接受到的信息来源。

         一、全局模型gbest：最早的粒子群优化版本是全局PSO，使用全局拓扑结构，社会 只能 通过种群中， 最优的那个粒子 ，对每个粒子施加影响。

                                   1. 优点：具有较快的收敛速度。

                                   2. 缺点：粒子间的交流不够充分，但更容易陷入局部极值。

         二、局部模型lbest：采用每个粒子仅在一定的邻域内进行信息交换，，粒子之间的交流相对比较缓慢。

                                   1. 优点：粒子更容易搜索问题空间中的不同地区。

                                   2. 缺点：信息传递缓慢，设计相对复杂。

                                   3. 分类：被动模型：微观领域、宏观领域、维度划分；主动模型。

                                   （1）微观邻域：细分到每个粒子。空间邻域(spatial neighborhood)、性能空间(performance space)邻域、社会关系邻域(sociometric neighborhood)。

                                            a. 空间邻域：直接在搜索空间按粒子间的距离(如欧式距离)进行划分。在搜索初始阶段，将邻域定义为每个粒子自身；随着迭代次数的增加，将邻域范围逐渐扩展到整个种群。

                                            b. 性能空间领域：根据性能指标(如适应度、目标函数值)划分的邻域，如：适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。

                                            c. 社会关系邻域： 按粒子存储阵列的索引编号进行划分，主要有：环形拓扑(ring or circle topology)、轮形拓扑(wheel topology)或星形拓扑(star topology)、塔形拓扑(pyramid topology)、冯－诺以曼拓扑(Von Neumann topology)以及随机拓扑(random topology)等。（随机拓扑往往对大多数问题能表现出较好的性能，其次是冯－诺以曼拓扑。）

                                   （2）宏观邻域：对群体进行划分。比如：使用簇分析将整个粒子群划分为多个簇，然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置；根据粒子相似性动态地将粒子群体按种类划分为多个子种群，再以每个子种群的最佳个体作为每个粒子的邻域最佳位置；划分一个主群体，多个仆群体，仆群体进行独立的搜索，主群体在仆群体提供的最佳位置基础上开展搜索；每间隔一定代数将整个群体随机地重新划分；每个粒子除了自身和邻域最佳历史位置外，还学习邻域内其他粒子的 成功经验（只学好的，不学坏的） 等等；

                                   （3）维度划分：想法源自于：搜索空间维数较高时往往容易遭受“维数灾”的困扰。假设粒子群的整体维度为D，则可以将D划分成不同的部分，比如划分成k份，使用不同的群体，分别优化不同的维度。

                                   （4）主动模型：主动改变粒子邻域空间，避免碰撞和拥挤。比如：将粒子分为带电粒子和自然粒子，带电粒子接近会产生排斥；为每个粒子引入与邻近粒子距离成反比的自组织危险度，距离越近危险度越高，当危险度达到一定阈值，对粒子进行重新初始化，或者弹开；为粒子赋一个半径，以检测两个粒子是否会发生碰撞，并且采取碰撞-弹开方式将其分离。

（3）参数选择：三种参数：惯性权重或收敛因子、最大速度、两个加速因子。

         一、惯性权重：

                     a. 惯性权重大：加强PSO 全局 搜索能力；惯性权重小：加强PSO 局部 搜索能力；

                     b. 矛盾点：初始惯性权重大，局部搜索能力差，可能错过最优点；后期，惯性权重小，全局搜索能力不行，导致整个粒子群就陷入局部最优解。

                     c. 优化方向：在适当的时候降低权重w，平衡全局和局部搜索能力；

                     d. 优化建议：w随着更新代数的增加从0.9线性递减到0.4；

         二、压缩因子：

                     a. 优势：惯性常数方法通常采用惯性权值随更新代数增加而递减的策略，算法后期由于惯性权值过小，会失去探索新区域的能力，而收缩因子方法则不存在此不足

                     b. 优化建议：通常φ取4.1，χ得0.729。

         三、最大速度的选择：为了抑制粒子更新的无规律的跳动，速度往往被限制在[-Vm,Vm]

                     a. Vm增大，有利于全局 探索（exploration） ，但可能越过全局最优解；Vm减小，有利于局部 开发（exploitation） ，但可能陷入局部最优；

                     b. 优化建议：一般设定为问题空间的10%~20%；或者动态调整Vm，比如：根据群体最佳适应和最差适应来进行调整；

         四、两个加速常数：加速常数C1和C2分别用于控制粒子指向自身或邻域最佳位置的运动。

                     a. C1增大，粒子全局搜索能力好；C2增大，粒子向着最优靠拢局部能力好，但粒子会过早收敛；

                     b. 优化建议：C1 = C2 = 2.0，并且C1+C2 <= 4.0;或者根据自适应调整，比如随着迭代次数增加，减小C1增大C2；

（4）混合法：PSO与其他方法结合。

                     这点我觉得，主要根据个人的学习积累来操作。考虑方向：增加粒子群的局部搜索能力。

‘拾’ 粒子群优化算法的PSO

演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。
不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitness function)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值。 这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数 (Benchmark function)IRIS数据集。(Iris 是一种鸢尾属植物) 在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据. 这样总共有150组数据或模式。
我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100] (这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。