シミュレーティッド・アニーリンによる巡回セールスマン問題への適用

羽鳥研究室

45528 笹子昌治  45548 中村恵吾

 


1. はじめに

1.1 TSP

TSPとはTraveling Salesman Problem(巡回セールスマン問題)の略で、複数の都市をそれぞれただ一度だけ訪問して出発点の都市に戻る巡回路のなかで、最短となる経路を求めるという問題である。最も単純な方法として、考えうる全ての巡回路を調べ、その中から移動距離が最小になるものを選ぶ列挙法(力ずく法)がある。この方法で調べると確実に最小解を求めることができるが、都市の数が多くなるにつれ、考えうる巡回路の数は爆発的に増加し、都市数N = 5のとき12通り、N = 10のとき181,440通り、N = 15のとき43,589,145,600通り、N = 20のとき2432902817664万通りとなる。一般に、都市数Nに対して考えうる巡回路の数は(N1)!である。また、1秒間に10億通りの計算を行うことができるコンピュータを使い、列挙法による時間の計測例は、N = 5のとき0.0000001秒、N = 10のとき0.0003628秒、N = 20のとき2432902008(= 77)となり、計測時間も巡回路とおなじように爆発的に増加するため、全ての組み合わせを調べるのは非現実的である。

 

1.2 TSPの目的関数

TSPを解くための目的関数について述べる。値01をとる都市N²個の変数を考える。

都市をX、訪れる順番をiとしたとき、

と定める。同時に2つの都市に行かないという条件は、

で表され、同じ都市に2度行かないという条件は、

で表される。ある1つの経路の距離は、都市Xと都市Yの距離をとすれば

で表される。これはについて見たとき、その前後に「1」があれば、都市間の距離を加えていくことになる。よって、TSPの目的関数は、ABCを十分に大きい正の定数として、

で表される。

 

2. 確率的探索機械

2.1 ボルツマンマシン

ボルツマンマシンとは、最急降下法を用いてエネルギーが最小になるように状態変化を繰り返すホップフィールドネットワークを改良したものである。ホップフィールドネットワークは、一般に学習をしないためローカルミニマム(局所最小解)に収束する可能性が多分にある。

そこで、確率的探索機械であるボルツマンマシンではホップフィールドネットワークに新しく温度Tというパラメータを導入し、確率的に状態変化を繰り返すことで平衡を保つように改良された。また、各ユニットの出力0または1を取るが、どちらになるかが決定論的に決まるのではなく1を出力する確率が

で表され、2つのパラメータ、エネルギーが変化したときの差分Δui (= uiui-1 )と温度Tによって確率を求め、各ユニットの状態を変化させている。ボルツマンマシンにおいては、温度Tというパラメータが出力に大きな影響を及ぼす。

 

2.2 シミュレーティッド・アニーリング

ある物質を溶融点以上に過熱し、その後徐々に凝固点まで冷却すると、よりエネルギー準位の低い安定した凍結状態に収束することがある。この現象をアニーリング(焼きなまし)と呼んでいる。シミュレーティッド・アニーリングとは、この現象を模擬することによってエネルギーに相当する関数の最小値を求めようとするものである。

温度というパラメータを導入し、温度が高い時は状態遷移をする確率がエネルギーの変化にあまり依存しないようにする。つまり、エネルギーが高い方へ変化する確率が、低温の時より高くする。逆に温度が低い時は、エネルギーをより小さくする状態遷移が有利になるようにするため、エネルギーが高い方へ変化する確率は低く、変化の幅も小さくする。シミュレーティッド・アニーリングでは、高い温度から初めて、ゆっくりと温度を下げていくことで、やがて低いエネルギーの状態に収束していく。

シミュレーティッド・アニーリングを行う際に、温度を下げる方法は冷却スケジュールと呼ばれる。いろいろな方法があるが、比較的速く収束する冷却スケジュールとして、以下の方法がある。

 Tt+1)=pT(t)

  ただし、0.8 p 1.0 程度とする。 

すなわち、現在の温度をTtとし、次のステップの温度Tt+1)は現在の温度をp倍するというものである。

 

.3 冷却スケジュールと計算時間・解の正確性

冷却スケジュールの因子pは、0.8以上1.0未満程度としてあるが、1.0に近ければ近いほど、より大域的な最小値に落ち着く可能性を高くできるが、計算時間は長くなる。逆に、0.8に近い値を選択すると計算時間は短縮できるが、ローカルミニマムに落ち込む可能性が高くなる。

また、温度の初期の値T(0)も、出力と計算時間に大きな影響を与える。初期の値が大きければ、より正確な解が得られる可能性が高くなるが、計算時間が長くなる。さらに初期の温度が大きすぎても、時間を浪費するだけで、より正確な解を得られるわけではない。小さすぎると、ローカルミニマムに落ち込む可能性が高くなる。

ローカルミニマムに落ち込む理由には、三つの要因がある。(1)初期温度が低すぎるため、エネルギーが高い方へ状態遷移することができず、その先にある最適解にたどり着くことがない。(2)冷却スケジュールが急すぎ、ローカルミニマムにいる時に冷却が起こる場合、一つ前の温度T(t−1)では抜け出せたローカルミニマムが現在の温度(tでは抜け出せなくなる。(3)ある一定の更新回数で、エネルギーの更新が起こらないと終了するという終了条件を満たしたためのいずれかである。この三つの要因の全てを満たさなければ、ローカルミニマムに落ち込むことはない。つまり、理論上、十分に初期温度を高くし、冷却スケジュールの因子p1.0に近づけ、終了条件となる更新回数を大きくとれば、必ず最適解を求めることができる。

 

 

.アルゴリズム

シミュレーティッド・アニ―リングは、初期温度と冷却スケジュールを初期設定した後、与えられた状態x1から出発して次の状態x2を生成し、そのエネルギーEを計算する。エネルギーの差分Δk (= E2 − E1)と温度に応じて受理するか否かを計算し、受理する場合は次の状態に推移する。この処理を繰り返して、現在の温度での平衡状態が実現されるまで、十分な探索を行う。温度T(t)で平衡状態に達したら、冷却スケジュールに従って、冷却処理を行って次の温度Tt+1)を求め、再びその温度で平衡状態に達するまで十分な探索を進める。十分温度が冷えて終了条件に達すれば、そのときの、状態とエネルギーを各々の最適状態、最適エネルギーとして出力する。

.実験結果

乱数によって都市の分布を生成しTSPに対して実験した。初期温度と冷却スケジュールをそれぞれ変えて、出力を出した実験結果の一部を以下の表に示す。

 

入力

    出力

冷却スケジュールの因子p

初期温度

(0)

到達距離

温度更新回数

0.80

1.0

766.808

8

0.80

3.0

722.239

14

0.80

5.0

721.213

24

0.85

1.0

763.183

11

0.85

3.0

711.042

21

0.85

5.0

706.131

22

0.90

1.0

752.434

23

0.90

3.0

707.185

26

0.90

5.0

709.377

36

0.95

1.0

743.660

20

0.95

3.0

719.018

53

0.95

5.0

707.676

48

表1 都市数75

 

.考察

ボルツマンマシンでは、シミュレーティッド・アニーリングの際にデータ(都市の数、都市座標の大きさ等)によって、冷却スケジュールの因子pと初期温度T(0) 変える必要がある。冷却スケジュールの因子pをある一定の値に固定し、初期温度T(0) を変化させていくと、必ずしも初期温度が高い方が、より適した解に近づくわけではないことがわかった。同様に初期温度T(0)を一定の値に固定し、冷却スケジュールの因子pを変化させた場合もまた、冷却スケジュールの因子p1.0に近いほど、より適した解が得られるとは限らない。これは、ボルツマンマシンが確率的に出力を決定することから、より大きな初期温度と1.0に近いアニーリングスケジュールにしても、「より適した解が得られる確率」が高くなるだけで、必ずしもより適した解が得られるものではないと考えられる。

 

 

.今後の課題

シミュレーティッド・アニ―リングは様々な組合せ最適化問題に有効な汎用近似解法である。しかし、最適解を得るためには長い計算時間を必要とすることや、適切な初期温度と冷却スケジュールの決定が容易でないなどの問題点を有する。

これまでに行われた、様々な組合せ最適化問題にシミュレーティッド・アニーリングを適用した研究において、特定範囲の温度でのアニーリングがシミュレーティッド・アニーリングの性能に大きく影響を与えることが分かっている(参考文献[]より引用)。そこでは、この重要な温度領域を自律的に探索するメカニズムを組み込んだ手法によって、最適解探索性能の向上を考えている。

また、TSPを解く方法として、シミュレーティッド・アニーリングの他に、遺伝的アルゴリズム、タブーサーチ手法、シミュレーティッド・エボリューション手法などがある。これらの手法とシミュレーティッド・アニーリングを並用することで、より効率よく解が得られる可能性がある。

 

 

 

.参考文献

[]「ニューロコンピューティングの数学的基礎」

  上坂吉則 著、近代科学社

[]ニューラルネットワーク入門

http://mars.elcom.nitech.ac.jp/java-cai/neuro/menu.html

[]「巡回セールスマン問題への招待」

  山本芳嗣 久保幹雄 著、 朝倉書店

[]巡回セールスマン問題

http://www-or.amp.i.kyoto-u.ac.jp/members/ibaraki/tsp/original1.html

[]TSPLIB

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

[]ニューラルネットワークの基礎概念

http://www.e.ics.nara-wu.ac.jp/~joe/Class/99/okuno.htm

[]Metal Brain

http://metalbrain.piroo.com/

[]同志社大学 三木研究室

http://mikilab.doshisha.ac.jp/