AtCoder Heuristic Contest 001
アルゴリズムの流れ
- 解(=各企業の領域)を初期化する
- いくつかの企業の領域を変更する(突然変異)
- 全ての企業をある方向に寄せる(引力発生)
その際、評価値が低い企業は引き伸ばす
3. は方向を変えて4回繰り返す - 2.3.の操作を近傍とみなして焼き鈍し
- 最後に、最良解について、微調整を行う
初期化
すべての企業の領域を、その基準点を囲う面積1の正方形とする
突然変異
ターゲット指定/範囲指定/ランダム の3種類から1つを行う
採用確率は
序盤から中盤 : 80%/14%/6%
終盤 : 20%/56%/24%
ターゲット指定
- 面積がr * max_per_r * 0.95より小さい企業からランダムにターゲット企業を選ぶ
※ max_per_r は時間経過につれて大きく - ターゲット企業の新しい端点y1 y2 x1 x2を、
世界の端(0または10000)と基準点の間からそれぞれ一様ランダムに選ぶ - ターゲット企業の評価値が大きく悪化していたら2からやり直し
- 他の企業の基準点を内包していたら2からやり直し
※ 累積和でO(1)で判定 - ターゲット企業と接触している企業の領域を適切に縮小する
※ すべての企業について愚直に確認 O(n)
※ y1 y2 x1 x2のうち1つを変更することで縮小
範囲指定
- ある大きさの正方形を一様ランダムに配置
※ 1辺の長さは時間経過とともに短く - 正方形と接触しているすべての企業の面積を1にする
ランダム
- すべての企業について、ある確率に基づいて面積を1にする
※ 確率は時間経過とともに小さく
引力発生
- 引力方向を決める
- 評価値を改善するターゲットとして「評価値の低い企業 + ランダムにいくつか」を選択
- 基準点が引力方向に近い企業から順に、引力をかける
・ターゲット→引力方向に、衝突するギリギリまで引き伸ばす。ただし、面積がr * max_per_r を超えないように調整
・非ターゲット→引力方向に、衝突するギリギリ/基準点が飛び出さないギリギリ まで平行移動
※ 区間をsetで管理する or 遅延セグ木を使う → 全体でO(nlogn)
※ 実際は区間をvectorで管理したほうが早かったのでそうした
1~3を方向を変えて4回繰り返します。
微調整
- 企業と企業の境界線を1マスずらしてみて、評価値が改善されるなら採用
- 引力発生(ただし平行移動のみ)
これらをたくさんやる
何をしたら伸びた？
最初期は引力のみ
突然変異を導入
← それまでは領域の縮小が無かったので、当然伸びる
引力発生の3において max_per_rを導入
← 想像以上に伸びてびっくりした
スペースに余裕のある企業は後でどうにでもなるので、
評価値の低い企業にスペースを譲るのが大事？
突然変異にターゲット指定を追加
← これも結構伸びた
ターゲット指定においてターゲットと接触した企業の対処を、
面積を1にする にしていたが 適切に縮小する に変更
↓
1回の突然変異に対して引力発生を30回行っていたが、
4回に減らしても改善解が発見されるようになった
← 近傍探索を行える回数が増えたので伸びた
微調整を導入
← 結構伸びる
(焼き鈍しフェイズがざっくりしているから というのは要因としてありそう)
定数倍高速化は行う度に大きく伸びた
山登りと焼き鈍しはあまり変化が無かった気がする...?
困ったこと
点数の分散が大きく(同じコードをsubmitしても49599~49624のブレ)、
コードの変更が改良なのか改悪なのか判断できなくて困った。
どうすればいいのでしょうか。
次回の長期マラソンではやりたいこと
- 解が改善されていく様子を確認するためのビジュアライザの作成
- パラメータチューニング
- 何をしたら何点伸びたのかメモしておく
