Attention Solves Your TSP

[Drunkar]

一言でいうと

論文リンク

https://arxiv.org/abs/1803.08475

著者/所属機関

W.W.M. Kool, M. Welling

• University of Amsterdam
• ORTEC Optimization

投稿日付(yyyy/MM/dd)

2018/3/22

掲載誌・学会等

arxiv.org

先行研究と比べてどこがすごい？

• 数学的なstate-of-the-art 解法より良いわけではない。
• AttentionをTSPに使う点ではPointer Network (PN)のalternativeだが、入力ノードの順番によらない。

  技術や手法のキモはどこ？

  どうやって有効だと検証した？

  議論や検証がまだ必要なところはある？

  次に読むべき論文は？

• Pointer Networks: O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692–2700, 2015.

  コメント

• https://github.com/arXivTimes/arXivTimes/issues/794

[Drunkar]

他の組合せ最適化問題にも応用可能か？

Heuristics are typically expressed in the form of rules, which can be interpreted as policies to make decisions. We believe that these policies can be parameterized using DNNs, and be trained to obtain new and stronger algorithms for many different combinatorial optimization problems, similar to the way DNNs have boosted performance in the applications mentioned before.

ヒューリスティクスは決定を行うルールの集合と考えることができるので、DNNsでパラメタライズし学習することでより強力なアルゴリズムを獲得できるはず。

[Drunkar]

計算量

computing a single instance for TSP100 takes 0.03s on a 6850K CPU, whereas we solve 10000 instances using a single 1080Ti in 5s (0.0005s/instance). Our method is O(n 2 ), and given sufficient parallelism runs in O(n),

[Drunkar]

Source Code

https://github.com/wouterkool/attention-tsp