比喩に基づくメタヒューリスティクスのリスト

シミュレーテッドアニーリングは、冶金における熱処理法であるアニーリングに着想を得た確率的アルゴリズムです。探索空間が離散的である場合（例えば、特定の都市群を訪れるすべての経路）によく用いられます。厳密な全体最適解を見つけることよりも、一定時間内に許容できる局所最適解を見つけることが重要な問題においては、シミュレーテッドアニーリングは勾配降下法などの代替手法よりも好ましい場合があります。

焼きなまし法の緩やかな冷却に相当するのは、シミュレーテッドアニーリングが解空間を探索するにつれて、より悪い解を受け入れる確率が徐々に減少していくことである。より悪い解を受け入れることは、メタヒューリスティクスの基本的な特性であり、最適な解をより広範囲に探索することを可能にする。

アリコロニー最適化アルゴリズムは、グラフ内の最適な経路を見つけることに帰着する計算問題を解決するための確率的手法です。1992年にMarco Dorigoが博士論文で最初に提案した^{[ 1 ] [ 2 ]}最初のアルゴリズムは、アリがコロニーと食料源の間の経路を探す行動に基づいて、グラフ内の最適な経路を探すことを目的としていました。この元のアイデアはその後、より広いクラスの数値問題を解決するために多様化し、その結果、アリの行動のさまざまな側面を利用したいくつかの問題が出現しました。より広い視点から見ると、ACO はモデルベースの探索^{[ 3 ]}を実行し、分布推定アルゴリズムといくつかの類似点を共有しています。

粒子群最適化は、与えられた品質基準に基づいて候補解を反復的に改善することで問題を最適化する計算手法です。この手法では、粒子と呼ばれる候補解の集団を用意し、粒子の位置と速度に関する単純な数式に従って探索空間内でこれらの粒子を移動させることで問題を解決します。各粒子の動きは、その粒子の局所的な最適位置によって影響を受けるだけでなく、他の粒子によってより良い位置が発見されるたびに更新される、探索空間内の最適位置へと導かれます。これにより、群全体が最適な解へと向かうことが期待されます。

PSOは元々Kennedy、Eberhart、Shi ^{[ 4 ] [ 5 ]}に帰属し、当初は鳥の群れや魚の群れにおける生物の動きを様式化して表現することで社会的行動をシミュレートする ことを目的としていました^{[ 6 ]}。アルゴリズムは簡略化され、最適化を実行していることが観察されました。KennedyとEberhartの著書^{[ 7 ]}では、PSOと群知能の多くの哲学的側面が説明されています。PSOの応用に関する広範な調査はPoliによって行われています^{[ 8 ] [ 9 ]}。PSOに関する理論的および実験的研究の包括的なレビューはBonyadiとMichalewiczによって発表されています^{[ 10 ] 。}

ハーモニーサーチは、2001 年に Zong Woo Geem、Joong Hoon Kim、および GV Loganathan ^{[ 11 ]}によって導入された現象模倣メタヒューリスティックであり、ジャズミュージシャンの即興演奏プロセスに触発されています。HS アルゴリズムでは、可能な解のセットがランダムに生成されます (ハーモニーメモリと呼ばれます)。新しい解は、ハーモニーメモリ内のすべての解を使用して生成され (GA で使用される 2 つだけではなく)、この新しい解がハーモニーメモリ内の最悪の解よりも優れている場合、最悪の解はこの新しい解に置き換えられます。HS の有効性と利点は、都市水道配水ネットワークの設計^{[ 12 ]} 、構造設計^{[ 13 ]} 、電気工学における負荷配分問題^{[ 14 ]} 、多目的最適化[ ^{15 ]}、名簿作成問題^{[ 16 ]} 、クラスタリング^{[ 17 ]}、分類および特徴選択などのさまざまなアプリケーションで実証されて^います。^{[ 18 ] [ 19 ]} HS の応用に関する詳細な調査は^{[ 20 ] [ 21 ]で見つけることができます。また、データ マイニングにおける HS の応用は[ 22 ]}で見つけることができます。

Dennis (2015) は、ハーモニーサーチは進化戦略アルゴリズムの特殊なケースであると主張した。^{[ 23 ]}しかし、Saka らは、進化戦略の構造はハーモニーサーチの構造とは異なると主張している。^{[ 24 ]}

人工蜂コロニーアルゴリズムは、ミツバチの採餌行動をシミュレートするメタヒューリスティックで、2005年にKarabogaによって導入されました^{[ 25 ]}。ABCアルゴリズムには、働き蜂、観察蜂、偵察蜂の3つのフェーズがあります。働き蜂フェーズと観察蜂フェーズでは、働き蜂フェーズでの決定論的選択と観察蜂フェーズでの確率的選択に基づいて選択された解の近傍で局所探索によって資源を利用します。偵察蜂フェーズは、採餌過程でミツバチが枯渇した食料源を放棄するのと類似しており、探索の進行にもはや有益でない解は放棄され、代わりに新しい解が挿入されて探索空間の新しい領域が探索されます。このアルゴリズムは、探索と利用のバランスの取れた能力を備えています。

ミツバチアルゴリズムは、2005年にPhamと彼の同僚によって考案され^{[ 26 ]}、2009年にさらに改良されました^{[ 27 ]。}ミツバチの採餌行動をモデルにしたこのアルゴリズムは、グローバルな探索とローカルな活用を組み合わせたものです。少数の人工ミツバチ（偵察蜂）が、適応度の高い解（収益性の高い食料源）を求めて解空間（環境）をランダムに探索する一方、大部分のミツバチは、適応度最適解を探して最も適応度の高い解の近傍を探索（収穫）します。生物のミツバチの尻振りダンスをシミュレートする決定論的な募集手順を使用して、偵察蜂の発見を採餌蜂に伝え、ローカル探索用に選択された近傍の適応度に応じて採餌蜂を分配します。解の近傍での探索が停滞すると、ローカルな適応度最適解が見つかったとみなされ、その場所は放棄されます。

帝国主義的競争アルゴリズム（ICA）は、進化計算分野のほとんどの手法と同様に、最適化プロセスにおいて関数の勾配を必要としません。特定の観点から見ると、ICAは遺伝的アルゴリズム（GA）の社会版と考えることができます。ICAは人間の社会進化の数学的モデルであり、コンピュータシミュレーションである一方、GAは種の生物学的進化に基づいています。

このアルゴリズムは、最適化問題の探索空間でランダムな候補解のセットを生成することから始まります。生成されたランダムな点は、初期国と呼ばれます。このアルゴリズムにおける国は、 GA の染色体や粒子群最適化の粒子に相当し、最適化問題の候補解の値の配列です。最適化問題のコスト関数は、各国の力を決定します。その力に基づいて、最良の初期国 (コスト関数の値が最小の国) の一部が帝国主義者となり、他の国 (植民地と呼ばれる) を支配し始め、初期帝国を形成します。^{[ 28 ]}

このアルゴリズムの主な操作は同化と革命の2つです。同化は、各帝国の植民地を社会政治的特性の空間（最適化探索空間）において帝国主義国家に近づけます。革命は、探索空間における一部の国の位置に突然ランダムな変化をもたらします。同化と革命の過程で、植民地はより良い位置に到達し、その後、帝国全体を支配して帝国の現在の帝国主義国家に取って代わる機会を得る可能性があります。^{[ 29 ]}

帝国主義的競争もこのアルゴリズムの一部です。すべての帝国はこのゲームに勝ち、他の帝国の植民地を奪おうとします。アルゴリズムの各ステップでは、帝国の力に基づいて、すべての帝国が最も弱い帝国の1つ以上の植民地を支配するチャンスがあります。^{[ 28 ]}

アルゴリズムは、停止条件が満たされるまで、前述のステップ（同化、革命、競争）を繰り返します。

上記の手順は、以下の擬似コードにまとめることができます。^{[ 30 ] [ 29 ]}

0) 目的関数を定義する:${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$ 1) アルゴリズムの初期化。探索空間内でランダムな解を生成し、初期帝国を作成します。 2) 同化: 植民地はさまざまな方向に帝国主義国家に向かって移動します。 3) 革命：一部の国の特徴にランダムな変化が生じる。 4) 植民地と帝国主義国との間の位置交換。帝国主義国よりも有利な位置にある植民地は、 既存の帝国主義者を交代させることで、帝国の支配権を奪うチャンスがある。 5) 帝国主義的競争: すべての帝国主義者は、互いの植民地を奪い合うために競争する。 6) 無力な帝国を排除する。弱い帝国は徐々に力を失い、最終的には消滅する。 7) 停止条件が満たされている場合は停止し、満たされていない場合は2に進みます。 8) 終了

河川形成ダイナミクスは、水が地面を侵食して堆積物を堆積させることで河川を形成する仕組みを模倣することに基づいています（水滴は群れとして機能します）。水滴が場所の高度を増減させることで地形を変化させた後、高度が減少する経路の形で解が与えられます。減少勾配が構築され、これらの勾配に続いて後続の水滴が新しい勾配を構成し、最良の勾配を強化します。このヒューリスティック最適化手法は、2007 年に Rabanal らによって提案されました^{[ 31 ]} 。RFDの他の NP 完全問題への適用可能性が研究されており^{[ 32 ] 、このアルゴリズムはルーティング[ 33 ]}やロボットナビゲーション^{[ 34 ]}などの分野に適用されています。RFDの主な応用例は、2017 年に Rabanal らが実施した調査で見つけることができます^{[ 35 ] 。}

重力探索アルゴリズムは、重力の法則と質量間の相互作用の概念に基づいています。GSAアルゴリズムはニュートン力学の理論を使用し、その探索エージェントは質量の集合です。GSAでは、質量の孤立系が存在します。重力を使用することで、システム内のすべての質量は他の質量の状況を見ることができます。したがって、重力は異なる質量間で情報を伝達する方法です。^{[ 36 ]} GSAでは、エージェントはオブジェクトとみなされ、そのパフォーマンスは質量によって測定されます。これらのオブジェクトはすべて重力によって互いに引き合い、この力によってすべてのオブジェクトがより重い質量を持つオブジェクトに向かって移動します。質量が大きいほど、問題のより良い解に対応します。エージェントの位置は問題の解に対応し、その質量は適合度関数を使用して決定されます。時間の経過とともに、質量は最も重い質量に引き寄せられ、理想的には探索空間で最適な解を示します。 GSAは、ニュートンの重力と運動の法則に従う質量の小さな人工世界と考えることができる。^{[ 37 ]} GSAの多目的バリアントであるMOGSAは、2010年にHassanzadehらによって提案された。^{[ 38 ]}

コウモリアルゴリズムは、コウモリのエコーロケーション行動に着想を得た群知能ベースのアルゴリズムです。BAは、多次元探索空間におけるシミュレーションされたコウモリの音量とパルス放出率を制御することで、探索（局所最大値付近で立ち往生しないように、グローバル探索空間を長距離ジャンプすること）と活用（局所最大値を見つけるために、既知の良好な解の周辺をより詳細に探索すること）のバランスを自動的に取ります。^{[ 39 ]}

自然界の螺旋現象に着想を得た螺旋最適化アルゴリズムは、目的関数勾配を持たない多点探索アルゴリズムです。これは、決定論的動的システムとして記述できる複数の螺旋モデルを使用します。探索点が現在の最良点として定義される共通中心に向かって対数螺旋軌道をたどるにつれて、より良い解が見つかり、共通中心が更新されます。^{[ 40 ]}

人工群知能は、インターネットを介して接続された人間のユーザーによるリアルタイムのクローズドループシステムであり、自然界の群れをモデルにしたフレームワークで構築されているため、グループの集合知が統一された創発知能として呼び起こされます。^{[ 41 ] [ 42 ]}このように、人間の群れは、さまざまな選択肢を集合的に探索し、同期して好ましい解決策に収束することで、質問に答え、予測を行い、意思決定を行い、問題を解決できます。2014 年にルイス・ローゼンバーグ博士によって発明された ASI 手法は、群れの個々のメンバーよりも優れた正確な集合的予測を行う能力で注目されています。^{[ 43 ]} 2016 年、 Unanimous AIの人工群知能グループは、ケンタッキーダービーの勝者を予測するように記者から挑戦を受けました。彼らは、540 対 1 のオッズを破り、上位 4 頭を順番に正しく選びました。^{[ 44 ] [ 45 ]}