粒子群最適化

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

粒子群最適化(りゅうしぐんさいてきか、Particle Swarm OptimizationPSO)とは、群知能の一種。 昆虫の大群や魚群において、一匹がよさそうな経路を発見すると(すなわち、食料を発見したとか安全であるという場合)、群れの残りはどこにいても素早くそれに倣うことができる。

これは多次元空間において位置と速度を持つ粒子群でモデル化される。これらの粒子はハイパー空間を飛びまわり、最善な位置を探す。位置の評価は適応度関数で行う。群れのメンバーは良い位置について情報交換し、それに基づいて自身の位置と速度を調整する。このコミュニケーションは主に次の二種類の方法でなされる。

  • 最も良い位置にいる粒子が全体に通知される。
  • ローカルなベストの位置にいる粒子が近傍の粒子群に通知される。

位置と速度の更新は以下の式で行われ、これが繰り返される。

  •  x \leftarrow x + v
  •  v \leftarrow wv + c_1 r_1 (\hat{x}-x) + c_2 r_2 (\hat{x}_g-x)
    • w は、慣性定数。多くの場合 1 より若干小さい値が最適である。
    • c_1c_2 は群のうちで良い位置に向かう粒子の割合。1 に近い値が多くの場合最適である。
    • r_1r_2[0, 1] の範囲の値をとる乱数。
    • \hat{x} は、その粒子がこれまでに発見したベストな位置
    • \hat{x}_g は群全体としてこれまでに発見したベストな位置。これをローカルなベスト \hat{x}_l にすれば、上記の後者の方法(近傍への通知)になる。

アルゴリズム[編集]

  • 各粒子について xv をランダムに初期化。値の範囲は問題の設定に依存する。
  • \hat{x} を現在位置に初期化。
  • \hat{x}_g を群全体で最も良い適応度を持つ粒子の位置に初期化。
  • \hat{x}_g での適応度がしきい値より小さく、かつループ回数が事前に設定した回数に達していないうちは、以下を繰り返し実行する。
    • 各粒子について、以下を実行する。
      • 上述の式に従って x を更新する。
      • 新たな位置での適応度を計算する。
      • \hat{x} での適応度よりも良い値が得られたら、\hat{x} を置き換える。
      • \hat{x}_g での適応度よりも良い値が得られたら、\hat{x}_g を置き換える。
      • 上述の式に従って v を更新する。

関連項目[編集]

外部リンク[編集]

いずれも英文