近傍トポロジー
どの粒子がどの粒子の情報を見るかという結び付き方。 PSO の性能を大きく左右するが、更新式には現れないので見落とされやすい。
代表的な形#
| トポロジー | 結び方 | 性格 |
|---|---|---|
| gBest（完全グラフ） | 全員が全員を見る | 情報が一瞬で伝わる。収束が速く、局所解に落ちやすい |
| lBest（リング） | 隣の 個だけを見る | 情報が輪を伝って少しずつ広がる。遅いが多峰性に強い |
| von Neumann（格子） | 上下左右の 4 個 | リングと完全グラフの中間 |
| star（車輪） | 1 個の中心を全員が見る | 中心が情報を仲介する |
何が起きているのか#
Kennedy と Mendes は多数のトポロジーを系統的に比較し、 結び付きが密なほど収束が速く、疎なほど多峰性の問題に強いという トレードオフを示した。彼らの実験では、全員が繋がった gBest よりも von Neumann 型が総合的に良い結果を出している。
直感的には、情報の伝播速度が探索と活用の 配分を決めていると読める。密なら「見つかった良い解」が即座に全員へ広まり、 全員がそこを活用しはじめる。疎なら各部分集団がしばらく独立に探索を続けられる。
手法選びより先に効くことがある
「PSO が悪かった」という比較結果の一部は、 gBest 型を既定で使ったことによる早すぎる収束が原因である場合がある。 論文を読むときはトポロジーの記述を確認したい。
参考文献#
- James Kennedy, Rui Mendes. Population structure and particle swarm performance. IEEE CEC, 2002. https://doi.org/10.1109/CEC.2002.1004493
- Riccardo Poli, James Kennedy, Tim Blackwell. Particle swarm optimization: An overview. Swarm Intelligence 1(1), 2007. https://doi.org/10.1007/s11721-007-0002-0