これまでのあらすじ:
2016年3月、フェルト生地を手で裁断している際にレーザーカッターがあれば複雑なカットが容易にできるなあと思って、安価になってきたレーザーカッターを購入しようと思ったのがきっかけ。調べていくうちに、合板も切れたほうがいいと思うようになって、CNCルーター(CNCミリング)についても考えるようになった。
Arduinoは以前から使っており、CNCシールドがあると気付いて自作も可能と思うようになった。当初はShapeOkoやX-CARVEを参考にMakerSlide、OpenRail、V-Wheel、2GTタイミングベルトなどで5万円くらいで自作しようと思っていた。AliExpressでも部品が安く買えることが分かって、しばらくは部品探し。探せば探すほど安くて本格的な部品も見つかってくるので、そんなにケチらなくてもいいのではないかと徐々にスペックアップ。最終的には剛性や精度のことも考えてボールスクリューやリニアスライドを使うことになり、予想以上に重厚な3軸CNCマシンをつくることに(約7万円)。
構想から約5週間(制作約3週間)でルーターとレーザーともに使えるようになり、現在はgrbl1.1+Arduino CNCシールドV3.5+bCNCを使用中(Macで)。余っていたBluetoothモジュールをつけてワイヤレス化。bCNCのPendant機能でスマホやタブレット上のブラウザからもワイヤレス操作可能。
その他、電子工作・プログラミング、最近は機械学習などもやっています。基本、Macを使っていますが、機械学習ではUbuntuを使っています。


CNCマシン全般について:
国内レーザー加工機と中国製レーザー加工機の比較
中国製レーザーダイオードについて
CNCミリングマシンとCNCルーターマシンいろいろ
その他:
利用例や付加機能など:
CNCルーター関係:



*CNCマシンの制作記録は2016/04/10〜の投稿に書いてあります。

TSP: Traveling Salesman Problem / 巡回セールスマン問題について


ここしばらく「巡回セールスマン問題」について試行錯誤していたので、これまでの経過をまとめ。

きっかけはKaggleの2018年の年末に開催していたクリスマス記念のコンペでした。
テーマが「巡回セールスマン問題」で都市数が197769個もあり、まともには解けないという感じでしたが、KaggkleのKernelsというページには参加者がヒントやテクニックなどを披露してくれているので、そこを参考にしながらやり始めてみました。

巡回セールスマン問題について

「巡回セールスマン問題」についてはこれまでやったことはなかったのですが、単純そうで難しいという面白さがありハマってしまいました。コンペの都市数は膨大なので厳密解を出すのは無理ですが、ヒューリスティックなアルゴリズムであれば工夫次第ではスコアが向上していくので途中でやめられなくなったという感じです。

TSP(巡回セールスマン問題):その2

コンペ中には未消化な部分もあったり、もう少し試してみたいアルゴリズムもあったので引き続きやってみることにしました。

調べてみると思った以上にいろいろなアルゴリズムがあり、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
この本も購入して読んでみました。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 件のコメント:

コメントを投稿

人気の投稿