最適化問題をメタヒューリスティクスと決定的アルゴリズムを組み合わせて解く

はじめに

$N$ 個の要素からいくつかの要素を選ぶことで，スコアが決まる問題についての話です．
要素の選び方を工夫することでなるべく良いスコアを得ることが目的です．

全ての組み合わせは $2^N$ 通りあり，全てを探索することは困難です．
そこで，メタヒューリスティクスとして，山登り法，焼き鈍し法や遺伝的アルゴリズムを使い，それぞれの要素について選ぶ/選ばないを決める手法が考えられます．

しかし，「ある特定の組み合わせについて一方を必ず選ばなければならない」など，選ぶ際の条件に制約が加わる場合があります．特に，invalid な選び方が存在する場合，メタヒューリスティクスが有効に機能しない場合があります．

そこで，このような制約がある問題について，頂点被覆を例に，メタヒューリスティクスと決定的な手法を組み合わせて解く手法を紹介します．

問題

なるべく小さい頂点被覆を求める問題を考えます．

頂点被覆とは，無向グラフが与えられたときに，次を満たすようにいくつかの頂点を選択したものを頂点被覆と呼びます．

• 全ての辺について，どちらかの頂点が選択されている

頂点被覆のちゃんとした説明は Wikipedia にお任せします．
https://ja.wikipedia.org/wiki/頂点被覆

手法

ここでは，メタヒューリスティクスとして，山登り法を採用します（焼き鈍し法や遺伝的アルゴリズムでも可能です）．
また，決定的な手法として，貪欲法を採用します．「隣接する被覆されていない頂点の数が多い頂点」を貪欲に選択する手法がこの問題では有効です．

山登り法では，それぞれの頂点について「必ず選択する」「選択してもしなくても良い」を決めます．
このように，不完全な解を山登り法では探索します．しかし，不完全な解ではスコア（この問題の場合，選択した頂点の数）を計算することができません．
そこで，「選択してもしなくても良い」頂点について，選択するか否かを決定的な手法を用いて決めます．ここでは，貪欲法を用いて山登り法の解を補完します．補完した結果について，スコアを計算します．

詳細には，以下の流れで解を更新していきます．

1. 初期解の生成
   初期解として，全ての頂点について「選択しなくても良い」と設定します．
2. 山登り法による探索
   1. 近傍解の生成
      近傍解を生成します．
      この問題の場合，頂点のいずれかを選び，「必ず選択する」「選択してもしなくても良い」を変更したものを近傍解とします．
   2. 解の補完とスコアの計算
      山登り法を用いて作成した解からそのままスコアを求めることはできません．
      そこで，貪欲法を用いて解を補完します．
      「選択してもしなくても良い」頂点群について，貪欲法を用いて解を補完します．
      補完した解について，スコアを計算します
   3. 解の更新
      もし，求めたスコアが既存の解より良い場合，解を更新します．
3. 繰り返し
   2 のステップを繰り返します．
4. 結果の出力
   最終的な解について，貪欲法で補完し，出力します．

まとめ

制約付き要素選択問題に対して，メタヒューリスティクスと決定的な手法を組み合わせることで，探索効率を高めつつ解の質を向上させていくことができます．
この記事では頂点被覆を例に説明しましたが，他の様々な問題にも応用可能な手法です．
この記事が役に立ったなら幸いです．