メタファーベースのメタヒューリスティクスのリスト

これは、メタファーベースのメタヒューリスティックスと群知能アルゴリズムを、提案された 10 年ごとに時系列に並べたリストです。

シミュレーテッド アニーリングは、冶金学における熱処理方法であるアニーリングにヒントを得た確率的アルゴリズムです。検索空間が離散的である場合 (たとえば、特定の都市セットを訪れるすべてのツアー) によく使用されます。正確なグローバル最適値を見つけることよりも、一定の時間内に許容可能なローカル最適値を見つけることの方が重要な問題の場合、シミュレーテッド アニーリングは勾配降下法などの代替法よりも適している場合があります。

アニーリングの緩やかな冷却に類似しているのは、シミュレーテッド アニーリングがソリューション空間を探索するにつれて、より悪いソリューションを受け入れる可能性がゆっくりと減少することです。より悪いソリューションを受け入れることは、より広範囲にわたる最適ソリューションの検索を可能にするため、メタヒューリスティクスの基本的な特性です。

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

粒子群最適化は、与えられた品質基準に関して候補ソリューションを反復的に改善することで問題を最適化する計算方法です。これは、候補ソリューションの集団(粒子)を用意し、これらの粒子を、粒子の位置と速度に関する簡単な数式^{[どの? ]}に従って探索空間内で移動させることで問題を解決します。各粒子の動きはその局所的な最適位置の影響を受けますが、探索空間内の最適位置に向かって導かれ、他の粒子によってより良い位置が見つかると、それらの最適位置が更新されます。これにより、群れが最適ソリューションに向かって動くことが期待されます。

PSOはもともとケネディ、エバーハート、シー^{[4] [5]}に帰属し、最初は鳥の群れや魚の群れの生物の動きを様式化した表現として社会的行動^[6]をシミュレートする ことを目的としていました。アルゴリズムは簡略化され、最適化を実行していることが観察されました。ケネディとエバーハートの著書^{[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]}を参照のこと。

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

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

ミツバチアルゴリズムは、2005年にファムと彼の同僚によって策定され、 ^[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の主な用途については、Rabanalら（2017）の調査をご覧ください。^[35]

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

BAは、群知能ベースのアルゴリズムで、ミクロコウモリのエコーロケーション行動にヒントを得たものです。BAは、多次元探索空間でシミュレートされたコウモリの音の大きさとパルス放出率を制御することで、探索（1つの局所的最大値の周りで行き詰まるのを避けるためにグローバル探索空間を長距離ジャンプする）と活用（局所的最大値を見つけるために既知の良い解決策の周りをより詳細に探索する）のバランスを自動的にとります。^[39]

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

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

近年、最適化アルゴリズムの分野では、微調整が非常に長く困難なプロセスになる可能性があるため、自己調整メタヒューリスティックスが大きな進歩として登場しました。^[46]これらのアルゴリズムは、問題に応じてパラメータを自律的に調整し、効率とソリューションの品質を向上させる機能によって差別化されています。この自己調整機能は、従来の方法では厳格なパラメータ設定のために苦労する可能性のある複雑な最適化シナリオで特に重要です。

個々のメタファーに触発されたメタヒューリスティックスは特定の問題に対して驚くほど効果的な解決策を生み出してきたが、^[47]メタファーに触発されたメタヒューリスティックス全般は、その有効性や新規性の欠如を精巧なメタファーの背後に隠しているとして研究者の間で批判を集めてきた。^{[47] [48]}ケネス・ソーレンセンは次のように指摘している。^[49]

近年、組み合わせ最適化の分野では、まさに「斬新な」メタヒューリスティック手法の津波が押し寄せてきました。そのほとんどは、何らかの自然または人工のプロセスのメタファーに基づいています。事実上あらゆる種類の昆虫の行動、水の流れ、ミュージシャンの共演など、どんなアイデアも、新たなメタヒューリスティックを生み出すきっかけとなるには突飛すぎるものではないようです。[私は]この研究の流れが、メタヒューリスティックの分野を科学的厳密さから遠ざける恐れがあると主張します。

ソーレンセンとグローバーは次のように述べた^[50]

多数の（そして増加中の）出版物は、メタファーに基づく（と思われる）新しいメタヒューリスティック フレームワークの開発に焦点を当てています。メタヒューリスティック フレームワークの基礎として使用されてきた自然または人工のプロセスのリストには、バクテリアの採餌、河川の形成、生物地理学、ミュージシャンの共演、電磁気、重力、帝国による植民地化、鉱山の爆発、リーグ チャンピオンシップ、雲など、現在では多様なプロセスが含まれています。重要なサブカテゴリは、動物の行動に基づくメタヒューリスティックです。アリ、ハチ、コウモリ、オオカミ、ネコ、ホタル、ワシ、イルカ、カエル、サケ、ハゲワシ、シロアリ、ハエなど、すべてが「新しい」メタヒューリスティックを刺激するために使用されました。 [...] 一般的に、メタファーベースのメタヒューリスティクスに関する論文の発表は、二流のジャーナルや会議に限られていますが、最近ではこのルールの例外もいくつか見られます。Sörensen (2013) は、この方向の研究には根本的な欠陥があると述べています。最も重要なのは、著者が、基礎となるメタファーの新規性によって、結果として得られるフレームワークが自動的に「新規」になるわけではないと主張していることです。それどころか、メタファーベースの方法のほとんどが、興味深い意味で新しいものではないという証拠が増えています。

これに対して、シュプリンガーのジャーナル・オブ・ヒューリスティックスは編集方針を更新し、次のように述べている。^[51]

新しいパラダイムの提案は、遺伝的アルゴリズム、タブー探索、シミュレーテッドアニーリングなどの古典的なフレームワークに組み込まれているような革新的な基本的アイデアが含まれている場合にのみ受け入れられます。Journal of Heuristics では、自然または人工のシステムやプロセスのメタファーに基づいていると主張される方法に古いアイデアを再パッケージ化して組み込んだ記事の掲載を避けています。これらのいわゆる「新しい」方法では、インテリジェントな水滴、ジャズを演奏するミュージシャン、帝国主義社会、リープフロッグ、カンガルー、あらゆる種類の群れや昆虫、さらには地雷の爆破プロセスにまで及ぶアナロジーが採用されています (Sörensen、2013)。研究者が新しい方法についての独自のアイデアを刺激するためにメタファーを使用する場合、それでもその方法は、採用された戦略が明確に理解され、その新規性が明確にわかるように、メタファーのない言語に翻訳する必要があります (以下の項目 2 と 3 を参照)。メタファーは安価で簡単に手に入ります。方法を「見せかけ」るためにそれらを使用することは受け入れられません。」

[...] 実装は、標準的な最適化用語を使用して説明する必要があります。この場合、ソリューションは「ソリューション」と呼ばれ、わかりにくいメタファー (調和、ハエ、コウモリ、国など) に関連する他の何かと呼ばれることはありません。

[...] Journal of Heuristics は、メタファーベースの「新しい」方法は、その分野への貢献を示せない場合は出版すべきではないという Sörensen の見解を全面的に支持しています。既存の概念の名前を変更することは、貢献とはみなされません。これらの方法は「新しい」と言われることが多いですが、既存の方法論のわずかなバリエーションを除けば、新しいアイデアを提示するものはほとんどありません。これらの方法は、真に革新的なアイデアや研究のためにジャーナルのスペースを占有すべきではありません。標準的な最適化用語を使用していないため、理解するのが不必要に困難です。

シュプリンガーのジャーナル「4OR - A Quarterly Journal of Operations Research」のポリシーには次のように記されている。^[52]

科学的厳密さと革新性に重点を置くということは、特に、十分な検証なしに既知の方法の偽装されたバリエーションを単に提案するだけの論文 (たとえば、自然または人工のシステムやプロセスとの比喩的な比較のみに基づいて「効果的」であると主張するメタヒューリスティクス) はジャーナルに掲載しないことを意味します。新しい方法は、古典的なパラダイムとの関係を確立することにより、比喩のない言語で提示する必要があります。その特性は、数学的証明、制御された実験、客観的な比較など、科学的に説得力のある議論に基づいて確立する必要があります。

ACM Transactions on Evolutionary Learning OptimizationやEvolutionary Computation誌にも同様の記述がある。^{[53] [54]}

• 概念的メタファー
• 科学コミュニティの比喩
• メタヒューリスティックスの表

• セーレンセン、ケネス。マルク・セヴォー。フレッド・グローバー（2017-01-16）。 「メタヒューリスティックの歴史」(PDF)。マルティでは、ラファエル。パノス、パルダロス。レゼンデ、マウリシオ(編)。ヒューリスティックのハンドブック。スプリンガー。ISBN 978-3-319-07123-7。
• Sörensen, Kenneth (2015). 「メタヒューリスティックス - メタファーの暴露」.国際オペレーショナルリサーチ取引. 22 : 3–18. CiteSeerX  10.1.1.470.3422 . doi :10.1111/itor.12001. S2CID  14042315.
• Lones, Michael A. ( 2014)。「自然にヒントを得たアルゴリズムのメタヒューリスティック」。遺伝的および進化的計算コンパニオンに関する 2014 年会議コンパニオンの議事録 - GECCO Comp '14。pp. 1419–22。CiteSeerX 10.1.1.699.1825。doi :  10.1145 /2598394.2609841。ISBN 9781450328814. S2CID  14997975。
• フィスター、イズトク。ヤン、シンシェ。フィスター、イズトク。ブレスト、ジャネス。フィスター、ドゥシャン (2013)。 「自然にヒントを得た最適化アルゴリズムの簡単なレビュー」。エレクトロテニシュキ ヴェストニク。arXiv : 1307.4186。

• 進化的計算ベストイアリ – 学術出版の広い世界に存在する、メタファーに基づく奇妙なメタヒューリスティクスのすべてを冗談交じりに解説します。
• サイエンスマトリックスのメタヒューリスティックリスト^{[リンク切れ‍ ]}  – 名前、著者、年でフィルタリング可能なメタヒューリスティックアルゴリズムの完全なリスト。各アルゴリズムの主な出版物へのリンクも提供しています。