ヒューリスティック（コンピュータサイエンス）

数理最適化とコンピュータサイエンスにおいて、ヒューリスティック（ギリシャ語のεὑρίσκω「私は見つける、発見する」^[1]に由来）とは、従来の方法では正確な解や近似解を見つけるのに時間がかかりすぎる場合、または従来の方法では探索空間内で正確な解を見つけられない場合に、より迅速に問題を解決するために設計された手法です。これは、最適性、完全性、正確性、または精度を犠牲にして速度を得ることで実現されます。ある意味では、近道と考えることができます。

ヒューリスティック関数（単にヒューリスティックとも呼ばれる）は、利用可能な情報に基づいて各分岐ステップで探索アルゴリズムの選択肢をランク付けし、どの分岐に従うかを決定する関数である。たとえば、正確な解決策を近似する場合があります。^[2]

ヒューリスティックの目的は、妥当な時間枠内で、目の前の問題を解決するのに十分なソリューションを生み出すことです。このソリューションは、この問題に対するすべてのソリューションの中で最善ではないかもしれませんし、正確なソリューションに近似しているだけかもしれません。しかし、それを見つけるのに法外なほど長い時間はかからないため、それでも価値があります。

ヒューリスティックは、それ自体で結果を生成する場合もあれば、効率を向上させるために最適化アルゴリズムと組み合わせて使用​​される場合もあります (たとえば、適切なシード値を生成するために使用される場合があります)。

理論計算機科学におけるNP 困難性に関する結果により、現実世界のアプリケーションで日常的に解決する必要があるさまざまな複雑な最適化問題に対して、ヒューリスティックが唯一の実行可能な選択肢となります。

ヒューリスティックスは、既知のアルゴリズムが存在しない状況でも使用できるため、人工知能や思考のコンピュータシミュレーションの分野全体に浸透しています。^[3]

特定の問題を解決するためにヒューリスティックを使用するかどうかを決定するためのトレードオフ基準は次のとおりです。

• 最適性:特定の問題に対して複数の解決策が存在する場合、ヒューリスティックによって最適な解決策が見つかることが保証されますか? 最適な解決策を見つけることが実際に必要ですか?
• 完全性:特定の問題に対して複数の解決策が存在する場合、ヒューリスティックはそれらすべてを見つけることができますか? 実際にすべての解決策が必要ですか? 多くのヒューリスティックは、1 つの解決策のみを見つけることを目的としています。
• 正確性と精度:ヒューリスティックは、想定される解決策の信頼区間を提供できますか? 解決策のエラー バーは不当に大きくなっていますか?
• 実行時間: これは、このタイプの問題を解決するための最もよく知られているヒューリスティックですか? 一部のヒューリスティックは、他のヒューリスティックよりも速く収束します。一部のヒューリスティックは、従来の方法よりもわずかに速いだけであり、その場合、ヒューリスティックを計算する際の「オーバーヘッド」が悪影響を及ぼす可能性があります。

場合によっては、ヒューリスティックの基礎となる理論があまり精巧ではないため、ヒューリスティックによって見つかった解決策が十分に優れているかどうかを判断するのが難しいことがあります。

ヒューリスティックに期待される計算パフォーマンスの向上を達成する 1 つの方法は、その解決策が最初の問題の解決策でもある、より単純な問題を解決することです。

巡回セールスマン問題(TSP) を解くための近似の例は、Jon Bentleyによって説明されています。

• 「都市のリストと各都市間の距離が与えられた場合、各都市を 1 回ずつ訪れて元の都市に戻る最短のルートはどれでしょうか?」

ペンプロッタを使用して描画する順序を選択する。TSP はNP 困難であることが知られているため、中規模問題であっても最適解を解くのは困難です。代わりに、貪欲アルゴリズムを使用すると、適度に短い時間で、最適ではないが優れた解 (最適な答えの近似値) を得ることができます。貪欲アルゴリズムのヒューリスティックでは、後で適切なステップを実行できない (または実行できなくなる) かどうかに関係なく、現時点で最適な次のステップを選択することが推奨されます。これは、実践では十分に優れたソリューションであることが示され、理論ではより優れたソリューションがあることが示されている (場合によっては、どの程度優れているかが示されている) という意味でヒューリスティックです。^[4]

ヒューリスティックによってアルゴリズムが高速化される別の例は、特定の検索問題で発生します。最初、ヒューリスティックは、フルスペース検索アルゴリズムと同様に、各ステップですべての可能性を試します。ただし、現在の可能性がすでに見つかった最善の解決策よりも悪い場合は、いつでも検索を停止できます。このような検索問題では、ヒューリスティックを使用して最初に適切な選択肢を試し、悪いパスを早期に排除することができます (アルファ-ベータ プルーニングを参照)。A * 検索などの最良優先検索アルゴリズムの場合、ヒューリスティックが許容される限り、ヒューリスティックによってアルゴリズムの収束が改善され、正確性が維持されます。

チューリング賞受賞スピーチで、アレン・ニューウェルとハーバート・A・サイモンは、ヒューリスティック検索仮説について論じています。物理的な記号システムは、既知の記号構造を繰り返し生成および変更し、作成された構造がソリューション構造と一致するまで続けます。後続の各ステップは、その前のステップに依存しているため、ヒューリスティック検索は、現在のステップがソリューションにどれだけ近いかを測定することで、追求する手段と無視する手段を学習します。したがって、ソリューションを完成させる可能性が低いと測定されたいくつかの可能性は、決して生成されません。

ヒューリスティック法は、探索木を使用することでその目的を達成することができます。しかし、ヒューリスティック法では、すべての可能な解決策の分岐を生成するのではなく、他の分岐よりも結果を生み出す可能性が高い分岐を選択します。各決定ポイントで選択的であり、解決策を生み出す可能性が高い分岐を選択します。^[5]

ウイルス対策ソフトウェアは、多くの場合、ウイルスやその他の形式のマルウェアを検出するためにヒューリスティック ルールを使用します。ヒューリスティック スキャンは、ウイルスの種類やファミリーに共通するコードや動作パターンを検索し、ウイルスごとに異なるルール セットを使用します。ファイルまたは実行中のプロセスに一致するコード パターンが含まれていることや、その一連のアクティビティが実行されていることがわかった場合、スキャナーはファイルが感染していると推測します。動作ベースのヒューリスティック スキャンの最も高度な部分は、より単純な文字列スキャン方法では簡単に検出できない、高度にランダム化された自己修正/変異 (ポリモーフィック) ウイルスに対抗できることです。ヒューリスティック スキャンは、ウイルスを最初にどこか別の場所で検出し、ウイルス スキャナー開発者に送信して分析し、スキャナーの検出更新をスキャナーのユーザーに提供しなくても、将来のウイルスを検出できる可能性があります。

一部のヒューリスティックには、強力な基礎理論があります。それらは、理論からトップダウン方式で導き出されたか、実験または現実世界のデータに基づいて導き出されたものです。その他のヒューリスティックは、理論をまったく考慮せずに、現実世界の観察や経験に基づいた単なる経験則です。後者は、より多くの落とし穴にさらされています。

ある状況で「機能する」ことが確認されたという理由で、特定の要件セットを満たすことが数学的に証明されていないにもかかわらず、ヒューリスティックがさまざまな状況で再利用される場合、現在のデータ セットが必ずしも将来のデータ セットを表すとは限らず (オーバーフィッティングを参照)、「解決策」とされるものがノイズに似たものになる可能性もあります。

ヒューリスティックを使用して誤った結果の確率を推定する場合、統計分析を行うことができます。検索問題またはナップサック問題を解くためにヒューリスティックを使用するには、ヒューリスティックが許容可能かどうかを確認する必要があります。というラベルの付いたノードまたは頂点の合計を含む有向グラフで、目標ノードまでの真の最適距離を近似することを目的としたヒューリスティック関数を考えると、「許容可能」とは、おおよそヒューリスティックが目標までのコストを過小評価すること、または正式には、のすべての場合について であることを意味します。 ${\displaystyle h(v_{i},v_{g})}$${\displaystyle d^{\star }(v_{i},v_{g})}$${\displaystyle v_{g}}$${\displaystyle G}$${\displaystyle n}$${\displaystyle v_{0},v_{1},\cdots ,v_{n}}$${\displaystyle h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})}$ ${\displaystyle (v_{i},v_{g})}$${\displaystyle {i,g}\in [0,1,...,n]}$

ヒューリスティックが許容されない場合は、グラフの行き止まりで終わるか、2 つのノードの間を行ったり来たりして、目標を見つけられない可能性があります。 ${\displaystyle G}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle {i,j}\neq g}$

無料辞書のウィクショナリーで「ヒューリスティック」を調べてください。

「ヒューリスティック」という言葉は19世紀初頭に使われるようになった。これは「見つける」という意味のギリシャ語heuriskeinから不規則に形成されたものである。 ^[6]

• 建設的ヒューリスティック
• メタヒューリスティック: 通常はメモリと学習を使用して、基本的なヒューリスティック アルゴリズムを制御および調整する方法。
• 数学的手法: メタヒューリスティックスと数理計画法 (MP) の手法を相互運用して作成された最適化アルゴリズム。
• 反応型検索最適化:ヒューリスティックの自己調整のためのオンライン機械学習原理を使用する方法。