概要
先日Atcoderにて開催されたAtcoder 第3回 Asprova プログラミングコンテストに参加しました。
初めてのマラソンマッチ参加であり、焼きなまし法の実装すら初めてということで結果は23位となかなか残念なことになりました。
点数は7.3億点程度。まだまだパラメータ調整や運次第で上がり目はありそうでしたが、トップが11億点弱とかなり差があり、方針が良くなかったのかなと思いあきらめました。
初参加で思ったことをまとめておきたいと思います。
本コンテストは大変残念なことに会社側の意向により終了後も他の人のソースコードが見れないのですが、有りがたいことに1位の方の解説記事を発見しましたので、そちらを参考にさせていただいております。これが無いと何も反省できない状況だったので、本当に有りがたいです。
焼きなまし法かビームサーチか
マラソンマッチというと大体この2つの手法のどちらかが使われるようです。
ビームサーチはまだ実装したことが無いのですが、「ゲームのように時系列があるもの」はビームサーチ、それ以外は焼きなましなのかなあと勝手に思っていたので、今回は焼きなまし法を実装しました。
焼きなまし法で方針として考えるべき3つのこと
焼きなまし法を始めるに当たり、重要なのは以下の3点だと思いました。
- 初期解
- 遷移方法（近傍の取り方）
- 評価関数
初期解
初期解とはすなわち焼きなまし法の「スタート地点」のことです。
今回私は特に何も考えず能力追加が無い状態を初期解にしてしまいましたが、これがあまりよくなかったようで、
「とりあえず全オーダーが納期に間に合うよう大量に能力を追加した状態」を初期解にした方がよかったようです。
なぜかと言うと、「納期に間に合わない」→「納期に間に合う」の山登りは勾配が急になるのに対し、
「納期に間に合うが能力が追加されすぎ」→「納期に間に合っていて能力も適正」の山登りは勾配がなだらかになるからです。
実際、私のコードでは、全然納期に間に合う方向に遷移してくれず、かなり無茶なことをして無理やり遷移させていました。（スコアの倍率を高めたり、遷移で追加する能力の上限を上げて一発で納期に間に合わせようとしたり…）
もっとも、この工夫だけでは「納期に間に合うより間に合わない方が得」なオーダーを無理やり納期に間に合うようにさせてしまうことがあるので、その壁を超えるためには後述する評価関数が重要になってきます。
遷移方法（近傍の取り方）
今回の問題では、パッと見「どの設備・日にどれだけ能力を追加するか」が状態のパラメータであるように思えます。
ただ、これをもとに遷移しようとすると、あるボトルネック工程の日付がずれるような遷移に対処できず、局所解に陥ってしまうのではと考えました。
そこで代わりに「どの工程にどれだけ能力を追加するか」を状態のパラメータとし、これを変えるように遷移させました。
この場合、「どの工程に～」を「どの設備・日に～」に変換する処理が必要となり、実装したのですが、この処理にかなり時間がかかり高速化を阻害していたと思います。（実際practice05のループが数万回程度しか回りません。1位の人は300万回以上回せていたようで、Javaだからというレベルではないくらい遅いことがわかります）
とはいえ、方針としてはたぶん合っていただろうと思います。
評価関数
勾配をなだらかにするため、実際のスコア関数と別に評価関数を用意するというのは、焼きなまし法を調べればすぐに見つかる手法の一つです。
私も今回「納期に間に合わなくても、近づく」ことに対し一定の点数を得られるような評価関数を組み、それ自体は正しい方針だと思います。
ただ、1位の人は「徐々に評価関数をスコア関数に近づける」という手法を行っており、これは目から鱗でした。
確かに、これなら「納期に間に合わないのに無駄に能力を追加している」という状態を回避できます。
（上記「初期解」「評価関数」の工夫を行いつつチューニングを試行中です。）
感想
- 最初に最適解がどんな感じになるかもっとイメージできると良かったかも。今回は高性能なビジュアライザが提供されたのである程度のイメージはできたが、具体的に「何割くらいが納期に間に合う形を目指せばよいのか」が見えていた方が、初期解や遷移を適切に選べたかもしれない。
- 繰り返しになるが今回は高性能なビジュアライザが提供されたおかげでイメージしやすかったが、そうでないマラソンマッチもあるので、ビジュアライザを作成できるようになっておきたい。Webの勉強やAIの勉強も兼ねJSやpythonの学習を進めておく。
- マラソンマッチはアルゴリズム問題と比べてとっつきにくさがあったが、実際やってみるとなかなか楽しい。賞金ももらえるし、もっとAtcoderでも開催されると嬉しい（訳：賞金が欲しい）。
ソースコード
(工事中)