メタヒューリスティクスを使って最適化問題を解こう！

メタヒューリスティクスとは？

メタヒューリスティクスとは、種々の最適化問題を解くための経験的手法である「ヒューリスティクス」を複数組み合わせることで生まれた解法のことを指します。

ヒューリスティクスという言葉が示すとおり、これらの解法は解の精度に理論的保証がありません。

しかし、大規模な問題を解くにあたり、短時間で高精度の解を要求される場合にはとても有効な手段となります。

最適化問題とは？

最適化問題とは、空ではない集合$F$と関数$g：F→R$が与えられた時に、$g$の最小値を与えるような$F$の元を求める問題のことです。

ここで、集合$F$を実行可能解の集合といい、その元を実行可能解と呼びます。また、関数$g$を目的関数と呼びます。

要するに、制約条件を表現しているのが$F$という集合なわけです。

上記最適化問題を数式で表現したものを「数理計画問題」と呼び、制約条件の種類によってさらに細分化されています。

制約条件と目的関数がともに線形の式で記述されている場合、線形計画問題といいます。

さらに変数(の一部)が整数に制限されたものを混合整数計画問題（MIP）と呼んだりします。

現実問題への応用としては、生産計画問題や、施設配置問題、配送計画問題などがあります。

メタヒューリスティクスの基本思想と代表的な手法

良いヒューリスティクスには「集中化」と「多様化」という戦略が含まれていることが必要です。

集中化とは、何回かの試行によって得られた局所最適解と共通部分が多い解を初期解として選択する戦略を指します。

反対に、多様化とは、なるべく多様な解を得るために以前に生成/選択した解の情報を用いることです。

以下ではこれらの戦略を実現させるために重要な思想について簡単に触れていきます。

近傍探索

近傍とは、ある解が与えられた時、その解を少しだけ変化させた解全体の集合のことです。

簡単にいうと、発見した実行可能解と近い解の中から、現在の解よりも良いものを発見しようとする手法のことです。

例：局所探索法、多点出発局所探索、焼き鈍し法、タブーサーチ、大近傍探索、部品最適化法など

近似解を構成する

何もない状態から近似解を構成する手法を構築法と呼びます。

以前は構築法と改善法は異なるものだとされていましたが、最近ではそれらを統一的に捉えるフレームワークが考えられています。

キーワード：半順序集合（poset）、Hasse図

例：多点出発局所探索、貪欲ランダム適応型探索法、蟻群生法など

問題を分割する

大規模な問題を分割して生成された子問題の解をもとにして、元問題の解を構成するような手法が用いられることがあります。

問題を分割することによって計算時間の削減が期待できます。

例：部品最適化法、多レベル法

複数の解を元に解を改善する

ひとつの解だけを改善するよりも、複数の解を改善していく方が効率よく良い解を発見できるだろう、という発想から、このような手法も用いられています。

例：蟻群生法、遺伝的アルゴリズム、散布探索法

ランダム性

ランダム性を用いない場合、メタヒューリスティクスがうまく働かないような問題が存在する可能性があり、その場合はあまり良い解が得られないことが予想されます。

そこで、ランダム性を組み入れることによって毎回悪い解を出すといった事態を避けることができるようになります。

例：焼き鈍し方、蟻群生法、貪欲ランダム適応型探索法など

問題の変形・単純化

問題に含まれる数値のスケーリングや些細な影響しか与えない変数の削除、変数の集約、目的変数の変形などを通して問題を単純化して解く場合もあります。

複雑な実問題の定式化などの過程でよく用いられます。

例：誘導局所探索法、探索空間平滑化法、多レベル法など

探索履歴の利用

長時間計算機を回し続けた際に、継続して解が改善され続けるものが望ましい手法です。

そのため、同じ解を何度も探索することを避けるために探索履歴を記録しておくことが考えられます。

例：タブーサーチ、誘導局所探索法、蟻群生法、散布探索法など

どのような問題に適用できるか？

• グラフ分割問題
• 最大安定集合問題
• グラフ彩色問題
• 巡回セールスマン問題
• 2次割り当て問題
• 多制約ナップサック問題
• 数分割問題

などの問題に適用することができます。