ハイパーヒューリスティック

ハイパーヒューリスティックとは、多くの場合機械学習技術を組み込むことによって、いくつかのより単純なヒューリスティック（またはそのようなヒューリスティックのコンポーネント）を選択、組み合わせ、生成、または適応するプロセスを自動化し、計算検索問題を効率的に解決しようとするヒューリスティック検索方法です。ハイパーヒューリスティックを研究する動機の1つは、1つの問題を解決するのではなく、問題のクラスを処理できるシステムを構築することです。^[1]^[2]^[3]

問題を解決するために選択できるヒューリスティックは複数ある場合があり、各ヒューリスティックにはそれぞれ長所と短所があります。その考え方は、既知のヒューリスティックの長所を組み合わせ、短所を補うことで、自動的にアルゴリズムを考案することです。^[4]典型的なハイパーヒューリスティックフレームワークには、高レベルの方法論と一連の低レベルのヒューリスティック（構成的または摂動的なヒューリスティック）があります。問題インスタンスが与えられると、高レベルの方法は、特徴によって決定される現在の問題状態（または検索段階）に応じて、特定の時点でどの低レベルのヒューリスティックを適用するかを選択します。^[2]^[5]^[6]

ハイパーヒューリスティックとメタヒューリスティック

メタヒューリスティックとハイパーヒューリスティックの基本的な違いは、メタヒューリスティックの実装のほとんどが問題解決の検索空間内を検索するのに対し、ハイパーヒューリスティックは常にヒューリスティックの検索空間内を検索することです。したがって、ハイパーヒューリスティックを使用する場合、問題を直接解決しようとするのではなく、特定の状況で適切な方法またはヒューリスティックのシーケンスを見つけようとします。さらに、単一の問題インスタンスを解決するのではなく、一般的に適用可能な方法論を探しています。

ハイパーヒューリスティックは、「オーダーメイド」のメタヒューリスティックとは対照的に、「既成」の方法とみなすことができます。ハイパーヒューリスティックは、実装が容易な一連の低レベルのヒューリスティックに基づいて、許容できる品質のソリューションを生成する汎用的な方法を目指しています。

モチベーション

これまで、さまざまなアプリケーション領域の検索方法の構築において大きな進歩が見られてきましたが、このようなアプローチでは、特定の問題領域で専門家が専門知識を統合する必要があります。コンピューターサイエンス、人工知能、オペレーションズリサーチの多くの研究者は、このような状況で人間の専門家の役割に代わる自動化システムの開発の必要性をすでに認識しています。ヒューリスティックの設計を自動化するための主要なアイデアの 1 つは、機械学習メカニズムをアルゴリズムに組み込んで、検索を適応的にガイドすることです。学習プロセスと適応プロセスはどちらも、オンラインまたはオフラインで実現でき、建設的または摂動的なヒューリスティックに基づくことができます。

ハイパーヒューリスティックは通常、探索方法論におけるドメイン知識の量を減らすことを目的としています。結果として得られるアプローチは、実装が安価で迅速で、問題ドメインまたはヒューリスティック手法のどちらかに対する専門知識が少なくて済み、（理想的には）さまざまなドメインのさまざまな問題インスタンスを効果的に処理できるほど堅牢である必要があります。目標は、おそらくテーラーメイドのメタヒューリスティックアプローチと比較してソリューションの品質が低下する（ただし、まだ許容できる）という代償を払って、意思決定支援方法論の一般性のレベルを上げることです。^[7]テーラーメイドスキームとハイパーヒューリスティックベースの戦略のギャップを縮小するために、並列ハイパーヒューリスティックが提案されています。^[8]

起源

「ハイパーヒューリスティック」という用語は、2000 年の出版物で Cowling と Soubeiga によって初めて造られ、この用語は「ヒューリスティックを選択するためのヒューリスティック」というアイデアを説明するために使用されました。^[9]彼らは、次に使用するヒューリスティックを選択する際に、活用と探索をトレードオフする「選択関数」機械学習アプローチを使用しました。^[10]その後、Cowling、Soubeiga、Kendall、Han、Ross などの著者は、進化アルゴリズムや病的な低レベルヒューリスティックなどの分野でこのアイデアを調査し、拡張しました。この用語を使用した最初のジャーナル記事は 2003 年に発表されました。^[11]このアイデア (用語ではありません) の起源は 1960 年代初頭にまで遡ることができ^[12]^[13]、1990 年代に何度か独立して再発見され、拡張されました。^[14]^[15]^[16]ジョブショップスケジューリングの分野では、フィッシャーとトンプソンによる先駆的な研究^[12]^[13]で、確率学習を使用して、組み合わせたスケジューリングルール (優先順位ルールまたはディスパッチルールとも呼ばれる) が、個別に採用されたルールよりも優れているという仮説を立て、実験的に証明しました。当時は「ハイパーヒューリスティック」という用語は使用されていませんでしたが、これが最初の論文でした。ハイパーヒューリスティックの概念に影響を与えたもう 1 つのルーツは、人工知能の分野にあります。より具体的には、自動計画システムに関する研究から生まれ、最終的には制御知識の学習の問題に焦点を当てるようになりました。グラッチらによって開発されたいわゆる COMPOSER システム^[17]^[18]は、多数の地球周回衛星と 3 つの地上局を含む衛星通信スケジュールの制御に使用されました。このシステムは、可能な制御戦略の空間における山登り探索として特徴付けることができます。

アプローチの分類

これまでのところ、ハイパーヒューリスティックなアプローチは、2つの主なカテゴリに分類できます。最初のクラスは、ヒューリスティックを選択するためのヒューリスティックというフレーズで表現され、^[9]^[10]、ハイパーヒューリスティックフレームワークには、対象の問題を解決するための既存の、一般的に広く知られているヒューリスティックのセットが提供されます。タスクは、問題を効率的に解決するために、これらのヒューリスティック（ハイパーヒューリスティックのドメイン内では低レベルヒューリスティックとも呼ばれる）の適切な適用シーケンスを見つけることです。各決定段階で、選択メカニズムと呼ばれるコンポーネントを通じてヒューリスティックが選択され、既存のソリューションに適用されます。選択されたヒューリスティックの適用から生成された新しいソリューションは、受け入れ基準と呼ばれる別のコンポーネントに基づいて受け入れ/拒否されます。ソリューションを拒否する場合は単に破棄されるのに対し、受け入れる場合は既存のソリューションが置き換えられます。 2番目のクラスであるヒューリスティックを生成するヒューリスティックでは、主要な考え方は「既知のヒューリスティックのコンポーネントを利用して新しいヒューリスティックを進化させる」ことです。^[19] このプロセスでは、最初のクラスのハイパーヒューリスティックと同様に、対象の問題を解決するのに役立つことがわかっている適切なヒューリスティックのセットを選択する必要があります。ただし、これらをフレームワークに直接提供するのではなく、ヒューリスティックはまず基本的なコンポーネントに分解されます。

これら 2 つの主なタイプは、建設的探索と摂動的探索のどちらに基づいているかによってさらに分類できます。ハイパーヒューリスティックスのもう 1 つの直交分類では、学習プロセス中にフィードバックを提供するソースを考慮します。これは、研究対象の基礎となる問題の 1 つのインスタンス (オンライン学習) または多数のインスタンス (オフライン学習) のいずれかになります。

ヒューリスティックを選択するための方法論

固定された、人間が設計した、よく知られた低レベルのヒューリスティックの適切な組み合わせを発見します。

建設的なヒューリスティックに基づく
摂動的なヒューリスティックスに基づく

ヒューリスティックを生成する方法論

既存のヒューリスティックメソッドの基本コンポーネントを使用して、新しいヒューリスティックメソッドを生成します。

建設的ヒューリスティックスの基本要素に基づく
摂動的なヒューリスティックスの基本要素に基づく

オンライン学習ハイパーヒューリスティック

学習はアルゴリズムが問題のインスタンスを解決している間に行われるため、タスクに依存するローカルプロパティを高レベル戦略で使用して、適用する適切な低レベルヒューリスティックを決定できます。ハイパーヒューリスティック内のオンライン学習アプローチの例としては、ヒューリスティック選択のための強化学習の使用や、一般的にはヒューリスティックの検索空間での高レベル検索戦略としてのメタヒューリスティックの使用などがあります。

オフライン学習ハイパーヒューリスティック

このアイデアは、一連のトレーニングインスタンスからルールまたはプログラムの形式で知識を収集し、それが未知のインスタンスを解決するプロセスに一般化されることを願うものです。ハイパーヒューリスティックにおけるオフライン学習アプローチの例には、学習分類システム、事例ベース推論、遺伝的プログラミングなどがあります。

2020年には、選択ハイパーヒューリスティックの拡張分類が提供され、 ^[20]現代の選択ハイパーヒューリスティック手法のより包括的な分類が提供される。

アプリケーション

ハイパーヒューリスティックは、さまざまな問題に適用されてきました。実際、ハイパーヒューリスティックの目的の 1 つは、さまざまな種類の問題に適用できることです。次のリストは、ハイパーヒューリスティックが研究されてきた問題と分野の一部です (網羅的ではありません)。

ビンパッキング問題
ブール充足可能性問題
教育の時間割
ジョブショップスケジューリング
多目的問題解決と空間割り当て
看護師勤務表
人員スケジュール
巡回セールスマン問題
車両経路問題
多次元ナップサック問題
0-1 ナップサック問題
最大カット問題
二次方程式の割り当て問題
風力発電所のレイアウト

既存のフレームワーク

現在、さまざまなプログラミング言語で利用できるフレームワークがいくつかあります。これらには以下が含まれますが、これらに限定されません。

ハイフレックス

パルハイフレックス

エボヒップ

マトHH

参照

参考文献と注記

^ EK Burke、E. Hart、G. Kendall、J. Newall、P. Ross、および S. Schulenburg、「ハイパーヒューリスティックス: 現代の検索テクノロジーの新たな方向性」、メタヒューリスティックスハンドブック (F. Glover および G. Kochenberger 編)、Kluwer、2003 年、pp. 457–474。
^ ab P. Ross、「ハイパーヒューリスティックス、検索方法論：最適化と意思決定支援技術の入門チュートリアル」（EK Burke とG. Kendall編）、Springer、2005 年、529-556 ページ。
^ E. Ozcan、B. Bilgin、EE Korkmaz、「ハイパーヒューリスティックスの包括的分析」^{[リンク切れ‍ ]}、Intelligent Data Analysis、12:1、pp. 3-23、2008年。
^ E. Ozcan、B. Bilgin、EE Korkmaz、「Hill Climbers and Mutational Heuristics in Hyperheuristics」、Lecture Notes in Computer Science、Springer-Verlag、The 9th International Conference on Parallel Problem Solving From Nature、2006 年、202-211 ページ。
^ Amaya, I., Ortiz-Bayliss, JC, Rosales-Perez, A., Gutierrez-Rodriguez, AE, Conant-Pablos, SE, Terashima-Marin, H. および Coello, CAC, 2018. 特徴変換による選択ハイパーヒューリスティックの強化。IEEE Computational Intelligence Magazine、13(2)、pp.30-41。https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8335843
^ Amaya, I., Ortiz-Bayliss, JC, Gutiérrez-Rodríguez, AE, Terashima-Marín, H. and Coello, CAC, 2017 年 6 月。「特徴変換によるハイパーヒューリスティックパフォーマンスの向上」。2017 IEEE 進化計算会議 (CEC) (pp. 2614-2621)。IEEE。https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7969623
^ Burke EK、Landa Silva JD、Soubeiga E.: 空間割り当てと時間割作成のための多目的ハイパーヒューリスティックアプローチ、メタヒューリスティックス: 実際の問題解決者としての進歩、第 5 回メタヒューリスティックス国際会議 (MIC 2003) からの選抜論文、pp 129-158、2005 年。
^ C. Segura、G. Miranda、C. León: 頻度割り当て問題のための並列ハイパーヒューリスティックス自然に着想を得た最適化のための協力戦略に関する特集号、Memetic Computing、自然に着想を得た最適化のための協力戦略に関する特集号、( doi :10.1007/s12293-010-0044-5 [1])、2010年。
^ ab Cowling P. および Soubeiga E. 人員スケジュールの近隣構造: サミット会議スケジュールの問題 (要約)、第 3 回国際会議の議事録、自動タイムテーブル作成の実践と理論、Burke EK および Erben W. (編)、2000 年 8 月 16 ～ 18 日、コンスタンツ、ドイツ
^ ab Cowling P.、Kendall G.、Soubeiga E.、「セールスサミットのスケジュール設定に対するハイパーヒューリスティックアプローチ」、2001年、Lecture Notes in Computer Science 2079、Springer-Verlag、pp. 176–190、2001年、ISBN 3540424210、（doi：10.1007/3-540-44629-X
^ Burke EK、Kendall G.、およびSoubeiga E.（2003）タイムテーブル作成と勤務表作成のためのタブーサーチハイパーヒューリスティック。Journal of Heuristics、9（6）：451-470。（doi：10.1023 / B：HEUR.0000012446.94732.b6 [2]）
^ ab H. Fisher および GL Thompson、「ローカルジョブショップスケジューリングルールの確率的学習の組み合わせ」、工場スケジューリング会議 (カーネギー工科大学)、1961 年。
^ ab * H. Fisher および GL Thompson、「確率的学習によるローカルジョブショップスケジューリングルールの組み合わせ」、Industrial Scheduling (New Jersey) (JF Muth および GL Thompson 編)、Prentice-Hall, Inc、1963 年、225 ～ 251 ページ。
^ RH Storer、SD Wu、R. Vaccari、「ジョブショップスケジューリングへの応用を伴う順序付け問題のための新しい探索空間」、Management Science、38 (10)、1992、1495–1509。
^ HL Fang、P. Ross、および D. Corne、「ジョブショップスケジューリング、再スケジューリング、およびオープンショップスケジューリング問題に対する有望な遺伝的アルゴリズムアプローチ」、第 5 回国際遺伝的アルゴリズム会議 (サンマテオ) (S. Forrest 編)、Morgan Kaufmann、1993 年、375 ～ 382 ページ。
^ U. DorndorfとE. Pesch、「ジョブショップスケジューリング環境における進化ベースの学習」、Computers and Operations Research、22(1)、1995、25–40。
^ J. Gratch、S. Chien、G. DeJong、「深宇宙ネットワークスケジューリングのための探索制御知識の学習」、第10回国際機械学習会議の議事録（マサチューセッツ州アマースト）、1993年、135～142頁。
^ J. GratchとS. Chien、「大規模スケジューリング問題に対する適応型問題解決：ケーススタディ」、Journal of Artificial Intelligence Research、4、1996、365–396。
^ M. Bader-El-Den および R. Poli、「GP ハイパーヒューリスティックフレームワークを使用した sat ローカル検索ヒューリスティックの生成」、Wayback Machineに 2017-08-09 にアーカイブ済み、人工進化、第 8 回国際会議、Evolution Artificielle、EA 2007、トゥール、フランス、2007 年 10 月 29 ～ 31 日、改訂選択された論文。Lecture Notes in Computer Science 4926 Springer、2008 年、37 ～ 49 頁。
^ Drake J. H、Kheiri A.、Ozcan E.、Burke EK、(2020) 選択ハイパーヒューリスティックの最近の進歩。ヨーロッパオペレーションズリサーチジャーナル、285(2)、pp.405-428。( doi :10.1016/j.ejor.2019.07.073 [3])

外部リンク