1. イントロ

この記事では、Gray Wolf Optimization（GWO）アルゴリズムとその仕組みを確認します。 名前から結論できるように、これはオオカミの群れの行動に基づく自然に触発されたメタヒューリスティックです。 遺伝的アルゴリズムやホタルアルゴリズムなどの他の自然に触発されたメタヒューリスティックと同様に、最適なソリューションを見つけることを期待して検索スペースを探索します。

要約すると、これは最適化問題に使用される反復法です。

2. インスピレーション

このアルゴリズムのインスピレーションは、大きな獲物を群れで狩り、個々のオオカミ間の協力に依存する灰色オオカミの行動です。 この動作には2つの興味深い側面があります。

  • 社会階層
  • ハンティングメカニズム

灰色オオカミは非常に社会的な動物であり、その結果、複雑な社会的階層を持っています。 オオカミが強さと力に従ってランク付けされるこの階層システムは、「支配階層」と呼ばれます。 したがって、アルファ、ベータ、デルタ、およびオメガがあります。

  1. アルファのオスとメスは階層の最上位にあり、パックをリードしています。 パックのすべてのメンバーは、特定のランク内で注文しました。 オオカミの階層システムは、支配と攻撃性だけではありません。 また、自分で狩りをすることができない脆弱なメンバーを支援します。
  2. その後は、アルファオオカミの決定をサポートし、パック内の規律を維持するのに役立つベータオオカミです。
  3. デルタオオカミは、ランクのベータオオカミの下にあります。 彼らはしばしば強いですが、リーダーシップのスキルやリーダーシップの責任を引き受ける自信がありません。
  4. そして最後に、オオカミにはまったく力がなく、他のオオカミはすぐに彼を追いかけます。 オオカミは若いオオカミを見守る責任もあります。

社会階層に加えて、灰色のオオカミは独自の戦略で非常に特殊な狩猟方法を持っています。彼らは群れで狩りをし、グループで協力して獲物を群れから分離します。その後、1〜2匹のオオカミが追いかけます。他の人がストラグラーを追い払っている間、獲物を攻撃します。

Muro et al。は、オオカミの群れの狩猟戦略について説明しています。

  • 獲物に近づき、追跡し、追跡する
  • 獲物が動かなくなるまで、追跡、嫌がらせ、および獲物の周りを取り巻く操作
  • 獲物が使い果たされたときに攻撃する

3. 意味

前述の方法論を最適化問題に適用し、各ステップで、アルファ、ベータ、デルタの3つの最良のソリューションをそれぞれ示し、その他のソリューションをオメガで示します。 基本的に、それは最適化プロセスが3つの最良の解決策の流れに沿って進むことを意味します。また、獲物は最適化の最適な解決策になります。

ほとんどのロジックは次の方程式に従います。

(1)  

(2)  

ここで、は現在の反復を示し、は係数ベクトル、は獲物の位置ベクトル、はオオカミの位置です。 ベクトルとは次の値に等しい：

(3)  

(4)  

ここで、の成分は反復によって2から0に直線的に減少し、は、各反復で各オオカミに対して計算された、からの値を持つランダムベクトルです。 ベクターは、探索と活用の間のトレードオフを制御しますが、常にある程度のランダム性を追加します。 これが必要なのは、エージェントがローカルオプティマにとらわれる可能性があり、ほとんどのメタヒューリスティックにはそれを回避する方法があるためです。

最適解の実際の位置がわからないため、3つの最良の解に依存し、各エージェント（オオカミ）を更新するための式は次のとおりです。

(5)  

(6)  

(7)  

ここで、はエージェントの現在の位置であり、は更新された位置です。 上記の式は、オオカミの位置がそれに応じて前の反復から最高の3匹のオオカミに更新されることを示しています。 3つの最高のオオカミの平均と正確に等しくなるわけではありませんが、ベクトルのために、小さなランダムシフトが追加されることに注意してください。 これは理にかなっています。なぜなら、一方の側からは、エージェントが最高の個人に導かれることを望んでおり、もう一方の側からは、ローカル最適点にとらわれたくないからです。

最後に、GWOの擬似コードは次のとおりです。

アルゴリズムの時間計算量は、反復回数、エージェント、およびベクトルのサイズに依存しますが、一般に、時間計算量は、で近似できます。ここで、は反復回数、はエージェント数です。

4. 例

このアルゴリズムをよりよく理解するために、オオカミの群れの振る舞いの具体的な例を1つ紹介します。 下の画像（左）では、エージェントの初期状態を確認できます。ここで、獲物または最適なソリューションは赤色になっています。 獲物に最も近いオオカミ（アルファ、ベータ、デルタ）は、それぞれ緑、青、紫の色をしています。 黒い点は他のオオカミ（オオカミ）を表しています。

さらに、前のセクションで説明した式に従ってオオカミの位置を更新すると、下の画像（右）でエージェントの動作を観察できます。 探索と活用の間のトレードオフを制御する変数が値2に設定されていることに注意してください。 これは、私たちが探鉱の乱獲を好むことを意味します。

次に、次の画像は、変数が値1に設定されている場合のオオカミの群れの動作を示しています。 通常、これは、最適化プロセスの途中であり、悪用プロセスがますます出現することを意味します。

最後に、下の画像では、変数は0に等しくなっています。 これは、最適化プロセスが終了したことを意味し、うまくいけば、ベスト3のオオカミに続く最適なソリューションに向かって収束しています。 アルファ、ベータ、デルタのエージェント間の重心を幾何学的に表すポイントの周りで、オオカミが最高の3匹のオオカミの間にどのように集まっているかを見ることができます。

オメガとの比較のために、アルファ、ベータ、およびデルタエージェントの位置を更新しなかったことに注意してください。 それ以外の場合は、すべてのエージェントの位置を更新し、その後、新しいアルファ、ベータ、およびデルタを選択します。 結局のところ、GWOエージェントの収束は次のアニメーションのようになります。

5. アプリケーション

一般に、このアルゴリズムを使用して、さまざまな最適化問題を解決できます。 以下では、機械学習に役立つ可能性のあるものの一部についてのみ説明します。

5.1. ハイパーパラメータの調整

興味深いアプリケーションの1つは、機械学習アルゴリズムのハイパーパラメータ調整です。 ハイパーパラメータ調整の背後にある主なアイデアは、特定のアルゴリズムのパフォーマンスを最大化するために、パラメータの最適な値のセットを見つけることです。

たとえば、GWOを使用すると、勾配ブースティングのハイパーパラメータを最適化できます。 その場合、値の各ベクトルコンポーネントが特定のハイパーパラメーターを持つように位置ベクトルを構築できます。 たとえば、X =（学習率、木の数、最大深度）。 エージェント間の距離を計算するための独自のメトリックをいつでも定義できるため、パラメータに数値を設定する必要はありません。

5.2. 特徴選択

機械学習にも関連するGWOのもう1つのアプリケーションは、特徴選択です。 アルゴリズムは、可能な機能のセットを構築し、目的のソリューションが見つかるまで、パフォーマンス測定に基づいてこれらの機能を繰り返し変更することによって機能します。

このアプローチは、機能の最適なサブセットを選択するための複雑さが変数を追加するたびに指数関数的に増加するため、時間の複雑さの点ではるかに安価です。 これは、要素を持つセットのサブセットの総数がであるためです。 つまり、機械学習アルゴリズムへの入力として30の異なる特徴がある場合、結果として、30の特徴の可能なサブセットの数は！

したがって、30個の特徴をサイズ30のバイナリベクトルとして表す方が現実的です（各ビットは1つの特定の特徴であり、1は特徴が含まれていることを示し、0は含まれていないことを示します）。 そのバイナリベクトルはエージェントの位置を表し、GWOまたはその他のメタヒューリスティックで簡単に使用できます。

5.3. その他の例

上記の例に加えて、GWO は、次のようなさまざまな問題の解決に成功しています。

  1. 巡回セールスマン問題（TSP）
  2. 最小スパニングツリーの問題
  3. 非線形方程式システム
  4. パワーフローの問題など

6. 結論

この記事では、GWOアルゴリズムの背後にある直感とロジックについて説明し、最適化問題を解決するためにGWOアルゴリズムを適用する方法をより深く理解できるようにしました。 このアルゴリズムを導入したのは、非常に効果的でありながら、簡単に理解できるほど単純だからです。 この記事では、GWOとは何か、GWOがどのように機能するかの例を示し、アプリケーションの例に関するいくつかの重要な考慮事項を示します。