粒子群最適化

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

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

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

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

• $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_{1}$ と $c_{2}$ は群のうちで良い位置に向かう粒子の割合。1 に近い値が多くの場合最適である。
  • $r_{1}$ と $r_{2}$ は $[0,1]$ の範囲の値をとる乱数。
  • ${\hat {x}}$ は、その粒子がこれまでに発見したベストな位置
  • ${\hat {x}}_{g}$ は群全体としてこれまでに発見したベストな位置。これをローカルなベスト ${\hat {x}}_{l}$ にすれば、上記の後者の方法（近傍への通知）になる。

アルゴリズム

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

関連項目

• 蟻コロニー最適化
• 群知能
• 最適化問題

外部リンク

いずれも英文

• Particle Swarm Central
• JSwarm-PSO 粒子群最適化パッケージ
• Simple introduction to PSO with link to Java source code
• PSOのソースコードへのリンク集
• CILib - GPL化された計算知能シミュレーションおよび研究環境。Javaで書かれていて、PSOの実装例も多く含む。
• Particle swarm optimization （英語） - スカラーペディア百科事典「粒子群最適化」の項目。