Pythonが粒子群アルゴリズムを実現する例


粒子群アルゴリズムは鳥類の餌探しに基づいて開発された最適化アルゴリズムであり、ランダム解から出発し、最適解を反復的に探し、適合度によって解の品質を評価する。

PSOアルゴリズムの検索性能は、粒子群初期化、慣性係数w、最大飛翔速度、加速定数など、その大域探索と局所微細化のバランスに依存する。
PSOアルゴリズムは以下の利点を有する。
問題情報に依存せず、実数を用いて解くと、アルゴリズムの汎用性が高い。
調整が必要なパラメータが少なく、原理が簡単で実現が容易であることが、PSOアルゴリズムの最大の利点である。
共同で検索して、同時に個人の局部情報と群体の大域情報を利用して検索を指導します。
収束速度が速く、アルゴリズムはコンピュータメモリとCPUに対して要求が高くない。
ローカル最適情報をより容易に飛び越える。ターゲット関数に対しては、少なくとも最適値を検索する情報しか提供できません。他のアルゴリズムでは検索方向を判別できない場合、PSOアルゴリズムの粒子は飛越性の特徴があり、検索面での情報不足の障害を越えて、グローバル最適目標値に到達することができます。例えば、Generalized Rosenbrock関数の大域最小値は元の近くにあります。しかし、この関数の大域最適値と到達可能な局所最適値の間の右側の長い山道は、曲面山間部ではほとんど関数最小値までの最適な方向に垂直であり、大域最小値を見つける可能性は極めて小さいです。しかしPSOアルゴリズムはグローバル最適値を完全に見つける可能性がある。
同時に,PSOアルゴリズムの欠点も明らかである。
アルゴリズムは局所的な検索能力が低く、検索精度があまり高くない。
アルゴリズムは大域最適解を検索することを絶対に保証できない。
PSOアルゴリズムの設計の具体的なステップは以下の通りである。
  • は、粒子群(速度と位置)、慣性係数、加速定数、最大反復回数、アルゴリズム終了の最小許容誤差を初期化する。
  • は、各粒子の初期適合値を評価する。
  • は、初期適合値を現在の各粒子の局所最適値とし、各適応値に対応する位置を各粒子の局所最適値がある位置とする。
  • は、最適初期適合値を現在のグローバル最適値とし、最適適応値に対応する位置をグローバル最適値がある位置とする。
  • は、式に従って、各粒子の現在の飛翔速度を更新する。
  • は、各粒子の飛翔速度をリミッティング処理し、設定された最大飛翔速度を超えられないようにする。
  • は、式に従って、各粒子の現在位置を更新する。
  • は、現在の各粒子の適応値が歴史的な局所最適値よりも良いかどうかを比較し、よければ、現在の粒子適合値を粒子の局所最適値とし、その対応する位置を各粒子の局所最適値がある位置とする。
  • は、現在の群においてグローバル最適値を見出し、現在のグローバル最適値に対応する位置を粒子群のグローバル最適値がある位置とする。
  • は、設定された最小誤差または最大反復回数
  • を満たすまで、ステップ(5)〜(9)を繰り返す。
  • は、粒子群のグローバル最適値とその対応する位置、および各粒子の局所最適値とその対応する位置を出力する。
  • 本論文では、10次元のベクトルを解く必要があると仮定し、ここでの適応度関数は簡単な線形誤差求和を採用する。
    
    #       
    #vi+1 = w*vi+c1*r1*(pi-xi)+c2*r2*(pg-xi)        
    #xi+1 = xi + a*vi+1        (  a=1)
    #w = wmax -(wmax-wmin)*iter/Iter       
    #iter       Iter       c1、c2     r1、r2    pi         pg       
    #    wmax=0.9 wmin=0.4   c1=c2=2 Iter       (10,20)     (100,200)
    #       w、c1 c2,                        
    #      ,    、     
    #              10   ,y=[1.7]*10,     f(x)= |x-y| <=0.001    
    
    import numpy as np
    
    swarmsize = 500
    partlen = 10
    wmax,wmin = 0.9,0.4
    c1 = c2 = 2
    Iter = 400
    
    def getwgh(iter):
      w = wmax - (wmax-wmin)*iter/Iter
      return w
    
    def getrange():
      randompv = (np.random.rand()-0.5)*2
      return randompv
    
    def initswarm():
      vswarm,pswarm = np.zeros((swarmsize,partlen)),np.zeros((swarmsize,partlen))
      for i in range(swarmsize):
        for j in range(partlen):
          vswarm[i][j] = getrange()
          pswarm[i][j] = getrange()
      return vswarm,pswarm
    
    def getfitness(pswarm):
      pbest = np.zeros(partlen)
      fitness = np.zeros(swarmsize)
      for i in range(partlen):
        pbest[i] = 1.7
    
      for i in range(swarmsize):
        yloss = pswarm[i] - pbest
        for j in range(partlen):
          fitness[i] += abs(yloss[j])
      return fitness
    
    def getpgfit(fitness,pswarm):
      pgfitness = fitness.min()
      pg = pswarm[fitness.argmin()].copy()
      return pg,pgfitness
    
    vswarm,pswarm = initswarm()
    fitness = getfitness(pswarm)
    pg,pgfit = getpgfit(fitness,pswarm)
    pi,pifit = pswarm.copy(),fitness.copy()
    
    for iter in range(Iter):
      if pgfit <= 0.001:
        break
      #       
      weight = getwgh(iter)
      for i in range(swarmsize):
        for j in range(partlen):
          vswarm[i][j] = weight*vswarm[i][j] + c1*np.random.rand()*(pi[i][j]-pswarm[i][j]) + c2*np.random.rand()*(pg[j]-pswarm[i][j])
          pswarm[i][j] = pswarm[i][j] + vswarm[i][j]
      #     
      fitness = getfitness(pswarm)
      #        
      pg,pgfit = getpgfit(fitness,pswarm)
      #        
      for i in range(swarmsize):
        if fitness[i] < pifit[i]:
          pifit[i] = fitness[i].copy()
          pi[i] = pswarm[i].copy()
    
    for j in range(swarmsize):
      if pifit[j] < pgfit:
        pgfit = pifit[j].copy()
        pg = pi[j].copy()
    print(pg)
    print(pgfit)
    以下の結果はそれぞれ300回と400回の繰り返しの結果である。

    400回の反復が期待されていないが,得られたベクトルは期待される結果に近いことが見られた。
    最後に書く:粒子群アルゴリズムの最も重要なパラメータは慣性重みと学習因子であり、この二つのパラメータに対して新しい最適化粒子群アルゴリズム(IPSO)がある。また、初期化された粒子群の速度と位置範囲の決定には、群の大きさと反復回数の選択が含まれており、これらはすべて「石を触って川を渡る」であり、標準的な答えはない。
    以上がPythonの粒子群アルゴリズムの例の詳細です。Python粒子群アルゴリズムに関する詳細は他の関連記事に注目してください。