标准粒子群算法(PSO)及其Matlab程序和常见改进算法_粒子群算法应用实例

标准粒子群算法(PSO)及其Matlab程序和常见改进算法_粒子群算法应用实例第2章标准粒子群算法(PSO)2.1粒子群算法思想的起源粒子群优化(ParticleSwarmOptimization,PSO)算法是Kennedy和Eberhart受人工生命研究结果的

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

第2章 标准粒子群算法(PSO)

2.1 粒子群算法思想的起源

      粒子群优化(Particle Swarm Optimization, PSO)算法是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法,自然界中各种生物体均具有一定的群体行为,而人工生命的主要研究领域之一是探索自然界生物的群体行为,从而在计算机上构建其群体模型。自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣,生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模型,在他的仿真中,每一个个体遵循:

      (1) 避免与邻域个体相冲撞;

      (2) 匹配邻域个体的速度;

      (3) 飞向鸟群中心,且整个群体飞向目标。

      仿真中仅利用上面三条简单的规则,就可以非常接近的模拟出鸟群飞行的现象。1995年,美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出了粒子群算法,其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的启发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正,以使粒子飞向解空间并在最好解处降落。Kennedy在他的书中描述了粒子群算法思想的起源。

2.2 算法原理

     PSO从这种模型中得到启示并用于解决优化问题。PSO 中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ,每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个极值来更新自己;第一个就是粒子本身所找到的最优解,这个解称为个体极值;另一个极值是整个种群目前找到的最优解,这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。

    假设在一个clip_image002维的目标搜索空间中,有clip_image004个粒子组成一个群落,其中第clip_image006个粒子表示为一个clip_image002[1]维的向量

clip_image009clip_image011

     第clip_image006[1]个粒子的“飞行 ”速度也是一个clip_image002[2]维的向量,记为

clip_image013clip_image015

     第clip_image006[2]个粒子迄今为止搜索到的最优位置称为个体极值,记为

clip_image018clip_image011[1]

     整个粒子群迄今为止搜索到的最优位置为全局极值,记为

clip_image021

      在找到这两个最优值时,粒子根据如下的公式(2-1)和( 2-2)来更新自己的速度和位置:

clip_image023 (2-1)

clip_image025 (2-2)

     其中:clip_image027clip_image029为学习因子,也称加速常数(acceleration constant),w为惯性因子,clip_image031clip_image033为[0,1]范围内的均匀随机数。式(2-1)右边由三部分组成,第一部分为“惯性(inertia)”或“动量(momentum)”部分,反映了粒子的运动“习惯(habit)”,代表粒子有维持自己先前速度的趋势;第二部分为“认知(cognition)”部分,反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance),代表粒子有向自身历史最佳位置逼近的趋势;第三部分为“社会(social)”部分,反映了粒子间协同合作与知识共享的群体历史经验,代表粒子有向群体或邻域历史最佳位置逼近的趋势, clip_image035,clip_image037是粒子的速度,clip_image039clip_image041是常数,由用户设定用来限制粒子的速度。clip_image031[1]clip_image033[1]是介于clip_image045之间的随机数。

2.3 标准粒子群算法流程

    算法的流程如下:

     Step1:初始化粒子群,包括群体规模clip_image004[1],每个粒子的位置clip_image048和速度clip_image050

     Step2:计算每个粒子的适应度值clip_image052

    Step3: 对每个粒子,用它的适应度值clip_image052[1]和个体极值clip_image054比较,如果clip_image056 ,则用clip_image058替换掉clip_image054[1]

    Step4: 对每个粒子,用它的适应度值clip_image058[1]和全局极值clip_image061比较,如果clip_image056[1]则用clip_image052[2]clip_image061[1]

    Step5: 根据公式(2-1),(2-2)更新粒子的速度clip_image050[1]和位置clip_image048[1]

    Step6: 如果满足结束条件(误差足够好或到达最大循环次数)退出,否则返回Step2。

clip_image065

图2-1. PSO算法流程图

2.4 特点

       1、式(2-1)中第1部分可理解为粒子先前的速度或惯性;第2部份可理解为粒子的“认知”行为,表示粒子本身的思考能力;第3部分可理解为粒子的“社会”行为,表示粒子之间的信息共享与相互合作。公式(2-2) 表示了粒子在求解空间中,由于相互影响导致的运动位置调整。整个求解过程中,加速因子clip_image027[1]clip_image029[1]和最大速度clip_image041[1]共同维护粒子对全局和局部搜索能力的平衡。

       2、粒子群优化算法初期,其解群随进化代数表现了更强的随机性,正是由于其产生了下一代解群的较大的随机性,以及每代所有解的“信息”的共享性和各个解的“自我素质”的提高。

       3、PSO 的一个优势就是采用实数编码,不需要像遗传算法一样采用二进制编码(或者采用针对实数的遗传操作) 。例如对于问题clip_image072求解, 粒子可以直接编码为clip_image074 ,而适应度函数就是clip_image076

       4、粒子具有“记clip_image074[1]忆”的特性,它们通过“自我”学习和向“他人”学习,使其下一代解有针对性的从“先辈”那里继承更多的信息,从而能在较短的时间内找到最优解。

       5、与遗传算法相比,粒子群优化算法的信息共享机制是很不同的:在遗传算法中,染色体互相共享信息,所以整个种群的移动是比较均匀的向最优区域移动;在粒子群优化算法中,信息流动是单向的,即只有clip_image061[2]将信息给其他的粒子,这使得整个搜索更新过程跟随当前解。

2.5 惯性权重线性递减的粒子群算法(PSO-W)

      探索是偏离原来的寻优轨迹去寻找一个更好的解,探索能力是一个算法的全局搜索能力。开发是利用一个好的解,继续原来的寻优轨迹去搜索更好的解,它是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例,对一个问题的求解过程很重要。1998年,Yuhui Shi[9]提出了带有惯性权重的改进粒子群算法。其进化过程为:

clip_image078 (2-3)

clip_image080 (2-4)

       在式(2-1)中,第一部分表示粒子先前的速度,用于保证算法的全局收敛性能;第二部分、第三部分则是使算法具有局部收敛能力。可以看出,式(2-3)中惯性权重clip_image082表示在多大程度上保留原来的速度。clip_image082[1]较大,全局收敛能力强,局部收敛能力弱;clip_image082[2]较小,局部收敛能力强,全局收敛能力弱。

clip_image084时,式(2-3)与式(2-1)完全一样,表明带惯性权重的粒子群算法是基本粒子群算法的扩展。实验结果表明,clip_image082[3]clip_image086之间时,PSO算法有更快的收敛速度,而当clip_image088时,算法则易陷入局部极值。

      由于较大的权重因子有利于跳出局部最小点,便于全局搜索,而较小的惯性因子则有利于对当前的搜索区域进行精确局部搜索,以利于算法收敛,因此针对PSO算法容易早熟以及算法后期易在全局最优解附近产生振荡现象,可以采用线性变化的权重,让惯性权重从最大值clip_image090线性减小到最小值clip_image092。随算法迭代次数的变化公式为:

clip_image094 (2-5)

其中,clip_image090[1],clip_image092[1]分别表示clip_image098的最大值和最小值,t表示当前迭代步数,clip_image100表示最大迭代步数,通常取clip_image102,clip_image104.

2.6 带收缩因子的粒子群算法(PSO-X)

      学习因子cl和c2决定了微粒本身经验信息和其他微粒的经验信息对微粒运行轨迹的影响,反映了微粒群之间的信息交流。设置c1较大的值,会使微粒过多地在局部范围内徘徊,而较大的c2的值,则又会促使微粒过早收敛到局部最小值。微粒有效地控制微粒的飞行速度,使算法达到全局探测与局部开采两者间的有效平衡,Clerc构造了引入收缩因子的PSO模型,采用了压缩因子,这种调整方法通过合适选取参数,可确保PSO算法的收敛性,并可取消对速度的边界限制。速度公式如下:

clip_image106 (2-6)

其中clip_image108称为收缩因子,clip_image110clip_image112,且clip_image114

2.7测试仿真函数

    用2个单峰函数和2个多峰函数来测试以上三种算法,求函数的最小值,

1.单峰函数-Sphere Model

函数表达式 clip_image116

全局最优值 clip_image118

函数维数为2时的模型为:

clip_image120clip_image122

Sphere Model Schwefel’s Problem2.22

2.单峰函数 Schwefel’s Problem2.22

函数表达式 clip_image124

全局最优值 clip_image126

3.病态函数Generalized Rosenbrock

函数表达式 clip_image128

全局最优值 clip_image130

clip_image132 clip_image134

Generalized Rosenbrock Generalized Rastrigin

4.多峰函数Generalized Rastrigin 函数

函数表达式 clip_image136

全局最优值 clip_image138

2.8测试结果

初始条件为粒子群数目为20,每个粒子维数为20,迭代1000次

clip_image140

图2-2单峰函数Sphere Model 测试结果

clip_image142

图2-3单峰函数Schwefel’s Problem2.22 测试结果

clip_image144

图2-4病态函数Generalized Rosenbrock 测试结果

clip_image146

图2-5多峰函数Generalized Rastrigin测试结果

表2-1 基本粒子群算法、惯性权重线减粒子群算法,带收缩因子粒子群算法输出结果

函数

PSO

PS0-W

PSO-X

单峰

函数

clip_image148

最优值

0.0021(好解)

2.56E-05(好解)

2.45E-04(好解)

均值

0.0233

0.0084

0.0041

clip_image150

最优值

0.1129(差解)

0.0754(好解)

0.0849(好解)

均值

0.3304

0.1275

0.1011

病态函数

clip_image152

最优值

8.5907(差解)

7.7378(差解)

8.2623(差解)

均值

9.9060

8.4721

8.5427

多峰函数

clip_image154

最优值

1.2151(差解)

1.2344(差解)

0.8977(差解)

均值

3.4962

1.678

1.209

2.9测试结论

       从上图2-2~2-5及表一我们可以知道,以上三种粒子群算法,只对于单峰函数且非病态方程才能取得最优解,迭代次数越多,种群数目越多,得到的精度就会越高,但同时也会延长运算的时间,所以迭代次数和种群数需设置好,并且相对来说惯性权重线性递减的粒子群算法找到的解是最好的。

      然而对于多峰函数以及病态方程,以上三种粒子群算法无法取得最好的解,无论是增加迭代次数还是种群数目,精度都不会有太大的改变,这就是基本粒子群一个最大的缺点,即容易陷入局部最优解的位置,算法容易早熟,对多峰函数或病态函数无法找到最优解,所以我们可以得出惯性权重线减粒子群算法,带收缩因子粒子群算法改进的效果意义不大,算法没有本质上的改变,精度也无法提高很多。

      由于在我们实际生活中,大部份的优化问题都是多峰函数或病态函数,为了克服基本粒子群算法的缺陷,我研究了以下四种改进的粒子群算法:基于混沌思想改进的粒子群算法、基于遗传思想改进的混合粒子群算法、基于免疫记忆和浓度机制改进的混合粒子群算法.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166676.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 聊聊互联网行业年终奖:大家一起关门哭吧「建议收藏」

    聊聊互联网行业年终奖:大家一起关门哭吧

  • mysql删除表数据及其关联数据_MYSQL中delete删除多表数据与删除关联数据

    mysql删除表数据及其关联数据_MYSQL中delete删除多表数据与删除关联数据在mysql中删除数据方法有很多种,最常用的是使用delete来删除记录,下面我来介绍delete删除单条记录与删除多表关联数据的一些简单实例。1、deletefromt1where条件2、deletet1fromt1where条件3、deletet1fromt1,t2where条件4、deletet1,t2fromt1,t2where条件前3者是可行的,第…

  • MD5加密函数

    MD5加密函数其实C#里已经写好了怎么生成MD5,简单的一个函数调用就可以。 //////MD5加密/////////publicstaticstringGetMD5(stringsDataIn){MD5CryptoServiceProvidermd5

  • 监督学习、无监督学习、自监督学习和强化学习

    监督学习、无监督学习、自监督学习和强化学习监督学习监督学习是目前最常见的机器学习类型。给定一组样本(通常由人工标注),他可以学会将输入数据映射到已知目标。一般来说,近年来过度关注的深度学习应用几乎都属于监督学习,比如光学字符识别、语音识别、图像分类和语言翻译。监督学习主要包括分类和回归,但还有更多的奇特变体,主要包括如下几种:1、序列生成(sequencegeneration)。给定一张图像,预测描述图像的文字。序列生成有时可…

  • 网页升级中每天自动更新什么意思_快照搜索

    网页升级中每天自动更新什么意思_快照搜索网站被收录是百度蜘蛛爬行、记录、筛选的结果。网站被爬行后会在搜索引擎数据库中留下数据,当判断收录的内容达到用户要求质量时,网站的快照才会被释放出来,而快照的时候很多时候都是最初的爬行时间。这也是我们很多站长发现被收录后,快照时间不是当天时间的原因了。  在我们的认知中,每次百度快照的更新都是搜素引擎对网站数据的一次爬行收录过程,也就意味着更新就会带来网站排名的微调动。所以,更多时候

  • 一致性哈希算法原理详解

    一致性哈希算法原理详解(1)一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环,称为Hash环;(2)接着将各个服务器使用Hash函数进行哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,从而确定每台机器在哈希环上的位置;(3)最后使用算法定位数据访问到相应服务器:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针寻找,第一台遇到的服务器就是其应该定位到的服务器

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号