メタヒューリスティック

コンピュータサイエンスと数理最適化において、メタヒューリスティックとは、特に不完全または不完全な情報や限られた計算能力がある場合に、最適化問題または機械学習問題に対する十分に優れた解を提供できるヒューリスティック（部分探索アルゴリズム）を見つけ、生成し、調整し、選択するように設計された高レベルの手順またはヒューリスティックです。 ^{[1] [2]}メタヒューリスティックは、完全に列挙したり探索したりするには大きすぎる解のサブセットをサンプリングします。メタヒューリスティックは、解決する最適化問題について比較的少ない仮定を行う可能性があるため、さまざまな問題に使用できます。^{[3] [4] [5] [6]}計算時間が長すぎるか、提供された解が不正確すぎるなどの理由で、正確な方法や他の（近似）方法が利用できない、または適切でない場合、メタヒューリスティックの使用は常に興味深いものです。

最適化アルゴリズムや反復法と比較すると、メタヒューリスティックスは、ある種の問題でグローバルに最適な解が見つかることを保証しません。 ^[3]多くのメタヒューリスティックスは、何らかの形の確率的最適化を実装しているため、見つかった解は生成されたランダム変数の集合に依存します。^[2]組合せ最適化では、 NP完全問題のクラスに属する問題が多くあり、比較的低い複雑度では許容時間内に正確に解くことができなくなります。^{[7] [8]}そのため、メタヒューリスティックスは、近似法、反復法、または単純なヒューリスティックスよりも少ない計算量で優れた解を提供することがよくあります。^{[3] [4]}これは、連続または混合整数最適化の分野にも当てはまります。^{[4] [9] [10]}このように、メタヒューリスティックスは最適化問題に対する有用なアプローチです。^[2]このテーマについては、いくつかの書籍と調査論文が出版されています。^{[2] [3] [4] [11] [12]}メタヒューリスティック最適化に関する文献レビュー^[13]では、メタヒューリスティックスという言葉を作ったのはフレッド・グローバーであると示唆されている。^[14]

メタヒューリスティックスに関する文献のほとんどは実験的な性質のものであり、アルゴリズムを用いたコンピュータ実験に基づく経験的結果を説明しています。しかし、収束や大域的最適値を見つける可能性に関する正式な理論的結果もいくつかあります。^{[3] [15]}また、特定の問題に対して他のすべてのメタヒューリスティックよりも優れたメタヒューリスティックは存在しないという、 ノーフリーランチ定理も言及する価値があります。

特に2000年代に入ってからは、多くのメタヒューリスティック手法が、新規性と実用的有効性を主張して発表されてきた。この分野では質の高い研究も行われているが、最近の出版物の多くは質が低く、曖昧さ、概念の詳細化の欠如、実験の質の悪さ、先行文献の無視などの欠点がある。^{[16] [17]}

これらはほとんどのメタヒューリスティックスを特徴付ける特性である: ^[3]

• メタヒューリスティックスは、検索プロセスを導く戦略です。
• 目標は、最適または最適に近いソリューションを見つけるために、検索空間を効率的に探索することです。
• メタヒューリスティック アルゴリズムを構成する技術は、単純なローカル検索手順から複雑な学習プロセスまで多岐にわたります。
• メタヒューリスティックアルゴリズムは近似的であり、通常は非決定論的です。
• ^{メタヒューリスティクスは特定の問題に特化するものではありません。しかし、連続問題[18] [19]}や組合せ最適化^[20]などの問題クラスに関連して開発され、その後一般化されたケースもあります。^{[21] [22]}
• メタヒューリスティックの高レベル戦略によって制御されるヒューリスティックの形でドメイン固有の知識を活用できます。
• 検索空間の特定の領域で行き詰まるのを防ぐメカニズムを含めることができます。
• 現代のメタヒューリスティックでは、検索を制御するために検索履歴がよく使用されます。

メタヒューリスティックにはさまざまな種類があり^{[2] [4]}、それらを分類するための特性も数多くあります。^{[3] [24] [25] [26]}したがって、以下のリストは例として理解されるべきです。

1つのアプローチは、探索戦略のタイプを特徴付けることです。^[3]探索戦略の1つのタイプは、単純な局所探索アルゴリズムの改良です。よく知られている局所探索アルゴリズムは、局所最適解を見つけるために使用されるヒルクライミング法です。ただし、ヒルクライミングでは、グローバル最適解が見つかるとは限りません。

より良い解決策を見つけるために、局所探索ヒューリスティックを改善するメタヒューリスティックのアイデアが数多く提案されました。このようなメタヒューリスティックには、シミュレーテッドアニーリング、タブー探索、反復局所探索、可変近傍探索、GRASPなどがあります。^[3]これらのメタヒューリスティックは、局所探索ベースまたはグローバル探索メタヒューリスティックに分類できます。

局所探索ベースではない他のグローバル探索メタヒューリスティックは、通常、集団ベースのメタヒューリスティックです。このようなメタヒューリスティックには、アリコロニー最適化、遺伝的アルゴリズムや進化戦略などの進化計算、粒子群最適化、ライダー最適化アルゴリズム^{[27] 、バクテリア採餌アルゴリズム[28]}などがあります。

もう 1 つの分類次元は、単一解と集団ベースの探索です。^{[3] [12]}単一解アプローチは、単一の候補解の修正と改善に重点を置いています。単一解のメタヒューリスティックには、シミュレーテッド アニーリング、反復局所探索、可変近傍探索、ガイド付き局所探索が含まれます。^[12]集団ベースのアプローチは、多くの場合、集団の特性を使用して探索をガイドし、複数の候補解を維持および改善します。集団ベースのメタヒューリスティックには、進化計算と粒子群最適化が含まれます。 [12]メタヒューリスティックの別のカテゴリは、集団または群れ内の分散型の自己組織化エージェントの集合的な行動である群知能です。蟻コロニー最適化、^[29]粒子群最適化、^[12]社会的認知最適化、細菌採餌アルゴリズム^[28]はこのカテゴリの例です。

ハイブリッド メタヒューリスティックとは、数理計画法、制約プログラミング、機械学習のアルゴリズムなど、他の最適化手法とメタヒューリスティックを組み合わせたものです。ハイブリッド メタヒューリスティックの両方のコンポーネントは同時に実行され、検索をガイドするために情報を交換します。

一方、ミームアルゴリズム^{[30]は、進化的アプローチや集団ベースのアプローチと、問題探索のための個別の個別学習または局所的改善手順との相乗効果を表しています。ミームアルゴリズムの例としては、進化的アルゴリズムにおける基本的な}突然変異演算子の代わりに、またはそれに加えて局所探索アルゴリズムを使用することが挙げられます。

並列メタヒューリスティックとは、並列プログラミングの手法を使用して複数のメタヒューリスティック検索を並列に実行するもので、単純な分散スキームから、相互作用して全体的なソリューションを改善する同時検索実行までの範囲にわたります。

集団ベースのメタヒューリスティックでは、個体またはグループをそれぞれ別のスレッドで処理するか、メタヒューリスティック自体を1台のコンピュータで実行して子孫を反復ごとに分散的に評価することで、集団自体を並列化できます。^[31]後者は、評価の計算量が子孫の生成の計算量よりもかなり大きい場合に特に便利です。これは多くの実用的なアプリケーション、特にシミュレーションベースのソリューション品質の計算に当てはまります。^{[32] [33]}

非常に活発な研究分野は、自然にヒントを得たメタヒューリスティックスの設計です。最近のメタヒューリスティックス、特に進化的計算ベースのアルゴリズムの多くは、自然システムからヒントを得ています。自然は、複雑な計算問題に対処するための人工計算システムを設計するための概念、メカニズム、原理の源泉として機能します。このようなメタヒューリスティックスには、シミュレーテッド アニーリング、進化的アルゴリズム、アント コロニー最適化、粒子群最適化などがあります。

最近のメタファーにヒントを得たメタヒューリスティクスの多くは、その新規性の欠如を手の込んだメタファーで隠しているとして、研究コミュニティから批判を集め始めている。 ^{[16] [17] [25]}その結果、この分野の著名な科学者の多くが、メタヒューリスティクスをより比較しやすいものにするために、メタヒューリスティクスの標準化のための研究課題を提案している。^[34]もう1つの結果として、多くの科学雑誌の出版ガイドラインがそれに応じて改訂された。^{[35] [36] [37]}

ほとんどのメタヒューリスティクスは検索方法であり、それらを使用する場合、評価関数は数学的最適化よりも高い要件に従う必要があります。望ましいターゲット状態を定式化する必要があるだけでなく、評価では、検索プロセスをサポートして加速するために、ターゲットまでの途中でソリューションの改善を評価する必要があります。進化的アルゴリズムまたはミーム的アルゴリズムの適応関数が例として挙げられます。

メタヒューリスティクスは、連続問題から混合整数問題、組合せ最適化、またはそれらの組み合わせに至るまで、あらゆる種類の最適化問題に使用されます。 ^{[9] [38] [39]組合せ最適化では、}離散的な探索空間で最適解が求められます。一例として巡回セールスマン問題が挙げられますが、この問題では、候補解の探索空間が問題のサイズが大きくなるにつれて指数関数よりも速く増加し、最適解を徹底的に探索することが不可能になります。 ^{[40] [41]}さらに、形状探索や動作探索などの工学におけるほとんどの設計問題^{[6] [42] [43] [44]を含む多次元の組合せ問題は}次元の呪いに悩まされており、これもまた徹底的な探索や分析手法には実行不可能な問題となっています。

メタヒューリスティクスは、スケジューリング問題にも頻繁に適用されます。この組み合わせタスク クラスの代表的なものはジョブ ショップ スケジューリングです。これは、すべてのジョブが時間どおりに、かつ全体として可能な限り最短時間で完了するように、ジョブの作業ステップを処理ステーションに割り当てます。^{[5] [45]実際には、たとえば、定義済みのワークフロー[46]}を通じてジョブの作業ステップの許容されるシーケンスを制限したり、たとえばエネルギー需要を平滑化する形でリソースの使用率に関して制限したりするなど、制約を遵守しなければならないことがよくあります。 ^{[47] [48]}組み合わせ問題に対する一般的なメタヒューリスティクスには、Holland らによる遺伝的アルゴリズム^[49] 、Glover による散布探索^[50]、タブー探索^[51]などがあります。

もう一つの大きな応用分野は、連続または混合整数探索空間における最適化タスクである。これには、例えば、設計最適化^{[6] [52] [53]}やさまざまなエンジニアリングタスクが含まれる。^{[54] [55] [56]}組み合わせ最適化と連続最適化を組み合わせた例としては、産業用ロボットの好ましい動作経路の計画がある。^{[57] [58]}

MOFは、「メタヒューリスティックスのセットの正確で再利用可能な実装と、提供された技術を使用して特定の問題インスタンスを解決するために必要な、パートナーの従属ヒューリスティックス（ソリューションエンコーディングと技術固有の演算子を含む可能性がある）の実装を加速するための基本メカニズムを提供するソフトウェアツールのセット」と定義できます。^[59]

さまざまな機能を持つ MOF として考えられる最適化ツールの候補は多数あります。次の 33 個の MOF は、^[59] Comet、EvA2、evolvica、Evolutionary::Algorithm、GAPlayground、jaga、JCLEC、JGAP、jMetal、n-genes、Open Beagle、Opt4j、ParadisEO/EO、Pisa、Watchmaker、FOM、Hypercube、HotFrame、Templar、EasyLocal、iOpt、OptQuest、JDEAL、Optimization Algorithm Toolkit、HeuristicLab、MAFRA、Localizer、GALIB、DREAM、Discropt、MALLBA、MAGMA、UOF で詳細に比較および評価されています。並列実装のサポートに関する出版物は多数ありますが、特に 10 年代後半以降は、この比較研究では欠けていました。^{[32] [33] [60] [61] [62]}

さまざまなメタヒューリスティックスが存在し、新しい変種が継続的に提案されています。この分野への最も重要な貢献のいくつかは次のとおりです。

• 1952年: ロビンスとモンローが確率的最適化手法の研究を行う。^[63]
• 1954年:バリチェリは進化プロセスの最初のシミュレーションを実行し、それを一般的な最適化問題に適用しました。^[64]
• 1963年: ラストリギンがランダム探索を提案。^[65]
• 1965年: マティアスがランダム最適化を提案^[66]
• 1965年:ネルダーとミードは単体ヒューリスティックを提案し、パウエルはそれがいくつかの問題において非定常点に収束することを示した。 ^[67]
• 1965年:インゴ・レッヒェンベルグが最初の進化戦略アルゴリズムを発見。^[68]
• 1966年:フォーゲルらが進化プログラミングを提案^[69]
• 1970年: ヘイスティングスがメトロポリス・ヘイスティングスのアルゴリズムを提案した。^[70]
• 1970年: カヴィッキオは最適化装置の制御パラメータの適応を提案した。^[71]
• 1970年: カーニハンとリンは、可変深度探索と禁止ベース（タブー）探索に関連するグラフ分割法を提案した。^[72]
• 1975年:ホランドが遺伝的アルゴリズムを提案した。^[49]
• 1977年:グローバーが散布探索法を提案。^[50]
• 1978年: マーサーとサンプソンは、別のオプティマイザを使用してオプティマイザのパラメータを調整するためのメタプランを提案した。 ^[73]
• 1980年: スミスが遺伝的プログラミングについて説明[ 74 ^]
• 1983年: カークパトリックらがシミュレーテッドアニーリングを提案した。^[75]
• 1986年：グローバーがタブー探索を提案し、メタヒューリスティックという用語が初めて登場した。^[51]
• 1989年: モスカートがミームアルゴリズムを提案^[30]
• 1990年: MoscatoとFontanari ^[76]とDueckとScheuer ^[77]はそれぞれ独立して、探索を加速するシミュレーテッドアニーリングの決定論的更新規則を提案した。これにより閾値受容メタヒューリスティックが生まれた。
• 1992年:ドリゴは博士論文でアリコロニー最適化を紹介した。 ^[29]
• 1995年: ウォルパートとマクレディがフリーランチ定理を証明。^{[78] [79] [80] [81]}

• 確率的探索
• メタ最適化
• 数学
• ハイパーヒューリスティック
• 群知能
• 進化的アルゴリズム、特に遺伝的アルゴリズム、遺伝的プログラミング、または進化戦略。
• シミュレーテッドアニーリング
• 労働力モデリング

• セーレンセン、ケネス。マルク・セヴォー。フレッド・グローバー（2017-01-16）。 「メタヒューリスティックの歴史」(PDF)。マルティでは、ラファエル。パノス、パルダロス。レゼンデ、マウリシオ(編)。ヒューリスティックのハンドブック。スプリンガー。ISBN 978-3-319-07123-7。
• Ashish Sharma (2022)、「ランダム化されたハイパーコンピューティングの観点から見た自然にインスパイアされたアルゴリズム」。情報科学。https ://doi.org/10.1016/j.ins.2022.05.020。

• Fred Gloverおよび Kenneth Sörensen (編)。「メタヒューリスティックス」。Scholarpedia。
• この分野の研究者のための EU/ME フォーラム。
• Metaheuristics.jl いくつかの実装のソース。