第七章 粒子群优化算法.

Presentation on theme: "第七章 粒子群优化算法."— Presentation transcript:

1 第七章 粒子群优化算法

2 第七章 粒子群优化算法 一.前言 二.基本算法 三.标准算法 四.PSO的改进与变形 五.学习PSO的几点体会

3 一.前言 PSO的产生 Particle Swarm Optimization(PSO)，粒子群优化或者微粒群优化
PSO算法由美国学者Kennedy （社会心理学家）和Eberhart（电机工程师） 于1995年提出，通过模拟鸟群和鱼群的社会交互行为而不仅仅依赖个体认知行为而设计的一种智能优化方法 Kennedy

4 一.前言 PSO的产生 2000年以后，PSO算法在国际上逐步被接受，并有大批不同领域的学者投入该算法相关研究，已经成为智能优化领域研究的热门算法 2003年，《控制与决策》第二期刊登国内第一篇综述性文章

5 一.前言 PSO的基本思想 对社会行为的模拟 对鸟群行为的模拟：Reynolds和Heppner，Grenander在1987年和1990年发表的论文中都关注了鸟群群体行动中蕴涵的美学。他们发现，由数目庞大的个体组成的鸟群飞行中可以改变方向，散开，或者队形的重组等等，那么一定有某种潜在的能力或者规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中他们把重点都放在了个体间距的处理，也就是让鸟群中的个体之间保持最优的距离。

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

7 一.前言 PSO的基本思想 对社会行为的模拟 对人类的社会行为的模拟： a. 与前者不同，最大区别在于抽象性！
b. 鸟类和鱼类是调节他们的物理运动，来避免天敌， 寻找食物，优化环境的参数，比如温度等。人类调节 的不仅是物理运动，还包括认知和经验。我们更多的 是调节自己的信仰和态度，来和社会中的杰出人物或 者专家，或者在某件事情上获得最优解的人保持一致。

8 一.前言 PSO的基本思想 对社会行为的模拟 对人类的社会行为的模拟： c. 这种不同导致了计算机仿真上的差别，至少有一个
明显的因素：碰撞（collision）。 d. 两个个体即使不被绑在一块，也具有相同的态度和 信仰，但是两只鸟是绝对不可能不碰撞而在空间中占 据相同的位置。这是因为动物只能在三维的物理空间 中运动，而人类还在抽象的多维心理空间运动，这里 是碰撞自由的（collision-free）。

9 一.前言 PSO的基本思想 采纳基于种群(swarm)的机制 个体(particle)均是问题的一个潜在解
算法寻优依赖于在种群拓扑结构上个体间的社会交互行为

10 一.前言 名称的由来：Swarm和Particle Swarm：在美国传统字典中有三个意思 一大群尤指正在行进中的一大群昆虫或其它细小生物
蜂群由蜂王带领迁移到别处建立一新据点的一群蜜蜂 一大群尤指处于骚乱中或成群出动的一大批喧闹的人或动物 作者引用此词是借用了Millonas在1994年的论文中的人工生命的一个应用模型中的提法

11 一.前言 名称的由来：Swarm和Particle Particle:
算法中有速度和加速度的字眼，这比较适合于粒子。Reeves在1983年的论文中讨论了粒子系统包括基本粒子团和云、火、烟雾等弥漫性物体 作者的想法是让粒子尽量具有一种普遍性的意义 用粒子在超空间（Hyperspace）的飞行来模拟个体的社会性行为

12 二.基本算法 算法描述 种群中m个个体分布在一个D维搜索空间中 每个个体均具有当前位置、速度以及历史最优位置三个属性
种群具有一定的拓扑结构，个体可以基于种群拓扑结构与其邻域内的其他个体进行相互作用 算法迭代时，每个个体会根据自身信息（认知行为）和邻域内其他个体的信息（社会行为）进行状态更新

13 二.基本算法 基本PSO的公式 Index 粒子i 粒子群

14 二.基本算法 基本PSO的公式 (1) (2)

15 二.基本算法 基本PSO的公式 c1和c2：学习因子（learning factor）或加速系数（acceleration coefficient），一般为正常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近。通常等于2。 ξ和η：0-1之间的随机数

16 二.基本算法 基本PSO的公式 粒子的速度被限制在[-Vmax, Vmax]的范围内。引入Vmax的原因： 防止溢出 保证算法稳定

17 二.基本算法 基本PSO的公式 粒子群的拓扑结构决定个体间的相互影响程度
PSO的全局版本将整个群体看作是一个全连通图，群体内所有个体共享一个邻域最优 gbest PSO的局部版本中每个个体的邻域将是整个群体的一个子集，此时影响个体的gbest取决于具体的拓扑结构，一种简单的方法是群体内粒子根据其编号相邻的原则组成一个环状结构

18 二.基本算法 基本PSO算法流程图 begin
initialize and evaluate a swarm of particles with random positions and velocities on D dimensions in the search space; repeat for each particle i do update gbest of particle i; endfor adapt the velocity of particle i using Equation (1); update the position of particle i using Equation (2); evaluate the fitness of particle i; update pbest of particle i; until a stop condition is met end

19 三.标准PSO 带有惯性权重的PSO 为改善算法收敛性能，Shi和Eberhart在1998年的论文中引入了惯性权重的概念，将速度更新方程修改为： (3)

20 三.标准PSO 带有惯性权重的PSO 这里，w称为惯性权重，其大小决定了对粒子当前速度继承的多少，合适的选择可以使粒子具有均衡的探索和开发能力。可见，基本PSO算法是惯性权重w=1的特殊情况。 分析和实验表明，设定Vmax的作用可以通过惯性权重的调整来实现。现在的PSO基本上使用Vmax进行初始化，将Vmax设定为每维变量的变化范围，而不必进行细致的选择与调节。

21 四.PSO的改进与变形 带有收缩因子的PSO
2002年Clerc和Kennedy在基本PSO算法中引入可收缩因子的概念，指出该因子对于算法的收敛是必要的，将速度更新公式修改为： 其中， (4)

22 四.PSO的改进与变形 带有收缩因子的PSO Clerc将参数取值为： 则 若带有惯性权重的PSO采用如下的参数设置：

23 三.标准PSO 计算举例 求解无约束优化问题：5维的Rosenbrock函数

24 三.标准PSO 计算举例 简单分析： Rosenbrock是一个著名的测试函数，也叫香蕉函数，其特点是该函数虽然是单峰函数，在[100，100]n上只有一个全局极小点，但它在全局极小点临近的狭长区域内取值变化极为缓慢，常用于评价算法的搜索性能。这种实优化问题非常适合于使用粒子群优化算法来求解。

25 三.标准PSO 计算举例 算法设计 编码：因为问题的维数为5，所以每个粒子为5维的实数向量。
初始化范围：根据问题要求，设定为[-30，30]。根据前面的参数分析，我们知道，可以将最大速度设定为Vmax=60。 种群大小：为了说明方便，这里采用一个较小的种群规模，m=5。 停止准则：设定为最大迭代次数100次。

26 三.标准PSO 计算举例 算法设计 惯性权重：采用固定权重0.5。 邻域拓扑结构：使用星形拓扑结构，即全局版本的粒子群优化算法。

27 三.标准PSO 计算举例 一次迭代后的结果

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

29 三.标准PSO 计算举例

30 四.PSO的改进与变形 惯性权重 固定权重 即赋予惯性权重以一个常数值，一般来说，该值在0和1之间。固定的惯性权重使粒子在飞行中始终具有相同的探索和开发能力。显然，对于不同的问题，获得最好优化效果的这个常数是不同的，要找到这个值需要大量的实验。通过实验我们发现：种群规模越小，需要的惯性权重越大，因为此时种群需要更好的探索能力来弥补粒子数量的不足，否则粒子极易收敛；种群规模越大，需要的惯性权重越小，因为每个粒子可以更专注于搜索自己附近的区域。

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

32 四.PSO的改进与变形 惯性权重 模糊权重 模糊权重是使用模糊系统来动态调节惯性权重。下面的文献给出了一种模糊权重的设置方式 Shi Y, Eberhart R. Fuzzy adaptive particle swarm optimization: IEEE Int. Congress on Evolutionary Computation [C]. Piscataway, NJ: IEEE Service Center, 2001:

33 四.PSO的改进与变形 惯性权重 随机权重 随机权重是在一定范围内随机取值。例如可以取值如下：
其中，Random为0到1之间的随机数。这样，惯性权重将在0.5到1之间随机变化，均值为0.75。

34 四.PSO的改进与变形 邻域拓扑结构 基于索引号的拓扑结构 环形结构

35 四.PSO的改进与变形 邻域拓扑结构 基于索引号的拓扑结构
星形结构：每个粒子都与种群中的其他所有粒子相连，即将整个种群作为自己的邻域。也就是粒子群算法的全局版本。这种结构下，所有粒子共享的信息是种群中表现最好的粒子的信息。

36 四.PSO的改进与变形 邻域拓扑结构 基于距离的拓扑结构
基于距离的拓扑结构是在每次迭代时，计算一个粒子与种群中其他粒子之间的距离，然后根据这些距离来确定该粒子的邻域构成。 一种动态邻域拓扑结构：在搜索开始的时候，粒子的邻域只有其自己，即将个体最优解作为邻域最优解，然后随着迭代次数的增加，逐渐增大邻域，直至最后将群体中所有粒子作为自己的邻域成员。这样使初始迭代时可以有较好的探索性能，而在迭代后期可以有较好的开发性能。

37 四.PSO的改进与变形

38 四.PSO的改进与变形 学习因子 c1和c2同步时变

39 四.PSO的改进与变形 学习因子 c1和c2异步时变

40 四.PSO的改进与变形 学习因子 c1和c2异步时变
在优化的初始阶段，粒子具有较大的自我学习能力和较小的社会学习能力，这样粒子可以倾向于在整个搜索空间飞行，而不是很快就飞向群体最优解； 在优化的后期，粒子具有较大的社会学习能力和较小的自我学习能力，使粒子倾向于飞向全局最优解。

41 四.PSO的改进与变形

42 五.学习PSO的几点体会 收敛很快的算法 解决约束优化问题时，如何处理飞出约束域的粒子是个关键 较为适用于求解实优化问题