kaggleの最適化コンペ "Traveling Santa 2018" にソロで参加しました。結果は1874チーム中328位。着手したのが2018/12/22と遅く、冬休みはまるまる何もできず。かけた時間がいくら何でも少なすぎました。スコアが平凡であまり価値はありませんが、記録としてやったことをメモしておきます。
問題概要
2次元座標上に197769個の都市が与えられる。都市には0から197768までの番号が付いている。0から始まりすべての都市を１つずつ通る経路のうち、「経路の総距離」と「ペナルティ」の和からなるスコアが小さくなるような経路を見つける。
ここで、ペナルティは、経路を構成する都市のうち10個おきに発生しうる。もしその都市の番号が素数ならペナルティなし、素数でないなら、その都市と次の都市との間の距離に0.1をかけた値がペナルティとなる。正確な理解のためには https://www.kaggle.com/seshadrikolluri/understanding-the-problem-and-some-sample-paths を参照すること。
初期検討 - 自力実装
都市番号順に並べるだけの愚直解で 446884407.52。スコア計算が正しくできていることを確認。
初期解を求める方法を2つ実装。
1つ目はNearest Neighbor法。都市0から始めて、未使用の都市のうちもっとも近い都市を繋いでいく方法。これでスコアは1812602.18点。
2つ目は挿入法。都市0→都市1→都市0と戻る最小構成の経路を最初に作成。総距離の増加長をもっとも短くなる場所を選んで都市2, 都市3, ...を順に挿入していく。スコアを記録し忘れたがNN法よりはよかったはず。
当初は、これらで得られる経路を初期解として、後述する経路組み換えを行いスコア改善を狙った。焼きなましも実装した。しかしスコアの改善に行き詰まり、1652066.12点が限界。
Concordeの導入
カーネル https://www.kaggle.com/blacksix/concorde-for-5-min を実行。これは巡回セールスマン問題のソルバであるConcordeを実行するというもの。わずか5分で1518313.05点が出て衝撃を受ける。 これで603位相当。
Concordeは商用利用不可とあったので使って良いのか不安だったが、https://www.kaggle.com/c/traveling-santa-2018-prime-paths/discussion/72767 を読むとConcordeを使ってよいことがわかる。 そこで今後はConcordeの解を初期解として使っていくことにする。
経路組み換えの実装
Concordeで得られる経路を初期解とする。これに以下の経路組み換えを行い、スコアの低減を目指した。
- 2都市のスワップ
- 1都市を経路から削除し他の場所に挿入
- 経路の一部分をreverse
スコアを高速に計算できるように、「経路の総距離」と「ペナルティ」とを分けて持つ工夫をした。上記のどの経路組み換えを行っても「経路の総距離」は一瞬で計算できる。「ペナルティ」は残念ながら再計算が必要だが、それでも最悪で全都市の1/10について再計算すればよい。
また、例えば2都市を入れ替えるとき、遠くにある2都市を入れ替えても意味がない。そこで、各都市についてその近傍の都市をN個（N=10, のちに20) 持っておくようにした。これによりスコアが改善する可能性がある経路組み換えだけを実行できる。
Concordeの初期解に対して上記の経路組み換えを適用して山登りすることで、130ポイントほどスコアが向上することを確認できた。
本当は上記以外にもより複雑な経路組み換え法 (3-optなど) を実装したかったのだが、餅とおせちを食べるのに忙しくなり進捗がなくなる。その間に次々と激強カーネルが投稿された影響で順位が大幅に下がっていることに気付く。これらの激強カーネルの結果を初期解として、上記経路組み換えを行って少しだけスコア改善したものを投稿、というしょうもないことを片手間でしばらくやった。スコア改善に寄与したのは上記の方法のうち2と3だけだったように思う。スコア改善とはいっても改善幅はほんのわずかで、行き詰まりを感じる。
そこで焼きなましを導入してスコア改善を図ったが、スコアが低下したまま向上してくれず、全然うまくいかなかった。
セグメント単位の焼きなまし
終了日前日、経路を適当な長さ（100程度）のセグメントに分割し、セグメント単位で焼きなましを行うことを思いつく。ハイパーパラメータの調節をする暇は全然なかったし、一晩しか回せなかったので全セグメントを舐めきることもできなかったのだが、それでも効果はあった。終了直前に投稿されたカーネルのスコア1515564.01から、1515562.86まで改善。だがここで時間切れ。コンペ終了後も12時間ほど動かしたら1515561.30になったことからまだ少しはポテンシャルがあった。もっと早くこの方針に辿りつくべきだった。とはいえブロンズ圏内である1515493.13までたどり着くためにはこれだけでは足りなかったと思われる。
反省点
- 他人のカーネルを使わせてもらうばかりで中をほとんど読まなかった。PythonのNumbaを使って高速計算したり、C++のコードを文字列としてファイル保存・コンパイルすることでC++のコードを動かしたり、Concordeのソースを持ってきてビルドして実行したりといった技が詰まっていたので後でも勉強したい。
- 久しぶりにC++を書くと経路組み換え時のスコア計算がバグだらけでデバッグが大変だった。数十都市からなるミニデータでデバッグするのは有用だったのでもっと簡単にデータを切り替えられるようにしたい。
- 経路を長さ10程度のセグメントに区切って、全経路順を生成してスコア最小のパスを選ぶ実装は簡単なのでやっておくべきだった。
