粒子群最適化

計算科学において、粒子群最適化（PSO）^[1]は、与えられた品質の尺度に関して候補解を繰り返し改善することで問題を最適化する計算手法である。この手法では、候補解の集団（ここでは粒子と呼ぶ）を用意し、粒子の位置と速度に関する簡単な数式に従って探索空間内でこれらの粒子を移動させることで問題を解決します。各粒子の動きはその局所的な最良位置の影響を受けますが、探索空間内の最良位置に向かって導かれ、他の粒子によってより良い位置が見つかると、その位置は更新されます。これにより、群れが最良解に向かって動くことが期待されます。

PSOはもともとケネディ、エバーハート、シー^{[2] [3]に帰属し、最初は}社会的行動をシミュレートする ことを目的としていました^[4]、鳥の群れや魚の群れにおける生物の動きの様式化された表現として。アルゴリズムは簡略化され、最適化を実行していることが観察されました。ケネディとエバーハートの著書^{[5]では、PSOと}群知能の多くの哲学的側面が説明されています。PSOのアプリケーションの広範な調査はPoliによって行われています。^{[6] [7]} 2017年には、PSOに関する理論的および実験的研究の包括的なレビューがBonyadiとMichalewiczによって出版されました。^[1]

PSO は、最適化される問題についてほとんどまたはまったく仮定を行わず、非常に大きな候補ソリューションの空間を検索できるため、メタヒューリスティックです。また、PSO は最適化される問題の勾配を使用しないため、勾配降下法や準ニュートン法などの従来の最適化方法で要求されるような、最適化問題が微分可能である必要はありません。ただし、PSO などのメタヒューリスティックでは、最適なソリューションが見つかることを保証するものではありません。

PSO アルゴリズムの基本的なバリエーションは、候補ソリューション(粒子と呼ばれる) の集団 (群れと呼ばれる) を持つことで機能します。これらの粒子は、いくつかの簡単な公式に従って検索空間内を移動します。^[8]粒子の動きは、検索空間内の粒子自身の最もよく知られている位置と、群れ全体の最もよく知られている位置によって誘導されます。改善された位置が発見されると、それが群れの動きを誘導するようになります。このプロセスが繰り返され、そうすることで最終的に満足のいくソリューションが発見されることが期待されますが、保証されるわけではありません。

正式には、f : ℝ ⁿ  → ℝ を最小化する必要があるコスト関数とします。この関数は、実数のベクトルの形式で候補ソリューションを引数として受け取り、与えられた候補ソリューションの目的関数値を示す実数を出力として生成します。fの勾配は不明です。目標は、探索空間内のすべてのbに対してf ( a ) ≤  f ( b )となるソリューションa を見つけることです。これは、 a がグローバル最小値であること を意味します。

S を群れの中の粒子の数とし、各粒子は探索空間内で位置 x i ∈ ℝ n を持ち、速度v _i  ∈ ^ℝ n_を 持つ^ものとする。p i を粒子 i の既知の最適位置とし、_gを群れ全体の既知の最適位置とする。コスト関数を最小化する基本的な PSO アルゴリズムは次のようになる: ^[9]

各粒子i  = 1, ...,  S について
    、粒子の位置を一様分布のランダムベクトルで初期化します: x i  ~  U ( b lo ,  b up )
    粒子の既知の最適位置を初期位置に初期化します: p i  ←  x i 、
    f ( p i ) < f ( g )の場合 、
        群れの既知の最適位置を更新します: g  ←  p i 、
    粒子の速度を初期化します: v i ~ U  (  - | b up - b lo |、| b up - b lo |)
 、終了基準が満たされていない場合は、
    各粒子i  = 1、...、  Sに対して、各次元d  = 1、...、  nに対して、
            乱数を選択します: r p、r g ~ U (0、1) 
         
            粒子の速度を更新します: v i,d  ← w v i,d + φ p  r p ( p i,d - x i,d ) + φ g  r g ( g d - x i,d )
        粒子の位置を更新します: x i  ←  x i + v i 
        if  f ( x i ) < f ( p i ) then
            粒子の最もよく知られている位置を更新します: p i  ←  x i 
            if  f ( p i ) < f ( g ) then
                群れの最もよく知られている位置を更新します: g  ←  p i

b _loとb _{up の}値は、それぞれ検索空間の下限と上限を表します。w パラメータは慣性重みです。パラメータ φ _p と φ _{g は}、認知係数と社会係数と呼ばれることがよくあります。

終了基準は、実行される反復回数、または適切な目的関数値が見つかる解である。^[10]パラメータw、φp _、およびφg_は、実践者によって選択され、PSO法の動作と有効性を制御します（以下）。

PSOパラメータの選択は最適化のパフォーマンスに大きな影響を与える可能性があります。そのため、優れたパフォーマンスをもたらすPSOパラメータを選択することは、多くの研究の対象となっています。^{[11] [12] [13] [14] [15] [16] [17] [18] [19]}

発散（「爆発」）を防ぐために、慣性重みは1より小さくなければなりません。他の2つのパラメータは、狭窄アプローチ^[16]によって導出するか、自由に選択することができますが、解析ではそれらを制約するための収束領域が示唆されています。典型的な値は です。 ${\displaystyle [1,3]}$

PSOパラメータは、メタ最適化と呼ばれる別のオーバーレイ最適化ツールを使って調整することもできる^{[20] [21] [22] [23]}。また、最適化中にファジー論理などを使って微調整することもできる^{[24] [25] 。}

さまざまな最適化シナリオに合わせてパラメータも調整されています。^{[26] [27]}

群れのトポロジーは、各粒子が情報を交換できる粒子のサブセットを定義します。^[28]アルゴリズムの基本バージョンでは、群れの通信構造としてグローバル トポロジーを使用します。^[10]このトポロジーにより、すべての粒子が他のすべての粒子と通信できるため、群れ全体が単一の粒子からの同じ最適な位置g を共有します。ただし、このアプローチでは、群れがローカル ミニマムに陥る可能性があるため、^[29]さまざまなトポロジーを使用して粒子間の情報の流れを制御します。たとえば、ローカル トポロジーでは、粒子は粒子のサブセットとのみ情報を共有します。^[10]このサブセットは、幾何学的なもの^[30] (たとえば、「m 個の最も近い粒子」) である場合もあれば、より一般的には、距離に依存しない粒子のセットであるソーシャル サブセットである場合もあります。このような場合、PSO バリアントはローカル ベスト (基本 PSO のグローバル ベストに対して) であると言われています。

一般的に使用される群集トポロジーはリングであり、各粒子は2つの隣接粒子のみを持ちますが、他にも多くの隣接粒子が存在します。^[10]トポロジーは必ずしも静的ではありません。実際、トポロジーは粒子の通信の多様性に関係しているため、^[31]適応型トポロジーを作成するためのいくつかの取り組みが行われてきました（SPSO、^[32] APSO、^[33]ストキャスティックスター、^[34] TRIBES、^[35]サイバースウォーム、^[36] C-PSO ^[37]）

リングトポロジーを使用することで、PSOは世代レベルの並列性を実現し、進化速度を大幅に向上させることができます。^[38]

PSO アルゴリズムがなぜ、どのように最適化を実行できるかについては、 いくつかの考え方があります。

研究者の間では、群れの行動は探索行動（検索空間のより広い領域を探索する）と搾取行動（（おそらく局所的な）最適値に近づくための局所指向の探索）の間で変化するというのが一般的な考えです。この考え方は、PSO の誕生以来広く信じられてきました。^{[3] [4] [12] [16]この考え方では、PSO アルゴリズムとそのパラメータは、}局所最適値への早期収束を避けつつも最適値への良好な収束率を確保するために、探索と搾取のバランスが適切に取れるように選択する必要があると主張しています。この考えは、以下に示す多くの PSO バリアントの先駆けとなっています。

もう 1 つの考え方は、PSO スウォームの挙動が実際の最適化パフォーマンスにどのように影響するかという点では十分に理解されていないというものです。特に、高次元の検索空間や、不連続、ノイズ、時間変動の可能性がある最適化問題ではそうです。この考え方では、スウォームの挙動が探索や活用などに関連してどのように解釈されるかに関係なく、優れたパフォーマンスをもたらす PSO アルゴリズムとパラメータを見つけようとします。このような研究により、PSO アルゴリズムが簡素化されました (以下を参照)。

PSO に関して、収束という言葉は通常、次の 2 つの異なる定義を指します。

• 全ての粒子が探索空間内の一点に収束する解の列の収束（別名、安定性解析、収束）は、最適解である可能性もあれば、そうでない可能性もある。
• 群れがどのように動作するかに関係なく、すべての個人的な最高値pまたは群れの既知の最高位置gが問題の局所最適値に近づく局所最適値への収束。

PSO では、解のシーケンスの収束が調査されてきました。^{[15] [16] [17]}これらの分析の結果、一点への収束を引き起こし、群れの粒子の発散を防ぐと考えられる PSO パラメータを選択するためのガイドラインが得られました (粒子は無制限に移動することはなく、どこかに収束します)。しかし、Pedersen ^[22]は、群れには粒子が 1 つしかなく、確率変数を使用しておらず、吸引点、つまり粒子の最もよく知られている位置pと群れの最もよく知られている位置gは最適化プロセス全体を通じて一定であると仮定しているため、分析が単純化されすぎていると批判しました。しかし、 ^[39]では、これらの単純化は、群れが収束するパラメータについてこれらの研究で見つかった境界には影響しないことが示されました。近年、PSOの安定性解析で利用されるモデリング仮定を弱めるための多大な努力がなされており、^[40]最新の一般化された結果は、多数のPSOバリアントに適用され、最小限必要なモデリング仮定であることが示されたものを利用している。^[41]

^{PSOの局所最適値への収束は[42]}と^[43]で分析されている。局所最適値を見つけることを保証するためにはPSOに何らかの修正が必要であることが証明されている。

これは、異なる PSO アルゴリズムとパラメータの収束能力を決定することは、依然として経験的結果に依存していることを意味します。この問題に対処するための 1 つの試みは、pとgの関係にすでに存在する情報をより有効に活用し、主要な収束例を形成し、どの PSO トポロジでも有効になるようにする「直交学習」戦略の開発です。その目的は、より速いグローバル収束、より高いソリューション品質、より強力な堅牢性など、PSO 全体のパフォーマンスを向上させることです。^[44]しかし、このような研究は、実際にその主張を証明する理論的証拠を提供していません。

収束（「活用」）と発散（「探索」）のトレードオフを必要とせずに、適応メカニズムを導入することができます。適応型粒子群最適化（APSO）^[45]は、標準的なPSOよりも優れた検索効率を特徴としています。APSOは、より高い収束速度で、検索空間全体にわたってグローバル検索を実行できます。実行時に慣性重み、加速係数、およびその他のアルゴリズムパラメータを自動的に制御できるため、検索の有効性と効率性が同時に向上します。また、APSOは、グローバルに最適な粒子に作用して、可能性のある局所最適値から抜け出すことができます。ただし、APSOは新しいアルゴリズムパラメータを導入しますが、それでも設計や実装の複雑さは追加されません。

さらに、スケール適応型適応度評価メカニズムを利用することで、PSOは計算コストの高い最適化問題に効率的に対処することができます。^[46]

基本的なPSOアルゴリズムでさえ、さまざまなバリエーションが考えられます。たとえば、粒子と速度を初期化する方法（たとえば、速度をゼロから開始する）、速度を減衰させる方法、群れ全体が更新された後にのみpiとgを更新する方法などがあります。これらの選択肢のいくつかと、それらがパフォーマンスに与える影響については、文献で議論されています。^[14 _]

一連の標準実装は、一流の研究者によって作成されており、「技術の改善のパフォーマンステストのベースラインとして、また、より広範な最適化コミュニティに PSO を紹介するために使用することを目的としています。よく知られた、厳密に定義された標準アルゴリズムを持つことで、研究分野全体で新しい進歩をより適切にテストするために使用できる貴重な比較ポイントが提供されます。」^[10]最新のものは、標準 PSO 2011 (SPSO-2011) です。^[47]

最適化のパフォーマンスを向上させるために、新しくより洗練された PSO の変種も継続的に導入されています。その研究には一定の傾向があり、1 つは PSO と他の最適化装置を組み合わせたハイブリッド最適化手法を作成することです^{[48] [49] [50]。}たとえば、生物地理学に基づく最適化と組み合わせた PSO や^[51]効果的な学習方法の組み込みなどです^{[44] 。}

もう一つの研究傾向は、例えばPSO粒子の動きを逆転させたり乱したりすることによって、早期収束（つまり最適化の停滞）を軽減しようとするものである。 ^{[19] [52] [53] [54]}早期収束に対処するためのもう一つのアプローチは、複数の群れを使用することである^[55]（マルチスウォーム最適化）。マルチスウォームアプローチは、多目的最適化を実装するためにも使用できる。^[56]最後に、最適化中にPSOの動作パラメータを適応させる開発がある。^{[45] [24]}

もう一つの考え方は、PSO はパフォーマンスを損なうことなく可能な限り単純化されるべきであるというものです。これは、オッカムの剃刀と呼ばれる一般的な概念です。PSO の単純化はもともと Kennedy ^[4]によって提案され、より広範囲に研究され、^{[18] [21] [22] [57]}、最適化のパフォーマンスが向上し、パラメータの調整が容易になり、さまざまな最適化問題にわたってより一貫したパフォーマンスが得られることが明らかになりました。

PSO を単純化することを支持するもう 1 つの論拠は、メタヒューリスティックの有効性は、有限数の最適化問題に対する計算実験を行うことによってのみ経験的に実証できるという点です。つまり、PSO などのメタヒューリスティックは正しいと証明できず、記述や実装でエラーが発生するリスクが高まります。この良い例^{[58]では、}遺伝的アルゴリズム(別の一般的なメタヒューリスティック)の有望な変種が紹介されましたが、後に欠陥があることが判明しました。最適化検索において、検索空間内の異なる次元の類似値に強く偏っており、それがたまたま検討したベンチマーク問題の最適値であったためです。この偏りはプログラミング エラーによるもので、現在は修正されています。^[59]

速度の初期化には追加の入力が必要になる場合があります。Bare Bones PSOバリアント^[60]は2003年にJames Kennedyによって提案されており、速度をまったく使用する必要がありません。

このPSOの変種では、粒子の速度を使わず、代わりに次の単純なルールを使用して粒子の位置を更新します。

${\displaystyle {\vec {x}}_{i}=G\left({\frac {{\vec {p}}_{i}+{\vec {g}}}{2}},||{\vec {p}}_{i}-{\vec {g}}||\right)\,,}$

ここで、は粒子の位置と最適位置、は全体最適位置、は平均と標準偏差を持つ正規分布、 はベクトルのノルムを表します。 ${\displaystyle {\vec {x}}_{i}}$${\displaystyle {\vec {p}}_{i}}$${\displaystyle i}$${\displaystyle {\vec {g}}}$${\displaystyle G({\vec {x}},\sigma )}$${\displaystyle {\vec {x}}}$${\displaystyle \sigma}$${\displaystyle ||\dots ||}$

もう一つのより単純な変種は加速粒子群最適化（APSO）^[61]であり、これも速度を使用する必要がなく、多くのアプリケーションで収束を高速化できます。APSOの簡単なデモコードが利用可能です。^[62]

このPSOの変種では、粒子の速度と粒子の最適位置の両方が不要になります。粒子の位置は次の規則に従って更新されます。

${\displaystyle {\vec {x}}_{i}\leftarrow (1-\beta ){\vec {x}}_{i}+\beta {\vec {g}}+\alpha L{\vec {u}}\,,}$

ここで、はランダムな一様分布ベクトル、は問題の典型的な長さ、 とは方法のパラメータです。 この方法の改良として、 を各反復で減少させることができます。ここで、は反復回数、 は減少制御パラメータです。 ${\displaystyle {\vec {u}}}$${\displaystyle L}$${\displaystyle \beta \sim 0.1-0.7}$${\displaystyle \alpha \sim 0.1-0.5}$${\displaystyle \alpha}$${\displaystyle \alpha _{n}=\alpha _{0}\gamma ^{n}}$${\displaystyle n}$${\displaystyle 0<\gamma <1}$

PSOは多目的問題にも適用されており^{[63] [64] [65]}、目的関数の比較ではPSO粒子を移動する際にパレート優位性が考慮され、非優位解はパレートフロントに近似するように保存されます。

上記のPSO方程式は実数に対して作用するため、離散問題を解くために一般的に使用される方法は、離散探索空間を連続領域にマッピングし、古典的なPSOを適用し、結果をデマッピングすることです。このようなマッピングは非常に単純なもの（たとえば、丸められた値を使用するだけ）もあれば、より複雑なものもあります。^[66]

ただし、運動方程式では次の 4 つのアクションを実行する演算子が使用されていることに注意してください。

• 2つの位置の差を計算する。結果は速度（より正確には変位）である。
• 速度に数値係数を掛ける
• 2つの速度を加える
• 位置に速度を適用する

通常、位置と速度はn個の実数で表され、これらの演算子は単純に-、*、+、そして再び+です。しかし、これらすべての数学的対象は、バイナリ問題（またはより一般的には離散問題）や組み合わせ問題に対処するために、まったく異なる方法で定義することができます。^{[67] [68] [69] [70]} 1つのアプローチは、集合に基づいて演算子を再定義することです。^[71]

• 人工蜂コロニーアルゴリズム
• ミツバチアルゴリズム
• 導関数を使わない最適化
• マルチスウォーム最適化
• 粒子フィルター
• 群知能
• 魚群探知
• 分散ハエの最適化

ウィキメディア・コモンズには、粒子群最適化に関連するメディアがあります。

• Particle Swarm Central は PSO に関する情報のリポジトリです。いくつかのソース コードは無料で入手できます。
• 3 つのベンチマーク関数を最適化する粒子群の短いビデオ。
• 2 次元空間における PSO 収束のシミュレーション (Matlab)。
• PSO のアプリケーション。
• Liu, Yang (2009). 「高速かつエリートな多目的粒子群アルゴリズムを使用した降雨流出モデルの自動較正」.エキスパートシステムとアプリケーション. 36 (5): 9533–9538. doi :10.1016/j.eswa.2008.10.086.
• PSO ソースコードへのリンク