貪欲法、山登り法、焼きなまし、ビームサーチ、これらの間の関係について
概要
マラソンマッチにおける有力なアルゴリズムとして焼きなましとビームサーチがある。 たいていの問題においてこのどちらかのうちより適切な方を実装すれば上位が得られることや、性質や実装の仕方が異なることから、これらの関係は二項対立のようにして理解されている。 しかしこのふたつのアルゴリズムがどちらも貪欲法の延長にあることも知られている。
この記事では、貪欲法を中心に整理して焼きなましとビームサーチの二項対立の構図は適切でないことを示す。 特に、これらの差異が状態空間の間のグラフが有向であるか無向であるかのみであることを明らかにし、下図のような形で整理する。 またその系として、焼きなましとビームサーチの間で互いに知見を流用できることを説明する。
<?xml version=”1.0” encoding=”UTF-8”?>
準備
最適化問題
形式化
この記事では最小化問題だけを取り扱う。 つまり、集合 \(X\) と関数 \(f : X \to \mathbb{R}\) が与えられたときに \(\arg\min _ {x \in X} f(x)\) を求めることを考える。 なお、この \(X\) を解空間、その要素 \(x \in X\) を解、\(f\) を目的関数と呼ぶ。
貪欲法
非形式的な説明
貪欲法は例えば 貪欲法 - Wikipediaarchive.org では次のように説明されている:
このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。
貪欲法とは、局所的な評価関数に従い先読みをせずに解を構築するようなアルゴリズムの総称と言える。 コストパフォーマンスのよい順にソートして順番に使うナップサック問題への貪欲法、などが典型的である。
ただし要素の評価やソートは必ずしも事前にすべて済ませる必要はない。 つまり評価値を現在までの選択に依存して定めてしまってもよい。 また、最適解が必ず求まるものには限定していないことにも注意してほしいnote。
形式化
貪欲法は次のようなものであると理解できる。 まず、問題に対し有向グラフ \((V, E)\) と関数 \(g : V \to \mathbb{R}\) を適切に選ぶ。 \(v \in V\) に対し \(N(v) = \{ w \in V \mid (v, w) \in E \}\) と定義し、さらに \(v \in V\) が \(N(v) = \emptyset\) ならば \(v \in X\) である (あるいはそう見做せるnote) と仮定する。 また、 \(v^\ast = \arg\min _ {w \in N(v)} g(w)\) と定義する。 適切な点 \(v = v_0 \in V\) から始めて \(N(v) \ne \emptyset\) な限り \(v \gets v^\ast\) と更新することを繰り返し、最終的に得られた \(v\) に対し \(h(v)\) が問題に対する解である。
なお、この \(V\) を状態空間、その要素 \(v \in V\) を状態、\(E\) あるいは \(e \in E\) を遷移、\(g\) を評価関数と呼ぶ。 さらに \(N(v)\) あるいはその要素 \(w \in N(v)\) を状態 \(v\) の近傍と呼ぶ。 \(N(v) = \emptyset\) な \(v \in V\) を \(X\) に埋め込む操作が非自明なときや陽に扱いたいとき、これを解釈関数 \(h : V \to X\) と呼ぶ。
例: 巡回セールスマン問題
巡回セールスマン問題を考えよう。 \(n\) 頂点とする。 関数 \(d : n \times n \to \mathbb{R}\) が与えられる。 解空間 \(X\) は \(n\) 要素の順列全体なので置換群 \(\mathfrak{S} _ n\) であり、目的関数 \(f(\sigma) = \sum _ {i \lt n - 1} d(\sigma(i), \sigma(i + 1))\) となる。
\(|X| = n!\) であるのでこれは大きすぎる。 そこで順列を前から \(1\) 要素づつ構築していくことを考える。 特に、頂点 \(0\) から初めて、まだ訪れていない頂点の中で最も近いものを訪れることを繰り返せば、これは \(O(n^2)\) でそれなりの解が得られるだろう。
これは上記の形式化において、状態空間を \(V = \{ \sigma : k \rightarrowtail n \mid k \le n \land \sigma \text{は単射} \}\) とおき、遷移を \(E = \{ (\sigma, \sigma ^ a) \mid \sigma, \sigma ^ a \in V \}\) とし、評価関数を \(g(\sigma) = \sum _ {i \lt k - 1} d(\sigma(i), \sigma(i + 1))\) としたものである。
ビームサーチ
非形式的な説明
貪欲法は見ている範囲の状態のうち「最も良いものだけ」を記憶し利用していた。 ビームサーチとは、これを「良い順に \(k\) 個まで」と緩和することでさらに良い解を得ようとするものである。
形式化
貪欲法においては、状態 \(v = v_0 \in V\) から始めて \(v \gets v^\ast\) と更新することを繰り返した。 ビームサーチとは、これを状態集合 \(\mathbf{v} = \{ v_0 \} \subseteq V\) から始めて \(\mathbf{v} \gets \mathbf{v}^\ast\) と更新するものである。 ただし \(\mathbf{v}^\ast\) は集合 \(\bigcup _ {v \in \mathbf{v}} N(v)\) の中から \(g(v)\) の小さい順に \(k\) 個取り出してできる集合と定義する。
ビームサーチは貪欲法の拡張である
これは明らかである。 特に、状態を状態の集合へ拡張したものと理解できる。
chokudaiサーチについて
(chokudaiサーチ(ビームサーチ亜種)の利点の話 - chokudaiのブログarchive.org が詳しい)
余談: DPとの関連について
(ビームサーチは DP - びったんびったんarchive.org が詳しいnote)
余談: 不確定性を含む場合に、貪欲法のビームサーチ化は自然に定まらない
(省略)
山登り法
非形式的な説明
貪欲法は例えば 山登り法 - Wikipediaarchive.org では次のように説明されている:
山登り法とは「現在の解の近傍の内で最も成績の良い解」を近傍解として選び、「現在の解より近傍解の成績の方が良い場合」に近傍解と現在の解を入れ換える局所探索法の方法。
形式化
山登り法は次のようなものであると理解できる。 まず、\(V = X\) とし無向グラフ \((V, E)\) と関数 \(g : V \to \mathbb{R}\) を適切に選ぶ。 \(v \in V\) に対し \(N(v) = \{ w \in V \mid (v, w) \in E \}\) とおき、これは常に非空であるとする。 適切な点 \(v = v_0 \in V\) から始めて、 \(w \in N(v)\) をランダムに取り出し \(g(w) \le g(v)\) ならば \(v \gets w\) と更新するということを一定回数だけ繰り返し、最終的に得られた \(v \in X\) が得られた解である。
なお、この \(V\) を状態空間、その要素 \(v \in V\) を状態、\(E\) あるいは \(e \in E\) を遷移、\(g\) を評価関数と呼ぶ。 さらに \(N(v)\) あるいはその要素 \(w \in N(v)\) を状態 \(v\) の近傍と呼ぶ。
焼きなましとは
非形式的な説明
焼きなましは冶金における焼きなましから名前を取ったアルゴリズムである。 山登り法では解が改善される場合にのみ更新を行うが、悪化される場合でも時間に依存して確率的に更新を行う。
実用の上では次のテクニック集が役に立つ: hakomo/Simulated-Annealing-Techniquesarchive.org
形式化
山登り法においては \(v \gets w\) という更新を行うのは \(g(w) \le g(v)\) の場合のみであった。 焼きなましとは、これを \(g(w) \gt g(v)\) でも温度 \(t\) のとき確率 \(p(t, v, w)\) で更新を行うようにしたものである。
焼きなましは山登り法の拡張である
これは明らかである。 特に、採択確率を非自明なものへと拡張したものと理解できる。
適用条件について
焼きなましや山登り法の適用条件は比較的厳しめで、操作の間の可換性のようなものが要求される。 これは「文脈を持たない」などと表現されることが多い:
多点スタートについて
(省略)
状態プールについて
焼きなましは通常は単一の状態のみを保持するが、複数の状態を保持する派生を考えることもできる。 これを状態をプールする焼きなましと呼ぶ。
余談: 位相の言葉を用いての整理について
(省略)
本論
貪欲法と山登り法の類似について
両者は共にグラフ上を単純な形で探索するアルゴリズムである。 形式化された形の両者を観察すれば、差異は主に以下の \(3\) 点であることが分かる:
- 有向グラフか、無向グラフか
- 近傍をすべて見るか、ランダムに取り出すか
- 状態空間を別に用意するか、解空間をそのまま使うか
しかしこれらの違いは常に見られるものではない。 山登り法を有向グラフ上で行う場合はあるし、貪欲でも近傍を尽くせない場合はランダムにいくつか取り出して対処する場合はある。 山登り法 (や特に焼きなまし) において、解空間をそのまま使うのでなくこれを緩和して状態空間を作る (ただし解に到達できない可能性を孕む) ことは多い。
このように見れば、貪欲法と山登り法との区別は曖昧であることが分かる。 また一方の性質をもう一方へ持ち込むことが有用であることも分かる。
焼きなましとビームサーチの関係について
焼きなましは山登り法の自然な拡張のひとつであり、ビームサーチは貪欲法の自然な拡張のひとつであった。 よって焼きなましとビームサーチの区別も曖昧であることは想像が付く。
実際に (いくらかの乱暴さはあるが) 次のように対応を説明できる:
- 貪欲法やビームサーチの評価関数に乱数を足し込むのは、山登りを焼きなましにする変化と同じことである
- 山登り法や焼きなましで状態を複数保持するのは、貪欲法をビームサーチにする変化と同じことである
- 多点スタートをビームサーチに適用したものが chokudai サーチである
- 初期解や先頭付近での選択への依存性が大きいときに、これを変えながらアルゴリズムを繰り返し実行する、という意味で類似がある
このように対応を取ることにより、焼きなましとビームサーチとの間で知識を共有することができる。 例えば、焼きなましは時間経過と共に採択確率が減少するが、ビームサーチも序盤は評価関数に大きめの乱数を加え、終盤はこれをほとんど加えずに点数を優先するようにすれば、適切に多様性が確保され点数が向上するのではないか、などと予想を立てることができるnote。
貪欲法と山登り法の差異について
貪欲法と山登り法の区別は曖昧であると言った。 しかしまったく同一であるとも思えない。 ではこれらの間の差として最も重要なものは何だろうか？
これは、状態の間のグラフが有向か無向かの違いが本質的であると言える。 候補としては先に挙げた \(3\) 点である。 近傍をどのように検査するかや、解空間を状態空間として使い回すかどうかは、どちらも単に実装の都合であるように思われるので選びたくはない。 焼きなましを行う際の要件として可換性や可逆性のようなものがあり、またビームサーチを行う要件としてはこれがないことを考えると、状態の関係が有向グラフなのか無向グラフなのかの違いは (しばしば成り立たないとしても) 重要であるように見える。
このような整理によって、概要の節で示した図式が従う。
追記
その他の類似の例
ランダムウォーク、モンテカルロ法、タブーサーチなども、山登り法の部分や拡張と見ることができる。 また、タブーサーチの重複除去という発想はビームサーチのそれと近い。
この記事への反応
chokudaiサーチ＋乱数、っていうのは囲碁のモンテカルロ木探索そのものに見える
— るふぁ (@lpha_z) 2019年3月6日
多変数を順番に焼きなまし、は内側が焼きなましで外側が貪欲だと解釈できる？
— るふぁ (@lpha_z) 2019年3月6日
拡張アンサンブル法はよく分かっておらず、次のツイートの真偽はまだ判定できていない:
また、焼きなまし＋状態空間保持、は拡張アンサンブル法ですね
— るふぁ (@lpha_z) 2019年3月6日