kaggle Traveling Santa 2018 参加記

kaggleの最適化コンペ "Traveling Santa 2018" にソロで参加しました。結果は1874チーム中328位。着手したのが2018/12/22と遅く、冬休みはまるまる何もできず。かけた時間がいくら何でも少なすぎました。スコアが平凡であまり価値はありませんが、記録としてやったことをメモしておきます。

問題概要

2次元座標上に197769個の都市が与えられる。都市には0から197768までの番号が付いている。0から始まりすべての都市を1つずつ通る経路のうち、「経路の総距離」と「ペナルティ」の和からなるスコアが小さくなるような経路を見つける。

ここで、ペナルティは、経路を構成する都市のうち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で得られる経路を初期解とする。これに以下の経路組み換えを行い、スコアの低減を目指した。

  1. 2都市のスワップ
  2. 1都市を経路から削除し他の場所に挿入
  3. 経路の一部分を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程度のセグメントに区切って、全経路順を生成してスコア最小のパスを選ぶ実装は簡単なのでやっておくべきだった。

"WslRegisterDistribution failed with error"への対応法(追記あり)

Windows 10にてwindows subsystem for linuxを利用したUbuntu 16.04を立ち上げると、以下のようなエラーが出て起動に失敗しました。(エラーコードの部分は0x800703faです)

Installing, this may take a few minutes...
WslRegisterDistribution failed with error: 0xXXXXXXXX
Error: 0xXXXXXXXX The parameter is incorrect.
Press any key to continue...

心当たりがあるとすれば、前回の起動時にsudo apt-get update && sudo apt-get upgradeしたときに、途中でエラーが出て失敗したのでCtrl - Cでkillしたことです。

How to resolve 'WslRegisterDistribution failed with error: - Microsoft Community にあるように以下のことをすると無事起動できるようになりました。

元回答とは異なり、自分の場合はsudo apt-get updateまでで大丈夫でした。


(2018/12/30追記) 後日、Windowsの再起動後に、上記と同じ"WslRegisterDistribution failed with error"が出ました。上記の対応法に則り、bashと打ちEnterをおしたところ、以下のエラーメッセージとともに失敗しました。

> bash
Windows Subsystem for Linux には、ディストリビューションがインストールされていません。
ディストリビューションは Microsoft Store にアクセスしてインストールすることができます:
https://aka.ms/wslstore
続行するには何かキーを押してください...

今度は以下の対応法をとることで再度Ubuntuが復活しました。

  • Windowsの機能の有効化または無効化」を開く
    • Explorerに「コントロール パネル\プログラム\プログラムと機能」と入力して、左側のペインから選ぶと簡単
  • "Windows Subsystem for Linux" にチェックが付いているはずなので、チェックを外してWindowsを再起動
  • 再度 "Windows Subsystem for Linux" にチェックを付けてWindowsを再起動

Visual Studio Codeで等幅フォントを使う

Visual Studio Codeはデフォルトだと日本語が等幅で表示されません。

f:id:minus9d:20181222110013p:plain

そこで以下の手順により、日本語がある場合でも等幅で表示されるようにしました。

  1. 公式ページ から Myrica.ttc をダウンロードし、インストール
  2. Visual Studio CodeCtrl + ,して設定を呼び出し、"font family"の欄に'Myrica M'を追加
    • f:id:minus9d:20181222110551p:plain

その結果、以下のようにいい感じに文字が表示されるようになりました。

f:id:minus9d:20181222110659p:plain

中古ノートPC Dynabook R734 を買いました

外での活動用にノートPCがほしいなと思っていました。友人からDynabookの中古はいいと聞いていたのでDynabook決め打ちで検索をかけ、2014年モデルのモバイル用ノートであるDynabook R734/E26KRを楽天市場で購入しました。外側に傷こそ目立つものの、中は予想していたよりもきれいで、バッテリーも4時間程度は持つ個体が来ました。十分満足いく部類だと思います。

スペック

私の入手した個体の主なスペックは以下のとおりです。詳細は R734 2014年7月発表モデル|ダイナブック(東芝) をご覧ください。

  • CPU: Core i5 4200M
    • PassMarkによるとスコアは4034。2017年発売のCore i3 7130Uのスコアが4033で、だいたい同じです。
  • メモリ: 4GB
    • スロット数は2で空きスロット数が1。追加で PC3L-12800(DDR3L-1600)規格の4GBのメモリ を購入して増設しました。8GBのメモリにするか迷いましたが、自分の使用頻度を考えるとオーバースペックかなと。
  • ストレージ: HDD 160GB
    • 手元のSSDで換装しました。
  • 大きさ・質量
    • 13.3型ディスプレイ、約1.5kg。光学ドライブがある分少し重いです。

長所

  • 増設の容易さ
    • 裏蓋のネジを4個外すだけで容易にメモリとストレージを交換できる設計なのが良いです。アップグレードを初心者でも自力で行えるのは魅力的です。アップグレードすれば、バリバリ開発するのでなければ今でも戦えるスペックになると思います。

短所

  • 画面解像度の低さ
    • 1,366×768は今の時代だと多少見劣りします。
  • 少し重い
    • MacBook Airなどと比べると少し重いですが、持ち運びの頻度の少なさを考えると完全に許容範囲です。
  • 旧世代のメモリが必要
    • 今から旧世代のメモリを買うのに少し抵抗がありました。中古もそれほど値段が落ちてないんですよね。

総評

本体17,000円 + メモリ3,000円 でそこそこのマシンを入手できて十分満足いく買い物ができました。

注意点

中古でノートPCを買う際の注意点です。運によるところも大きいですが、避けられるものは避けましょう。

  • バッテリー欠品、充電不可の個体があります。値段の安さにつられて誤って購入しないよう注意書きをよく読みましょう。
  • 同じ"R734”でも、CPU、メモリ、ストレージ、OSが異なった個体が大量に存在します。誤って自分の期待しない機種を買わないようスペックを確かめましょう。
  • R734の赤塗装は剥がれやすいようで、どの個体も傷が目立つものが多かったです。気になるなら写真をよく見るか、他機種を探しましょう。

Windows 10の環境構築

Windows 10がブルースクリーンを繰り返す事態に見舞われ、やむなく新しいSSD ( Samsung SSD 500GB 860EVO ) を調達してWindows 10を新規インストールしました。環境構築でやったことをメモします。

CapsをCtrlに

Ctrl2cap

インストーラで個別にインストール

基本アプリ

開発

ドライバ類

Chocolateyを使ってインストール

Chocolateyで大体のソフトが入ります。用心のため基本的に1万ダウンロードの実績があるものしか採用していません。cinst -y [アプリ名]とするとインストールの可否を問われることなくインストールされます。

editor

  • pycharm-community
  • visualstudiocode

開発

一般アプリ

以下は経験上Chocolateyで入れないほうがよいソフトです

Windows Subsystem for Linux の環境構築

  • 最初に
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install emacs lv zsh build-essential 

Cygwinの環境構築

  • Archive
    • unzip, zip
  • Devel
    • cmake, gcc-g++, git, make
  • Editors
  • Python
    • ぜんぶ
  • Shells
  • Utils
    • lv
  • Web

Topcoderの環境構築

greedを入れる(要追記)

各種設定

HACK TO THE FUTURE 2019予選 参加記 のまとめ

北大日立マラソン1st 参加記 のまとめ - minus9d's diary北大日立マラソン2nd 参加記 のまとめ - minus9d's diary に引き続き、HACK TO THE FUTURE 2019予選 - AtCoderの参加記を勝手ながらまとめました。

順位 atcoderのID URL 備考
1 kimiyuki HACK TO THE FUTURE 2019予選: A - ばらばらロボット
2 tomerun twitter
3 ats5515 twitter
4 sugim48
5 maroonrk
6 kurenai3110
7 shindannin HACK TO THE FUTURE 2019予選の反省 - じじいのプログラミング
8 hoshi524 twitter
9 WA_TLE
10 omi
11 not twitter (終了後、142k!)
12 spica314 twitter
13 hakomo twitter, twitter
14 packer_jp twitter
15 shamal_ref twitter
16 tanzaku twitter
17 tsukasa_diary twitter
18 YujiSoftware twitter
19 sumoooru twitter
20 iwashi31 twitter
21 math twitter
22 minus9d(自分です) minus9d's diary

HACK TO THE FUTURE 2019予選 参加記

HACK TO THE FUTURE 2019予選に参加しました。8時間中7時間半ほど参加して22位でした。前回より1位だけランクアップしましたが順位表の1ページ目には入れず残念。

試行ログ

まずは周囲に壁をつくるだけの初期配置を試し、80904点。


マークを盤面いっぱいにランダムに配置して点数を計算する方法を実装し、91248点。試行回数は手元で2700回ほど。


山登り法を実装。すなわち、ある盤面に対してランダムな位置にランダムなマークを配置し、点数が上がれば採用。114674点。このあたりで方向性がつかめてくる。


ベストなスコアを出す盤面について、付与されたマークの数を数えてみると、LやRの出現頻度がD, T, #よりもかなり多いことに気付く。そこでマークとしてLやRのみしか使わないようにする。119184点。


このあたりからはかなり怪しい修正を繰り返した。値は上がったり下がったりを繰り返していたので、どれがどれくらい効いたかがよくわからない。

  • 焼きなましの導入。点数の減少率が閾値以下であれば、ある確率でその変化を受け入れる。
  • マークを配置するマス目を左上からラスタスキャン順に全部試す
  • スコアが変わらなければ遷移
  • 変更するマスが必ず今と異なるマークとなるようにする(これは当たり前)
  • スコアの計算をするとき、停止カウントが4以上のマスにも点数に違いを与えて少しでもよい状態の方に遷移しやすくするように変更。

最終的なベストスコアは126504点で22位。正の点数を取った人が518人なので上位5%にすべりこめた。

本番中に気付いていたが実装できなかったアイデア

  • 点数再計算のとき、影響を受けるマス以降のみを再計算

本番中に気付かなかったアイデア

  • 命令列の圧縮
  • L, Rのマス上で動きに影響を受けるロボットだけ再計算する
  • 中央に近いマスから順番にマークを変える(終了後の動画より)
  • 初期盤面を全部Lで埋めて始める notさんのツイート
  • L, Rしか使わないと決めることでシミュレーションのコードを簡単化
  • example_01 の解をコードに埋め込む

感想と反省

終了後の動画解説の通り、L, Rだけ使うという方針に早期に辿りつけたのはよかったです。しかしD, T, #も用意されているからにはどこかで使うべきなのではないかとの疑念が頭を離れず、その後もちょくちょく復活を試みていたのは結果からいうと時間の無駄でした。また、LとRしか使わないことを決断してしまえばもっと高速化できる余地がありましたが、その発想に至れませんでした。

ずっとZipで配布された盤面のみを使って検討をしていましたが、検討が煮詰まってくるとローカルの点数から提出後の点数を予測するのが難しくなっていました。サボらず複数盤面からローカルの点数を算出したほうが結果的には無駄がなかったかなと思います。