蛾の炎の最適化
1. 序章
「蛾のように炎に」は、蛾が炎に引き付けられるのと同じように、強い引き付けを何かに関連付ける古い表現です。 蛾の飛翔行動は、まるで炎に収束しているかのように見えます。
最適化問題では、最適解を見つけて収束できるアルゴリズムを探すため、おそらく蛾がそのようなアルゴリズムの設計に役立つ可能性があります。 最適化問題の多くの解決策と同様に、Moth Flame Optimization(MFO)は自然界に触発されています。 私たちが探求するアルゴリズムは、炎の周りの蛾のらせん状の振る舞いを利用しています。
このチュートリアルでは、MFOアルゴリズムについて詳しく説明します。
2. 最適化問題
蛾は夜に明るい光の周りに集まるように見えることがよくあります。 彼らはこれらの光に惹かれているようです。 実際には、それは横方向として知られている彼らの自然なナビゲーション戦略の結果です。 蛾は直線で飛ぶために遠くの光源に依存しています。 彼らは、光源を自分たちに対して一定の角度に保つことによってこれを行います。 不自然な光がなければ、これは通常、月になります。 ただし、蛾にはるかに近い新しい光源は、この動作を歪めます。 このより近い光源に対して一定の角度を保つために、蛾は光の周りをらせん状になってしまいます。
蛾の集団を考慮して最適化アルゴリズムを組み立てます。集団ベースのアルゴリズムとして、。と呼ばれる行列を使用して蛾を表現します。 は蛾の数であり、は蛾が表す解ベクトルの次元です。
解決策がどこにあるかわからないので、それらを概算する必要があります。 これは、Flameマトリックスと呼ばれる別の蛾のマトリックスを使用して行います。 も行列であり、と同じサイズです。 これまでに見つかった最良のソリューションを表します。 これらは検索エージェントが周回するビーコンであるため、フレームマトリックスと見なします。 とのそれぞれには関連するベクトルがあり、それぞれ、提案されたソリューションの適合度の値を保持しています。
2.1. アルゴリズム構造
提示されたフローチャートでアルゴリズムを視覚化します。 アルゴリズムは比較的コンパクトです。 フローチャートから、蛾の個体数を初期化する必要があることがわかります。 次に、炎を初期化または更新する必要があります。 炎を更新した後、蛾はそれぞれの炎に向かって移動します。 その後、このプロセスは収束するまで、またはプロセスがステップ制限に達するまで続きます。 私たちがしなければならないことは、蛾と炎の更新動作を定義することです。
2.2. スパイラル行動
(1)
(2)
らせんは、蛾とそれに対応する炎の間の距離に依存します。 また、ユーザーパラメータとして、および時間の経過とともにスパイラルの範囲を縮小する確率変数として含めます。
2.3. 探索対。 搾取
多くのエージェントベースの最適化パラダイムと同様に、探索/探索を考慮する必要があります。 私たちの場合には、
(3)
は現在の反復、は最大火炎数、は最大反復回数です。
対応する最適な炎に関連して蛾を更新します。炎の数を徐々に減らすため、残りの蛾は最後の炎に関連して更新されます。
2.4. 機能とアプリケーション
蛾の行動をモデル化し、それを使用して最適化問題を解決する方法を見てきました。 これで、アルゴリズムの機能のいくつかを繰り返し、それらが機能する理由について説明できます。
局所最適化は、最適化アルゴリズムの問題になる可能性があります。 母集団ベースのアルゴリズムとして、多くの潜在的な解決策が見つかり、反復され、多くの局所最適点の回避を可能にします。 さらに、蛾を炎に割り当て、炎のシーケンスを更新することにより、局所的な最適化も回避されます。
解決策は、炎に代表される既存の優れた解決策の近くを検索することで見つけることができます。 炎の数の適応的な減少は、良い解決策の開発を促進します。 したがって、アルゴリズムは時間の経過とともに収束し、検索空間の代替領域を探索することもできます。
3. MFO擬似コード
MFOの擬似コードを見てみましょう。
上記の擬似コードでアルゴリズムの概要を確認できます。 まず、蛾の個体数を初期化します。 次に、炎を初期化してから、更新手順を実行します。 その後、以前の炎と新しく更新された蛾を組み合わせて、新しい炎のリストを生成します。 最後に、これらの更新手順を合計時間ステップで繰り返すことがわかります。
4. 例
荒野のどこかにキャンプファイヤーがあり、MFOアルゴリズムを使用してそれを見つけたいとします。 さらに、蛾がキャンプファイヤーの熱の恩恵を受け、その恩恵はキャンプファイヤーからの距離に反比例するとします。 これにより、適応度関数を簡単に計算できます。 私たちの荒野は飛行機です。 キャンプファイヤーは、グリッド上の座標にあります。 最大反復回数をに設定します。
4.1. 蛾と炎を生成する
蛾を生成することから始めます。この例では、を設定します。 下の表に蛾の位置が表示されています。
4.2. 蛾を動かす
私たちは蛾を持っており、それらを採点しました。 最適化するための炎が必要です。これらは最高のパフォーマンスを発揮する蛾です。 蛾の最初のセットをフィットネス値で並べ替えることで達成されます。 以下の表に炎を示します。
式1を使用して各蛾の動きを計算します。これには、最初に検索する蛾とその炎の間の距離を計算する必要があります。 つまり、蛾と炎です。 距離は、単に2つのベクトル間の差の絶対値になります。 これを式4で示します。
(4)
次に、この距離に対数螺旋の項を掛けて、最後に炎の位置を追加します。 私たちの目的のために、私たちは設定し、ランダムな探索変数はとしてサンプリングします。 これは式5で計算されます。 新しい位置は、炎を表す蛾に近いです。 また、ターゲットのキャンプファイヤーに近いです。
(5)
4.3. 更新して繰り返す
蛾ごとにこの計算を繰り返します。 その後、炎の数を更新し、古い炎と新しい蛾の位置を使用して炎のリストを更新します。
この場合、反復のアルゴリズムを実行しているため、この反復で炎の数を減らすことはありません。 したがって、古い炎と新しい蛾を組み合わせるとき、私たちはまだ炎を探しています。 これは、新しい炎のマトリックスに前の表の炎と新しい蛾のマトリックスの炎が含まれていることを意味します。
最後に、収束するまでこれらの計算を繰り返すことができます。
5. MFOの複雑さ
MFOは蛾の並べ替えに依存しています。元の論文は、最悪の場合の実行時間がであるクイックソートを提案しています。 最悪の場合の実行時間がより良い他のソートアルゴリズムが可能です。 ただし、クイックソートを使用します。 並べ替えアルゴリズムの選択の詳細については、並べ替えアルゴリズムの選択に関する記事を参照してください。
全体の実行時間を式6で構成します。 このことから、反復ごとにソートを実行してから、MFO更新ループを実行する必要があることがわかります。 したがって、これにより、7に示されている非常に複雑になります。
(6)
(7)
6. 結論
この記事では、蛾の炎の最適化アルゴリズムについて説明しました。 さらに、アルゴリズムのインスピレーションについて説明し、そのインスピレーションを形式化する方法を示しました。
MFOは、ハイパーパラメータの選択から多層パーセプトロンの最適化まで、多くの潜在的な用途を持つ数値最適化アルゴリズムです。多くの同様の自然に触発された人口ベースの最適化アルゴリズムがあります。 このトピックの詳細については、グレイウルフ最適化、グラスホッパー最適化、およびアリコロニー最適化に関する他の記事をご覧ください。
結論として、MFOの利点を要約します。 人口ベースのアルゴリズムとして、極小値にとらわれることに対してある程度のロバスト性があります。 このアプローチは、これまでに発見された最良のソリューションを維持し、優れたソリューションで領域を徐々に活用します。 炎の数を適応的に更新することで、探査と探査のトレードオフのバランスをとることができます。 したがって、全体として、MFOは探索と悪用のバランスをとるアルゴリズムを提供します。 また、理解と実装も簡単です。