粒子群最適化（PSO）は、人工知能および計算科学における計算手法であり、与えられた品質指標に関して候補解の集団を反復的に改善することで問題を最適化する。これは、粒子と呼ばれる候補解の集団間の相互作用を通じて問題を解決し、各粒子の位置と速度を調整する単純な数式に従って、探索空間内でそれらを移動させる。各粒子の動きは、これまでの自身の既知の最良位置と、その位相的近傍における既知の最良位置によって影響を受ける。近傍には、指定されれば集団全体が含まれる場合もある。より良い位置が見つかるとベクトルが更新され、これにより群れが良い解に向かって移動することが期待される。
PSOはメタヒューリスティックであり、最適化対象の問題についてほとんどまたは全く仮定を置かず、候補解の非常に大きな空間を探索できる。問題の勾配を使用しないため、勾配降下法や準ニュートン法のような古典的手法とは異なり、最適化問題が微分可能であることを必要としない。しかし、PSOのようなメタヒューリスティックは、最適解が必ず見つかることを保証するものではない。
起源と発展
PSOは元々ケネディとエバーハートに帰属され、彼らは当初これを、鳥の群れや魚の学校における生物の移動、あるいは人間集団における態度の進化を様式化して表現した社会的行動のシミュレーションとして意図していた。社会的行動の原理のシミュレーションが、困難な数学的問題を解く能力を持つことが観察された。ケネディとエバーハートの著書は、PSOと群知能の多くの哲学的側面を記述している。PSOの応用に関する広範な調査はポリによって行われ、2017年にはPSOに関する理論的および実験的研究の包括的なレビューがボニャディとミハレヴィチによって発表された。
アルゴリズム
PSOアルゴリズムの基本バリアントは、候補解（粒子と呼ばれる）の連結された集団（群れと呼ばれる）で初期化される。候補解は数値のベクトルであり、探索空間内の点の座標と見なすことができ、反復的に移動する点として粒子と概念化できる。粒子はいくつかの単純な数式に従って探索空間内を移動する。各粒子には接続された近傍があり、その近傍は少数または他の全ての集団メンバーである場合がある。粒子の次の位置は、探索空間における自身のこれまでの最良位置と、粒子の最良近傍のこれまでの最良位置によって確率的に決定される。改善された位置（目的関数でより良い結果を生むもの）が発見されると、粒子のこれまでの最良位置が更新される。このプロセスが繰り返され、それによって満足のいく解が最終的に発見されることが期待されるが、保証はされない。
形式的には、\( f: \mathbb{R}^n \to \mathbb{R} \) を最小化すべきコスト関数とする。この関数は実数のベクトル形式の候補解を引数として受け取り、目的関数値を示す実数を出力として生成する。\( f \) の勾配は未知である。目標は、探索空間内の全ての \( b \) に対して \( f(a) \le f(b) \) となる解 \( a \) を見つけること、すなわち \( a \) が大域的最小値であることである。
\( S \) を群れ内の粒子数とし、各粒子は位置 \( x_i \in \mathbb{R}^n \) と速度 \( v_i \in \mathbb{R}^n \) を持つとする。\( p_i \) を粒子 \( i \) の既知の最良位置、\( g \) を粒子の近傍の既知の最良位置とする。コスト関数を最小化する基本PSOアルゴリズムは以下の通りである：
- 各粒子 \( i = 1, \dots, S \) について：
- 粒子の位置を一様分布のランダムベクトルで初期化する： \( x_i \sim U(b_{lo}, b_{up}) \)。
- 粒子の既知の最良位置を初期位置に設定する： \( p_i \leftarrow x_i \)。
- もし \( f(p_i) < f(g) \) なら、群れの既知の最良位置を更新する： \( g \leftarrow p_i \)。
- 粒子の速度を初期化する： \( v_i \sim U(-|b_{up}-b_{lo}|, |b_{up}-b_{lo}|) \)。
- 終了基準が満たされない間：
- 各粒子 \( i = 1, \dots, S \) について：
- 各次元 \( d = 1, \dots, n \) について：
- ランダム数 \( r_p, r_g \sim U(0,1) \) を選ぶ。
- 粒子の速度を更新する： \( v_{i,d} \leftarrow w v_{i,d} + \phi_p r_p (p_{i,d} - x_{i,d}) + \phi_g r_g (g_d - x_{i,d}) \)。
- 粒子の位置を更新する： \( x_i \leftarrow x_i + v_i \)。
- もし \( f(x_i) < f(p_i) \) なら、粒子の既知の最良位置を更新する： \( p_i \leftarrow x_i \)。
- もし \( f(p_i) < f(g) \) なら、群れの既知の最良位置を更新する： \( g \leftarrow p_i \)。
値 \( b_{lo} \) と \( b_{up} \) は探索空間の下限と上限を表す。パラメータ \( w \) は慣性重みである。パラメータ \( \phi_p \) と \( \phi_g \) は、しばしば認知係数および社会係数と呼ばれる。終了基準は、実行された反復回数または適切な目的関数値が見つかった解である。パラメータ \( w \)、\( \phi_p \)、\( \phi_g \) は実践者によって選択され、PSO法の挙動と有効性を制御する。
パラメータ選択
PSOパラメータの選択は、最適化性能に大きな影響を与える可能性がある。良好な性能をもたらすパラメータを選択することは、多くの研究の対象となっている。発散（「爆発」）を防ぐためには、慣性重みは1より小さくなければならない。他の2つのパラメータは、収縮アプローチを用いて導出するか、自由に選択できるが、分析により収束領域を制約することが示唆されている。典型的な値は範囲 [1, 3] にある。PSOパラメータは、メタ最適化として知られる別の上位オプティマイザを使用して調整することもでき、ファジィ論理などを通じて最適化中に微調整することもできる。パラメータは様々な最適化シナリオに合わせて調整されてきた。
近傍とトポロジー
群れのトポロジーは、各粒子が情報を交換できる粒子のサブセットを定義する。アルゴリズムの基本バージョンは、群れの通信構造としてグローバルトポロジーを使用する。このトポロジーにより、全ての粒子が他の全ての粒子と通信できるため、群れ全体が単一の粒子からの同じ最良位置 \( g \) を共有する。しかし、このアプローチは群れが局所的最小値に閉じ込められる可能性があるため、粒子間の情報の流れを制御するために異なるトポロジーが使用されてきた。例えば、局所トポロジーでは、粒子は粒子のサブセットとのみ情報を共有する。このサブセットは幾何学的なもの（例えば「最も近いm個の粒子」）または、より一般的には社会的なもの、すなわち距離に依存しない粒子の集合である場合がある。そのような場合、PSOバリアントは局所最良（基本PSOの大域最良に対して）と呼ばれる。一般的に使用される群れトポロジーはリングであり、各粒子はちょうど2つの近傍を持つが、他にも多くのものがある。トポロジーは必ずしも静的ではなく、最適化プロセス中に変化することができる。
応用と関連手法
PSOは、工学、経済学、機械学習などの分野にわたる幅広い最適化問題に適用されてきた。探索空間が大きく、目的関数が非微分可能またはノイズが多い場合に特に有用である。PSOは、遺伝的アルゴリズムや蟻コロニー最適化などの他の集団ベースのメタヒューリスティックと類似点を共有するが、社会的行動に触発された速度更新メカニズムによって区別される。機械学習の文脈では、PSOはハイパーパラメータ調整やニューラルネットワークの訓練に使用できるが、勾配ベースの手法としばしば比較される。その確率的性質と勾配要件の欠如により、人工知能のより広い分野における多用途なツールとなっている。