1. 序章

このチュートリアルでは、比較的新しい自然に触発されたメタヒューリスティック最適化手法の詳細について説明します。 これは、深海でよく見られる海のサルパの群れ行動に触発されています。

これは活発な研究分野ですが、特定の最適化問題に役立つことがすでに証明されています。

2. サルパの群れとは何ですか？

サルパはサルパ科に属する樽型の板状の被嚢類です。 これは、動物界で最も効率的なジェット推進の例の1つを示しています。 これは、それが収縮して動くときであり、それによってそのゼラチン状の体を通して水を汲み上げます。

サルプの興味深い行動の1つは、サルプが互いに隣り合って整列することによって糸状のコロニーを形成するときです：

生物学的観点から、このサルプの群れ行動の理由については明らかではありません。 しかし、研究者たちは、これがより良い移動と採餌のために行われるかもしれないことを示しました。 サルパの群れをサルパチェーンと呼びますが、時には非常に巨大になることもあります。

3. なぜこれが私たちにとって興味深いのですか？

サルプは魅力的な生き物であり、自然の生息地でサルプをよりよく理解するために多くの研究がまだ進行中です。 しかし、最適化問題の利益のために、それらの群れの振る舞いは私たちに最も特有です。 重要なのは、複雑な最適化問題を解決する際にこの動作を模倣することです。 これが私たちにとって興味深い理由がわかります。

群知能は、分散型の自己組織化システムの集合的な動作です。 これらのシステムは、自然または人工の場合がありますが、通常、互いにローカルに相互作用する単純なエージェントとその環境で構成されます。 エージェントは単純なルールに従いますが、それらの相互作用はインテリジェントなグローバル動作の出現につながります。

実生活での最適化問題は、本質的に非常に複雑であることがよくあります。 それらが生成する検索空間は、限られた時間とリソースでグローバルに最適なソリューションを見つけるための数理計画法にとって非常に難しいことがよくあります。 これは、メタヒューリスティックがより少ない計算労力で適切なソリューションを見つけることを約束できる場所です。 ただし、グローバルに最適なソリューションを見つけることを保証するものではありません。

アリ、バッタ、クジラ、ミツバチ、ツチボタルなどの天然物質の群れ行動は、このような複雑な問題を解決するためのメタヒューリスティックを開発するために数年間研究されてきました最適化問題。 それらはすべて、複雑な問題を全体として解決することを示していますが、個別に解決することはできません。 たとえば、アリは、巣から遠く離れた場所でも協力して食料源を見つけることができます。

興味深いことに、特定のメタヒューリスティックは特定の最適化問題のセットを解決できますが、他のメタヒューリスティックではうまく機能しない可能性があります。 これがまさにこの分野の研究を繁栄させ続けるものです。 特定の最適化問題をより効率的に解決するために、サルパの群れの行動を学習してモデル化できるかどうかを理解しようとしています。

4. 数学的モデリング

コンセプト自体は非常に魅力的ですが、サルプの群れ行動を数学的にモデル化できない限り、どこにも連れて行かれません。 そうするための最も初期の試みの1つはによって提示されました S。 ミルジャリリ他 al。 彼らの研究論文で数年前に公開されました。 これを達成するために、彼らは群れの中のサルパの個体数をリーダーとフォロワーに分割することを提案しました：

上記の概略図からわかるように、単一のサルパ（a）が集まってサルパチェーン（b）を形成します。 数学的モデリングの目的で、サルパチェーンの運動方向の最初のサルパをリーダーサルパとして指定し、残りのサルパをフォロワーサルパとして指定します（c）。

まず、次元探索空間でのサルパの位置を定義します。ここで、は特定の問題の変数の数です。 すべてのサルパの位置をと呼ばれる2次元マトリックスに格納し、検索スペースのように食料源を指定できます。

これで、次の式を使用してリーダーサルパの位置を更新できます。

   

ここで、は第3次元のリーダーサルパの位置を示し、第3次元の食料源の位置を示します。 さらに、とはそれぞれth次元の上限と下限を表します。

また、、、は確率変数です。 ご覧のとおり、これらの係数のうち、は、探索と活用のバランスを取るのに役立つため、最も重要です。 この係数は次のように更新できます。

   

係数とは、区間で均一に生成される乱数です。 それらは、th次元の次の位置とステップサイズを決定します。

興味深いことに、リーダーサルパは食料源に関してその位置を更新するだけです。 フォロワーサルパは互いに対する位置を更新するため、最終的にリーダーサルパになります。

ニュートンの運動の法則からの方程式を使用して、フォロワーのサルプの位置を更新できます。 最適化問題の領域に適した特定の変更により、次の方程式に到達します。

   

ここで、は、th次元におけるthフォロワーサルパの位置を示します。

これらの方程式を使用して、最後に、サルパの群れの動作を数学的に合理的にシミュレートできます。 この数学的モデルを使用して、最適化問題を解くためのアルゴリズムを開発できます。

5. サルパスウォームアルゴリズム

サルパの群れの数学的モデルができたので、それを使用して、最適化問題のいくつかを解決するためのアルゴリズムを作成します。 もちろん、これらの問題を解決するためにモデルをそのまま使用することはできません。 目前の問題に合わせて、その一部を調整する必要があります。 最適化問題は、単一目的または多目的のいずれかである可能性があり、アルゴリズムはそれぞれに固有である必要があります。

5.1. 単一目的の問題

名前が示すように、単一目的最適化問題には、を追跡する目的が1つだけあります。 目的は、最大化または最小化することです。 これらはさらに、一連の等式または不等式の制約を持つことができます。 これらの問題は次のように数学的に定式化できます。

   

   

   

   

この定式化は、不等式制約と等式制約の対象となる、変数の数で目的関数を最小化するためのものです。 さらに、th変数には、それぞれ下限と上限があります。

サルパの群れの数学的モデルを使用してこの問題を解決するには、食料源を最適なグローバルソリューションに置き換えることから始めます。 これは事前にわからないので、これまでに得られた最良の解をグローバル最適と仮定し、これを追跡するサルパチェーンを仮定することができます。

したがって、サルパ群モデルを使用して単一目的最適化問題を解くためのアルゴリズムの擬似コードを取得します。

元の論文の著者は、このアルゴリズムを単一目的サルパ群アルゴリズム（SSA）と呼んでいます。 まず、ランダムな位置で複数のサルプを開始します。 次に、各サルパの適応度を計算して、最適なサルパを見つけます。 これに続いて、係数の更新とリーダーとフォロワーのサルプの位置の更新が行われます。 これが現在のグローバル最適になります。

現在、リーダーサルパは現在の最適なソリューションに関してのみその位置を更新するため、周囲のスペースの探索と活用が可能になります。 さらに、フォロワーサルプの段階的な動きは、局所的に最適なソリューションでの潜在的な停滞を防ぎます。 サルパチェーンは、複数の反復を通じて実際のグローバル最適に向かって移動する可能性があります。

5.2. 多目的問題

推測できるように、多目的問題には対処すべき複数の目的があり、すべての目的を同時に最適化する必要があります。 それらの数学的定式化は、単一の目的問題の定式化と非常に似ていますが、複数の目的があります。

   

   

   

   

ここで、前述のように、定式化には残りの説明を最小化する目的関数があります。

現在、単一の目的で、関係演算子を使用して候補ソリューションを比較することは非常に明確です。 ただし、複数の目的がある場合、これは非常に複雑になります。 このために、パレート最適優位性と呼ばれる概念を参照します。 これは数学的に次のように定義できます。

   

これは恐ろしいように見えるかもしれませんが、目的に等しく、少なくとも1つのより良い値がある場合に限り、によって表されるソリューションが別のソリューションよりも優れていることを示しています。 このような場合、ソリューションが他のソリューションを支配すると言われます。 それ以外の場合、ソリューションはパレート最適ソリューションまたは非優勢ソリューションであると言われます。

多目的最適化問題のパレート最適解のセットがあります。これをパレート最適セットと呼びます。 目的空間におけるパレート最適セットの投影は、パレート最適フロントと呼ばれます。

この種の問題を解決するためにサルパの群れの数学モデルを採用する最初のステップは、1つの最適なソリューションを最大制限の非優勢ソリューションのリポジトリに置き換えることです。 2番目のステップは、最も混雑していない近隣の非支配的なソリューションのセットから食料源を選択することです。

したがって、アルゴリズムの擬似コードを更新して、サルパ群モデルの多目的問題を次のように解決できます。

元の論文の著者は、このアルゴリズムを多目的サルパ群アルゴリズム（MSSA）と呼んでいます。 アルゴリズムは主にSSAについて前に説明したものと似ていますが、現在複数の目的を扱っていることに対応するためにいくつかの変更が加えられています。 最も重要な違いは、現在維持している非優勢ソリューションのリポジトリがあることです。

もちろん、このアルゴリズムには、まだ説明していない複雑さがあります。 たとえば、リポジトリがいっぱいで、リポジトリの居住者と比較して支配的ではないサルパを持っている状況に対処する方法。 アルゴリズムは、リポジトリ常駐と交換することを提案します。 しかし、削除するリポジトリ常駐を選択するにはどうすればよいですか？

隣接するソリューションの数に基づいて各リポジトリ常駐にランクを割り当て、ルーレット盤を選択してそのうちの1つを選択できます。 このアプローチは、反復の過程で常駐するリポジトリの分散を改善するのに役立ちます。 SSAのすべてのメリットを継承する一方で、このアルゴリズムは、パレート最適フロントの混雑の少ない領域に向けて検索を導きます。

6. 実用的なアプリケーション

サルパの群れに基づくアルゴリズムは活発な研究分野であり、進歩するにつれて新しい方法で役立つことがわかりました。 前に見たように、メタヒューリスティックアルゴリズムは通常、特定の最適化問題のセットでのみ他のアルゴリズムよりも優れたパフォーマンスを発揮します。 このようなアルゴリズムが、一般的なクラスの問題で他のアルゴリズムよりも優れているとは期待できません。

元の論文では、著者が一連の定性的指標を提示し、定量的結果を収集して、SSAを同様のアルゴリズムと比較しました。 彼らはまた、MSSAアルゴリズムを文献の同様のアルゴリズムと比較しました。 これらの比較の詳細な分析は、この記事の範囲を超えています。

ただし、著者は、特定のクラスの実際の問題におけるSSAおよびMSSAのパフォーマンスも示しています。 これらには、3つのバートラス設計問題、溶接梁設計問題、Iビーム設計問題、片持ち梁設計問題、引張/圧縮ばね設計問題などの古典的な最適化問題が含まれます。

これには、2次元翼型設計問題の解決にSSAを採用し、船舶用プロペラ設計問題にMSSAを採用することも含まれます。 結果から、SSAとMSSAがこれらの問題に最適な形状を見つけることができることが明らかです。 もちろん、この分野でのさらなる研究は、これらのアルゴリズムの効率を証明し、エクストリームマシンラーニング（ELM）の最適化のようなより実用的なアプリケーションを見つけるでしょう！

7. 結論

このチュートリアルでは、サルパの群れの詳細と、それらが最適化問題にどのように関心を持つことができるかを理解しました。 さらに、サルパの群れの数学的モデリングを行い、メタヒューリスティックアルゴリズムを作成するためにそれを適応させました。 これは、単一目的および多目的問題を解決するためのアルゴリズムをカバーしました。