Neural Combinatorial Optimization with Reinforcement Learning http://arxiv.org/abs/1611.09940 深層学習で組合せ最適化をする論文で、TSPを題材に、Vinyalsらが最適解を用いた教師付き学習でツアーを直接生成していたのに対して、方策勾配法による強化学習をすることで、よりよい結果を得られた。

Pointer Network は sequence-to-sequence と attention を用いたモデルで、ツアーで順列のそれまでの要素で条件付けされた次の要素の確率分布を得られるが、
(1) 強化学習で事前学習済みのモデルを使って、最も確率の高い要素を貪欲に選択、
(2) 事前学習していないモデルでアクティブサーチ、
(3) 強化学習で事前学習済みのモデルでサンプリング、
(4) 強化学習で事前学習済みのモデルでアクティブサーチ、
で比較して、(4)が一番良かった。 (2)も時間はかかるが近い解を発見できる。

得られた解はChristofidesヒューリスティクスや、 Google OR Tools の vehicle routing の local search ソルバよりも良い解だった。使っている問題は100ノードとそんなに大きくない(?)気がするけど、面白い結果。

こういうのは ChainerRL とか使うと簡単に実装できたりするのかなぁ……