メタヒューリスティクス

最適化問題 > 組合せ最適化 > メタヒューリスティクス

メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。

概要

通常ある問題に対しての「解法」が存在するとき、その解法が適用できる範囲はその問題に対してのみである。

ところが近似アルゴリズムのように厳密な答えではなく、なるべく「答えに近い」まで拡大すると、局所探索法や貪欲法など複数の問題に対しても使用できる手法が存在する。

メタヒューリスティクスとは特定の問題に限定されず、どのような問題に対しても汎用的に対応できるように設計された、アルゴリズムの基本的な枠組みのことである。

言い換えればヒューリスティックアルゴリズムの内、特定の問題に依存せず手法のみが独立したものである。それゆえあらゆる問題に適用可能である。

このことはNP困難のような多項式時間で最適解を求めるアルゴリズムが存在しないと思われる問題などに対して有効である。

ただし、一般的にメタヒューリスティクスは特定の問題専用のヒューリスティクスより平均的な解の精度が劣ることが多い。これは汎用的な探索をするためには問題に対する事前知識を必要とせずに実装しなければならないので、それらを有効に使用することで解の探索を行う方法に対してどうしても不利な立場で探索を進める必要があるからである。

ノーフリーランチ定理

ノーフリーランチ定理によって平均的にはどの探索手法も同じ性能であることが示されて以来、「最も優れたメタヒューリスティクス」を求めることは無意味であることが示されている。この定理はしばしば「万能の探索アルゴリズムは存在しない」と表現されることがあり、メタヒューリスティクスに対するアンチテーゼとして用いられる。

しかしノーフリーランチ定理はあくまで「全ての問題に対する平均」であり問題空間をある程度まで限定した時の性能の善し悪しは論ずることはできない。また実際にメタヒューリスティックスを実装する場合は、探索効率を上げるためその問題の事前知識をさらに組み込んだりする例が多くある。それゆえ、この定理のみによってメタヒューリスティクスそのものに不要論を投げかけることはできない。