1. 概要


コンピュータサイエンスにはさまざまな最適化アルゴリズムがあり、Grasshopper Optimization Algorithm（GOA）もその1つです。このチュートリアルでは、このアルゴリズムの意味と機能について説明します。








次に、GOAアルゴリズムの手順を実行します。 GOAを使用した最適化の問題の解決策を示す数値例に加えて、その利点と欠点についても説明します。


2. グラスホッパー最適化アルゴリズムとは何ですか？


GOAは、メタヒューリスティックアルゴリズムであり、人口ベースのアルゴリズムです。 名前が示すように、このアルゴリズムは、 Saremi and Mirjalili、2017によって数値最適化の問題を解決するために提案されました。 これは最近の群知能アルゴリズムです。  GOAのインスピレーションは、特に、自然界のバッタの群れの行動と相互作用から来ています。


3. バッタは誰ですか？


バッタは作物に甚大な被害を与えるため、有害で破壊的な昆虫です。 バッタのライフサイクルを見てみましょう。これには3つのフェーズがあります。


    

  •  Egg ：初期段階では、夏に給餌植物の近くの地面にある鞘に産卵します。 この段階は、冬に休眠する前に数週間続きます。 その後、地温が上昇するとすぐに卵は発育を再開し、孵化して1齢のニンフになります
    • 

  • ニンフ：段階的に成熟し、各齢はますます大人のようになります。 1齢のニンフには羽がありません。 しかし、幼虫は成虫になるために6つの段階を経る必要があり、翼のつぼみは各段階でサイズが大きくなります。 したがって、彼らはゆっくりと動き、彼らの道にある各植物を食べます
    • 

  • 成人：翼は拡張され、最終齢期の後に完全に機能します。 それで、彼らは空中で群れを形成し、大規模な地域に速く移動します
    • 



つまり、Grasshopperのライフサイクルは次の画像のようになります。


バッタの群れの主な特徴を調べてみましょう。


    

  • 彼らは翼を持っていないので、群れはニンフフェーズで小さなステップを使用してゆっくりと移動します
    • 

  • バッタの群れは翼を持っているため、成人期の段階で突然のジャンプや長距離移動を行うことができます。この段階は、GOAアルゴリズムの背後にある主要なアイデアを表しています。
    • 

  • 群れは、プロセスを探索と搾取の2つの段階に分割することにより、食物を探します。 以下のグラフは、これらのフェーズを示しています。
    • 



探索段階では、群れが食料源を探します。 したがって、この段階では、バッタのすべての値の位置を更新し、適合度の値を計算します。 探索段階では、すべての解決策の中から最良の解決策を見つけます（より良い食料源を探します）。


4. バッタ最適化アルゴリズムの数学的モデル


 GOAアルゴリズムは、自然界のバッタの社会的行動と狩猟方法を模倣しています。これは人口ベースのアルゴリズムであり、各バッタは人口の解決策を表しています。 では、群れの中の各ソリューションの位置をどのように決定するのですか？


簡単です。計算する必要があるのは、ソリューションと他のバッタとの間の社会的相互作用、風の移流、およびソリューションにかかる重力の3つの力だけです。 次に、各解の位置を計算するために使用される数学モデルを見てみましょう。


 (1)    


ここで、はソリューションと他のバッタの間の社会的相互作用を表し、ソリューションに対する重力を表し、風の移流を表します。 次の方程式は、ランダムな動作を追加した後の各ソリューションの位置を表しています。


 (2)    


ここで、およびは[0、1]の乱数です。 ここで、式1で使用される各力のモデルを見てみましょう。


4.1. 社会的相互作用の力


まず、社会的相互作用の力から始めましょう。 次の方程式は、ソリューションと他のバッタの間の社会的相互作用を表しています。


 (3)    


 (4)    


ここで、はバッタとバッタの間の距離を表し、は単位ベクトルを表します。 さらに、は2つの社会的勢力（バッタ間の反発と引力）の強さを表します。ここで、は引力の長さの尺度であり、は引力の強さです。 実際、これらの成分はバッタの社会的行動に大きな影響を及ぼします。


これらの社会的勢力の強さをもう少し深く掘り下げてみましょう。2つのバッタ間の距離が間にあるときは反発が発生し、2つのバッタ間の距離がにあるときは引力も反発も発生せず、快適さを形成しますゾーン。 距離がを超えると、引力は増加し、その後、に達するまで徐々に減少します。


バッタ間の距離が。より大きい場合、この関数はバッタ間に力を加えることができません。 この問題を解決するために、間隔内のバッタの距離をマッピングします。 以下のグラフは、社会的相互作用をより詳細に説明しています。


4.2. 重力の力


次に、重力である2番目の力に進みましょう。 次の式は、重力を計算する方法を示しています。


 (5)    


ここで、は重力定数を表し、は地球の中心に向かう単位ベクトルです。


4.3. 風向の力


その後、ニンフや成虫のバッタに大きな影響を与える風向の力を調べます。 その結果、ニンフと成虫のバッタの動きは風向と相関しています。次の式は計算方法を示しています。


 (6)    


ここで、はドリフト定数を表し、は風向の単位ベクトルです。


4.4. バッタの位置


式3、4、5、および6を使用して式1を再構築しましょう。


 (7)    


最適化の問題を解決し、バッタがすぐに快適ゾーンに到達して群れが目標位置に収束しないのを防ぐために（グローバル最適）、式7にいくつかの変更を加えます。


 (8)    


ここで、、は次元の最良の解であり、およびはそれぞれ次元の上限と下限です。


パラメータは減少係数を表し、快適ゾーン、反発ゾーン、および引力ゾーンの減少を担当します。 バッタアプローチを使用して探索フェーズと活用フェーズのバランスをとるために、係数は反復回数に応じて減少します。 これがのモデルです：


 (9)    


ここで、およびはそれぞれの最大値と最小値であり、は現在の反復であり、は最大反復回数です。


5. GOAアルゴリズムのステップ


ここで、GOAオプティマイザーの実装を見てみましょう。






アルゴリズムでわかるように、パラメータ{}とバッタの個体数を初期化することから始めます。 次に、適応度関数を使用してその値を計算することにより、各ソリューションを評価します。 母集団内の各ソリューションを評価した後、その値に応じて最適なソリューションを割り当てます。 その後、係数パラメーターを更新して、引力、反発、および快適ゾーンを縮小します（式9）。


関数（式4）は、探索空間を反発、快適、および引力の各ゾーンに分割します。 セクション4.1で説明したように、関数がバッタの間に力を加えることができない場合、間隔で距離をマッピングします。


次に、バッタ（ソリューション）と他のバッタ（他のソリューション）の間の距離に基づいて、母集団内の各ソリューションを更新します。 また、式8を使用して、母集団の最適解と減少係数パラメーターを更新します。


ソリューションを更新した後にバッタが境界に違反した場合、バッタをそのドメインに戻します。 次に、母集団のソリューションごとに前の3つの手順を繰り返します。


その後、各ソリューションを更新および評価して、母集団の中で最適なソリューションを割り当てます。 最良のグローバルソリューションを返すために最大反復回数に達するまで、全体的な操作を繰り返します。


グラスホッパーアルゴリズムの時間計算量は、一般に反復回数とエージェント数に関連していることに注意してください。 つまり、はこのアルゴリズムの時間計算量を表し、はエージェントの数であり、は反復の数です。


6. バッタ最適化アルゴリズムの数値例


バッタオプティマイザーアルゴリズムを理解するために、数値例を使用します。


6.1. 初期化


まず、バッタの個体数をランダムに初期化します。ここで、。 その後、すべてのパラメーターを初期化し、ランダムな値のセットを使用します。




      




6.2. フィットネス値を計算する


各バッタの適応度値を計算するための適応度関数は次のとおりです。


      


適応度関数を使用して、現在の母集団の各バッタの適応度値を計算してみましょう。








6.3. 最適な解決策と状態の確認


すべての適合度の値を計算した後、すべての中から最適なソリューションを選択する必要があります。 最適なソリューションは、すべてのバッタの中で最小の適応度値を持つソリューションです。 結果として、は最初の反復に最適なソリューションです。 先に進んで状態を確認しましょう。 反復回数と、条件trueを意味することに注意してください。 その結果、次のステップに進みます。


6.4. 距離の正規化


以下の式を使用してバッタ間の距離を正規化するために計算する必要があります。




 (10)    






 (11)    




バッタ間の距離を正規化した結果は次のとおりです。








6.5. 位置を更新


式8を使用して各バッタの位置を更新するには、バッタの現在の位置（セクション6.2で計算）、見つかった最適なソリューション（セクション6.3で計算）、およびその他のバッタの位置（セクション6.4で距離を使用して計算）が必要です。 。 バッタの新しい位置は次のとおりです。








に見つかった最良のソリューションを追加することにより、新しい位置の値を取得しました。


6.6. 新しいフィットネス値を計算する


新しいフィットネス値を計算する前に、現在のバッタが境界の外に出た場合は元に戻します。 セクション6.5の表は、すべてのバッタが境界内にあることを示しています。 それでは、現在の母集団の各バッタの新しい適応度の値を計算してみましょう。








6.7. 最高のグローバルソリューション


最適なソリューションを更新するための新しい最適なソリューションがあるかどうかを確認します。 そのために、各バッタの古いフィットネス値と新しいフィットネス値を比較します。 古いフィットネス値と新しいフィットネス値を比較した後、を更新し、カウンターをインクリメントします。 次に、に達するまでを繰り返します。 もしもそれから停止します && を返します。 各反復の適合度の値を以下の表に示します。
















7. GOAアルゴリズムの長所と短所


他のオプティマイザアルゴリズムと同じように、GOAアルゴリズムには長所と短所があります。 次に、GOAアルゴリズムの長所と短所を見てみましょう。




8. 結論


この記事では、バッタの最適化アルゴリズムについて、数値例を使用してそのメカニズムのロックを解除する方法について説明しました。 このアルゴリズムは、自然界の群れの個体数を使用して、問題に対する最適なグローバルソリューションを検索します。 このアルゴリズムを導入したのは、グローバルな制約なしおよび制約付き最適化の問題を解決するのに非常に効果的だからです。