粒子群算法小记

又是小半年没写博客,期末考试考完之后,我曾经的面向对象设计课老师希望我能参加到学校的大数据实验室,来做一些科研方面的入门,我当然非常开心地接受了。老师跟我说比起做科研,首先要认识科研和工程的不同意义。科研是偏理论的一个方向,我认为科研成果是工程实践的基础,是一种理论支撑。目前学术方面的研究可能不受重视,国内这方面也是比较欠缺的,没有学术成果,大概没法创新吧。

实验室里,目前研究的方向是群智能。通俗来讲,大概是用真实世界中社会群体的活动规律,来进行数据的聚类。我觉得在算法上用到仿生学真的是一件非常神奇的事情了。

算法这么难的东西,我觉得总得做做笔记,记录一下自己的进展,否则一个假期过去怕是学的东西都被吃掉了。

那么,啥是粒子群算法(PSO)?

粒子群优化算法是由J. Kennedy和R. C. Eberhart等人于1995年提出的一种基于种群搜索的自适应进化计算技术。PSO算法实现容易、参数较少,能有效解决复杂优化任务,在过去几年中得到了飞速发展,并在图像处理、模式识别、优化等领域得到了广泛应用。

粒子群算法通过模拟鸟类在自然界中的捕食行为,抽象出点在三维坐标系中点运动的过程和趋势,并推广至N维来解决实际问题。针对问题的建模,就对应了N维空间的N个变量。基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。

试着想一下——一群鸟在寻找食物,在这个区域中只有一只虫子,所有的鸟都不知道食物在哪。但是它们知道自己的当前位置距离食物有多远,同时它们知道离食物最近的鸟的位置。想一下这时候会发生什么?

1.当一只鸟距离食物最近时,其他的鸟便会向这只鸟靠拢。(显而易见,这样可以快一点找到食物在哪里。)

2.同时各只鸟在位置不停变化时候离食物的距离也不断变化,所以一定有过离食物最近的位置,这也是它们的一个参考。

综上,影响鸟的运动状态变化有下面三个因素:

1.离食物最近的鸟的位置;

2.自己之前达到过的离食物最近的位置;

3.鸟在移动的过程中自身带有的惯性。

所以考虑这三个因素,粒子群算法的速度和位置公式如下:

其中:v为粒子运行的矢量速度,x为粒子的位置坐标;c1和c2为加速常数,用来平衡局部优势和全局优势;rand()是从0~1之间的一个随机值;pbest是个体粒子的历史最优位置,gbest是全局的历史最优位置。每个粒子的位置和速度都以随机方式进行初始化,而后粒子的速度就朝着全局最优和个体最优的方向靠近。

第一次看到这里,我是懵逼的。公式是什么玩意?怎么理解?

我们为了好理解,不妨把点简单地放到二位坐标系中,那么单独的一个粒子,他的运动趋势关系如图所示:

从整体上考虑,每个粒子都遵守上面的运动趋势,那么整体将越来越接近最优解:

粒子群算法流程

了解了粒子群算法的思想和概念,下面是算法的程序流程图:

1.初始化一群微粒,包括随机位置和速度;

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

3.对每个微粒,将其适应值与其经过的最好位置pbest作比较,如果较好,则将其作为pbest;

4.对每个微粒,将其适应值与其经过的最好位置 gbest作比较,如果较好,则将其作为gbest;

5.根据公式更新粒子速度和位置;

6.如果未达到结束条件则转第2步。

(迭代终止条件根据具体问题一般选为最大迭代次数或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值。)

参数不同的取值对算法的影响

在PSO的标准公式中,pbest和gbest分别表示微粒群的局部和全局最优位置。

当C1=0时,则粒子没有了个体认知能力,变为只有社会的模型,被称为全局PSO算法。粒子有扩展搜索空间的能力,具有较快的收敛速度,但由于缺少局部搜索,对于复杂问题比标准PSO 更易陷入局部最优

当C2=0时,则粒子之间没有社会信息,模型变为只有认知模型,被称为局部PSO算法。由于个体之间没有信息的交流,整个群体相当于多个粒子进行盲目的随机搜索,收敛速度慢,因而得到最优解的可能性小

后记

针对PSO算法的学习,让我提升了一个新的认识。对于离散数据的处理,可以借助仿生学来提出解决问题的算法。通过这次学习,给我提供了一个解决问题的新思路。

其中还有很多概念,包括欧氏距离、无监督学习、群体智能,这篇文章中并没有表述出来;另外对于PSO算法的若干优化方式,限于篇幅,本文也不再介绍,希望以后有时间再研究写出来。

参考文献

http://blog.csdn.net/myarrow/article/details/51507671

https://www.cnblogs.com/hxsyl/p/4521778.html

https://zh.wikipedia.org/wiki/%E7%B2%92%E5%AD%90%E7%BE%A4%E4%BC%98%E5%8C%96

https://wenku.baidu.com/view/0fdb3dff87c24028905fc321.html

https://www.zhihu.com/question/23103725

0 条评论

昵称

暂无评论,要说点什么吗?