粒子群最適化のソースを表示

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

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

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

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

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

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

== 関連項目 ==
<!-- * [[RPSO|Repulsive particle swarm optimization]] 訳語不明 -->
* [[蟻コロニー最適化]]
* [[群知能]]
* [[最適化問題]]

==外部リンク==
いずれも英文
*[http://www.particleswarm.info Particle Swarm Central]
*[http://jswarm-pso.sourceforge.net JSwarm-PSO 粒子群最適化パッケージ]
*[http://www.adaptiveview.com/articles/ipsoprnt.html Simple introduction to PSO with link to Java source code]
*[http://www.adaptivebox.net/research/bookmark/psocodes_link.html PSOのソースコードへのリンク集]
*[http://cilib.sourceforge.net CILib] - GPL化された[[計算知能]]シミュレーションおよび研究環境。Javaで書かれていて、PSOの実装例も多く含む。
*{{Wayback|url=http://www.scholarpedia.org/article/Particle_swarm_optimization |title=Particle swarm optimization |date=20070107115127}} - [[スカラーペディア]]百科事典「粒子群最適化」の項目。

{{DEFAULTSORT:りゆうしくんさいてきか}}
[[Category:メタヒューリスティクス]]
[[Category:進化的アルゴリズム]]
[[Category:数学に関する記事]]