SOMで巡回セールスマン問題を解こうとした

こんにちは．

今回はSOM（自己組織化マップ）の勉強目的で，巡回セールスマン問題に挑戦してみました．

作戦

巡回セールスマン問題は，2次元上に配置された複数個の都市を最短距離で巡回する解を求める問題……だったと思います．

作戦としては，都市がある平面上に適当なN個の巡回点を設けて，全ての巡回点に番号を振ります． この番号が巡回する順番になります． 各巡回点が都市に近づくように，また隣同士の番号（1と2，5と6など）が近づくように巡回点の更新をします． この更新を繰り返すことでなるべく短い距離で都市を巡回できるパスの生成を目指します．

今回はこの巡回点の更新にSOMを使います． 何かの論文を読んだり，実装を参考にしたわけではないので最適ではないと思いますが……．

コード

Pythonを使いました． NumPyとMatplotlibが必要です．

TravelPointクラスがSOMの実装になっています． 今回都市数は20個で巡回点は100個としました．

更新は逐次型（オンライン）で行っています． バッチ学習にするともう少し精度が上がるでしょうか．

結果

青い点が都市，赤い線が巡回パスを表現しています．

更新回数が少なかったせいか，全ての都市を廻りきれていませんが， なんとなくやろうとしていることが見えてきました．

なんだかミミズみたいですね．

まとめ

今回の実装は非常にシンプルなコードで，解いた問題も単純なものですが， 個人的にはDeep Learningよりもこちらのほうが人工知能を実装している感があって楽しかったです．

今度は遺伝的アルゴリズムにも挑戦してみたいです．