数学建模4之粒子群算法 - 柯西恒等式

lgy-gdeu 2021-08-05 原文


数学建模4之粒子群算法


    一、官方定义:       

  首先我们要知道粒子群算法具体要解决的问题是什么,官方定义是:子群算法,也称粒子群优化算法或鸟群觅食算法(Particle Swarm Optimization),缩写为 PSO, 是近年来由J. Kennedy和R. C. Eberhart等开发的一种新的进化算法(Evolutionary Algorithm – EA)。PSO 算法属于进化算法的一种,和模拟退火算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。

     二、通俗理解:

  我们设想有这样一个场景:一群小鸟在随机的寻找食物,而且在这个特定的区域中只有一块食物,他们并不知道食物的具体位置,只知道和食物的距离,他们想要找到食物,最优的策略或者说最节省体能的寻找到食物的方法是啥?鸟群在搜索的时候总能找到最优的方法搜索到食物。

     那么我们可以得到一个类似于如下图这样的思路:也就是粒子群算法的基本思想:

 

 

 那么搜寻食物的最优策略是什么呢?

       1、 搜寻距离食物最近的鸟的的周围区域。

      2、  根据自己记得飞行经验判断食物所在区域。

单独这样讲的话可能我们还是不能从中抽象出近点的粒子群算法公式:那么应用一个故事来讲解:

     故事讲解

        鸟妈妈有7个鸟宝宝,有一天,鸟妈妈让鸟宝宝们自己去找虫子吃。于是鸟宝宝们开始了大范围的捕食行为。一开始鸟宝宝们不知道哪里可以找得到虫子,于是每个鸟宝宝都朝着不同的方向独自寻找。

 

  但是为了能够更快的找到虫子吃,鸟宝宝们协商好,谁发现了虫子,就互相说一声。

 

  找了一会,终于有一个鸟宝宝(称之为小蓝),似乎发现在他附近不远处有虫子的踪迹。于是它传话给其他鸟宝宝,其他鸟宝宝,收到消息后,边开始改变轨迹,飞到小蓝这边。最终,随着小蓝越来越接近虫子。其他虫宝宝也差不多都聚集到了小蓝这边。最终,大家都吃到了虫子。

 

      抽象提取:

       

  鸟宝宝捕食的故事,正是这个粒子群算法存在的原因。因此,如果想更好的了解粒子群算法,我们就要来分析鸟宝宝捕食的故事。首先,我们来分析分析鸟宝宝们的运动状态,即鸟宝宝自身是怎么决定自己的飞翔速度和位置的。

 

  (1) 呐首先,我们知道物体是具有惯性的,鸟宝宝在一开始飞翔的时候,无论它下一次想怎么飞,往哪个方向飞,它都有一个惯性,它必须根据当前的速度和方向来进行下一步的调整。对吧,这个可以理解吧,因此,“惯性”——当前的速度vcurrentvcurrent是一个因素。

 

  (2) 其次,由于鸟宝宝长期捕食,因此鸟宝宝有经验,它虽然不知道具体哪里是有虫子的存在,但是它能大概知道虫子分布在哪里。比如当鸟宝宝飞到贫瘠的地方,它肯定知道这里是不会有虫子的,因此,在鸟宝宝的心中,它每次飞,都会根据自己的经验来找,比如以往虫子分布的地区,它肯定优先对这部分的地方进行搜索。因此,自己的“认知”——经验,也是一个因素。

 

  (3) 最后,每个鸟宝宝发现自己离虫子更接近的时候,便会发出信号给同伴,在遇到这样的信号,其余还在找的鸟宝宝们就会想着,同伴的位置更接近虫子,我要往它那边过去看看。我们称之为“社会共享”,这也是鸟宝宝在移动时考虑的一个因素。

 

  综上所述,鸟宝宝每次在决定下一步移动的速度和方向时,脑子里是由这三个因素影响的。我们想,如果能够用一条公式来描述着三个因素的影响的话,那不就能写出每个鸟宝宝的移动方向和速度么。但是,每一个鸟宝宝,对这三个因素的考虑都是不一致的,比如对于捕食经验不高的鸟宝宝,移动的时候会更看重同伴分享的信息,而对于捕食经验高的鸟宝宝,则更看重自己的经验。因此,我们的公式,在“认知”和“社会共享”这部分,是具有随机性的。

抽象为数学公式

           粒子群的算法可以这样解释和理解:

         (1)每一个小鸟都是我们中的一个解,也就是我们把每一个小鸟当成一个“粒子”,而我们的小鸟索要寻找到的虫子,也就是食物就是我们的最优解总结起来就是一句话,小鸟寻找事物的过程就是所有粒子在解空间内寻找到最优解的过程

         (2)每一个粒子都是由一个 fitness function 来确定fitness value,依此来确定位置的好坏。

      (3)每一个粒子都有记忆功能,记忆了自己所搜寻过的最好位置位置。

         (4)每一个粒子都有一个速度以及决定飞行的距离和方向,这个根据它本身的飞行经验和同伴共享的信息所决定。

    

                   现在,在d维空间中,有n个粒子。其中:

 粒子i的位置:Xi=(xi1,xi2,,xid)                  

 粒子i的速度:Vi=(vi1,vi2,⋅⋅⋅,vid)

 粒子i所搜寻到的最好的位置(personal best):

 Pbestid=(pbesti1,pbesti2,,pbestid)Pbestid=(pbesti1,pbesti2,⋅⋅⋅,pbestid)

 种群所经历的最好的位置(global best):

 Gbestd=(gbest1,gbest2,,gbestd)Gbestd=(gbest1,gbest2,⋅⋅⋅,gbestd)

  另外,我们要给我们的粒子速度和位置做一个限制,毕竟我们不希望鸟宝宝的速度过快或者以及飞出我们要搜寻的范围。因此对于每个粒子i,有:Xi[Xmin,Xmax]

根据前面的分析,我们可以写出下面两条公式:

 

  • 在d维空间中,粒子i的速度更新公式为:

 Vki=wVk1i+c1rand()(PbestiXk1i)+c2Rand()(GbestiXk1i)Vik=wVik−1+c1rand()(Pbesti−Xik−1)+c2Rand()(Gbesti−Xik−1)

  • 在d维空间中,粒子i的位置更新公式为:

Xki=Xk1id+Vk1iXik=Xidk−1+Vik−1

   在上式中,上标k-1和k表示粒子从k-1次飞行操作到下一次飞行操作的过程。

  (1) 我们先来看看速度更新公式,可以看出包含三部分,分别是我们前面分析的“惯性”、“认知”、“社会共享”这三大块。而rand()和Rand()分别给认知”和“社会共享提供随机性,即每个粒子对这两部分的看重是不一样的。其中c_{1}和c_{2}是我们自己加的,表示我们自己对这两部分的分量的控制。另外w是一个惯性的权重,是用于调节对解空间的搜索范围。关于这个w的出现还有一段历史,大家感兴趣的可以去查查论文,这里就不细讲了。

  (2) 接着是位置更新公式,这部分很简单,我们都知道x=x0+vtx=x0+vt。可是这里为什么少了个tt呢,这里我们可以简单理解为从k-1次飞行到下一次飞行,耗费了一个单位时间tt,因此就没有tt出现了。

 代码步骤:

     (1) Initial:

  初始化粒子群体(群体规模为n),每个粒子的信息包括随机位置和随机速度。

  (2) Evaluation

  根据fitness function,算出每个粒子的fitness value。

  (3) Find the Pbest

  对于每个粒子,将其当前的fitness value与历史最佳的位置(Pbest)所对应的fitness value做比较。若当前的fitness value更高,则将当前的位置更新Pbest。

  (4) Find the Gbest

  对于每个粒子,将其当前的fitness value与群体历史最佳的位置(Gbest)所对应的fitness value做比较。若当前的fitness value更高,则将当前的位置更新Gbest。

  (5) Update the Velocity and Position:

  根据公式更新每个粒子的速度和位置

  (6) 如果未找到最佳值,则返回步骤2。(若达到了最佳迭代数量或者最佳fitness value的增量小于给定的阈值,则停止算法)

 

 

 

     

       

 

 

       

 

发表于
2019-09-17 23:35 
柯西恒等式 
阅读(400
评论(0
编辑 
收藏 
举报

 

版权声明:本文为lgy-gdeu原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/lgy-gdeu/p/11495090.html

数学建模4之粒子群算法 - 柯西恒等式的更多相关文章

  1. Google浏览器的所有版本下载 – luziluck

    Google浏览器的所有版本下载 Google浏览器有很多版本,比如说:stable(稳定版),beta(测试 […]...

  2. 判断程序是否运行在管理员权限下 – C Pointer

    判断程序是否运行在管理员权限下 1.提出两个概念(成立条件是系统是Vista后续版本,这是因为引入了UAC) […]...

  3. 以虎嗅网4W+文章的文本挖掘为例,展现数据分析的一整套流程 – 洛洛罗

    以虎嗅网4W+文章的文本挖掘为例,展现数据分析的一整套流程 本文转自知乎 作者:苏格兰折耳喵 ———————— […]...

  4. [微信平台智能问答] – 关于微信平台智能问答

    君网工作室 junteam 将开发智能问答,设计后台逻辑 将编程疑难以提问回答的方式输入到数据库  ...

  5. JaveWeb开发使用工具套装(较好的一整套开发工具简介) – EastChilde

    JaveWeb开发使用工具套装(较好的一整套开发工具简介) 工具介绍,仅java开发后台工具,前后端开发分离时 […]...

  6. 60个中国优秀电子技术网站 – 《花样男子》

    60个中国优秀电子技术网站 以下是一位高级电子工程师归纳总结的60个电子行业技术网站,电子工程师必备网站.   […]...

  7. 看完给跪了:技术大牛总结的Github与华为软件开发云完整对比 – 老鱼大哥

    看完给跪了:技术大牛总结的Github与华为软件开发云完整对比 2017-08-09 12:00  老鱼大哥  […]...

  8. 联想笔记本如何安装内存条——附安装结果检查方法及问题解决方法(专用) – Lukea

    联想笔记本如何安装内存条——附安装结果检查方法及问题解决方法(专用) 在现在,大家普遍想让自己的电脑运行的更流 […]...

随机推荐

  1. java初学者Win 10下eclipse的安装教程(超级详细)

    安装的前准备 首先查看电脑的位数 方法: 1.同时按Win键+R键,在打开的运行窗口中输入“dxdiag”,并 […]...

  2. java类对象的初始化顺序

    在下面这个例子中,我们分别在父类和子类中测试了静态代码块、普通代码块、静态成员变量、普通成员变量、构造器、静态 […]...

  3. 对开发人员有用的定律、理论、原则和模式

        这篇文章包含对一些定律、原则以及模式的解释,但不提倡其中任何一个。它们的应用始终存在着争论,并且很大程 […]...

  4. 算法 & 数据结构——任意多边形填充

    需求 .  在计算机中,选区是一个很常见的功能,例如windows按住鼠标左键拖动划出矩形选区,Photsho […]...

  5. matplotlib 在线绘图教程

    转自https://freeaihub.com/article/plot-online-with-matplo […]...

  6. Linux系统中的tar命令

      时间一长什么东西都容易忘记,尤其是一些不常用的东西忘记的更快,所以避免忘记,就记录下来,可以方面使用的时候 […]...

  7. Java监控工具、调优、调试辅助函数 – zhenjing

    Java监控工具、调优、调试辅助函数 2013-02-18 13:42  zhenjing  阅读(23327 […]...

  8. 使Excel中单元格内英文为Arial Narrow 中文为宋体显示打印

    因为在对数据表进行排版格式整理的时候,发现Arial Narrow字体是不支持中文的,所以中文默认为宋体,但是 […]...

展开目录

目录导航