粒子群优化

粒子群优化

PSO

引言

在机器学习问题中以及实际实践中,大多数的建模与控制问题最终都可以转化为一个约束或者无约束的优化问题,这些问题一般比较复杂,主要表现为规模大、维数高、非线性、非凸以及不可微等性质,而且由于非凸的原因往往存在较多的井点,传统的基于梯度的优化算法收敛速度快,但是对于初始值比较敏感,容易陷入局部最优(这也一直以来是bp神经网络的问题),对于高维复杂的函数难以实现高效优化。

粒子群优化(Particle Swarm Optimization),又称微粒群算法,是由J. Kennedy和R. C. Eberhart等于1995年开发的一种演化计算技术,来源于对一个简化社会模型的模拟。其中“群(swarm)”来源于微粒群符合M. M. Millonas在开发应用于人工生命(artificial life)的模型时所提出的群体智能的5个基本原则。“粒子(particle)”是一个折衷的选择,因为既需要将群体中的成员描述为没有质量、没有体积的,同时也需要描述它的速度和加速状态。

基本思想如下所示:

通过群体中个体间的协作和信息共享来寻找最优解,本质上是一种并行的去哪聚性随机搜索算法。算法最初是为了图形化的模拟鸟群优美而不可预测的运动。而通过对动物社会行为的观察,发现在群体中对信息的社会共享提供一个演化的优势,并以此作为开发算法的基础。通过加入近邻的速度匹配、并考虑了多维搜索和根据距离的加速,形成了PSO的最初版本。之后引入了惯性权重w来更好的控制开发(exploitation)和探索(exploration),形成了标准版本。

算法原理

从社会人之学角度而言,粒子群优化算法应用如下简单道理:即群体中的每个个体都可以从临近个体的认知经验中收益,其理论基础主要包括以下几个基本步骤:

刺激的评价

与临近的比较

对邻先近邻的模仿

PSO算法是基于群体的,根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子,而是将每个个体看作是D维搜索空间中的一个没有体积的微粒(点),在搜索空间中以一定的速度飞行,这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第i个微粒表示为Xi = (xi1, xi2, …, xiD),它经历过的最好位置(有最好的适应值)记为Pi = (pi1, pi2, …, piD),也称为pbest。在群体所有微粒经历过的最好位置的索引号用符号g表示,即Pg,也称为gbest。微粒i的速度用Vi = (vi1, vi2, …, viD)表示。对每一代,它的第d维(1 ≤ d ≤ D)根据如下方程进行变化:

其中w为惯性权重(inertia weight),c1和c2为加速常数(acceleration constants),rand()和Rand()为两个在[0,1]范围里变化的随机值。

此外,微粒的速度Vi被一个最大速度Vmax所限制。如果当前对微粒的加速导致它的在某维的速度vid超过该维的最大速度vmax,d,则该维的速度被限制为该维最大速度vmax,d。

对公式(1a),第一部分为微粒先前行为的惯性,第二部分为“认知(cognition)”部分,表示微粒本身的思考;第三部分为“社会(social)”部分,表示微粒间的信息共享与相互合作。

PSO流程

a). 初始化一群微粒(群体规模为m),包括随机的位置和速度;

b). 评价每个微粒的适应度;

c). 对每个微粒,将它的适应值和它经历过的最好位置pbest的作比较,如果较好,则将其作为当前的最好位置pbest;

d). 对每个微粒,将它的适应值和全局所经历最好位置gbest的作比较,如果较好,则重新设置gbest的索引号;

e). 根据方程(1)变化微粒的速度和位置;

f). 如未达到结束条件(通常为足够好的适应值或达到一个预设最大代数Gmax),回到b)。

PSO分类

粒子群算法主要分为4个分支

1

标准粒子群算法的变形

在这个分支中,主要是对标准粒子群算法的惯性因子、收敛因子(约束因子)、“认知”部分的c1,“社会”部分的c2进行变化与调节,希望获得好的效果。

惯性因子的原始版本是保持不变的,后来有人提出随着算法迭代的进行,惯性因子需要逐渐减小的思想。算法开始阶段,大的惯性因子可以是算法不容易陷入局部最优,到算法的后期,小的惯性因子可以使收敛速度加快,使收敛更加平稳,不至于出现振荡现象。经过本人测试,动态的减小惯性因子w,的确可以使算法更加稳定,效果比较好。但是递减惯性因子采用什么样的方法呢?人们首先想到的是线型递减,这种策略的确很好,但是是不是最优的呢?于是有人对递减的策略作了研究,研究结果指出:线型函数的递减优于凸函数的递减策略,但是凹函数的递减策略又优于线型的递减,经过本人测试,实验结果基本符合这个结论,但是效果不是很明显。

对于收敛因子,经过证明如果收敛因子取0.729,可以确保算法的收敛,但是不能保证算法收敛到全局最优,经过本人测试,取收敛因子为0.729效果较好。对于社会与认知的系数c2,c1也有人提出:c1先大后小,而c2先小后大的思想,因为在算法运行初期,每个鸟要有大的自己的认知部分而又比较小的社会部分,这个与我们自己一群人找东西的情形比较接近,因为在我们找东西的初期,我们基本依靠自己的知识取寻找,而后来,我们积累的经验越来越丰富,于是大家开始逐渐达成共识(社会知识),这样我们就开始依靠社会知识来寻找东西了。

2007年希腊的两位学者提出将收敛速度比较快的全局版本的粒子群算法与不容易陷入局部最优的局部版本的粒子群算法相结合的办法,利用的公式是

v=n*v(全局版本)+(1-n)*v(局部版本)

速度更新公式,v代表速度

w(k+1)=w(k)+v

位置更新公式

该算法在文献中讨论了系数n取各种不同情况的情况,并且运行来了20000次来分析各种系数的结果。

2

粒子群算法的混合

这个分支主要是将粒子群算法与各种算法相混合,有人将它与模拟退火算法相混合,有些人将它与单纯形方法相混合。但是最多的是将它与遗传算法的混合。根据遗传算法的三种不同算子可以生成3中不同的混合算法。

粒子群算法与选择算子的结合,这里相混合的思想是:在原来的粒子群算法中,我们选择粒子群群体的最优值作为pg,但是相结合的版本是根据所有粒子的适应度的大小给每个粒子赋予一个被选中的概率,然后依据概率对这些粒子进行选择,被选中的粒子作为pg,其它的情况都不变。这样的算法可以在算法运行过程中保持粒子群的多样性,但是致命的缺点是收敛速度缓慢。

粒子群算法与杂交算子的结合,结合的思想与遗传算法的基本一样,在算法运行过程中根据适应度的大小,粒子之间可以两两杂交,比如用一个很简单的公式

w(新)=n×w1+(1-n)×w2;

w1与w2就是这个新粒子的父辈粒子。这种算法可以在算法的运行过程中引入新的粒子,但是算法一旦陷入局部最优,那么粒子群算法将很难摆脱局部最优。

粒子群算法与变异算子的结合,结合的思想:测试所有粒子与当前最优的距离,当距离小于一定的数值的时候,可以拿出所有粒子的一个百分比(如10%)的粒子进行随机初始化,让这些粒子重新寻找最优值。

3

二进制粒子群算法

最初的PSO是从解决连续优化问题发展起来的.Eberhart等又提出了PSO的离散二进制版.用来解决工程实际中的组合优化问题。他们在提出的模型中将粒子的每一维及粒子本身的历史最优、全局最优限制为1或0,而速度不作这种限制。用速度更新位置时,设定一个阈值,当速度高于该阈值时,粒子的位置取1,否则取0。二进制PSO与遗传算法在形式上很相似,但实验结果显示,在大多数测试函数中,二进制PSO比遗传算法速度快,尤其在问题的维数增加时

4

协同粒子群算法

协同PSO,该方法将粒子的D维分到D个粒子群中,每个粒子群优化一维向量,评价适应度时将这些分量合并为一个完整的向量。例如第i个粒子群,除第i个分量外,其他D-1个分量都设为最优值,不断用第i个粒子群中的粒子替换第i个分量,直到得到第i维的最优值,其他维相同。为将有联系的分量划分在一个群,可将D维向量分配到m个粒子群优化,则前D mod m个粒子群的维数是D/m的向上取整。后m-(Dmod m)个粒子群的维数是D/m的向下取整。协同PSO在某些问题上有更快的收敛速度。

原文发布于微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文发表时间:2017-01-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

揭开深度学习黑箱:希伯来大学计算机科学教授提出「信息瓶颈」

一个称为「信息瓶颈」的新想法有助于解释当今人工智能算法的黑箱问题——以及人类大脑的工作原理。

10830
来自专栏AI科技评论

解读 | “数据为王”是真的吗?谷歌轻抚着100倍的数据量点了点头

AI 科技评论按:过去十年里,研究人员在计算视觉领域取得了巨大的成功,而这其中,深度学习模型在机器感知任务中的应用功不可没。此外,2012 年以来,由于深度学习...

36460
来自专栏人工智能头条

开发者成功使用机器学习的十大诀窍

14340
来自专栏AI研习社

Arxiv Insights | 克服稀疏奖励的束缚,让智能体在学习中成长

在强化学习的设置中,为了执行一个我们想学习的任务,智能体会应用一些特征提取方案来从原始数据中提取有用信息,然后会有一个策略网络用于提取特征。

20510
来自专栏机器之心

学界 | 批训练、注意力模型及其声纹分割应用,谷歌三篇论文揭示其声纹识别技术原理

55860
来自专栏机器之心

学界 | 学习一帧,为整段黑白视频上色:谷歌提出自监督视觉追踪模型

在谷歌最近提交的论文《Tracking Emerges by Colorizing Videos》中,研究人员引入了一种为灰度视频着色的卷积神经网络,但它只需要...

13830
来自专栏AI科技评论

学界 | 殊途同归还是渐行渐远?MIT神经科学教授James DiCarlo谈如何通过人类神经理解神经网络

AI 科技评论按:国际计算机视觉与模式识别顶级会议CVPR 2017于 7 月 21 日至7 月 26 日在美国夏威夷召开。我们的记者团也特赴夏威夷为大家带来一...

34690
来自专栏机器之心

学界 | MINIEYE首席科学家吴建鑫解读ICCV入选论文:用于网络压缩的滤波器级别剪枝算法ThiNet

机器之心报道 作者:高静宜 近日,南京大学计算机科学与技术系教授、MINIEYE 首席科学家吴建鑫所在团队的一篇论文《ThiNet: 一种用于深度神经网络压缩的...

43980
来自专栏机器之心

资源 | 实时评估世界杯球员的正确姿势:FAIR开源DensePose

左图:输入;中图:对应的 DensePose-RCNN 结果;右图:人体分割和 UV 参数化。

13800
来自专栏机器之心

CVPR2018 | 直接建模视觉智能体?让「小狗」动起来~

选自arXiv 作者:Kiana Ehsani 等 机器之心编译 参与:Pedro、路 近日,来自华盛顿大学和艾伦人工智能研究所的研究者在 arXiv 上发布论...

36560

扫码关注云+社区

领取腾讯云代金券