吉林大学学报工学版
主办单位:中华人民共和国教育部
国际刊号:1671-5497
国内刊号:22-1341/T
学术数据库优秀期刊 《中文科技期刊数据库》来源期刊
       首 页   |   期刊介绍   |   新闻公告   |   征稿要求   |   期刊订阅   |   留言板   |   联系我们   
  本站业务
  在线期刊
      最新录用
      期刊简明目录
      本刊论文精选
      过刊浏览
      论文下载排行
      论文点击排行
      
 

访问统计

访问总数:11867 人次
 
    本刊论文
原始粒子群算法的基本原理

  摘要:随着决策环境的复杂化,群体决策变得越来越重要,在此基础上研究粒子群优化算法,详细介绍其基本原理并进行分析显得十分重要。


  关键词:粒子群优化算法 种群大小 最大速度1.1优化算法的分类随着现代科学技术的飞速发展,目前解决优化问题的方法主要分为两大类:一是模拟自然进化过程而发展起来的进化算法,目前研究的进化算法主要有三种典型的类别:遗传算法,进化规划和进化策略,这三种算法是彼此独立发展起来的;二是基于群智能的智能优化算法,目前主要有粒子群算法和蚁群算法两大类。


  1.2粒子群算法的基本模型粒子群优化算法是兼有进化计算和群智能特点的一种优化算法,起初只是设想模拟鸟类捕食的过程,但后来发现粒子群算法是一种很好的优化工具。与其他的进化算法相类似,PSO进化算法也是通过个体间的协作与竞争来实现最优解的搜索。


  PSO算法为每个粒子制定了类似于鸟类运动的简单的行为规则,从而使粒子群的运动表现出与鸟类觅食相类似的特性,进而用于求解复杂的优化问题。


  PSO算法中的每一个粒子,即解空间中的一个解,它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行,所有的粒子都有一个被优化的函数决定的适应值,适应值用来评价粒子当前位置的好坏;每个粒子还有一个速度决定他们的飞行方向和距离,然后粒子们就追寻当前的最优粒子在解空间中进行搜寻。每个粒子在飞行过程中所经历过的最好位置,就是粒子本身找到的最优解;整个种群所经历过的最优位置,就是整个种群目前为止找到的最优解。前者叫做个体极值,后者叫做全局极值。每个粒子都通过上述两个极值不断的更新自己的位置和速度,从而产生新一代群体。


  从以上分析可以看出在用粒子群算法解决问题的时候,我们首先要弄清楚什么是“鸟”,有了对象,然后才能确定该对象所谓的“位置”和“速度”是代表什么意思,粒子群算法的核心就是适应度函数的确定,不同的问题有不同的适应度函数,我们通过适应度函数来评价粒子当前的位置是好是坏,适应度函数体现了当前位置与最优位置的关系,即鸟类捕食模型中“鸟”和“食物”之间的距离所代表的含义,我们通过它来确定当前位置与最优位置之间的差距,然后通过分析适应度函数的指标,确定与最优解的接近程度。


  1.3粒子群算法中参数的设置及其影响粒子通过“跟踪”个体极值和全局极值来更新自己,按照如下公式来完成自己的速度和位置的进化:


  在上述公式中:


  t:迭代次数。


  Vi(t):第t次迭代时粒子的速度。


  Xi(t):第t次迭代是粒子的位置。


  Pi:粒子本身的个体极值。


  Pg:种群的全局极值。


  c1和c2被称为加速因子,又叫学习因子,一般取c1=c2=2。


  rand( )和rand2( )是(0,1)之间的随机函数。


  算法的参数是影响算法性能和效率的关键,如何确定最优参数使算法性能最佳本身就是一个极其复杂的过程,由于参数空间的大小不同,且各参数之间具有相关性,在实际的应用当中,并无确定最优参数的通用方法,只能通过用户的经验选取,不同的参数对算法性能的影响有一定的规律可循,由于粒子群算法简单,易实现,且没有许多参数需要调整,这几个优点是它倍受研究者青睐的原因下面介绍一下不同的参数的设置及其对算法性能的影响。


  粒子数(种群的大小):一般取20-40其实对于大部分问题10个粒子已经足够可以取的好的结果。


  粒子的长度:这是由优化问题决定的,就是问题解的长度。


  粒子的范围:由优化问题决定,每一维可以设定不同的范围。


  Vmax:最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度。


  终止条件:最大迭代次数Tmax,计算精度,最大凝滞步数通常为粒子群算法的终止条件,在设置时需要根据遇到的具体情况,兼顾算法的搜索效率和优化质量等多方面的性能。


  1.3.1加速因子的影响加速因子c1和c2代表了粒子向自身极值pbest和全局极值gbest推进的随机加速权值。小的加速因子值,可使粒子在远离目标去区域内振荡;大的加速因子可使粒子迅速的向目标区域靠近,甚至又远离目标区域。


  1.3.2最大速度的影响最大速度是为了对粒子的运动进行适当的限制而设置的参数,粒子的速度在(-Vmax,Vmax)之间。因此,最大速度的设置也要兼顾算法搜索的性能和效率,做到全局和局部寻优能力的均衡。


  1.3.3种群大小的影响从给定精度下所需迭代次数的平均值上看PSO 对种群的大小不敏感,但当粒子数小于50时,可发现种群大小对PSO的性能还是有较大影响的。从计算复杂度上分析,种群粒子数多时,将需要更多的函数评价,从而增加算法的计算时间,但同时也增加算法的可靠性,所以,在选择粒子群大小时,应综合考虑算法的可靠性和计算时间,对通常问题10个粒子已经足够,对于较复杂的问题可取粒子数为50。


  1.4原始粒子群算法的优点及不足原始粒子群算法是1995年两位外国科学工作者根据鸟类捕食行为所研究出的最初的粒子群算法模型,它简单易懂,清楚的揭示了粒子群算法的本质,它的一大优势是采用实数编码不需要向遗传算法那样采用二进制编码,寻优的过程是一个迭代的过程,且没有许多参数需要调节。


  但是它在收敛速度和跳出局部最优的能力上还有待提高,当粒子当前位置既是其个体最优位置,又是其全局最优位置时,其下一次迭代的位置仅与当前的速度有关,也就是说其当前的速度的大小对其寻优能力有着重要的影响,可见原始粒子群算法在这方面的能力还有明显的不足,参数的设置对粒子群算法的性能有着在重要的作用。可见改进粒子群算法势在必行。


  1.5本章小结本章首先介绍了优化算法的分类,指出了两种优化算法下几个不同的优化技术,指出PSO算法是对群智能现象的一种仿真。然后以鸟类捕食模型为例,系统阐述了原始粒子群算法的基本原理对原始粒子群算法进行了评价,并指出了改进粒子群算法的必要性。


  参考文献[1]李元左。广义判断下的群决策方法[J].系统工程,2002,18(2):76-80.


  [2]李爱国,覃征,鲍复民等。粒子群优化算法[J].计算机工程与应用,2002,38(21):1-3.


  [3]李艳玲,李刚。粒子群优化算法研究进展[N].重庆工学院学报,2007.


特别说明:本站仅协助已授权的杂志社进行在线杂志订阅,非《吉林大学学报工学版》杂志官网,直投的朋友请联系杂志社。

版权所有 © 2009-2021《吉林大学学报工学版》编辑部  (权威发表网)   苏ICP备12048821号-1   --