多元宇宙オプティマイザー
1. 概要
コンピュータサイエンスにはさまざまな最適化アルゴリズムがあり、Multi-Verse Optimization Algorithm(MVO)もその1つです。
このチュートリアルでは、このアルゴリズムの意味とその機能を見ていきます。
次に、MVOアルゴリズムの手順を実行します。 最後に、数値例を使用して、MVOを使用した最適化の問題の解決策を示します。
2. 多元宇宙オプティマイザーとは何ですか?
MVOは、人口ベースのアルゴリズムであり、マルチバース理論の概念に基づくメタヒューリスティックアルゴリズムです。 名前が示すように、 Seyedali Mirjalili は、2015年に数値最適化の問題を解決するためにこのアプローチを導入しました。
3. マルチバース理論
多元宇宙という用語は宇宙の反対側にあり、私たち全員が住んでいる世界に加えて、追加の世界の存在を指す独自性の概念に異議を唱えています。 したがって、オブジェクトだけでなく、私、あなた、および他のすべての人の重複が存在する可能性があります。
多元宇宙論では、複数の宇宙が相互作用し、互いに衝突することさえあります。多元宇宙アプローチは、各世界が独自の物理的ルールのセットを持っている可能性があることも示しています。 多元宇宙論の3つの基本的な概念は、ホワイトホール、ブラックホール、およびワームホールです。
3.1. ホワイトホール
私たちの世界ではホワイトホールは観測されていませんが、ビッグバンはホワイトホールと見なされ、宇宙形成の主要な構成要素である可能性があります。さらに、それはサイクリックモデルで知られています平行宇宙が衝突する場所でホワイトホール(ビッグバン)が生成されるというマルチバース理論の例。 ホワイトホールの例を次に示します。
3.2. ブラックホール
何度か発見されたブラックホールは、白い全体とは根本的に異なった働きをします。 非常に強い引力で、光線を含むすべてのものを引き付けます。下の画像は、ブラックホールの例を表しています。
3.3. ワームホール
ワームホールは、宇宙のさまざまなセクションをつなぐ穴です。 それらは、多元宇宙アプローチにおいて時間/空間移動トンネルとして機能します。 アイテムは、ユニバースの任意の2つのコーナー間、またはこれらのトンネルを介して1つのユニバースから別のユニバースに瞬時に移動する可能性があります。ワームホールの例を次に示します。
3.4. MVOの宇宙のルール
最適化プロセス中にMVOの世界に適用する原則を見てみましょう。
- インフレ率が高くなると、ホワイトホールが発生する可能性が高くなります。
- インフレ率が高くなると、ブラックホールが発生する可能性は低くなります。
- インフレ率が高い宇宙は、ホワイトホールを通して物体を送る傾向があります。
- インフレ率が低い宇宙は、ブラックホールを通してより多くの物体を受け取る傾向があります。
- インフレ率に関係なく、すべての宇宙のオブジェクトは、ワームホールを介して最良の宇宙に向かってランダムに移動する可能性があります。
4. 多元宇宙アルゴリズムの数学的モデル
人口ベースのアルゴリズムで使用される検索手順を、探索と活用の2つの部分に分けてみましょう。
各ソリューションはユニバースと同等であり、その世界の各変数はオブジェクトです。 さらに、ソリューションに関連付けられた適応度関数の値に比例するインフレ率を各ソリューションに適用します。
4.1. MVOのルーレットビルドメカニズム
ルーレットホイールメカニズムを使用して、ホワイトホールトンネルとブラックホールトンネルの数学モデル、および宇宙を横切るオブジェクトの動きを記述します。運が左右するゲームであるルーレットホイールテーブルには、数字が含まれています。 数字の色は緑、その他の色は赤と黒です。 以下のグラフは、ルーレット盤を示しています。
そこで、ルーレットメカニズムを使用して、ホワイトホールのすべての中から1つのユニバースを選択します。 各反復で、フィットネス値(インフレ率)に従ってユニバースを並べ替え、ルーレットを使用してユニバースを選択します。
4.2. 宇宙選択の数理モデル
マルチバース理論によると、私たちは複数の宇宙を持っています:
以下のモデルは、ルーレットホイール選択メカニズムを使用して1つのユニバースを選択するために使用できる数学モデルを示しています。
ここで、はルーレットホイールメカニズムによって選択されたユニバースのパラメータを表し、はユニバースのパラメータを参照し、はユニバースであり、は間隔内のランダムな値です。
このメカニズムを使用すると、ユニバースは混乱することなくオブジェクトを相互に交換できます。
4.3. ワームホールトンネルの数学モデル
前に述べたように、ワームホールはブラックホールとホワイトホールの間のトンネルとして機能します。 したがって、各宇宙には、空間を介したオブジェクトのランダムな交換を保証するためのワームホールがあると仮定しましょう。 ワームホールは、インフレ率を考慮せずにオブジェクトをランダムに変更します。 ここで、ワームホールトンネルが常にユニバースと最良のユニバースの間に確立されていると仮定しましょう(各ユニバースにローカルな変更を提供するため)。 このメカニズムの定式化を発見しましょう:
ここで、は作成された最も適切なユニバースの変数を表し、区間、、、およびの乱数、、、、 {、、}のパラメーターを指します。
以下の式は、およびを表します。
5. 多元宇宙アルゴリズム
次に、MVOオプティマイザーの実装とそのタイルの複雑さを見てみましょう。
5.1. アルゴリズム
以下のアルゴリズムは、多元宇宙オプティマイザーを表しています。
アルゴリズムでわかるように、アルゴリズムの出力としてBest UniverseとそのFitness値を取得するには、入力として母集団のサイズ(ユニバースの数)と最大反復回数が必要です。
まず、パラメータ{}、{}および母集団のサイズ}を初期化します。 次に、適応度関数を使用してその値を計算することにより、各ソリューションを評価します。 母集団内の各ソリューションを評価した後、その値に応じて最適なソリューションを割り当てます。 その後、パラメータを更新します。
N個の中から1つのユニバースを選択するために、ホワイトホールとしてルーレットホイール選択メカニズムを使用します。 次に、異なる宇宙間のオブジェクト交換のためのトンネルとしてワームホールを使用します。 停止基準が一致するまで全体の操作を繰り返します。つまり、最大反復回数に達するまで現在の反復をチェックして、最適なグローバルソリューションを返します。
5.2. MVOの時間計算量
多元宇宙アルゴリズムの時間計算量は、一般に、反復回数()、ユニバース数()、およびオブジェクト数()に関連していることに注意してください。 したがって、次の式は、このアルゴリズムの時間計算量を表しています。
より詳細には、すべての反復で QuickSort アルゴリズムを採用していますが、これは最悪の場合の複雑さを伴います。 さらに、反復全体ですべてのユニバースのすべての変数にルーレットホイールメカニズムを使用します。これは、最悪の場合の複雑さを伴います。 クイックソートとルーレットホイールメカニズムの複雑さを使用して、マルチバースアルゴリズムの時間計算量を再構築しましょう:
6. 多元宇宙アルゴリズムの数値例
多元宇宙オプティマイザーアルゴリズムを理解するために、数値例を使用します。
6.1. 初期化
まず、人口サイズ(ユニバースの総数)をランダムに初期化します。 その後、ランダムな値のセットを使用してすべてのパラメーターを初期化します。
4つのユニバースの初期位置は次のとおりです():
6.2. フィットネス値を計算する
各ユニバースの適応度値を計算し、最適なユニバースを選択するための適応度関数は次のとおりです。
適応度関数を使用して、現在の母集団の各ユニバースの適応度値を計算してみましょう。
6.3. 最適なソリューションと更新パラメータ
すべての適合度値(各ユニバースのインフレ率)を計算した後、すべての中から最適なソリューション(ベストユニバース)を選択します。 最適なソリューションは、すべてのユニバースで最小のフィットネス値を持つソリューションです。 結果として、は最初の反復に最適なソリューションです。 先に進んで、各ユニバースのパラメータと各ユニバースのパラメータを更新しましょう。
6.4. 宇宙の選択
以下の数学モデルに基づいて、ルーレットホイール選択メカニズムをホワイトホールとして使用して、N個の中から1つのユニバースを選択する必要があります。
間隔からランダムに選択される場所。 したがって、ホワイトホールにすべての中から1つを選択するには、以下の2つのルールを適用します。
- インフレ率の高い宇宙にはホワイトホールがあると考えられています。
- インフレ率の低い宇宙にはブラックホールがあると考えられています。
つまり、値が最も高いフィットネス値が唯一のホワイトホールを表します。 各反復で、フィットネス値に従ってユニバースを並べ替えます。 次の表は、1つのホワイトホールを2番目のユニバースとして選択し、他のユニバースはブラックホールを選択したことを示しています。
6.5. ワームホールトンネル
次に、輸送媒体を使用して、オブジェクトをホワイトホールのある宇宙からブラックホールのある宇宙に移動してみましょう。 この場合、ワームホールをトンネルとして使用して、異なるユニバース間でオブジェクトを交換します:
したがって、ワームホールは、以下の数学モデルに基づいて、異なる宇宙間の時間/空間移動トンネルとして機能します。
間隔からランダムに選択される場所。 その後、。 これは、で形成された最高の宇宙を意味します。
6.6. ベストユニバースを更新する
ここで、最大反復と現在の反復を確認してから、基準に達するまで上記の手順を繰り返します。 ループを繰り返した後、最適な値が得られました。 次に、最高の宇宙として表示します。
7. 結論
この記事では、そのメカニズムのロックを解除するための数値例を使用して、多元宇宙最適化アルゴリズムについて説明しました。 このアルゴリズムは、マルチバース理論に基づいた問題の最良の解決策を表す最良の宇宙を検索します。 このアルゴリズムを導入したのは、グローバルな制約なしおよび制約付き最適化の問題を解決するのに非常に効果的だからです。