粒子群优化算法简介
来源:用户上传
作者:
摘要:介绍了基本PSO算法以及两种典型的改进算法:1) 全局邻域模式和局部邻域模式对粒子群优化算法的影响,全局邻域模式粒子群优化算法收敛快,但容易陷入局部极小值;局部邻域模式粒子群优化算法由于粒子倾向于在不同的局部区域搜索因而收敛速度慢,但能在较大程度上避开局部极小值; 2) 混沌粒子群优化算法,它具有混沌的随机性、遍历性、规律性等特性引导粒子及其组成的群落搜索全局最优解。
关键词:粒子群算法;领域模式;混沌;优化算法; 群智能
中图分类号:TP311 文献标识码:A文章编号:1009-3044(2010)21-6096-02
The Introduction of Particle Swarm Optimization
JIA Na, YE Er-lan
(Xinjiang Education Institute, Urumqi 830043, China)
Abstract: Describes the basic PSO algorithm and improved algorithm for some typical: 1) Describes the overall neighborhood and local neighborhood model the impact of PSO. the experiment PSO of overall neighborhood disappears fast, but apt to fall into some minimum;Because the particle inclines to search for and disappear slowly in different some areas among some neighborhood mode PSO, but can be avoiding some minimum than the great degree; 2) Describes chao PSO, Method this utilize randomness of Chaos,lead particle and community that make up search for the overall situation to be optimum to solve all over calendar, regularity characteristic.
Key words: particle swarm optimization; neighborhood model; chaos; optimization algorithm; swarm intelligence
目前通过模拟生物群体的行为来解决计算问题已经成为新的研究热点。美国的Eherhart博士和kennedy博士受鸟群觅食行为的启发与1995提出了粒子群优化(Particle Swarm Optimization, PSO)算法,。PSO通过鸟群的捕食模型得到启示并用于解决优化问题。PSO中,每个优化问题的解,都是搜索空间中的一只鸟,我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value),每个粒子还有一个速度决定他们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索。
由于认识到PSO在函数优化等领域所蕴涵的广阔的应用前景,目前已提出了多种PSO改进算法,并且广泛应用于函数优化,神经网络训练,模式分类等应用领域。本文将介绍基本PSO算法以及几种典型的改进算法。
1 粒子群算法
PSO是群智算法中的一种,PSO中,每个优化问题的解都是搜索空间中一个“粒子”的状态。所有的粒子都有一个适应函数(fitness function)决定的适应值(fitness value),每个粒子还有一个速度直接影响它们飞翔的距离。粒子根据当前自身情况和粒子群的情况在解空间中搜索。PSO初始化时,将一群粒子的状态赋随机值(随机解),然后根据公式(1)和(2)来更新自己的速度和新的位置。
(1)
(2)
其中vid是粒子的速度,c1, c2是学习因子,Rand()是介于(0,1)之间的随机数,xid是粒子当前位置,pid是粒子当前极值,pgd是粒子群当前极值,在公式(1),等式右边共有三项,第一项是粒子上一次的速度vid与惯性因子w的乘积,惯性因子即是粒子上一次的速度对本次飞行速度的影响因子,Shi[1]研究了惯性因子w对优化性能的影响,发现较大的w值有利于跳出局部极小点,而较小的w值有利于算法收敛;第二项是粒子自身行为差异比较;第三项是粒子群体行为差异比较;后两项合称为粒子的“意识”部分。
图1是PSO迭代曲线示例,其实验参数分别为:粒子个数是20;w=0.9;维度为10;适应函数为;粒子群最佳适应值变化曲线为左下方的红色虚线;平均适应值变化曲线为右边的蓝色实线;迭代次数为400。从图1中可以看出粒子群最佳适应值在不断减小,平均适应值有起有落表明在不断快速跳出局部极小值最终到达全局极小值。
2 邻域粒子群优化算法
粒子群算法中的每个粒子的每一次迭代,速度的更新由三个因素决定即在(1)中等式右边的三项:粒子上一次的速度vid与惯性因子w的乘积,粒子自身的认知部分,粒子群体意识部分。由于视野和视力范围的限制,实际觅食鸟群中的个体并不一定拥有全局“意识”而是观察周围飞鸟的位置和速度情况。在全局模式中,每个粒子的轨迹受例子群中所有粒子的所有的经验和意识的影响。在局部模式中,粒子的轨迹只受自身的认知和最邻近的粒子状况的影响。观察实际的飞鸟觅食过程,往往只是看到相邻的飞鸟的位置和动向,就这一点而言,局部模式更接近粒子群算法的生态本质。
3 混沌粒子群算法
3.1 混沌理论
1972年12月29日,美国麻省理工学院教授、混沌学开创人之一E.N.洛伦兹[1]在美国科学发展学会上提出一个貌似荒谬的论断:在巴西一只蝴蝶翅膀的拍打能在美国得克萨斯州产生一个陆龙卷,并由此提出了天气的不可准确预报性。混沌是一种普遍的非线性现象,其行为复杂且类似随机,但存在精致的内在规律性。混沌具有其独特的性质:随机性、遍历性、规律性。
3.2 混沌粒子群算法
针对粒子群算法中存在粒子的位置和速度初始赋值具有随机性,不宜有遍历性的弱点,产生了混沌粒子群优化算法,该算法利用混沌确定性与随机性的统一、对初始值敏感性和混沌的遍历性特点,引导粒子群中的粒子搜索。混沌PSO基本思想就是用类似载波的方法将混沌状态引入到优化变量(在粒子群算法中用粒子的维度表示)中,并把混沌运动的遍历范围由[0,1]区间“放大”到优化变量的取值范围,然后利用混沌变量进行搜索,具体表现在群体的混沌初始化和最优个体的混沌变尺度载波。
4 结论
本文介绍了基本PSO算法以及两种典型的改进算法,基于这两种方法,可以有效避免粒子搜索过程中容易发生的早熟,甚至是停滞,提高了粒子的搜索效率,改善了粒子群优化的性能。
参考文献:
[1] R. C. Eberhart, Y. Shi. Comparison between genetic algorithms and particle swarm optimization[M].Proceedings of 7th annual conference on evolutionary computation,1998,611-616.
[2] J.Kennedy, R. Eberhart. Swarm Intelligence. Morgan Kaufmann Publishers[J].Inc,San Francisco,CA,2001.
[3] R. C. Eberhart, Y. Shi. Comparison between genetic algorithms and particle swarm optimization. Proceedings of 7th annual conference on evolutionary computation,1998:611-616.
[4] V. Ferrari, T. Tuytelaars, and L. Van Gool .Markerless Augmented Reality with a Real-Time Affine Region Tracker[J] Proc. IEEE and ACM Int'l Symp. Augmented Reality, pp. 87-96, 2001.
[5] E. S. Peer, F. van den Bergh, A. P. Engelbrecht, Using Neighborhoods with the guaranteed Convergence PSO[J].Proceed of IEEE conference on Evolutionary Computation, 2003, 235-2.
[6] F. van den Bergh. An analysis of particle swarm optimizers. PhD thesis, University of Pretoria[J].South Africa,2002.
转载注明来源:https://www.xzbu.com/8/view-8701456.htm
