トップ > シミュレーションとは > 粒子群最適化法

粒子群最適化法(Particle Swarm Optimization:PSO)

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

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

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

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

X_k(t + 1) = X_i(t) + V_i(t + 1)
X_k(t + 1) = X_i(t) + V_i(t + 1)

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

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

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

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