蚁群算法-粒子群优化

粒子群优化一.导言二.基本PSO三.标准PSO四.PSO的改进与变形五.学习PSO的几点体会2PSO的产生Particle

Swarm

Optimization(PSO)，粒子群优化或者微粒群优化PSO算法由 学者Kennedy

和Eberhart于1995年正式提出Particle

swarm

optimization.

IEEE

InternationalConference

on

Neural

Networks,

1995.A

new

optimizer

using

particle

swarm

theory.The

6th

International

Symposium

on

Micro-machine

and

Human

Science,

1995.一.导言3PSO的产生五年后，在国际上逐步被接受，并有大批不同领域的学者投入该算法相关研究，目前已经成为智能优化领域研究的热门2003年，《控制与决策》第二期刊登国内第一篇PSO——综述文章一.导言4PSO的基本思想对社会行为的模拟对鸟群行为的模拟：Reynolds和Heppner，Grenander在1987年和1990年

的

中都关注了鸟群群体行动中的蕴涵的美学。他们发现，由数目庞大的

组成的鸟群飞行中可以改变方向，散开，或者队形的重组等等，那么一定有某种潜在的能力或者规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中他们把重点都放在了

间距的处理，也就是让鸟群中的 之间保持最优的距离。一.导言5PSO的基本思想对社会行为的模拟对鱼群行为的研究：1975年，生物社会学家Wilson在

中阐述了对鱼群的研究。他在中提出：“至少在理论上，鱼群的 成员能够受益于群体中其他

在寻找食物的过程中发现的和以前的经验，这种受益是明显的，它超过了之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散于四处。”这说明，同种生物之间信息的社会共享能够带来好处。一.导言6一.导言PSO的基本思想对社会行为的模拟对鱼群行为的研究：1975年，生物社会学家Wilson在

中阐述了对鱼群的研究。他在中提出：“至少在理论上，鱼群的 成员能够受益于群体中其他

在寻找食物的过程中发现的和以前的经验，这种受益是明显的，它超过了之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散于四处。”这说明，同种生物之间信息的社会共享能够带来好处。这是PSO的基础7PSO的基本思想对社会行为的模拟对人类的社会行为的模拟：与前者不同，最大区别在于抽象性！鸟类和鱼类是调节他们的物理运动，来避免天敌，寻找食物，优化环境的参数，比如温度等。人类调节的不仅是物理运动，还包括认知和经验。 的是调节自己的信仰和态度，来和社会中的杰出人物或者 ，或者在某件事情上获得最优解的人保持一致。一.导言8PSO的基本思想对社会行为的模拟对人类的社会行为的模拟：c.这种不同导致了计算机仿真上的差别，至少有一个明显的因素：碰撞（collision）。d.

两个

即使不被绑在一块，也具有相同的态度和信仰，但是两只鸟是绝对不可能不碰撞而在空间中占据相同的位置。这是因为动物只能在三维的物理空间中运动，而人类还在抽象的心理空间运动，这里是碰撞的（collision-free）。一.导言9PSO的基本思想速度匹配和“Craziness”鸟群首先在在二 中进行位置的初始化，每个 具有X和Y两个速度，对邻居间速度的匹配导致鸟群的行动完全一致，方向也不变化，显然小鸟不会这么听话，于是加入了Craziness变量，对坐标增加一些随机的成分。一.导言10一.导言11PSO的基本思想飞入麦田的最优决策鸟群开始不知道麦田在哪，但知道距离麦田多远，用与麦田的距离远近来评价小鸟当前位置好不好。怎样才能飞到麦田中？最简单有效的就是搜寻目前离食物最近的鸟的周围区域PSO的基本思想Kennedy和Eberhart对Hepper的模仿鸟群的模型进行了修正，以使粒子能够飞向解空间，并在最好解处降落，从而得到了PSO算法。PSO在 解空间的搜索可以理解为对人类心理空间的模仿， 在搜索时考虑自己的历史最好点，这是 经验的积累，同时考虑到群体内其他

的共享作用和的历史最好点，这是社会信息本身具有学习能力的表现。一.导言12名称的由来：Swarm和ParticleSwarm：在 传统字典中有三个意思一大群尤指正在行进中的一大群昆虫或其它细小生物蜂群由蜂王带领迁移到别处建立一新据点的一群蜜蜂一大群尤指处于

中或成群出动的一大批喧闹的人或动物一.导言13名称的由来：Swarm和Particle作者 此词是借用了Millonas在1994年的中的 的一个应用模型中的提法Millonas明确提出群体智能（swarm

in

ligence）的五点原则——在算法的研究中当深思the

proximity

principle：群体能够执行简单的时间和空间的计算thequalityprinciple：群体能够响应环境的特征要素一.导言14ligence）名称的由来：Swarm和ParticleMillonas明确提出群体智能（swarm

in的五点原则the

principleof

diverse

response：群体能够使自己的行动不被限制在一个狭小的范围内theprincipleofstability：群体不要每次环境变化都跟着改变自己的行为模式theprincipleofadaptability：群体的行为模式要能够在值得计算代价的时候发生改变一.导言15名称的由来：Swarm和ParticleParticle:算法中有速度和加速度的字眼，这比较适合于粒子。Reeves在1983年的中了粒子系统包括基本粒子团和云、火、烟雾等弥漫性物体作者的想法是让粒子尽量具有一种普遍性的意义用粒子在超空间（Hyperspace）的飞行来模拟人类的社会性行为一.导言16算法描述及简要分析一个由m个粒子（Particle）组成的群体（Swarm）在D维搜索空间中以一定的速度飞行，每个粒子在搜索时，考虑到了自己搜索到的历史最好点和群体内（或邻域内）其他粒子的历史最好点，在此基础上进行位置（状态，也就是解）的变化17二.基本PSO算法描述及简要分析与GA相类似的问题种群的规定与初始化：Swarm具有大小，随机初始化点的好坏如何判断：通过适值函数停止准则18二.基本PSO1.

算法描述及简要分析•还要解决的问题本身所找到的历史最好点如何进行考虑，也就是让这个点如何影响下一次迭代？对群体内或者邻域内成员所找到的历史最好点如何进行考虑？粒子的位置如何进行变化？二.基本PSO192.

基本PSO的公式二.基本PSO,

pgDxivi

(vi11

i

m,

1

pi

(

pi1,

pi

2

,

,pg

(

pg1,

pg

2

,202.

基本PSO的公式21二.基本PSO(7.1)(7.2)kkkid

id

1

idid

2gdidid

id

idvk

1

vk

c

(

p

x

)

c

(

p

xk

)xk

1

xk

vk

1

,

U[0,1]基本PSO的公式c1和c2：学习因子（learningfactor）或加速系数（acceleration

coefficient），一般为正常数。学习因子使粒子具有自我总结和向群体中优秀学习的能力，从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近。通常等于2。二.基本PSO22基本PSO的公式

粒子的速度被限制在一个最大速度Vmax的范围内。引入Vmax的原因：防止计算机溢出对人类学习和观念转变的模拟它还决定了空间搜索的粒子性23二.基本PSO基本PSO的公式当把群体内所有粒子都作为邻域成员时，得到粒子群优化算法的全局版本；当群体 分成员组成邻域时得到粒子群优化算法的局部版本。局部版本中，一般有两种方式组成邻域，一种是索引号相临的粒子组成邻域，另一种是位置相临的粒子组成邻域。粒子群优化算法的邻域定义策略又可以称为粒子群的邻域拓扑结构。二.基本PSO24二.基本PSO3.

基本PSO步骤步1：在初始化范围内，对粒子群进行随机初始化，包括随机位置和速度。步2：计算每个粒子的适应值。步3：对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好，则将其作为粒子的历史最优值，用当前位置更新

历史最好位置25二.基本PSO263.

基本PSO步骤步4：对每个粒子，将其历史最优适应值与群体内或邻域内所经历的最好位置的适应值进行比较，若更好，则将其作为当前的全局最好位置。步5：根据式（7.1）和（7.2）对粒子的速度和位置进行更新步6：若未达到终止条件，则转步2。标准PSO的公式为改善算法收敛性能，Shi和Eberhart在1998年的

中引入了惯性权重的概念，将速度更新方程修改为（7.3）所示：三.标准PSO1(7.3)k

k

kkidididid

2gdidvk

1

v

c

(

p

x

)

c

(

p

xk

)27标准PSO的公式这里，w称为惯性权重，其大小决定了对粒子当前速度继承的多少，合适的选择可以使粒子具有均衡的探索和开发能力。可见，基本PSO算法是惯性权重w=1的特殊情况。分析和实验表明，设定Vmax的作用可以通过惯性权重的调整来实现。现在的PSO基本上使用

Vmax进行初始化，将Vmax设定为每维变量的变化范围，而不必进行细致的选择与调节。28三.标准PSO标准PSO的公式目前，对于PSO算法的研究大多以带有惯性权重的PSO为对象进行分析、扩展和修正，因此大多数文献中将带有惯性权重的PSO算法称为PSO算法的标准版本，或者称为标准PSO算法；而将前述PSO算法称为初始PSO算法/基本PSO算法，或者称为PSO算法的初始版本。29三.标准PSO算法构成要素群体大小：mm是个整型参数。当m很小的时候，陷入局优的可能性很大。然而，群体过大将导致计算时间的大幅增加。并且当群体数目增长至一定水平时，再增长将不再有显著的作用。当m

=1的时候，PSO算法变为基于

搜索的技术，一旦陷入局优，将不可能跳出。当m很大时，PSO的优化能力很好，

收敛的速度将非常慢。三.标准PSO30算法构成要素学习因子：c1和c2学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向群体内或邻域内最优点靠近。c1和c2通常等于2，不过在文献中也有其他的取值。但是一般c1等于c2，并且范围在0和4之间。31三.标准PSO算法构成要素最大速度：Vmax惯性权重智能优化方法的运行是否成功，探索能力和开发

能力的平衡是非常关键的。对于粒子群优化算法

来说，这两种能力的平衡就是靠惯性权重来实现。32三.标准PSO算法构成要素邻域拓扑结构全局版本粒子群优化算法将整个群体作为粒子的邻域，速度快，不过有时会陷入局部最优；局部版本粒子群优化算法将索引号相近或者位置相近的作为粒子的邻域，收敛速度慢一点，不过很难陷入局部最优。显然，全局版本的粒子群优化算法可以看作局部版本粒子群优化算法的一个特例，即将整个群体都作为邻域。停止准则三.标准PSO33算法构成要素粒子的初始化较好地选择粒子的初始化空间，将大大缩短收敛时间。这是问题依赖的。34三.标准PSO重要的参数：惯性权重和邻域定义计算举例求解无约束优化问题：5维的Rosenbrock函数35三.标准PSOn1i1

x2

)2

(x

1)2

)i

ii1x[30,30]nmin

f

(x)

(100(x计算举例简单分析：Rosenbrock是一个著名的测试函数，也叫香蕉函数，其特点是该函数虽然是单峰函数，在[100，100]n上只有一个全局极小点，但它在全局极小点的狭长区域内取值变化极为缓慢，常用于评价算法的搜索性能。这种实优化问题非常适合于使用粒子群优化算法来求解。三.标准PSO36计算举例算法设计编码：因为问题的维数为5，所以每个粒子为5维的实数向量。初始化范围：根据问题要求，设定为[-30，30]。根据前面的参数分析，知道，可以将最大速度设定为Vmax=60。种群大小：为了说明方便，这里采用一个较小的种群规模，m=5。停止准则：设定为最大迭代次数100次。三.标准PSO37计算举例算法设计惯性权重：采用固定权重0.5。邻域拓扑结构：使用星形拓扑结构，即全局版本的粒子群优化算法。38三.标准PSO计算举例一次迭代后的结果三.标准PSO

11121304x

2.4265985,

29.665405,

18.387815,

29.660393,

-39.97371x

22.56745,

-3.999012,

-19.23571,

-16.373426,

-45.417023x

30.34029,

-4.6773186,

5.7844753,

5.4156475,

-43.92349

05x

2.7943296,

19.942759,

-24.861498,

16.060974,

-57.757202x

27.509708,

28.379063,

13.016331,

11.539068,

-53.67677739计算举例一次迭代后的结果从上面的数据可以看到，粒子有的分量跑出了初始化范围。需要说明的是，在这种情况下，一般不强行将粒子重新拉回到初始化空间，即使初始化空间也是粒子的约束空间。因为，即使粒子跑出初始化空间，随着迭代的进行，如果在初始化空间内有更好的解存在，那么粒子也可以自行返回到初始化空间。有研究表明，即使将初始化空间不设定为问题的约束空间，即问题的最优解不在初始化空间内，粒子也可能找到最优解。三.标准PSO403.

计算举例三.标准PSO41惯性权重固定权重即赋予惯性权重以一个常数值，一般来说，该值

在0和1之间。固定的惯性权重使粒子在飞行中始

终具有相同的探索和开发能力。显然，对于不同

的问题，获得最好优化效果的这个常数是不同的，要找到这个值需要大量的实验。通过实验

发现：种群规模越小，需要的惯性权重越大，因为

此时种群需要更好的探索能力来弥补粒子数量的

不足，否则粒子极易收敛；种群规模越大，需要

的惯性权重越小，因为每个粒子可以更专注于搜

索自己附近的区域。四.PSO的改进与变形42四.PSO的改进与变形惯性权重时变权重一般来说，希望粒子群在飞行开始的时候具有较好的探索能力，而随着迭代次数的增加，特别是在飞行的后期，希望具有较好的开发能力。所以希望动态调节惯性权重。可以通过时变权重的设置来实现。设惯性权重的取值范围为：min

,max

最大迭代次数为Iter_max，则第i次迭代时的惯性权重可以取为：max43iIter

_

max

max

min

i惯性权重模糊权重模糊权重是使用模糊系统来动态调节惯性权重。下面的文献给出了一种模糊权重的设置方式Shi

Y,

Eberhart

R.

Fuzzy

adaptive

particleswarm

optimization:

IEEE

Int.

Congress

onEvolutionary

Computation

[C].

Piscataway,

NJ:IEEE

Service

Center,

2001:

101-106.44四.PSO的改进与变形1.

惯性权重随机权重随机权重是在一定范围内随机取值。例如可以取值如下：其中，Random为0到1之间的随机数。这样，惯性权重将在0.5到1之间随

化，均值为0.75。四.PSO的改进与变形2

0.5

Random45邻域拓扑结构基于索引号的拓扑结构环形结构四.PSO的改进与变形46邻域拓扑结构基于索引号的拓扑结构带有捷径的环形结构四.PSO的改进与变形47邻域拓扑结构基于索引号的拓扑结构轮形结构四.PSO的改进与变形48邻域拓扑结构基于索引号的拓扑结构带有捷径的轮形结构四.PSO的改进与变形49邻域拓扑结构基于索引号的拓扑结构星形结构：每个粒子都与种群中的其他所有粒子相连，即将整个种群作为自己的邻域。也就是粒子群算法的全局版本。这种结构下，所有粒子共享的信息是种群中表现最好的粒子的信息。50四.PSO的改进与变形邻域拓扑结构基于索引号的拓扑结构随机结构：随机结构是在N个粒子的种群中间，随机地建立N个对称的两两连接。51四.PSO的改进与变形邻域拓扑结构基于距离的拓扑结构基于距离的拓扑结构是在每次迭代时，计算一个粒子与种群中其他粒子之间的距离，然后根据这些距离来确定该粒子的邻域构成。一种动态邻域拓扑结构：在搜索开始的时候，粒

子的邻域只有其自己，即将 最优解作为邻域最优解，然后随着迭代次数的增加，逐渐增大邻

域，直至最后将群体中所有粒子作为自己的邻域

成员。这样使初始迭代时可以有较好的探索性能，而在迭代后期可以有较好的开发性能。四.PSO的改进与变形52四.PSO的改进与变形53对将要计算邻域的粒子i，计算其与种群中其他所有粒子的距离。该粒子与粒子l（

l

i

）的距离记为：dist[l]。最大的距离记为：max_dist。定义一个关于当前迭代次数的函数fraction（取值为纯小数）：frac

3.0

ITER

0.6

MAXITERMAXITER当frac

0.9

时，满足的下列条件的粒子构成当前粒子i

的邻域：

dist[l]

frac

；max-

dist当frac

0.9

，将种群中所有粒子作为当前粒子i

的邻域。四.PSO的改进与变形学习因子c1和c2同步时变参照时变惯性权重的设置方法，将学习因子设置如下：设学习因子c1

和c2

的取值范围为：cmin

,cmax

，最大迭代次数为

Iter_max，则第

i次迭代时的学习因子取为：1

2i

maxIter

_

max

cmax

cminc

c

c

c

i(7.12)这是一种两个学习因子同步线性减小的变化方式，所以

这里称之为同步时变。特别地，Suganthan

在实验中将参数设置为：cmax=3，cmin=0.25但是发现，这种设置下，解的质量反而下降。54学习因子c1和c2异步时变使两个学习因子在优化过程中随时间进行不同的变化，所以这里称之为异步时变。这种设置的目的是在优化初期加强全局搜索，而在搜索后期促使粒子收敛于全局最优解。这种想法可以通过随着时间不断减小自我学习因子c1，和不断增大社会学习因子c2来实现。四.PSO的改进与变形55学习因子c1和c2异步时变在优化的初始阶段，粒子具有较大的自我学习能力和较小的社会学习能力，这样粒子可以倾向于在整个搜索空间飞行，而不是很快就飞向群体最优解；在优化的后期，粒子具有较大的社会学习能力和较小的自我学习能力，使粒子倾向于飞向全局最优解。56四.PSO的改进与变形四.PSO的改进与变形具体实现方式如下：11i1i1

fIter

_

maxc

c

c

iter

c(7.13)2iIter

_

m