粒子群优化
12
一.导言
3. 名称的由来:Swarm和Particle 名称的由来:Swarm和
Swarm: Swarm:在美国传统字典中有三个意思
• • • 一大群尤指正在行进中的一大群昆虫或其它细小 生物 蜂群由蜂王带领迁移到别处建立一新据点的一群 蜜蜂 一大群尤指处于骚乱中或成群出动的一大批喧闹 的人或动物
• •
16
二.基本PSO 基本PSO
1. 算法描述及简要分析
一个由m个粒子(Particle) 一个由m个粒子(Particle)组成的群体 Swarm) 维搜索空间中以一定的速度飞行, (Swarm)在D维搜索空间中以一定的速度飞行, 每个粒子在搜索时, 每个粒子在搜索时,考虑到了自己搜索到的历 史最好点和群体内(或邻域内)其他粒子的历 史最好点和群体内(或邻域内) 史最好点,在此基础上进行位置(状态, 史最好点,在此基础上进行位置(状态,也就 是解) 是解)的变化
7
一.导言
2. PSO的基本思想 PSO的基本思想
对社会行为的模拟
• 对人类的社会行为的模拟: 对人类的社会行为的模拟: a. 与前者不同,最大区别在于抽象性! 与前者不同,最大区别在于抽象性! b. 鸟类和鱼类是调节他们的物理运动,来避免天敌, 鸟类和鱼类是调节他们的物理运动,来避免天敌, 寻找食物,优化环境的参数,比如温度等。 寻找食物,优化环境的参数,比如温度等。人类调节 的不仅是物理运动,还包括认知和经验。 的不仅是物理运动,还包括认知和经验。我们更多的 是调节自己的信仰和态度, 是调节自己的信仰和态度,来和社会中的杰出人物或 者专家,或者在某件事情上获得最优解的人保持一致。 者专家,或者在某件事情上获得最优解的人保持一致。
• • Particle swarm optimization. IEEE International Conference on Neural Networks, 1995. A new optimizer using particle swarm theory. The 6th International Symposium on MicroMicromachine and Human Science, 1995.
10
一.导言
2. PSO的基本思想 PSO的基本思想
飞入麦田的最优决策
• 鸟群开始不知道麦田在哪,但知道距离麦田多远, 鸟群开始不知道麦田在哪,但知道距离麦田多远, 用与麦田的距离远近来评价小鸟当前位置好不好。 用与麦田的距离远近来评价小鸟当前位置好不好。 怎样才能飞到麦田中? 怎样才能飞到麦田中?
最简单有效的就是搜寻目前离食物最近的鸟的周围区域
11
一.导言
2. PSO的基本思想 PSO的基本思想
Kennedy和Eberhart对Hepper的模仿鸟群的模 Kennedy和Eberhart对Hepper的模仿鸟群的模 型进行了修正,以使粒子能够飞向解空间, 型进行了修正,以使粒子能够飞向解空间,并 在最好解处降落,从而得到了PSO算法 算法。 在最好解处降落,从而得到了PSO算法。 PSO在多维解空间的搜索可以理解为对人类多 PSO在多维解空间的搜索可以理解为对人类多 维心理空间的模仿, 维心理空间的模仿,个体在搜索时考虑自己的 历史最好点,这是个体经验的积累, 历史最好点,这是个体经验的积累,同时考虑 到群体内其他个体的历史最好点, 到群体内其他个体的历史最好点,这是社会信 息的共享作用和个体本身具有学习能力的表现。 息的共享作用和个体本身具有学习能力的表现。
6
一.导言
2. PSO的基本思想 PSO的基本思想
对社会行为的模拟
• 对鱼群行为的研究:1975年,生物社会学家 对鱼群行为的研究:1975年 Wilson在论文中阐述了对鱼群的研究 Wilson在论文中阐述了对鱼群的研究。他在论文 在论文中阐述了对鱼群的研究。 中提出: 至少在理论上, 中提出:“至少在理论上,鱼群的个体成员能够 受益于群体中其他个体在寻找食物的过程中发现 的和以前的经验,这种受益是明显的, 的和以前的经验,这种受益是明显的,它超过了 个体之间的竞争所带来的利益消耗, 个体之间的竞争所带来的利益消耗,不管任何时 候食物资源不可预知的分散于四处。”这说明, 候食物资源不可预知的分散于四处。 这说明, 同种生物之间信息的社会共享能够带来好处。 同种生物之间信息的社会共享能够带来好处。 这是PSO的基础 这是 的基础
• • • the principle of diverse response:群体能够使自 response: 己的行动不被限制在一个狭小的范围内 the principle of stability:群体不要每次环境变化 stability: 都跟着改变自己的行为模式 the principle of adaptability:群体的行为模式要 adaptability: 能够在值得计算代价的时候发生改变
17
二.基本PSO 基本PSO
1. 算法描述及简要分析
与GA相类似的问题 GA相类似的问题
• • • 种群的规定与初始化:Swarm具有大小,随机初 具有大小, 种群的规定与初始化:Swarm具有大小 始化 点的好坏如何判断: 点的好坏如何判断:通过适值函数 停止准则
18
二.基本PSO 基本PSO
9
一.导言
2. PSO的基本思想 PSO的基本思想
速度匹配和“Craziness” 速度匹配和“
• 鸟群首先在在二维空间中进行位置的初始化, 鸟群首先在在二维空间中进行位置的初始化,每 个个体具有X 两个速度, 个个体具有X和Y两个速度,对邻居间速度的匹 配导致鸟群的行动完全一致,方向也不变化, 配导致鸟群的行动完全一致,方向也不变化,显 然小鸟不会这么听话,于是加入了Craziness变量 变量, 然小鸟不会这么听话,于是加入了Craziness变量, 对坐标增加一些随机的成分。 对坐标增加一些随机的成分。
13
一.导言
3. 名称的由来:Swarm和Particle 名称的由来:Swarm和
作者引用此词是借用了Millonas在1994年的论文 作者引用此词是借用了Millonas在1994年的论文 中的人工生命的一个应用模型中的提法 Millonas明确提出群体智能 Millonas明确提出群体智能(swarm intelligence) 明确提出群体智能( intelligence) 的五点原则——在算法的研究中当深思 的五点原则——在算法的研究中当深思
5
一.导言
2. PSO的基本思想 PSO的基本思想
对社会行为的模拟
• 对鱼群行为的研究:1975年,生物社会学家 对鱼群行为的研究:1975年 Wilson在论文中阐述了对鱼群的研究 Wilson在论文中阐述了对鱼群的研究。他在论文 在论文中阐述了对鱼群的研究。 中提出: 至少在理论上, 中提出:“至少在理论上,鱼群的个体成员能够 受益于群体中其他个体在寻找食物的过程中发现 的和以前的经验,这种受益是明显的, 的和以前的经验,这种受益是明显的,它超过了 个体之间的竞争所带来的利益消耗, 个体之间的竞争所带来的利益消耗,不管任何时 候食物资源不可预知的分散于四处。”这说明, 候食物资源不可预知的分散于四处。 这说明, 同种生物之间信息的社会共享能够带来好处。 同种生物之间信息的社会共享能够带来好处。
8
一.导言
2. PSO的基本思想 PSO的基本思想
对社会行为的模拟
• 对人类的社会行为的模拟: 对人类的社会行为的模拟: c. 这种不同导致了计算机仿真上的差别,至少有一个 这种不同导致了计算机仿真上的差别, 明显的因素:碰撞(collision)。 明显的因素:碰撞(collision)。 d. 两个个体即使不被绑在一块,也具有相同的态度和 两个个体即使不被绑在一块, 信仰, 信仰,但是两只鸟是绝对不可能不碰撞而在空间中占 据相同的位置。 据相同的位置。这是因为动物只能在三维的物理空间 中运动,而人类还在抽象的多维心理空间运动, 中运动,而人类还在抽象的多维心理空间运动,这里 是碰撞自由的(collision-free)。 是碰撞自由的(collision-free)。
1. 算法描述及简要分析
还要解决的问题
• • • 个体本身所找到的历史最好点如何进行考虑, 个体本身所找到的历史最好点如何进行考虑,也 就是让这个点如何影响下一次迭代? 就是让这个点如何影响下一次迭代? 对群体内或者邻域内成员所找到的历史最好点如 何进行考虑? 何进行考虑? 粒子的位置如何进行变化? 粒子的位置如何进行变化?
3
一.导言
1. PSO的产生 PSO的产生
五年后,在国际上逐步被接受, 五年后,在国际上逐步被接受,并有大批不同 领域的学者投入该算法相关研究, 领域的学者投入该算法相关研究,目前已经成 为智能优化领域研究的热门
2003年 2003年,《控制与决策》第二期刊登国内第一篇 控制与决策》 PSO论文 PSO论文——综述文章 论文——综述文章
4
一.导言
2. PSO的基本思想 PSO的基本思想
对社会行为的模拟
• 对鸟群行为的模拟:Reynolds和Heppner, 对鸟群行为的模拟:Reynቤተ መጻሕፍቲ ባይዱlds和Heppner, Grenander在1987年和 Grenander在1987年和1990年发表的论文中都关 年和1990年发表的论文中都关 注了鸟群群体行动中的蕴涵的美学。他们发现, 注了鸟群群体行动中的蕴涵的美学。他们发现, 由数目庞大的个体组成的鸟群飞行中可以改变方 散开,或者队形的重组等等, 向,散开,或者队形的重组等等,那么一定有某 种潜在的能力或者规则保证了这些同步的行为。 种潜在的能力或者规则保证了这些同步的行为。 这些科学家都认为上述行为是基于不可预知的鸟 类社会行为中的群体动态学。 类社会行为中的群体动态学。在这些早期的模型 中他们把重点都放在了个体间距的处理, 中他们把重点都放在了个体间距的处理,也就是 让鸟群中的个体之间保持最优的距离。 让鸟群中的个体之间保持最优的距离。