嵌入局部一维搜索技术的混合粒子群优化算法

减小字体 增大字体 作者:龙 文 梁昔明 董淑华 阎 纲  来源:www.zhonghualunwen.com  发布时间:2009-10-12 23:26:31

  粒子群优化算法(PSO)是由Kennedy等人[1] 于1995年提出的一种模拟鸟类捕食行为的全局优化算法。其主要优点是算法不依赖于问题的信息、通用性强;前期收敛速度快、设置参数少、算法简单、容易实现;群体搜索并具有记忆能力,能够保留局部个体和全局种群的最优信息,还可利用个体和群体信息指导算法的下一步搜索,能够有效地解决复杂优化问题。在函数优化、模式识别、机器人学习、组合优化以及一些工程领域都得到了广泛的应用[2~4]。
  在科学研究和工程实践中,许多实际问题最终都可归结为求解函数的优化问题。然而目前已有的数值方法均基于局部搜索技术[5,6],能在较少次数迭代后快速收敛到问题的局部最优解,但当问题存在多个局部最优解时,这类方法很难获得其全局解;基于进化机制的全局优化算法[7,8],能收敛到问题的全局解,但是存在收敛速度慢、解精度不高的缺点。目前一些改进的混合算法研究得比较多,都是利用两种或多种算法的优点结合来提高算法的性能。局部一维搜索算法往往只需很少的迭代次数,具有局部搜索能力强和收敛速度快的优点,能保证迭代后的适应度值比迭代前的适应度值好。因此,合理融合局部搜索技术和进化机制的全局混合优化算法成为解决复杂优化问题的有效方法。鉴于目前对协同局部一维搜索的混合优化技术研究得较少,本文将局部一维搜索技术与标准粒子群算法结合起来,提出一种嵌入局部一维搜索技术的混合粒子群优化算法。
  
  1 混合粒子群优化算法
  
  1.1 标准粒子群优化算法
  假设用Xi=(xi1,xi2,…,xiD)T表示第i个粒子。其中D是粒子的维数。经历的最好位置表示为Pi=(pi1,pi2,…,piD)T,而整个群体经历的最好位置表示为Pg=(pg1,pg2,…,pgD)T,粒子i的速度为Vi=(vi1,vi2,…,viD)T。按追随当前最优粒子的原理,粒子i将按式(1)和(2)改变速度和位置,即
  vn+1id=wvnid+c1rand()(pnid-xnid)+c2rand()(pngd-xngd)(1)
  xn+1id=xnid+vn+1id(2)
  其中:n为当前的进化代数;c1、c2为学习因子;rand()为分布于(0,1)的随机数;w为惯性权重。研究表明,较大的w值有利于跳出局部极值点;较小的w值有利于算法的收敛和提高解的精度,惯性权重w起到平衡全局搜索和局部搜索能力的作用。
  标准粒子群优化算法的流程如下:
  a)随机初始化粒子的位置和速度。
  b)计算粒子的适应度值,将粒子的pi设置为当前位置;pg设置为初始群体的最佳粒子的位置。
  c)对所有粒子按式(1)(2)更新位置和速度,并计算粒子的适应度值。
  d)判断算法停止准则是否满足,如果满足,则结束;否则,转向b)。
  1.2 局部一维搜索算法
  一维搜索是从某个点出发,沿某个方向寻找函数最优点的方法,它是加快最优化方法收敛的一个基本和有效的技术。若在点x处沿适当的方向进行一维搜索,可得出比x更好的点。本文利用基于Wolfe-Powell不精确一维搜索产生步长的算法来加快算法的收敛。无约束优化问题可表示为min f(x),x∈Rn。求解上述问题的一维搜索算法可表示如下:
  a)选取初始点xk∈Rn,令k=1。
  b)计算f(xk),若f(xk)=0,则停止;否则,确定搜索方向dk,使得f(xk)Tdk<0,计算步长因子λk>0满足搜索准则。
  c)令xk+1=xk+λkdk,k=k+1,转b)。
  步骤b)中的步长因子λk要满足由Wolfe等人提出的不精确一维搜索准则,即Wolfe-Powell准则[9]:
  (λk)≤(0)+ρλkgTkdk(3)
  |gTk+1dk|≤-σgTkdk(4)
     其中:0<ρ<0.5,gk=f(xk),dk是搜索方向,λk是步长因子,σ∈(ρ,1)。结合式(3)和(4)即是著名的Wolfe-Powell准则,它具有良好的收敛性质和不错的数值表现,能够保证目标函数在每一步迭代以后产生一充分的下降,所以在许多数值计算和工程中被广泛应用。
  1.3 嵌入局部一维搜索的混合粒子群优化算法
  1.3.1 算法思路
  粒子群优化算法具有较强的全局搜索能力,但其局部搜索能力较弱。由于粒子初始化和演化过程的随机性,并不能完全保证迭代后的下一代粒子的适应度值一定比迭代前的上代粒子好。也就是说,粒子不一定沿着最优的方向进行迭代,从而影响了算法的收敛性能。局部一维搜索算法是一种以梯度信息确定搜索方向的算法,它能够保证每次迭代以后的目标函数值都有充分的下降,向着目标函数值下降的方向进行迭代,因此一般只需较少次数的迭代过程即可获得问题的局部最优解。
  基于以上的分析,本文充分利用两种搜索算法的优点,在粒子群算法中合理融入局部一维搜索算法来改善其性能。其思路是:在每一次粒子群算法迭代以后,每个粒子都有对应的适应度值,将所有粒子的适应度值进行排序,将粒子按照适应度值的优劣分为精英粒子和普通粒子,数量分别为n1和n2且n1+n2=n,即适应度值最好的n1个粒子为精英粒子,其余的粒子则为普通粒子。两类粒子采取不同的进化方式,即每轮迭代中,精英粒子采用局部一维搜索,在这里不采取随机选择粒子进行局部一维搜索,因为随机选取粒子的方法有时无法提高整体性能并且可能白白耗费运行时间,使得要花费很长时间才能收敛到最优点。对各个精英粒子直接进行一次以其梯度信息确定搜索方向的Wolfe-Powell一维搜索,搜索以后得到的后代粒子,保证其适应度值比上一代更优。如果一维搜索后粒子的适应度值优化不明显,则不必要进行一维搜索,否则可能计算量增大,而算法性能又得不到改善。没有参与一维Wolfe-Powell搜索的其他粒子则进行一次基本粒子群算法迭代,能够很好地保持粒子群优化算法的优点。随着迭代的进行,两类粒子之间相互转换,共同演化,增强混合算法的优化性能。

[1] [2] [3]  下一页

Tags:

作者:龙 文 梁昔明 董淑华 阎 纲
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论