计算智能(CI)之粒子群优化算法(PSO)(一)

计算智能(ComputationalIntelligence ,CI)是以生物进化的观点认识和模拟智能。按照这一观点,智能是在生物的遗传、变异、生长以及外部环境的自然选择中产生的。在用进废退、优胜劣汰的过程中,适应度高的结构被保存下来,智能水平也随之提高。因此计算智能就是基于结构演化的智能。计算智能的主要方法有人工神经网络、遗传算法、遗传程序、演化程序、局部搜索、模拟退火等等。这些方法具有以下共同的要素:自适应的结构、随机产生的或指定的初始状态、适应度的评测函数、修改结构的操作、系统状态存储器、终止计算的条件、指示结果的方法、控制过程的参数。计算智能的这些方法具有自学习、自组织、自适应的特征和简单、通用、鲁棒性强、适于并行处理的优点。在并行搜索、联想记忆、模式识别、知识自动获取等方面得到了广泛的应用。典型的代表如遗传算法、免疫算法、模拟退火算法、蚁群算法、微粒群算法,都是一种仿生算法,基于“从大自然中获取智慧”的理念,通过人们对自然界独特规律的认知,提取出适合获取知识的一套计算工具。总的来说,通过自适应学习的特性,这些算法达到了全局优化的目的。

粒子群优化算法(PartieleSwarm Optimization ,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。由Kennedy和Eberhart博士于1995年提出,是一种基于群智能(SwarmIntelligence , SI)方法的演化计算(EvolutionaryComputation , EC)技术,可通过微利之间的相互作用发现复杂搜索空间中的最优区域。

鸟被抽象为没有质量和体积的微粒(点),并延伸到N维空间,粒子I在N维空间的位置表示为矢量Xi=(x1,x2,…,xN),飞行速度表示为矢量Vi=(v1,v2,…,vN).每个粒子都有一个由目标函数决定的适应值(fitnessvalue),并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi.这个可以看作是粒子自己的飞行经验.除此之外,每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值).这个可以看作是粒子同伴的经验.粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

Millonas在开发人工生命算法时(1994年),提出群体智能概念并提出五点原则: 1.接近性原则:群体应能够实现简单的时空计算;

2.优质性原则:群体能够响应环境要素;

3.变化相应原则:群体不应把自己的活动限制在一狭小范围;

4.稳定性原则:群体不应每次随环境改变自己的模式;

5.适应性原则:群体的模式应在计算代价值得的时候改变。

下面介绍最原始的PSO算法,它公式的内涵也就是基于这5点原则的。

初始化粒子位置:按一定策略,随机生成一些粒子初试位置(随机解)。

通过迭代找到最优解。在每一次的迭代中,粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后,粒子通过下面的公式来更新自己的速度和位置

位置更新公式:

速度更新公式:

更新公式中,i=1,2…,N,N是此群中粒子的总数。rand()用于产生(0,1)之间的随机数。C1和C2是学习因子,通常设置为C1=C2=2。

改进后的离散二进制PSO(BinaryPSO , BPSO):

PSO主要优化连续实值问题,BPSO主要优化离散空间约束问题;

BPSO是在离散粒子群算法基础上,约定位置向量、速度向量均由0、1值构成。

初始化粒子位置:按一定策略,生成二进制编码。

速度更新公式:

但没有原始PSO的粒子位置更新公式,为了表示速度的值是二进制位取1的概率,速度的值被映射到区间[0,1],映射的方法一般采用(2)式sigmoid函数:

这里s(vid)表示位置xid取1的概率,粒子通过(3)式更新位置:

BPSO有很强全局搜索能力,但不能收敛于全局最优值,且随着算法迭代搜索随机性越来越强,缺乏后期的局部搜索能力。

实验:使用BPSO,借助MATLAB优化函数3*cos(x(1)*x(2))+ x(1) + x(2)^2

参数设置为:

群体粒子个数N=100,粒子维度D=2,最大迭代次数T=200;C1=C2=1.5,惯性权重W∈[0.4,0.8],位置值x∈[-4,4],速度值v∈[-1,1]。

实验代码如下:

实验结果如下:

从实验结果可以看出,在迭代大约十次之后,适应度值趋于平稳,说明此值是最优解。

PSO算法的应用:

由于PSO算法概念简单、调参少、容易实现等特点,现已成功的应用于诸多领域。目前主要的应用领域包括以下几个方面:

  1. 优化问题的求解。PSO算法可用于约束优化问题、多目标优化问题、离散空间组合优化问题以及动态跟踪优化问题的求解。
  2. 模式识别和图像处理。PSO算法已在图像分割、图像配准、图像融合、图像识别、图像压缩和图像合成等方面得到成功应用。
  3. 神经网络训练。PSO算法可完成人工神经网络中的各种任务,包括连接权值的训练、结构设计、学习规则调整、特征选择、连接权值的初始化和规则提取等。
  4. 电力系统设计。日本的Fuji电力公司的研究人员将电力企业某个著名的RPVC(Reactive Power and Voltage Control)问题简化为函数的最小值问题,并使用改进的PSO算法进行优化求解。与传统方法如专家系统、敏感性分析相比,实验产生的结果证明了PSO算法在解决该问题的优势。
  5. 半导体器件综合。半导体器件综合是在给定的搜索空间内根据期望得到的器件特性来得到相应的设计参数,一般情况下使用器件模拟器通常得到的特性空间是高度非线性的,因此很难用传统方法来计算,利用PSO算法能比遗传算法更快更好地找到较高质量的设计参数。
  6. 其他应用。除了以上领域外,PSO在自动目标检测、生物信号识别、决策调度、系统识别以及游戏训练等方面也取得了一定的研究成果。

参考文献

《计算智能基础》主编:张汝波、刘冠群、吴俊伟

《智能优化算法及其MATLAB实例》主编:包子阳、余继周

原文发布于微信公众号 - 磐创AI(xunixs)

原文发表时间:2018-03-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

自然语言处理终极方向:深度学习用于自然语言处理的5大优势

【新智元导读】在自然语言处理领域,深度学习的承诺是:给新模型带来更好的性能,这些新模型可能需要更多数据,但不再需要那么多的语言学专业知识。 在自然语言处理领域,...

39460
来自专栏人工智能头条

何时不应使用深度学习?

9410
来自专栏IT派

统计vs机器学习,数据领域的“少林和武当”!

虽然这两个学派的目的都是从数据中挖掘价值,但彼此“互不服气”。注重模型预测效果的人工智能派认为统计学派“固步自封”,研究和使用的模型都只是一些线性模型,太过简单...

10610
来自专栏数据派THU

【独家】深扒Yann LeCun清华演讲中提到的深度学习与人工智能技术(PPT+视频)

本文长度为3000字,建议阅读10分钟 本文为Yann LeCun在清华大学做的关于深度学习与人工智能技术的演讲梗概。 姚期智先生引言: 非常荣幸来给大家介...

23970
来自专栏ATYUN订阅号

【算法】“极简主义机器学习”算法可从极小数据中分析图像

美国能源部劳伦斯伯克利国家实验室(伯克利实验室)的数学家们开发了一种新的机器学习方法,旨在实验成像数据。这种新方法不是依靠典型机器学习方法所使用的数十或数十万个...

36470
来自专栏新智元

中星微夺冠国际人工智能算法竞赛,目标检测一步法精度速度双赢

21770
来自专栏悦思悦读

让AI自动翻译“媲美人类”的“对偶学习”是怎么回事?

突破 性进展 ---- 2018年3月14日,微软研究院宣布,他们研发的中英机器翻译系统在newstest2017测试集上,达到了可与人类翻译媲美的水平。 ne...

52790
来自专栏AI研习社

如何让无人机灵活穿越满是障碍的房间?训练一个循环神经网络试试看

如今,深度学习已经在语音识别、计算机视觉等多个应用领域取得了重大突破。然而,要说到它在机器人领域的发展,那就要另当别论了——深度学习在机器人领域,不仅发展速度慢...

348100
来自专栏机器之心

深度 | 超越DQN和A3C:深度强化学习领域近期新进展概览

我觉得,深度强化学习最让人喜欢的一点是它确实实在难以有效,这一点不同于监督学习。用神经网络来解决一个计算机视觉问题可能能达到 80% 的效果;而如果用神经网络来...

13710
来自专栏大数据文摘

大咖 | GAN之父Ian Goodfellow在Quora:机器学习十问十答

17140

扫码关注云+社区

领取腾讯云代金券