いわゆる巡回セールスマン問題を解くプログラムです.
こんな問題です.
これは組み合わせ最適化問題というものなのですが, 組み合わせ最適化問題には,以下のような課題があります.
そうした課題はあるのですが,以下のように条件を緩めることができれば, 「簡単なプログラムで,ほどほどの時間で,ほどほどに良い解を得る」ということができます.
まず,NLLをインストールしてください.
インストールの方法は以下を参照してください.
次に,以下のプログラムをひととおりダウンロードしてください.
Windowsの場合は,NLLを解凍したディレクトリ(nll.exeがあるディレクトリ)にダウンロードしたプログラムを置いてください.
適当な地図の画像をダウンロードし,BMP形式にしておいてください.
(注意:地図画像のライセンスに留意してください)
(無い場合や面倒な場合は,上記からダウンロードできるmap.bmpを利用してください(ただの真っ白な画像です))
Windowsの場合は,コマンドプロンプトを起動して「cd」コマンドでNLLのディレクトリに入り,実行してください.
まず,適当な地図の画像を背景にして,ビューワを起動します.
$ nll -q view.nll position.dat map.bmp
背景にmap.bmpを利用した場合,ビューワはこのような真っ白の画面になります.
ビューワ上で追加したい場所(経由地)をマウスの左クリックで指定します.
クリックで指定した順番に,経由地を繋ぐとりあえずの経路が描かれます.
右クリックで,最も新しく指定した経由地を削除します.
経路は,スタート地点に戻ってくるように(つまり1周してくるように)なっています.
とりあえず適当に,30箇所くらいを指定するといいでしょう.
このようにして経由地を指定してもいいのですがここでは面倒なので,以下で乱数でランダムに100箇所を指定します.
$ nll -q makedata.nll position.dat 100 500 1
500は範囲,1は乱数の種です.
乱数の種が同じだと,同じパターンで乱数を発生します.
いろいろ変えて試す場合は,乱数の種を2や3のように別の値にしてください.
以下で,経由地の順番を適当にシャッフルします.
$ nll -q shuffle.nll position.dat 1 1001はシャッフルするための,乱数の種です.
この段階では,乱数で適当に経路を決めただけなので,かなり無駄な経路になっていると思います.
というより,ぐちゃぐちゃですね.
以下で,現時点での経路の総距離を計算します.
$ nll -q distance.nll position.dat 23760
以下で,経路を最適化していきます.
$ nll -q change.nll position.dat 1 100001は乱数の種,10000は以下の最適化を行う回数です.
これをやると,経路がどんどん最適化されていく様子がリアルタイムでビューワで見えます.
見た目にも,かなりすっきりしました. まだ無駄はありそうですが,とりあえず近いところどうしが繋がっているので,さっきよりはずっとマシそうです.
このときのアルゴリズムは,以下のようなものです.
このように
「経由地の順番に,乱数で何らかの入れ替えをして,それによって総距離が短くならないか試してみる」
ということを繰り返して,より短い経路を少しずつ探っていきます.
総距離を計算してみましょう.
$ nll -q distance.nll position.dat 6835だいぶ短くなりました.
乱数の種を変えて,もう少し最適化してみます.
$ nll -q change.nll position.dat 2 10000 $ nll -q change.nll position.dat 3 10000 $ nll -q change.nll position.dat 4 10000 $ nll -q change.nll position.dat 5 10000 $ nll -q change.nll position.dat 6 10000
やってみるとわかるのですが,だんだん変化が少なくなり,やがてはほとんど変化しなくなっていまいました.
総距離を見てみます.
$ nll -q distance.nll position.dat 5484良くはなっているようです.
同じアルゴリズムでいくら試しても,これ以上は良くはならなさそうです.
先ほどは「2箇所を入れ替える」というアルゴリズムでしたが,別のアルゴリズムを試してみましょう.
これは1箇所を抜き出して,別の位置に移動してみるというものです.それを10000回繰り返します.
$ nll -q move.nll position.dat 1 10000
経路に変化がありました.効き目がありそうです.
乱数の種を変えながら,繰り返しやってみましょう.
$ nll -q move.nll position.dat 2 10000 $ nll -q move.nll position.dat 3 10000 $ nll -q move.nll position.dat 4 10000 $ nll -q move.nll position.dat 5 10000 $ nll -q move.nll position.dat 6 10000
さらに最適化が進みましたが,やはりこれ以上はほとんど変化しなくなりました.
まだまだ,別のアルゴリズムが必要そうです.
経路には,交差している部分がいくつもあります.ここはまだ最適化ができそうです.
交差しているということは,順番を反転させるようなことができれば,効果がありそうです.
そこで「2箇所の経由地を選んで,その間の経由地の順番をぜんぶ逆にする」というアルゴリズムを試してみましょう.
$ nll -q reverse.nll position.dat 1 10000 $ nll -q reverse.nll position.dat 2 10000 $ nll -q reverse.nll position.dat 3 10000
これは効果がありました.最適化が一気に進み,交差が無くなりました.
これでもう一度「1箇所を別の位置に移動する」というアルゴリズムを試してみましょう.
$ nll -q move.nll position.dat 7 10000 $ nll -q move.nll position.dat 8 10000 $ nll -q move.nll position.dat 9 10000 $ nll -q move.nll position.dat 10 10000
多少は変化がありましたが,やはりほとんど変化しなくなりました.
「2箇所を選んで,その間の順番をひっくり返して別の位置に移動する」 というアルゴリズムを試してみます.
$ nll -q rmove.nll position.dat 1 10000 $ nll -q rmove.nll position.dat 2 10000 $ nll -q rmove.nll position.dat 3 10000
さらに最適化が進みました.
ここから今までの4つのアルゴリズムを,乱数の種を変えてもう一度ひととおり試してみましょう.
今度は30000回ずつ試してみます.
$ nll -q change.nll position.dat 99 30000 $ nll -q move.nll position.dat 99 30000 $ nll -q reverse.nll position.dat 99 30000 $ nll -q rmove.nll position.dat 99 30000しかし,変化はありませんでした.
乱数の種を変化させて試してもほとんど変化しませんので,ひとまずほぼ収束しているようです.
総距離を見てみましょう.
$ nll -q distance.nll position.dat 3584
ある程度収束しましたが,別の収束した形があるかもしれません.
シャッフルしなおして,再度収束させてみましょう.
まず,データを再生成します.乱数の種を同じにすることで,同じデータが再生成できます.
$ nll -q makedata.nll position.dat 100 500 1
今度は乱数の種を2にして,シャッフルしてみます.
$ nll -q shuffle.nll position.dat 2 100
収束させていきます.
$ nll -q change.nll position.dat 1 60000 $ nll -q move.nll position.dat 1 60000 $ nll -q reverse.nll position.dat 1 30000 $ nll -q rmove.nll position.dat 1 80000前回の経路と並べて見てみましょう.(左が今回,右が前回)
前回とは違った経路に収束しているように見えます.
$ nll -q distance.nll position.dat 3432総距離はさっきよりも短くなっています.
もう一度,ひととおりのアルゴリズムを試しておきます.
$ nll -q change.nll position.dat 99 30000 $ nll -q move.nll position.dat 99 30000 $ nll -q reverse.nll position.dat 99 30000 $ nll -q rmove.nll position.dat 99 30000 $ nll -q distance.nll position.dat 3432総距離に変化はありませんでした.ここでほぼ収束しているようです.
このように初期経路や最適化の順番を変えることで,違った経路に収束するようです.
最も,これはまだ収束しきっていないかもしれないし,そもそもこれが最短経路かどうかはわかりません. (それを調べるためには,すべての経路パターンを調べなければならない,ということになります)
しかしこのようにして,いくつかの初期経路で繰り返し収束させ,最も短い総距離の経路を選ぶことで (最適ではないかもしれないが)「ほどほどに良い解」を得ることができます.
ビューワはビューワ上で[q]を押すと終了します.
経由地を乱数で生成した場合や,経路の最適化後でも,ビューワで左/右クリックすることで,経由地の追加/削除が可能です.
またそのようにして修正したデータに対して,経路の最適化を再度行うこともできます.
経由地をいろいろ修正して,繰り返し試してみましょう.
$ nll -q near.nll position.datスタート位置の移動(スタート位置は赤で表示されます)
$ nll -q up.nll position.dat $ nll -q down.nll position.dat全体の順番を反転
$ nll -q inv.nll position.dat
以下はメロンではなく,経由値を1000にして収束させてみたものです.
さすがにこの数になると収束に時間はかかりますが,それなりに良い経路が
見つけられている…ように思います.