メタヒューリスティクス

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

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

概要

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

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

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

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

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

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

ノーフリーランチ定理

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

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

メタヒューリスティクスの例

進化的計算

進化的アルゴリズム
- 遺伝的アルゴリズム(Genetic Algorithm)
- 進化戦略(Evolution Strategy)
- 進化的プログラミング(Evolutionary Programming)
- 遺伝的プログラミング(Genetic Programming)

群知能
- 蟻コロニー最適化(Ant Colony Optimization)
- 粒子群最適化(Particle Swarm Optimization)
- 人工蜂コロニーアルゴリズム（英語版）(Artificial Bee Colony Algorithm)
- ホタルアルゴリズム(Firefly Algorithm)
- カッコウ探索（英語版）(Cuckoo Search)
- コウモリアルゴリズム（英語版）(Bat Algorithm)
- 狼探索アルゴリズム（英語版）(Wolf Search Algorithm)
- 花粉媒介アルゴリズム（英語版）(Flower Pollination Algorithm)
- バッタ探索アルゴリズム（英語版）(Locust Search Algorithm)
- トンボアルゴリズム（英語版）(Dragonfly Algorithm)

差分進化(Differential Evolution)
風力駆動最適化（英語版）(Wind Driven Optimization)
ブレインストーミング最適化（英語版）(Brain Storm Optimization)
渦最適化（英語版）(Spiral Optimization)

近傍探索法

タブー探索(Tabu Search)
焼きなまし法(Simulated Annealing)

その他のアルゴリズム

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。