Skip to content

局所探索/山登り/焼きなまし

状態

  • 盤面やグラフなど、問題の解空間をそのまま状態に持つ
  • TSP系
    • 訪問点の順番
    • 訪問辺順番
  • 問題の解空間の一部だけ状態に持つ(残りは別途最適化)
  • 操作列をそのまま持つ
  • 「解空間->状態空間->解空間」みたいな変換(復元)ができる場合、より性質の良い(探索空間の小さい)状態空間で探索する
  • など

状態の局所性

  • 局所性
    • 状態内の離れた2つの要素に関連性(依存関係、文脈)がなければ、それぞれの要素は独立に考えることができる
    • 焼きなましは、「状態を少し変えて改善(局所探索)」という感じのため、近傍を考えるうえで重要
      • 状態の1つの要素を入れ替えるのが容易などであれば、それを近傍として局所探索/山登り/焼きなましができる
      • 2次元グリッドなどの問題の場合、部分的な領域で見るとそこだけを入れ替えて別の状態にできるなら近傍として利用できる

近傍

  • 同じ焼きなまし解だとしても差がでる大きな要素
    • 近傍によって探索空間の形が変わるため、探索の質に直結する
  • 「極小で高速な近傍」「依存する要素をまとめて置き換える近傍」など
  • 近傍として望ましい条件にはいくつかありえるが、基本的には、良い状態間を行き来できるような近傍を考えられるか

変化量が小さな近傍

  • 状態の変化(スコアの変化量)がとても小さい近傍のこと
    • 状態の1要素を他の要素と入れ替える、位置を1だけずらす、2つの要素をswapする、など
  • 「一番小さい」と思っても、より変化量が小さい近傍が作れる可能性があるので、できるだけ検討する

確実に前進する近傍

greedy 遷移 / 局所探索遷移

  • 評価値が良くなるとは限らなくても、何らかgreedyな操作や局所探索を1回の遷移とする近傍
    • 多少の無駄な遷移が入っても、良い遷移が入っていればよい
  • 対象を動かせなくなるまで動かす、部分破壊再構築などでランダムに再構築、など

無駄な遷移をなくす

  • xy座標系(-10^6 <= x,y <= 10^6)とかのときに、1ずつずらすとかは無駄なので、点が存在するところ、接するところ、交点などだけに遷移する
    • 必ず評価値が変化する
  • 「評価値が変わらない遷移」
    • 例えば、パスの長さがスコアのときなどに、パスに関係していない辺を変えてもスコアは変化しないが、繋ぎ変えなどでより長いパスにできたりする
    • どちらかというと、評価関数の方で考慮するような方法を考えるべき
  • pertubation for tie-breaking
    • 同評価値の状態に対してランダムに選ぶのを変えたりなど摂動を与える

2-opt 近傍

  • https://en.wikipedia.org/wiki/2-opt
  • 巡回セールスマン問題などで、2 点を交換する 2-swap 近傍は 4 辺変化してしまうが、そこを 2 辺変化させるような近傍
  • 実装方法にもよるが、訪問点の順を状態に持っている場合は、ある範囲を reverse する感じになる
  • その他
    • k-opt(3-opt, 4-opt, double-bridge)
    • Lin-Kernighan Heuristic

類型

  • 系列を3箇所で切ってそれぞれ系列A、系列B、系列C、系列Dとして、ACBDの順番で連結する

kick 近傍

  • 局所解を抜け出す(kick)ような状態を大きく変える近傍
  • Introduction to Heuristics Contest 解説 p.7
  • k-swap-kick
    • TSP などで、k 個のセグメント s1,s2,...,sk を s1,sk,...,s2 にする感じ
  • 2-opt ではたどり着くのが難しいような double bridge みたいな形にキックする

部分破壊と再構築

  • パスや状態の一部分を壊して再構築するような近傍
  • https://togetter.com/li/607979?page=2
  • パスやサイクルの一部を破壊してDFSで再構築
  • 領域の一部を破壊して再構築
    • AHC014
      • 解が操作列でも、盤面での部分領域に対応する部分列の削除＆後ろに操作列追加で近傍を作成可能
      • 操作列に注目しても、操作列の依存関係を有向グラフとしてトポロジカルソートすると操作列の途中から最後をまとめて削除、ということもできる
    • AHC020
      • ある放送局の強度を0にして、カバーできなくなった家を適当な順番で最小コストでカバーする近傍
      • ある放送局の強度を上げて、順番にカバーできない家ができないように最小化する近傍
      • など

Invalidな状態を許容する焼きなまし

  • 解の条件を満たさない状態になることを許容することで、探索空間で推移が難しい状態に推移できやすくなる可能性がある
    • 最終状態では条件を満たす必要があるため、最後にチェックをしておいたほうが良い
    • 条件を満たさない場合はペナルティとして、時間に応じて徐々に強くしていく、など
  • AHC011
    • 最終的に「与えられたタイルで作れる」必要があるが、辺の追加・削除を近傍に、与えられたタイルで作れない状態も探索
      • ただし、評価関数は各利用タイル数の差にして0になるよう目指す

評価関数

  • スコアをそのまま利用
  • 避けたい状態に対してペナルティ
  • AHC011
    • 2タイルをswapする近傍で、「一番大きな木のサイズ」を評価関数にすると、それ以外のタイルの状態が考慮できないので、「連結成分の個数(が1になるようにする)」や「連結成分のサイズの2乗和」などにすると、収束が速い

高速だが正確ではない評価関数

  • 「高速だが正確ではない評価関数」が作れる場合、探索回数を確保でき、よりよい解にたどり着ける可能性が高まる
  • 正確ではない評価関数で探索し、その結果を初期値として、最後だけ正確な評価関数で探索する

時間に応じて近傍や評価関数を変える

  • 時間に応じて、荒く→細かく探索する
    • 時間で区切って条件を変える
  • 時間に応じて、徐々に正確にしていく、徐々に条件を満たすようにしていく
    • alpha * eval1() + (1-alpha) * eval2()的に混ぜる
    • 時間で区切って使う評価関数を変える

冷却スケジュール

# rは時間の割合(0<=r<=1)
# T0: 初期温度
# T1: 最終温度
T = pow(T0, 1-r) * pow(T1, r)
か
T = T0 * pow(T1/T0, r)

高速化

差分計算

  • 近傍への遷移では、状態を一部分だけ変化させる場合が多く、スコアや評価関数の値をその差分だけ高速に計算できる場合がある
  • AHC012
    • 直線の追加削除は、その直線の両側の領域だけを考えれば良い
    • ある領域にある個数は座圧＋二次元累積和でO(1)で求められ、領域数はO(K)程度

TSPのパスをdequeで持ちながらスコア計算

  • TSPパスをdequeで持つ
    • 訪問マスをdequeで持って、front/backに対する操作のみ許す
  • AHC027

状態更新/判定処理を後に持っていくテク

  • 「近傍に遷移(状態更新)してから評価関数の値を計算」ではなく「遷移後の評価関数の値を計算して移動すると判断した場合だけ状態を更新」する
  • 評価関数の値を計算後にundo操作するとundo操作分の時間がかかってしまうが、状態更新前に評価関数が計算できる場合はundo操作を省略できる
  • AHC009
    • 前からDP・後からDPを持っておくと、差分計算が高速に求められる
    • さらに、近傍更新時の変更箇所をターン順方向に固定すると、状態更新の方も高速化可能
  • AHC024
    • 「色を変える→スコア計算→焼きなましの採用判定→採用されるなら連結性判定＆隣接判定」とすることで、結局rollbackするときに重い判定処理を省略できる

評価関数計算の打ち切り

  • https://qiita.com/not522/items/cd20b87157d15850d31c
    • 変化量からしきい値以下か判定するところを式変形して、遷移先に依存しないところを先に計算しておくことで、評価関数内でしきい値を超えることがわかったタイミングで打ち切れるようになるテク

exp()の計算部分を2^xの計算で近似して高速処理するテク

  • 自分のコードの場合は、以下のようにする感じ？(＋温度調整) 
    if (exp(delta / T) >= frand()) {
↓
if (((uint32_t)(1) << (uint32_t)(32 + delta / T)) >= xor128()) {

状態の複数候補生成/サンプリング

その他

Successive Halving

その他のネタ