粒子群优化算法PSO_xuxinrk的博客-程序员ITS203

技术标签: 粒子群优化算法  智能优化算法  PSO  

原文

同进化算法(见博客《[Evolutionary Algorithm] 进化算法简介》,进化算法是受生物进化机制启发而产生的一系列算法)和人工神经网络算法(Neural Networks,简称NN,神经网络是从信息处理角度对人脑的神经元网络系统进行了模拟的相关算法)一样,群体智能优化算法也属于一种生物启发式方法,它们三者可以称为是人工智能领域的三驾马车(PS:实际上除了上述三种算法还有一些智能算法应用也很广泛,比如模拟金属物质热力学退火过程的模拟退火算法(Simulated Algorithm,简称SA),模拟人体免疫系统在抗原刺激下产生抗体过程的人工免疫系统算法(Artificial Immune System,简称AIS)等,但是相对三者而言,模拟退火和人工免疫系统算法已逐渐处于低潮期)。群体智能优化算法主要模拟了昆虫、兽群、鸟群和鱼群的群集行为,这些群体按照一种合作的方式寻找食物,群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索,从而在解空间内找到最优解。

回到顶部

1. 常见的群体智能优化算法分类

  常见的群体智能优化算法主要有如下几类:

  (1)蚁群算法(Ant Colony Optimization,简称ACO)[1992年提出];

  (2)粒子群优化算法(Particle Swarm Optimization,简称PSO)[1995年提出](简单易于实现,也是目前应用最为广泛的群体智能优化算法);

  (3)菌群优化算法(Bacterial Foraging Optimization,简称BFO)[2002年提出];

  (4)蛙跳算法(Shuffled Frog Leading Algorithm,简称SFLA)[2003年提出];

  (5)人工蜂群算法(Artificial Bee Colony Algorithm,简称ABC)[2005年提出];

  除了上述几种常见的群体智能算法以外,还有一些并不是广泛应用的群体智能算法,比如萤火虫算法、布谷鸟算法、蝙蝠算法以及磷虾群算法等等。

回到顶部

2. 粒子群优化算法思想

  由于博主对粒子群优化算法比较熟悉,在硕士期间也进行了比较系统的学习,所以利用本博文系统的介绍一下应用最为广泛的PSO算法。

  粒子群优化算法是在1995年由Eberhart博士和Kennedy博士一起提出的,它源于对鸟群捕食行为的研究。它的基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程,从而获得问题的最优解。我们可以利用一个有关PSO的经典描述来对PSO算法进行一个直观的描述。设想这么一个场景:一群鸟进行觅食,而远处有一片玉米地,所有的鸟都不知道玉米地到底在哪里,但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略,也是最简单有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。PSO就是从这种群体觅食的行为中得到了启示,从而构建的一种优化模型。

  在PSO中,每个优化问题的解都是搜索空间中的一只鸟,称之为“粒子”,而问题的最优解就对应为鸟群要寻找的“玉米地”。所有的粒子都具有一个位置向量(粒子在解空间的位置)和速度向量(决定下次飞行的方向和速度),并可以根据目标函数来计算当前的所在位置的适应值(fitness value),可以将其理解为距离“玉米地”的距离。在每次的迭代中,种群中的粒子除了根据自身的“经验”(历史位置)进行学习以外,还可以根据种群中最优粒子的“经验”来学习,从而确定下一次迭代时需要如何调整和改变飞行的方向和速度。就这样逐步迭代,最终整个种群的粒子就会逐步趋于最优解。

回到顶部

3. 粒子群优化算法的基本框架

  在介绍PSO的算法流程之前,我们写给出PSO中常用的迭代算子的形式。令Xi=(xi1,xi2,...,xin)Xi=(xi1,xi2,...,xin)代表粒子ii的位置向量,Vi=(vi1,vi2,...,vin)Vi=(vi1,vi2,...,vin)代表粒子ii的速度向量(其中nn为优化问题的维度大小),最早版本的粒子群优化算法的迭代算子形式如下:

  速度向量迭代公式:

Vi=Vi+c1r1(Pbesti−Xi)+c2r2(Gbest−Xi)Vi=Vi+c1r1(Pbesti−Xi)+c2r2(Gbest−Xi)       (1)

  位置向量迭代公式:

Xi=Xi+ViXi=Xi+Vi        (2)

其中在公式(1)中,PbestiPbesti和GbestGbest分别代表粒子ii的历史最佳位置向量和种群历史最佳位置向量。根据公式(1)(2)可以看出,种群中的粒子通过不断地向自身和种群的历史信息进行学习,从而可以找出问题的最优解。

  但是,在后续的研究中表明,上述原始的公式中存在一个问题:公式(1)中ViVi的更新太具有随机性,从而使得整个PSO算法的全局优化能力很强,但是局部搜索能力较差。而实际上,我们需要在算法迭代初期PSO有着较强的全局优化能力,而在算法的后期,整个种群应该具有更强的局部搜索能力。所以根据上述的弊端,Shi和Eberhart通过引入惯性权重修改了公式(1),从而提出了PSO的惯性权重模型:

  速度向量迭代公式:

Vi=wVi+c1r1(Pbesti−Xi)+c2r2(Gbest−Xi)Vi=wVi+c1r1(Pbesti−Xi)+c2r2(Gbest−Xi)       (3)

其中参数ww称为是PSO的惯性权重(inertia weight),它的取值介于[0,1]区间,一般应用中均采取自适应的取值方法,即一开始令w=0.9w=0.9,使得PSO全局优化能力较强,随着迭代的深入,参数ww进行递减,从而使得PSO具有较强的局部优化能力,当迭代结束时,w=0.1w=0.1。参数c1c1和c2c2称为是学习因子(learn factor),一般设置为1.4961;而r1r1和r2r2为介于[0,1]之间的随机概率值。

   整个粒子群优化算法的算法框架如下:

  Step 1 种群初始化:可以进行随机初始化或者根据被优化的问题设计特定的初始化方法,然后计算个体的适应值,从而选择出个体的局部最优位置向量PbestiPbesti和种群的全局最优位置向量GbestGbest。

  Step 2 迭代设置:设置迭代次数gmaxgmax,并令当前迭代次数g=1g=1;

  Step 3 速度更新:根据公式(3)更新每个个体的速度向量;

  Step 4 位置更新:根据公式(2)更新每个个体的位置向量;

  Step 5 局部位置向量和全局位置向量更新:更新每个个体的PbestiPbesti和种群的GbestGbest;

  Step 6 终止条件判断:判断迭代次数时都达到gmaxgmax,如果满足,输出GbestGbest;否则继续进行迭代,跳转至Step 3

  对于粒子群优化算法的运用,主要是对速度和位置向量迭代算子的设计。迭代算子是否有效将决定整个PSO算法性能的优劣,所以如何设计PSO的迭代算子是PSO算法应用的研究重点和难点。

回到顶部

4. 对粒子群优化算法中惯性权重的认识

  参数ww被称之为是惯性权重,顾名思义ww实际反映了粒子过去的运动状态对当前行为的影响,就像是我们物理中提到的惯性。如果w<<1w<<1,从前的运动状态很少能影响当前的行为,粒子的速度会很快的改变;相反,ww较大,虽然会有很大的搜索空间,但是粒子很难改变其运动方向,很难向较优位置收敛,由于算法速度的因素,在实际运用中很少这样设置。也就是说,较高的ww设置促进全局搜索,较低的ww设置促进快速的局部搜索。

回到顶部

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xuxinrk/article/details/81632284

智能推荐

Linux下的信号(一)----信号的基本概念与产生_snow_5288的博客-程序员ITS203_linux信号6

一,信号的基本概念1,什么是信号? 日常生活中,当我们走到马路上时,看到的绿灯是一种信号,它能提示我们怎样安全的过马路。又比如,新学期开始学校给每个班发的课表也是一种信号,它能提示同学们在适当的时间地点去上相应的课程而不是虚度光阴……生活中其实我们忽略了很多信号,正是由于这些信号的存在,才使得我们的生活方便而有序。 总结一下你会发现信号是什么,信号就是当你看到它是知道

《Android 4高级编程(第3版)》(完整书签).pdf_weixin_30681121的博客-程序员ITS203

下载地址:网盘下载内容简介编辑《Android 4高级编程(第3版)》由Android权威专家编写,涵盖了所有最新的内容,是学习使用Android 4 SDK开发移动应用程序的理想指南。本书见解深刻,帮助经验丰富的Android开发人员充分挖掘Android 4的新特性的潜力,同时讲解了Android开发的基础知识,使初学者也可以借助本书入门...

峰度(kurtosis)的c/c++实现_GodenEngineer的博客-程序员ITS203

峰度:随机变量在均值附近的相对平坦程度或峰值程度,以正态分布为界,峰度值为0,如比正态分布陡,峰度值大于0,否则小于0.以下为c++实现:#include&lt;iostream&gt;using namespace std;int main(){ //自定义一个数集,用数组a存储 int a[10] = {1,2,2,6,8,8,2,15,20,8}; int b[10]; int count; double exp = 0.0;//期望 double sum1 = 0.0, su

购物车(Shopping cart) —— B2C网站核心产品设计 (二)_youshandeyang的博客-程序员ITS203

购物车是做什么的?我们先来看一下现实超市中的购物车,一个带四个轱辘的铁筐子,客人推来推去,看到什么东西喜欢,就扔进去,觉得东西差不多了,就推到收银台。那B2C网站中的购物车又是一个什么东西呢?从广义上说,购物车在B2C网站里无处不在,当客人进入一个B2C网站时,他就相当于推着购物车开始逛超市了,只是客人暂时看不到购物车,直到进入购物车(Shopping cart page)

Java学习手册:如何通过JDBC访问数据库?_浩比浩比的博客-程序员ITS203

一、如何通过JDBC访问数据库?二、使用JDBC时需要注意哪些问题?答:在使用JDBC时,首先需要建立数据库连接,才能完成对数据库的访问,由于与数据库的连接是非常重要的资源。JDBC连接池提供了JDBC连接定义和数目有限的连接,如果连接数量不够,就需要长时间的等待。不正常关闭JDBC连接会导致等待回收无效的JDBC连接。只有正常的关闭和释放JDBC连接,JDBC资源才可以被快速地重用,从而使得...

Laya HTMLDivelement组件微信小游戏使用问题_IM魂影的博客-程序员ITS203

官方提供了HTMLDivelement组件在微信小游戏使用的方案,需要开发者在game.js里单独的引入xml解析文件,用法如下:require(&quot;weapp-adapter.js&quot;);window.Parser = require(&quot;./js/dom_parser&quot;);这里还需要引入LayaAir引擎库,AS3跟JS或TS不一样,这里自行引入即可。 代码片段:var p ...

随便推点

opencv之图像阈值化处理_普通网友的博客-程序员ITS203

一、函数简介1、threshold—图像简单阈值化处理函数原型:threshold(src, thresh, maxval, type, dst=None)src:图像矩阵thresh:阈值maxVal:像素最大值type:阈值化类型2、adaptiveThreshold—图像自适应阈值化处理函数原型:adaptiveThreshold(src, max...

使用C#自带的ReportViewer控件生成报表_平平淡淡才是true的博客-程序员ITS203_c#报表控件

第一步:新建数据集第二步:新建模板,添加数据集第三步:新建Form窗体,拖入ReportViewer控件第四步:加载之前建立的模板文件最后一步:赋值源代码如下:private void FormWWLHZ2_Load(object sender, EventArgs e) { this....

中国到美国最安全的飞机航线_微电子学与固体电子学-俞驰的博客-程序员ITS203

这里的安全仅仅考虑沿陆地飞行、尽可能少地横渡海面。因为出意外时,陆地更容易迫降。根据以下链接:http://map.variflight.com/origin可知:下面两条航线,除了需要经过白令海峡,其余的的飞行时段都是沿陆地飞行。北京首都-&gt;达拉斯沃尔斯堡北京首都-&gt;休斯顿北京首都-&gt;卡尔加里三条路线如下图:可以看到,他...

Java中实现连接数据库并进行查询_weixin_30670151的博客-程序员ITS203

  首先我们在在File中选择new在选择java project在任意取一个名字,如图:  选择才创建的项目userManager,在src下分别创建dao包,DBHelper包(可直接在其他项目中把它复制过来),entity包和servlet包,如图:  打开entity,在它下面new一个class,命名为User,然后定义三个变量代码如下:package entit...

配置flutter 遇到的问题及解决办法_liy010的博客-程序员ITS203

我是在windows环境下安装的。1. 从官网下载压缩包https://flutter.io/sdk-archive/#windows解压放在你某一个目录下(我的是C:\aplication\, 目录建的时候名字写错了), 这个目录就相当于flutter的安装目录。然后配置环境变量。2.安装 AndroidStutiohttps://developer.android.com/s...

斗鱼虎牙合并之后,平台背后的程序员将何去何从?_weixin_43802541的博客-程序员ITS203

10月12日消息,斗鱼和虎牙共同宣布,正式接受大股东腾讯提出的合并邀约,进行战略合并。同时,斗鱼与腾讯还签署了关于企鹅电竞业务的转让协议,从腾讯获得企鹅电竞业务。如此一来,直播行业格局将再生变数。作为一名对游戏直播颇感兴趣的程序员妹纸,汇智妹不仅关心各直播平台间今后博弈的精彩戏码,更关心三家巨头合并后,各自平台背后的程序员将何去何从?首先来看斗鱼和虎牙合并之后,作为鹅厂旗下的游戏直播中坚,对目前的直播格局撼动几何?必须肯定的是,这两家均有腾讯投资的平台从...