誰でもできる焼きなまし法

マラソンマッチ

　マラソン系コンテストに興味のある競プロer向けです。

前置き（注意）

　この記事で書くのは僕の感覚的なことです。
　背景にある理論とかそういうのは僕はわからないです。
　ただまぁ多分感覚でなんとかなります（多分）。


焼きなまし法の概要

  • 山登り法にランダム性を入れて局所解に陥りにくくしたもの
  • スコアが改善されたら無条件遷移だが、悪化のときも確率的に遷移する
  • ランダム性を時間経過に応じて小さくしていくことで収束させていく

ややこしそうに見えますが、実際にはやることは超単純です（後述）。
極論、山登り法さえ実装すれば後はテンプレに入れるだけです。
欠点: 状態を少しいじるという操作が難しい問題が存在して、ビームサーチ解に勝ちにくいことがある（けど最近頻度が低い）

山登り法の概要

  • 今持っている状態を少しいじってスコアがよくなったら更新するということを延々繰り返すもの

適切にこれを書けば短時間コンテストなら勝てることがたまにあります。
欠点: 焼きなまし法の劣化版なので単体で勝てることは滅多にない


山登り法のパーツ

山登り法で必要なもの

  • 初期状態（一番最初の状態）
  • 状態遷移（今ある状態を少しいじって新しい状態を作る）
  • スコア計算の関数（状態を受け取ってそのスコアを返す関数）
初期状態

　基本的にシンプルな貪欲法などによるアルゴリズムで初期状態を構成することが多いです。
　ランダムでも問題ない場合もあります。
　問題によっては初期状態によってスコアが有意に変わったりしますが、それは後で考えればいいです。

スコア計算の関数

　状態のスコアとして、問題で与えられた得点に加えて何かしら自分で特徴量を加えて新たな値を設定するとよい場合があります。
　また、高速化のため実際の得点の計算式を簡略化したものを用いる場合もあります。
　スコア関数は近傍の定義の仕方とも絡むので時には難しいですが、最初から色々考えてもしょうがないのでとりあえず問題で与えられた得点をそのままスコアとして実装して、あとから調整すればいいと思います。

遷移関数

　この後山登り法を焼きなまし法に拡張するので拡張することを前提に遷移関数を考えます。
　焼きなまし法で他の人と明確に違いが生まれ得るのはこのパートだけです*1。
　僕が思う遷移関数が満たすべき性質は以下の3つです

  • 計算が軽いこと（焼きなまし法は試行回数が命です）
  • 任意の状態に確率的に遷移できること（到達しにくそうな状態があったら無理やり確率的にねじ込んだり）
  • 状態遷移が極端でないか（良い状態の近くには良い状態が、悪い状態の近くには悪い状態があるようにすること）

計算が軽いことは必須です。焼きなまし法の精度は試行回数と強い相関があるので、残りの2条件が満たされている限り極力処理が軽いものを遷移関数にしましょう。
任意の状態に遷移できない場合、探索範囲が限定されてしまいます。探索できない範囲が全て悪い解であることが保証されてるならいいですが基本的には任意の状態に遷移できるべきです。
3番目の条件が最も大切です。スコア100の状態からスコア110の状態に遷移するには途中で-1000の状態を経由しなければいけないというように遷移関数が定義されていたら絶望的です。この条件を満たすようにするコツは、よい状態から遷移しうる状態をすべて"いい感じ"の状態にすることです。例えば、ブロックの敷き詰めるような問題の場合、ブロックを削除するという遷移をするとどうしてもスコア減ってしまって嬉しくなく、削除と追加をワンセットにしたり、ブロックがない状態を適切に評価する特徴量を追加するなどして調節することが大切です。

ソースコード的には以下のものを実装すればいいです
高速化とかは後述で

//状態
struct STATE {
};

// 状態の初期化
void init (STATE& state) {
}

// 状態遷移
void modify (STATE& state) {
}

// 状態のスコア計算
int calc_score (STATE& state) {
}

// 山登り法
void mountain() {
    STATE state;
    init(state);
    double start_time; // 開始時刻
    while (true) { // 時間の許す限り回す
        double now_time; // 現在時刻
        if (now_time - start_time > TIME_LIMIT) break;

        STATE new_state = state;
        modify(new_state);
        int new_score = calc_score(new_state);
        int pre_score = calc_score(state);

        if (new_score > pre_score) { // スコア最大化の場合
            state = new_state;
        }
    }
}

焼きなまし法のパーツ

焼きなまし法で必要なもの

  • 山登り法
  • 温度関数（どの時間帯にはどの程度のスコアの悪化を許すかの目安）
  • 遷移確率関数（新たな状態に遷移する確率を決定する関数）

温度関数や遷移確率関数を決めるのが面倒くさそうですが、テンプレ通りである程度大丈夫です。

温度関数
start_temp = (一回の遷移で動きうるスコア幅の最大値程度);
end_temp = (一回の遷移で動きうるスコア幅の最小値程度);
temp = (線形でstart_tempからend_tempに減少する);

としておけばよいです。
最終的にはそれぞれチューニング対象ですが、まずは何も考えずこれでいいと思います。

遷移確率関数
prob = exp((new_score-pre_score)/temp);

としておけばいいです。とりあえずこの式つかっときゃいいです（よくわかってない人）。
この式が満たしている嬉しい性質は

  • スコアが改善しているときは遷移確率が1以上になる
  • スコアが悪化しているときは悪化度合いが大きいほど遷移しにくい
  • 温度が大きいときほど悪い方向にも遷移しやすい

の3つです。チューニング段階ではこの3つ満たしている式に適当に置き換えたり、expは遅いので近似したりします。

温度関数や遷移確率関数については以下の記事がわかりやすいです。
shindannin.hatenadiary.com
つまり、最終的なチューニング作業を除けば、山登りから焼きなましへの移行は機械的に終わります。
短時間コンテストでは温度などのチューニングはせずに高速化だけして終わったりします（実際テンプレのパラメータは割と優秀なので）。

ソースコード的には以下のものを実装すればいいです。

//状態
struct STATE {
};

// 状態の初期化
void init (STATE& state) {
}

// 状態遷移
void modify (STATE& state) {
}

// 状態のスコア計算
int calc_score (STATE& state) {
}

// 焼きなまし法
void sa() {
    STATE state;
    init(state);
    double start_temp, end_temp; // 適当な値を入れる（後述）
    double start_time; // 開始時刻
    while (true) { // 時間の許す限り回す
        double now_time; // 現在時刻
        if (now_time - start_time > TIME_LIMIT) break;

        STATE new_state = state;
        modify(new_state);
        int new_score = calc_score(new_state);
        int pre_score = calc_score(state);

        // 温度関数
        double temp = start_temp + (end_temp - start_temp) * (now_time-start_time) / TIME_LIMIT;
        // 遷移確率関数(最大化の場合)
        double prob = exp((new_score-pre_score)/temp);

        if (prob > (rand()%INF)/(double)INF) { // 確率probで遷移する
            state = new_state;
        }
    }
}


例

atcoder.jp
この問題を例に雛型を埋めてみます。まずは山登り法です。

  • 状態としては各セルに割り振った数字の二次元配列をそのまま持てばよさそうです
  • 初期状態は各数字をランダムに入れてもいいですし、適当な貪欲で数字を埋めてもいいです
  • 状態遷移は例えばあるセルの数字をランダムに変更することにします
  • スコア計算はその状態の点数を計算するものとします（アレンジを加えず）

次に焼きなまし法にします。

  • start_tempは50ぐらいにして、end_tempは10ぐらいにしておきます。
  • 温度関数と確率遷移関数はテンプレのものをそのまま使います。

これで焼きなまし法と呼べるアルゴリズムが完成しました。
遷移関数が適切か評価してみます。

  • 十分軽いか ... セル1つの値を変えるだけなのでこの上なく軽そうです
  • 任意の状態に遷移できるか ... 明らかに可能です
  • 状態遷移が極端でないか ... 少し怪しいですが、影響を受けるのは高々そのセルを含むブロックだけなので減少スコアは小さいと思ってよい気がします


焼きなまし、その後

一通り焼きなましの雛型がそろってそれっぽいスコアが出たとして、その後何をするかです（代表的なもの）

  • 高速化
  • 初期状態の吟味
  • 温度関数、状態遷移関数の調整
  • 遷移関数の調整
  • 焼きなましの繰り返し
高速化

頑張りましょう。コンテストによっては皆似たような遷移関数を定義します。そのときは速い人の勝ちです。
先ほどの雛型ではscore計算が分離されていましたが、極力状態遷移と同時にdiffだけ計算するようにしましょう。
速度が1割速くなるだけでも有意にスコアが上がることが多いです。プロファイラやその他を使ってひたすら高速化しましょう。
速度のために精度やその他が多少犠牲になってもスコアが上がることも多いです。

初期状態の吟味

問題によっては初期状態の影響を受けてしまう場合が往々にしてあります。
基本的に貪欲で埋めればよいと思いますが、色々試してみるとよいかもしれないです。

温度関数、状態遷移関数の調整

虚無作業ですが、場合によっては結構スコアに影響します。
いじって、実験してを繰り返します。十分なテストケース数を用意してから調整しましょう。過学習するとよくないです。

遷移関数の調整

遷移関数には乱数性がありますが、スコアが高そうなものを高い確率で選ぶようにしたりとちょこちょこいじってみるといいかもです。

焼きなましの繰り返し

例えばn回焼きなましを行うとするとそれぞれの焼きなましに使える時間は1/nになってしまいますが、こうして分割したほうがスコアが高くなる場合があります。余裕があるとやってみるといいかもです。

以上を踏まえて、僕が前にやったマラソンマッチでの焼きなましです（あくまで、例です）。かなり雑ですみません。

gasin.hatenadiary.jp
gasin.hatenadiary.jp

焼きなましの資料集（日本語）

以下の記事を読めばこの記事なんて読まなくていいという話がありますが、はい。

atsさんによる焼きなまし法を用いたコンテストの参加記のエントリがたくさんあります。
ats5515.hatenablog.com
hakomoさんによる焼なまし法の解説です。
github.com
診断人さんによる焼きなまし法のテクニック集です。
shindannin.hatenadiary.com
tomerunさんによる焼きなましの高速化の話です。
topcoder.g.hatena.ne.jp

*1:速度なりパラメータなり温度管理などありますが本質的には