Markov Chain Monte Carlo for Traveling Salesman Problem

巡回セールスマン問題を例にモンテカルロシミュレーションのキーとなる， 非対称なモンテカルロ配置の列が生成される様子を見よう． 巡回セールスマン(traveling salesman) 問題は， 熱統計力学から少し外れている． これは，ある街から出発していくつかの街を次々とめぐって 元の街に戻ってくる最短の経路を求める問題である． 訪れる街の数が少ないときにはすべての 経路を数え上げればいいが， 数が増えると，その計算時間は指数関数的に増えてしまうと予想される． このような問題はセールスマンだけでなく， コンピュータのCPU の配置や，都市ガスの配管設計などでも出会う．

図１16都市でのルート

街の配置が図1左パネル のようになっているとしよう． 1 つの街は2 次元座標の特定の位置で表わされ， その並びが厳密な意味での配位空間である． しかし，巡回セールスマン問題を解く場合には， 1 つ1 つの街の細かな位置は問題にならない． あるいは問題が移動の所要時間や料金であるなら， 位置座標そのものが意味を失う． 問題になるのは，訪れる街の順番だけである．

道順Pathを配位空間とし， 距離をエネルギーと見立てることによって， 統計力学の手法であるMonte Carlo 法によく似た アニーリング法(simulated annealing) で最適化がおこなえる． これは格子欠陥を多く含んだ金属を高温へ上げて， 欠陥を掃き出し柔らかくする熱処理(焼きなまし，annealing) からの類推で名付けられた．

巡回セールスマン問題でのポテンシャルエネルギーは対象となる経路の長さの合計，

とする． ここで\({\bf a}\) は巡る街の順番を示している． \({\bf r}\) はそれぞれ街の座標で， \(\left\|{\bf r}\right\|\) によって距離を求める． 初期の配置を

として，一定の手順で変更\(\delta {\bf a}\) を加える．

アニーリング法のアルゴリズムは，以下のとおりである．

1. 配置\({\bf a}\) を仮定し\(E({\bf a})\) を求める．
2. \({\bf a}\) からすこし違った配置\({\bf a+\delta a}\) を作る．
3. \(\Delta E = E({\bf a+\delta a})-E({\bf a})\) を求める．
4. \(\Delta E < 0\) なら新たな配置を採用する．
5. \(\Delta E > 0\) なら新たな配置を\(\exp(-\Delta E/T)\) の確率で受け入れる．
6. 手順2以下を適当な回数繰り返す．

図1 で考えると，道順の11と12番目を入れ替えている． それに伴う総距離(Total_dist)の変化が\(\Delta E\) の値に対応する．

ここで，新たな配置が\(\Delta E > 0\) の場合に， \(\exp(-\Delta E/T)\) の確率で受け入れる操作は， 最小値を探すためには時として必要となる， 極小値から脱出するための 「坂を駆け登る動き」に対応している(演習課題[\thechapter-2]参照)．

アニーリング法の目的はあくまでも最小値を捜すことであるので， 温度から類推される制御パラメータ\(T\) を下げ， 最小値に近い状態が確率的に高く出現するように系をコントロールする． エネルギー(経路の総和)の減少の様子を図2真ん中グラフに示した． あまり温度を下げすぎると右上に示したように減少する配置しか取れないが， その場合は，極小値から抜けられず高い値で止まる．

図2 16都市での総距離の変化と対応するルート地図．

適当な温度にあげると， ある値のまわりでエネルギーが揺らいでいることが分かる． こうして得られた状態は，その温度での平衡状態を記述していることに対応する． さらに，ある程度低いとそのゆらぎの中で最小となる ルートを見出すことが可能である．

図3 64都市での総距離の変化と対応するルート地図．

図3には，64都市のいくつかの温度での様子を示している． それぞれ特徴的な挙動を示す．

以下の手順に従って解け．

1. 16都市の2次元の位置を[0..1]の乱数発生器を使って作る．
2. 16都市を順番に巡るルートを定義する．これを\(\bf a\) とする．
3. 2都市間の距離を求めた2次元配列を用意する．
4. ルートを受け取って距離を返す関数を定義する．これを\(E({\bf a})\) とする．
5. ルートから2都市を選んで入れ替える．これを\(\delta a\) とする．
6. 距離の差を求めて，これを\(\Delta E\) と見なして非対称なサンプリングを実行する．

温度は低めに設定する．さらに\(\delta a\) を

2都市を選んでその間のルートを逆向けにする．つまり，
  a_i=[1,2,3,4,5,6,7,1]
で3,6が選ばれた場合に
  a_j=[1,2,6,5,4,3,7,1]
などとなる．

とすれば，都市数を増やしても比較的うまく最小値を求めてくれる．