粒子群最適化(Particle Swarm Optimization：PSO)法とは、 組み合わせ最適化問題の近似解を求める為のメタヒューリスティク スアルゴリズムの一つです。

代表的なメタヒューリスティクスの例として、進化的戦略 を利用した遺伝的アルゴリズム(genetic algorithm: GA)や、 シミュレーテッドアニーリング(Simulated Annealing：SA) が知られていますが、PSO は、探索空間内において複数の 粒子を用いた探索を行う、群知能の一種です。

粒子は位置情報だけではなく、速度の情報も持ち、粒子の群 れの中の個体の情報を、群全体で共有しながら探索を行います。

反復回数 において、粒子 の位置と速度は以下のように 計算されます。

ここで、、 は反復回数 での粒子の位置と速度であり、 は反復回数 までの粒子 の最良解(personal best)、 は反復回数 までの粒子群全体 での最良解(global best) です。 は前回の速度を維持する大きさをコントロールし慣性の役割 を果たします。この値が1 より大きいと速度は大きくなりすぎ、 小さすぎると局所探索しか行わなくなります。 、 は係数で、 、 は乱数です。

一般に探索アルゴリズムでは、exploration(どれだけ多くの探 索領域を探索できるか) とexploita-tion(ある程度信頼の置け る領域に対して、どれだけ詳しく探索できるか) のバランスを 取る事は非常に重要です。

これらに対して、S-Quattro では準乱数(超一様分布列)を用いて 粒子の初期化を行い、局所解を回避するロジックとして、Mutation を行う機能を追加しています。Mutation では、速度の絶対値が 指定した値よりも小さくなった場合に、速度に対して乱数を振り、 その速度で位置を更新しています。

【参考文献】
雪島正敏，山本晃成 「S3 Simulation Systemの開発3 シミュレーション最適化」
日本オペレーションズ・リサーチ学会 2011年秋季研究発表会アブストラクト集(2011)