■ [TCO][MM] TCO17 Marathon Round1 
https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16903
やったこと
3段階で焼きなましをした。
- 35*35のグリッド上で、ランダムな頂点をランダムな位置に動かす遷移。評価値は、各辺について目的の長さと実際の長さの差の絶対値
- 点の位置の重複は許す
- 終わったら、各頂点をグリッド内の20*20のどこかにばらまいて700*700にする
- ランダムな頂点をランダムな近傍に動かす遷移。現在の辺の比の最大/最小の少し内側を目標にして、そこから外れた辺にペナルティがつく評価値
- 比が最大/最小の辺に属した頂点をランダムな近傍に動かす遷移。真のスコアが評価値
最後の仕上げとして山登りをした。遷移は、比が最大/最小の辺に属した頂点を微少に動かして、他の辺が最大/最小を超えたら再帰的にその辺の頂点を動かす、というのを一定深さまでやる。
一応無意味ではないかな…くらいの効果はあった（結果のBestsが多かったのはこれのおかげだと思っている）
焼きなましの3フェーズの時間配分は 0.39:0.16:0.45 だった。これと別に最後の山登りに50ms使う。
焼きなましのイテレーション回数は合計6000万回くらい。SSEも使った（高速化の恩恵は1割程度）
時系列で
とりあえず真っ先に思いつくのは比が最大/最小の辺をいじることだけど、最大/最小だけ見てたら評価がハードすぎて一瞬で局所最適にハマりそう。もっとソフトな感じに評価したい。
一瞬バネ物理シミュレーションが浮かんだのだけど、その手の問題は以前ぼろ負けした（TCO13R3）のでひとまず考えないことにする。
というわけでまず焼きなましPhase2だけを作った。これが初日の48万点。
で、いろいろなケースの結果を出力して眺めていたら、長い辺がボトルネックになりがちなことが分かる。
長い辺は後から微調整が効きづらいので、最初の方でだいたい良い感じにしておかないといけない、と考える。
そこで焼きなましPhase1を作った。比で評価すると短い辺の重みが強くなってしまうので、差で評価。これで70万点超え。
ちょこちょこ調整した結果が3submit目の76万点。
ここで満を持してPhase3を追加すると4submit目の78.5万点。
（https://twitter.com/tomerun/status/855468636860891136 ここで言っていた「伸びしろ」はこれのこと）
このあとはほとんど焼きなましの調整と高速化だけだったと言ってよい。
最終日の1日前の段階でアルゴリズム的な改善は打ち止めにして、ここで有給休暇を取って細かい高速化をまとめてやり、最終日に会社行っている間にクラウド使ってパラメタ調整、というのが最近の試合運びのトレンドになっている。
EC2のc4.8xlargeを24時間ほど動かして$17くらい使った。35スレッドだと1000ケースのテストが3分で終わるので良い。
もうちょっと探っておくべきだったかなーというところは、
- 多スタート
- 難しいケースでスコアが0.1くらいぶれることがあるので、その安定性のため
- 辺の目標長を最初から短めに設定しておく
- ちょっとやってみたら良くならなかったので捨てたのだけど、実際最終状態が短い方に寄るケースが多いし、Psyhoさんはこれ入れるとめっちゃ伸びる（余裕で1位超えるくらい）らしいし、もっと時間をかけて見ておくべきだったかも
- 頂点の移動先はランダムじゃなくて辺の向きを考えて選ぶ
- 1位2位はそれをやっているみたいなので
