位置と速度の更新 — 知識ノート

PSO の中身はこの 2 本の式に尽きる。

v_{i} \leftarrow w v_{i} + c_{1} r_{1} ⊙ (p_{i} - x_{i}) + c_{2} r_{2} ⊙ (g - x_{i})

x_{i} \leftarrow x_{i} + v_{i}

$r_{1}, r_{2}$ は各成分が $[0,1]$ の一様乱数、 $⊙$ は成分ごとの積。

3 つの項#

項	呼び名	働き
$w v_{i}$	慣性	前の動きを引き継ぐ。行き過ぎと探索の源
$c_{1} r_{1} (p_{i} - x_{i})$	認知項	自分の最良へ引き戻す
$c_{2} r_{2} (g - x_{i})$	社会項	群れの最良へ引き寄せる

認知項だけなら各粒子が独立に探索し、社会項だけなら全員が一点に集まる。両方あることで、群れとしてまとまりつつ広がりも保つ。

慣性重み#

原論文には慣性項が無く、速度が発散しやすかった。 Shi と Eberhart が 1998 年に $w$ を導入して安定させた。 $w$ を反復に応じて 0.9 から 0.4 へ線形に減らす運用が広く使われる。序盤は広く探し、終盤は収束させるという探索と活用の切り替えにあたる。

収縮係数#

Clerc と Kennedy は、更新式を力学系として解析し、発散しない条件から収縮係数 $χ$ を導いた。

v_{i} \leftarrow χ [v_{i} + c_{1} r_{1} (p_{i} - x_{i}) + c_{2} r_{2} (g - x_{i})]

$φ = c_{1} + c_{2} > 4$ のとき $χ = 2 / | 2 - φ - \sqrt{φ^{2} - 4 φ} |$ 。 $φ = 4.1$ なら $χ \approx 0.7298$ で、慣性重み 0.7298・ $c_{1} = c_{2} = 1.4962$ という広く使われる設定と一致する。経験則だった設定に理論的な裏付けを与えた点で重要な結果。

参考文献#

James Kennedy, Russell Eberhart. Particle Swarm Optimization. Proceedings of ICNN'95, 1995. https://doi.org/10.1109/ICNN.1995.488968
Yuhui Shi, Russell Eberhart. A modified particle swarm optimizer. IEEE ICEC, 1998.（慣性重みの導入） https://doi.org/10.1109/ICEC.1998.699146
Maurice Clerc, James Kennedy. The particle swarm — explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation 6(1), 2002.（収縮係数） https://doi.org/10.1109/4235.985692