blog2019-09-03誰でもできる焼きなまし法マラソンマッチマラソン系コンテストに興味のある競プロer向けです。焼きなましの繰り返し焼きなましの資料集(日本語)前置き(注意)この記事で書くのは僕の感覚的なことです。背景にある理論とかそういうのは僕はわからないです。感覚でなんとかなります(多分)。山登り法にランダム性を入れて局所解に陥りにくくしたものスコアが改善されたら無条件遷移だが、悪化のときも確率的に遷移するランダム性を時間経過に応じて小さくしていくことで収束させていくややこしそうに見えますが、実際にはやることは超単純です(後述)。極論、山登り法さえ実装すれば後はテンプレに入れるだけです。今持っている状態を少しいじってスコアがよくなったら更新するということを延々繰り返すもの適切にこれを書けば短時間コンテストなら勝てることがたまにあります。基本的にシンプルな貪欲法などによるアルゴリズムで初期状態を構成することが多いです。ランダムでも問題ない場合もあります。問題によっては初期状態によってスコアが有意に変わったりしますが、それは後で考えればいいです。状態のスコアとして、問題で与えられた得点に加えて何かしら自分で特徴量を加えて新たな値を設定するとよい場合があります。高速化のため実際の得点の計算式を簡略化したものを用いる場合もあります。スコア関数は近傍の定義の仕方とも絡むので時には難しいですが、最初から色々考えてもしょうがないのでとりあえず問題で与えられた得点をそのままスコアとして実装して、あとから調整すればいいと思います。遷移関数この後山登り法を焼きなまし法に拡張するので拡張することを前提に遷移関数を考えます。焼きなまし法で他の人と明確に違いが生まれ得るのはこのパートだけです*1。僕が思う遷移関数が満たすべき性質は以下の3つです計算が軽いこと(焼きなまし法は試行回数が命です)任意の状態に確率的に遷移できること(到達しにくそうな状態があったら無理やり確率的にねじ込んだり)状態遷移が極端でないか(良い状態の近くには良い状態が、悪い状態の近くには悪い状態があるようにすること)計算が軽いことは必須です。焼きなまし法の精度は試行回数と強い相関があるので、残りの2条件が満たされている限り極力処理が軽いものを遷移関数にしましょう。任意の状態に遷移できない場合、探索範囲が限定されてしまいます。探索できない範囲が全て悪い解であることが保証されてるならいいですが基本的には任意の状態に遷移できるべきです。3番目の条件が最も大切です。スコア100の状態からスコア110の状態に遷移するには途中で-1000の状態を経由しなければいけないというように遷移関数が定義されていたら絶望的です。この条件を満たすようにするコツは、よい状態から遷移しうる状態をすべて"いい感じ"の状態にすることです。ブロックの敷き詰めるような問題の場合、ブロックを削除するという遷移をするとどうしてもスコア減ってしまって嬉しくなく、削除と追加をワンセットにしたり、ブロックがない状態を適切に評価する特徴量を追加するなどして調節することが大切です。温度関数(どの時間帯にはどの程度のスコアの悪化を許すかの目安)遷移確率関数(新たな状態に遷移する確率を決定する関数)温度関数や遷移確率関数を決めるのが面倒くさそうですが、テンプレ通りである程度大丈夫です。(線形でstart_tempからend_tempに減少する);としておけばよいです。最終的にはそれぞれチューニング対象ですが、まずは何も考えずこれでいいと思います。exp((new_score-pre_score)/temp);としておけばいいです。この式つかっときゃいいです(よくわかってない人)。この式が満たしている嬉しい性質はスコアが改善しているときは遷移確率が1以上になるスコアが悪化しているときは悪化度合いが大きいほど遷移しにくい温度が大きいときほど悪い方向にも遷移しやすいの3つです。チューニング段階ではこの3つ満たしている式に適当に置き換えたり、expは遅いので近似したりします。温度関数や遷移確率関数については以下の記事がわかりやすいです。shindannin.hatenadiary.comつまり、最終的なチューニング作業を除けば、山登りから焼きなましへの移行は機械的に終わります。短時間コンテストでは温度などのチューニングはせずに高速化だけして終わったりします(実際テンプレのパラメータは割と優秀なので)。ソースコード的には以下のものを実装すればいいです。}}例atcoder.jpこの問題を例に雛型を埋めてみます。状態としては各セルに割り振った数字の二次元配列をそのまま持てばよさそうです初期状態は各数字をランダムに入れてもいいですし、適当な貪欲で数字を埋めてもいいです状態遷移は例えばあるセルの数字をランダムに変更することにしますスコア計算はその状態の点数を計算するものとします(アレンジを加えず)次に焼きなまし法にします。start_tempは50ぐらいにして、end_tempは10ぐらいにしておきます。温度関数と確率遷移関数はテンプレのものをそのまま使います。これで焼きなまし法と呼べるアルゴリズムが完成しました。遷移関数が適切か評価してみます。コンテストによっては皆似たような遷移関数を定義します。そのときは速い人の勝ちです。先ほどの雛型ではscore計算が分離されていましたが、極力状態遷移と同時にdiffだけ計算するようにしましょう。速度が1割速くなるだけでも有意にスコアが上がることが多いです。プロファイラやその他を使ってひたすら高速化しましょう。速度のために精度やその他が多少犠牲になってもスコアが上がることも多いです。問題によっては初期状態の影響を受けてしまう場合が往々にしてあります。虚無作業ですが、場合によっては結構スコアに影響します。いじって、実験してを繰り返します。十分なテストケース数を用意してから調整しましょう。過学習するとよくないです。遷移関数には乱数性がありますが、スコアが高そうなものを高い確率で選ぶようにしたりとちょこちょこいじってみるといいかもです。焼きなましの繰り返し例えばn回焼きなましを行うとするとそれぞれの焼きなましに使える時間は1/nになってしまいますが、こうして分割したほうがスコアが高くなる場合があります。余裕があるとやってみるといいかもです。以上を踏まえて、僕が前にやったマラソンマッチでの焼きなましです(あくまで、例です)。gasin.hatenadiary.jpgasin.hatenadiary.jp焼きなましの資料集(日本語)以下の記事を読めばこの記事なんて読まなくていいという話がありますが、はい。atsさんによる焼きなまし法を用いたコンテストの参加記のエントリがたくさんあります。ats5515.hatenablog.comhakomoさんによる焼なまし法の解説です。github.com診断人さんによる焼きなまし法のテクニック集です。shindannin.hatenadiary.comtomerunさんによる焼きなましの高速化の話です。検索はてなブログをはじめよう!gasinさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。