熱した金属材料はセールスマン革命を起こす

巡回セールスマン問題の解法について研究中です。
以前の記事で取り上げたとおり、巡回セールスマン問題は「最適解を求めることはあきらめましょう」という難問です。
もっとも今回考える120箇所程度の問題であれば最適解は求まるんですけどね。けど時間かかるし。
いろいろやったところ、焼きなまし法は非常に安定していい結果が出せることがわかった。
あくまでいい結果で最適解ではないですね。事実これまでの方法で最適解と思っていたのよりずっといい結果が出たので。
まぁそんなわけでさらにいい結果が出せる方法を探して行けたらいいとおもうけどね。


さて、以前、2-opt法とか書いたがあれはちょっと間違い。
あれは入れ替えの方法じゃなくて、入れ替え候補の作り方ですね。
前回やった方法も、今回やる焼きなまし法も、局所探索法と呼ばれるものの1つで、
まず、ランダムに解の候補を作成する。もっともランダムに作った答えなので結果は散々でしょうね。
さて、これを少し変更した近傍解というのを作る。この方法が2-opt法とかOr-opt法とかだ。
この近傍解が解の候補よりも優れていれば入れ替える。これを繰り返してよい解を見つける。
これが前回の方法で、山登り法と呼ばれる方法です。
どのへんが山登りなのかというと、まず山を発見する。これがランダムに作成した解の候補。
これをとにかく登っていく。それで高い山に登れればいいのですが、運悪くその山が天保山ならばうれしくもなんともない。
それを回避するために僕は何度も計算してよい結果を取ろうとしたわけです。
実際ひどい有様で、10回計算して、その中でもっとも成績がいいのは335移動ぐらい、まぁ毎度違うんだけど、
ところが、毎度そんな結果が出るわけでもなく、悪いときは350移動ぐらいの答えがもっとも成績がいいと。
まぁそんなわけで、なかなかうまいこと成績を出せないわけですよ。
それに10回計算すると時間もかかる。特に、Or-opt法は点の数が増えるとものすごい時間がかかる。
計算時間が点の数の三乗に比例するんだったと。2-opt法は点の数の二乗に比例だったはず。
しかし、Or-opt法での改善効果はかなりあるので、外せなかった。380移動ぐらいなのを335移動ぐらいまで改善してくれるから。
もし、ここで四本の矢印を入れ替える4-opt法を導入すればさらに成績はよくなるだろうけど、
時間がかかって仕方ない。そんなわけでもうこの方法は限界であると。そう考えるわけだ。


焼きなまし法は、運悪く天保山を登ることにならないような工夫ですね。
焼きなましとは金属加工の技術の1つらしい。しかし金属加工など僕は詳しく知らない。
加工を行った金属の内部のひずみを取り除くために、その金属を熱してゆっくり冷やすことで結晶を再構築する技術。
ここでポイントなのは熱すること。熱するというのは金属をぐちゃぐちゃにすることでもある。
一旦ぐちゃぐちゃにしたものを、ゆっくり冷やして質のいい結晶を作ると。
熱すると言うことは質のいい結晶が出来ようとする一方で、質のよさそうな結晶がつぶれることでもある。
まぁしかし最終的にはきれいになればいいですねということです。
山登り法では改善される方向にしか作った近傍解への入れ替えを行わなかった。
しかし、この方法では改善される方向は必ず、そうじゃないときも一定の確率で入れ替えを行う。
一見悪くなるようだけど、実はそこから改善につながるかも知れない。そういう考えです。
その一定の割合をどんどん小さくしていって、十分小さくなったとき完成とそういうことです。
この確率だが、近傍解のコストと現在の解のコストの差、すなわち改悪量をΔと置くと、
e-(Δ/t) の確率でやるといいとされている。
delta<0 || myrnd.NextDouble()tは温度、もっとも現実の温度とは関係なくて、焼きなまし法が材料の温度を上げて、ゆっくり下げることに由来している。
ループ1回回るたびにtに一定量を掛けて、tを小さくしていく。これが十分小さくなれば終了と。
tが大きいほど、Δが小さいほど、確率は1に近づいて、悪い方向にも入れ替えされやすいと。


さて、この方法のいいところは何かというと、山登り法では行けなかった高いところに行けること。
山登り法では天保山に登るなら天保山にしか登れなかったが、
ところが少し悪い程度なら簡単に改悪されてしまう。
そんな風に改悪され続けて、生駒山に近づく方向に改悪された。すると生駒山に近づいた途端急激に登る。
まぁそんな感じで高い山にもたどり着けるのではないかということです。
ただ難しいのは温度をどれぐらい高くするか、温度をどのように下げるかということ。
もし目標がチョモランマならば、非常に高い温度で始めて、ゆっくり行かないと行けないだろう。
けど範囲が近畿に限定されていたらそんなに気合いを入れることはなくて、そこそこの温度で高速で冷やしてもいい。
まぁその辺の兼ね合いが難しいところです。


いろいろ調整してたが結果的には予想より遙か低い温度から始めて急激に下げていけばよかった。
まぁそんなわけでそこが難しい。ただ315移動程度と、山登り法では考えられなかったいい結果が出た。
なお、入れ替えを実行したときの改悪度の総和を求めて、それがこれまでの最小記録より小さくなったとき、
最小記録を変更して、最小の結果をメモする。
この方法、温度が小さくなればなるほど改悪される確率は減るけど、やはり改悪されます。
まぁそのあたりがあるので、今までのところもっともいい記録を残しておくと。そしてそれを答えにするようにした。
なお、山登り法で10回計算するよりは速い。
一応1回では悪い結果が出たとき困るので2回計算しているが、大体1回でも満足する結果が出てる。
それと、近傍解の作り方は、2-opt法のみで行った。
もともと、隣接した点の順序を入れ替えるだけでいいと思ってたが、
思ったよりよい方向に進まないので、前回の2-opt法のアルゴリズムを温度を変えながら何度もやることにした。
だから一回にかかる時間が長いですよ。前の計算を100回ぐらい繰り返してやるわけですから。
まぁOr-opt法がないだけましですけど。そう、Or-opt法なしでもいい結果が得られたわけです。
パラメーターの調整はもう少ししないといけないけど、まぁ今回のパラメーターは参考になるかと。
まぁこのあたりが難しいところでして、焼きなまし法は職人
技的な面があるんですよね。
点の数を変更して、どういうときどんなパラメーターが合うか調べてみたいとは思うけどね。