2016/6/5
19
Shi和Eberhart提出了一种随着算法迭代次数的增加惯性权重线 性下降的方法。 惯性权重的计算公式如下：
max max min
kmax kn
max和min分别表示权重的最大及最小值，kn为当前迭代次数， kmax表示最大迭代次数。
文献试验了将设置为从0.9到0.4的线性下降，使得PSO在开 始时探索较大的区域，较快地定位最优解的大致位置，随着 逐渐减小，粒子速度减慢，开始精细的局部搜索。该方法使 PSO更好地控制exploration和exploitation能力，加快了收敛速 度，提高了算法的性能，称之为权重线性下降的粒子群算法， 简记为LDW(Linearly Decreasing Inertia Weight)。
2016/6/5
4
粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的 飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个 被目标函数决定的适应值(fitness value)，这个适应值用于评价 粒子的“好坏”程度。 每个粒子知道自己到目前为止发现的最好位置(particle best， 记为pbest)和当前的位置，pbest就是粒子本身找到的最优解， 这个可以看作是粒子自己的飞行经验。 除此之外，每个粒子还知道到目前为止整个群体中所有粒子发 现的最好位置(global best，记为gbest)，gbest是在pbest中的最 好值，即是全局最优解，这个可以看作是整个群体的经验。
一个是粒子本身所找到的最好解，即个体极值(pbest)，另一个 极值是整个粒子群中所有粒子在历代搜索过程中所达到的最优 解(gbest)即全局极值。 找到这两个最好解后，接下来是PSO中最重要的“加速”过程， 每个粒子不断地改变其在解空间中的速度，以尽可能地朝pbest 和gbest所指向的区域“飞”去。
G best 是整个种群在第d维的全局极值点的位置。
最大速度vmax：决定了问题空间搜索的力度，粒子的每一维速 度vid都会被限制在[－vdmax，+vdmax ]之间，假设搜索空间的第d 维定义为区间[－xdmax，+xdmax ] ，则通常vdmax=kxdmax ， 0.1k1.0，每一维都用相同的设置方法。
2016/6/5
13
(4)粒子的最大速度vmax ：粒子的速度在空间中的每一维上都有 一个最大速度限制值vdmax ，用来对粒子的速度进行钳制，使速 度控制在范围[－vdmax，＋vdmax ]内，这决定问题空间搜索的力 度，该值一般由用户自己设定。 vmax是一个非常重要的参数，如果该值太大，则粒子们也许会 飞过优秀区域；另一方面如果该值太小，则粒子们可能无法对 局部最优区域以外的区域进行充分的探测。实际上，它们可能 会陷入局部最优，而无法移动足够远的距离跳出局部最优达到 空间中更佳的位置。 (5) rand1和rand2是介于［0,1］之间的随机数，增加了粒子飞行 的随机性。 (6)迭代终止条件：一般设为最大迭代次数Tmax、计算精度或最 优解的最大停滞步数△t。
2016/6/5
5
每个粒子使用下列信息改变自己的当前位置： (1)当前位置； (2)当前速度； (3)当前位置与自己最好位置之间的距离； (4)当前位置与群体最好位置之间的距离。
2016/6/5
6
粒子群算法的基本思想
用随机解初始化一群随机粒子，然后通过迭代找到最优解。在 每一次迭代中，粒子通过跟踪两个“极值”来更新自己：
2016/6/5
7
粒子群优化算法的一般数学模型
假设在一个N维空间进行搜索，粒子i的信息可用两个N维向量 来表示：
第i个粒子的位置可表示为 xi xi1 , xi 2 , xiN
速度为 vi vi1, vi 2 ,viN
T
T
在找到两个最优解后，粒子即可根据下式来更新自己的速度和 位置：
k 1 k k k k k k vid vid c1 rand1k ( Pbestid xid ) c2 rand2 (Gbestd xid ) (1)
k 1 k k 1 xid xid vid
(2)
v
k id ：是粒子i在第k次迭代中第d维的速度；
PSO算法就从这种生物种群行为特性中得到启发并用于求解优化 问题。
在PSO中，把一个优化问题看作是在空中觅食的鸟群，那么“食 物”就是优化问题的最优解，而在空中飞行的每一只觅食的 “鸟”就是PSO算法中在解空间中进行搜索的一个“粒 子”(Particle)。 “群”(Swarm)的概念来自于人工生命，满足人工生命的五个基 本原则。因此PSO算法也可看作是对简化了的社会模型的模拟， 这其中最重要的是社会群体中的信息共享机制，这是推动算法 的主要机制。
2016/6/5
2
粒子群算法的基本原理
PSO的基本概念源于对鸟群捕食行为的研究：
一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟 都不知道食物在哪里。但是他们知道当前的位置离食物还有多 远。
那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目 前离食物最近的鸟的周围区域。
2016/6/5
3
——Calculate particle velocity according equation (1) ——Update particle position according equation (2) — End
While maximum iterations or minimum error criteria is not attained
2016/6/5 9
k d
更新公式的意义 公式(1)主要通过三部分来计算粒子i更新的速度：
粒子i前一时刻的速度
k vid ；
k k xid ) ； 粒子当前位置与自己历史最好位置之间的距离 ( Pbestid
k k 粒子当前位置与群体最好位置之间的距离 (Gbestd xid ) 。
粒子通过公式(2)计算新位置的坐标。
2016/6/5 12
如果c2 = 0，则粒子没有群体共享信息，一个规模为M的群体等 价于运行了M个各行其是的粒子，得到解的几率非常小，因此 一般设置c1 = c2 。这样，个体经验和群体经验就有了相同重要 的影响力，使得最后的最优解更精确。 改变这些常数会改变系统的“张力”，较低的c1 和 c2值使得粒 子徘徊在远离目标的区域，较高的c1 和 c2值产生陡峭的运动或 越过目标区域。 Shi和Eberhart建议，为了平衡随机因素的作用，一般情况下设 置c1 ＝ c2，大部分算法都采用这个建议。
2016/6/5 16
PSO的各种改进算法
PSO收敛速度快，特别是在算法的早期，但也存在着精度较低， 易发散等缺点。 若加速系数、最大速度等参数太大，粒子群可能错过最优解， 算法不收敛； 而在收敛的情况下，由于所有的粒子都向最优解的方向飞去， 所以粒子趋向同一化（失去了多样性），使得后期收敛速度 明显变慢，同时算法收敛到一定精度时，无法继续优化，所 能达到的精度也不高。 因此很多学者都致力于提高PSO算法的性能。
粒子群算法
2016/6/5
1
粒子群算法的研究背景
粒子群算法(Particle Swarm Optimization，简称PSO)，是一种基 于群体智能的进化计算方法。PSO由Kennedy和Eberhart博士于 1995年提出。 粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员 称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为 主体。主体有适应性，它能够与环境及其他的主体进行交流， 并且根据交流的过程“学习”或“积累经验”改变自身结构 与行为。整个系统的演变或进化包括：新层次的产生（小鸟 的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的 群）；新的主题的出现（鸟寻找食物过程中，不断发现新的 食物）。
2016/6/5
17
惯性权重法（Inertia Weight） 如果没有公式(1)的第一部分，PSO的搜索过程是一个通过迭代 搜索空间逐渐收缩的过程，展现出一种局部搜索((exploitation) 能力；反之，如果增加了第一部分，粒子就有能力扩展搜索空 间，展现出一种全局搜索(exploration)的能力。在搜索过程中， 全局搜索能力与局部搜索能力的平衡对于算法的成功起着至关 重要的作用。 引入一个惯性权重到公式(1)， 是与前一次速度有关的一个 比例因子，较大的可以加强PSO的全局探测能力，而较小的 能加强局部搜索能力，也就是这个执行了全局搜索和局部搜 索之间的平衡角色。 惯性权重法是由Shi等提出的，其速度更新公式为：
k 1 k k k k k k vid vid c1 rand1k ( Pbestid xid ) c2 rand2 (Gbestd xid )
(3)
18
为非负数，称为惯性因子，惯性权重，是控制速度的权重
2016/6/5
(1)线性调整的策略 允许的最大速度vmax实际上作为一个约束，控制PSO能够具有的 最大全局搜索能力。如果vmax较小，那么最大的全局搜索能力将 被限制，不论惯性权重的大小，PSO只支持局部搜索；如果设 置vmax较大，那么PSO通过选择 ，有一个可供很多选择的搜索 能力范围。 由此可以看出，允许的最大速度间接地影响全局搜索能力，而 惯性权重直接影响全局搜索能力，所以希望找到一个非常好的 惯性权重来达到全局搜索和局部搜索之间的平衡。 类似于人的“原动力”，如果原动力比较大，当达到某个目 标的时候，会继续向前实现更高的目标：如果原动力较小，到 达某个目标就停滞。
2016/6/5 14
算法流程
开始 初始化粒子X、V
计算Pbest、Gbest
粒子位置、速度更新
计算适应函数值
更新Pbest、Gbest
达到迭代次数或精 度要求？ 是