粒子群最適化(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)