ここしばらく「巡回セールスマン問題」について試行錯誤していたので、これまでの経過をまとめ。
きっかけはKaggleの2018年の年末に開催していたクリスマス記念のコンペでした。
門脇 大輔 阪田 隆司 保坂 桂佑 平松 雄司
技術評論社
売り上げランキング: 363
技術評論社
売り上げランキング: 363
テーマが「巡回セールスマン問題」で都市数が197769個もあり、まともには解けないという感じでしたが、KaggkleのKernelsというページには参加者がヒントやテクニックなどを披露してくれているので、そこを参考にしながらやり始めてみました。
・巡回セールスマン問題について
「巡回セールスマン問題」についてはこれまでやったことはなかったのですが、単純そうで難しいという面白さがありハマってしまいました。コンペの都市数は膨大なので厳密解を出すのは無理ですが、ヒューリスティックなアルゴリズムであれば工夫次第ではスコアが向上していくので途中でやめられなくなったという感じです。
・TSP（巡回セールスマン問題）：その２
コンペ中には未消化な部分もあったり、もう少し試してみたいアルゴリズムもあったので引き続きやってみることにしました。
調べてみると思った以上にいろいろなアルゴリズムがあり、TSPのみならず他のことにも応用できそうなので奥が深いなという感じ。また、自分のアイデアに近いアルゴリズムもあるので、それらを参考に試してみました。
アルゴリズムもTSP解決に直結するもの、派生的なもの、他のものにも応用できるものなど、様々あります。
・convex hull：凸包/ギフト包装法/Graham scanアルゴリズム
TSPは組み合わせの問題でもあるのですが、いろいろ検索しているとグラフ理論という分野もあるようで、どんどん視野が広がっていきました。
最小全域木（MST）あたりから難しくなってきましたが、いかにもアルゴリズムという感じで面白くもなってきます。
・最小全域木（MST: minimum spanning tree)、Christofides algorithmによるTSP初期経路生成
関連アルゴリズム（主にヒューリスティック）：
とりあえず、ここまでで出てきたアルゴリズム（以下）。
・貪欲法
・挿入法
- 凸包（Convex hull）
- グラハムスキャン
・最小全域木（MST:minimum spanning tree）
- クラスカル法
- プリム法
・オイラー路（グラフ理論）
- Double Treeアルゴリズム
- クリストフィードアルゴリズム
- 最小重み完全マッチング
最初はヒューリティックに解いていくTSPのアルゴリズムを試していましたが、徐々にグラフ理論っぽい方向へと向かっていくことに。TSPに関連しつつも未知の分野でもあったので関心は尽きませんでした。
ウィリアム・J・クック
青土社
売り上げランキング: 403,740
青土社
売り上げランキング: 403,740
この本も購入して読んでみました。TSPの歴史から一通りいろいろなアルゴリズムについて紹介されています。実装例はないのですが、仕組みを理解するにはいいかもしれません。
厳密解アルゴリズム：
厳密解アルゴリズム：
ここで一旦原点へ戻って厳密解を求めるアルゴリズムについて試してみることにしました。
厳密解を求めるには全ての組み合わせを羅列して比較すればいいだけですが、TSPの都市数が増えると計算量が指数関数的に増えてしまうので、その工夫が必要となってきます。もちろんいかに計算量が少ないアルゴリズムで処理するのかというTSPには限らない問題解決にもつながります。
線形計画法（Linear Programming）：
厳密解を求めるには線形計画法（整数計画法・混合整数線形計画法）を使うといいらしく、これもまた未知の分野でしたが試してみることに。実社会においても、製造コストの最適な組み合わせなど様々な分野で活用されているらしく、オペレーションズリサーチという分野も初めて知りました。専用の最適化ソルバーがあり、アルゴリズムというよりはどのようにそのソルバーをつかいこなすかという感じ（あるいはどのソルバーが優れているか、適しているか）。
TSPも線形計画法の式に変換すると最適化ソルバーで解けるのですが、部分巡回路除去をどのようなアルゴリズムするかということが次の問題になってくるようです。
・TSP LP (Linear Programming)：線形計画法による巡回セールスマン問題 / Subtour Elimination 部分巡回路除去
・TSP LP Lazy Subtour Elimination Constraints：巡回セールスマン問題 逐次組込制約による部分巡回路除去
いくつか部分巡回路除去アルゴリズムがあるようで内容を理解しつつも試してみました。ここまでくると、最初にイメージしていたヒューリスティックなアルゴリスムとは全く違う視点でTSPを捉えることになり、TSPは単に最短距離を求める問題というだけではなく、いかに演算コストを低減できるかというアルゴリズム全般にかかわる問題に置き換えられてきます。
TSBLIB：
その後、LPでの解法が分かってきたのでTSBLIBにあるデータを使って試してみました。基本的な方法は同じですが、簡潔なコードに書き直してみました。
・TSP LP: US48 cities / 巡回セールスマン問題 線形計画法
Pulpなどの整数計画法が可能なソルバー/モデラーは便利ですが、敢えて連続値しか扱えないLPライブラリであるscipy.optimize.linprogで解いてみました。
・TSP LP with scipy.optimize.linprog
GEODUAL：
もうひとつ気になるのが「GEODUAL」という方法です。各都市にControl zoneという可変的な半径を持つ円を配置してLPでTSPを解いていくというビジュアル的にも理解しやすい方法なので面白そうです。コーディングできればそのうち掲載しようと思います。
まとめ：
数学は公式に値を渡すと解析的に一発で答えが分かるというイメージでしたが、厳密解ではなくともより良い答えを探し出すヒューリスティックな方法、あるいは必要に応じて解いていくLazyな方法などがあり、TSPを通して様々なアルゴリズムやそれに関連するテクニックなど学ぶことができました。これらはTSPに限らず他の領域でも応用できそうです。またこれをきっかけに、グラフ理論や整数計画法にも興味が湧いてきました。
機械学習/ディープラーニングのときは、分類識別問題や画像生成などそれ特有のアルゴリズムの斬新さにばかり目が向きましたが、かならずしも数理的に考えてコーディングしているわけでもなかったので、TSPのような演算コストを意識しつつアルゴリズムを考えるというのはコンピュータにおける原点的な難しさと面白さがあってより刺激的でした。
TSPサイト：
http://www.math.uwaterloo.ca/tsp/
0 件のコメント:
コメントを投稿