社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

カオスノイズを都市配置に加えた巡回セールスマン問題の解法
吉田泰之†

上手洋子†

西尾芳文†

† 徳島大学〒 770-8506 徳島県徳島市南常三島町 2-1
E-mail: †{yasu0824, uwate, nishio}@ee.tokushima-u.ac.jp
あらまし

組合せ最適化問題は, 時間をかければ解くことは可能だが, 要素数が多くなるとその時間は長くなり, 計算は困難なものとなる. このような組合せ最適化問題では, 出来るだけ早く最適解を得ることが求めらる. そのため, 近似解法が用いられるが, 最適解を得ようとすると局所解に陥るという問題が発生する. 最適解を得るには, この局所解を回避する必要があり, 近似解法にノイズを注入する手法が提案されている. 本研究では, 組合せ最適化問題の１つである巡回セールスマン問題の解法において, 都市配置にカオスノイズを注入して近傍探索法で解探索を行う手法を提案し, 局所解の回避に対してカオスノイズの有効性の確認を行う.
キーワード

カオス，巡回セールスマン問題

Eﬀects of Chaos Noise to City Placement of Traveling Salesman Problems
Yasuyuki YOSHIDA† , Yoko UWATE† , and Yoshifumi NISHIO†† Dept. of E.E. Eng., Tokushima University, 2-1 Minami-Josanjima, Tokushima 770-8506, JAPANE-mail: †{yasu0824, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract Although it would be possible to solve combinatorial optimization problems with a huge number ofelements if we have inﬁnite long time, it does not make any sense for practical problems. In several approximation
methods, the solutions are trapped into local minima and do not escape. In order to avoid this problem, technicalmethods to escape from local minima are required. In this study, we propose an novel algorithm pouring the chaosnoise to the city placement for solving the traveling salesman problems. By carrying out computer simulations forvarious problems, we conﬁrm that the chaos noise has a good eﬀect to avoid local minima and achieves to a goodsolution of the traveling salesman problems.
Key words Chaos, TSP

1. ま え が き
組合せ最適化問題は実社会においては時間制約窓付き配送計画問題に応用されており, 工学分野では, LSI の配置・配線, タ

これらの手法では, 解探索アルゴリズムを拡張しノイズを注入するため, パラメータ数が多くなり, パラメータの設定が困難になる.
本研究では, 組合せ最適化問題の要素データにノイズを注入ンパク質の構造解析などに応用されている. 組合せ最適化問題

することで, 局所解を回避できないか, 検証を行う. 近似解法とでは、時間をかければ解くことは可能だが, 要素数が大きくなして用いるのは, 局所探索法である 2-opt 法, 2-opt+Or-opt 法

ると実時間での計算が非常に長くなり, 総当たりの計算では実である. 2-opt 法は TSP において, 良い解を探索可能だが, や質困難なものとなる. 中でも, 巡回セールスマン問題 (TSP) なはり局所解に陥ることがある. そこで, Or-opt 法と併用するこどの N P − 完全とされる組合せ最適化問題は, 最適解を探すのとで, より強力な解探索が可能となる. 2-opt+Or-opt 法に対しが難しく, 計算時間も非常に長くなる. このような組合せ最適化ても, ノイズが有効か比較として用いる. 注入するノイズは, 組問題では, 出来るだけ早く最適解を得ることが求められる. ま合せ最適化問題に有効であると報告されているインターミッテ

た, 最適解を得る際に, 局所解に陥る問題が発生する. 最適解をンシーカオス [3][4] を用いる. 組合せ最適化問題の一つである得るには, 局所解を回避する必要がある. そのため, 近似解法とTSP の都市配置にノイズを注入し, 2-opt 法, 2-opt+Or-opt 法

してニューラルネットワークを用いて、パラメータにノイズをで解探索を行うことで局所解に対して有効か確認を行う. また,注入する手法で数多くの研究が進められてきた [1][2]. しかし,カオスノイズの有効性を確認するため, ランダムノイズとの比—1—して, 枝をつなぎ直して巡回路が短くなるなら, 枝の相互交換が較を行う.

行われ, 新しい巡回路｛i − k − j − l｝が生成される.

2. 組合せ最適化問題の解析
2. 1 巡回セールスマン問題 (TSP)
組合せ最適化問題には, 巡回セールスマン問題 (TSP) や二次割り当て問題 (QAP), ナップサック問題など様々な問題がある
が, TSP は最適解を得ることが困難とされる N P − 完全問題である. しかし, 問題はいたって単純で,ある 1 人のセールスマンが与えられた全ての都市を 1 度ずつ訪問し, 一巡したときの総移動距離が最も小さくなる値を求める と定義された問題で

図 3 2-opt アルゴリズム

ある [5]. 例として, 図 1 は都市数が 16 の問題の都市配置であり, この問題での最適解が図 2 の巡回路となる.

2. 3 Or-opt
Or-opt アルゴリズムは 2-opt アルゴリズムと同様, 枝を比較し巡回路が短くなるならば相互交換を行い, 新たに短い巡回路を生成する. 例として, 図２に示す都市配置における巡回路｛i − j − k − l − m − n − o｝が与えられた場合, 2-opt アルゴリ
ズムでは, 2 本の枝での比較, 交換であるのに対し, Or-opt アルゴリズムは複数の枝 i − j, l − m, n − o と i − m, n − l, j − o を比較する. そして, 枝をつなぎ直して巡回路が短くなるなら, 枝の相互交換が行われ, 新しい巡回路｛i − m − n − l − k − j − o｝が生成される.

図 1 都市配置例 (TSP)

図 4 Or-opt アルゴリズム

2. 4 提 案 手 法
近似解法では, 最適解を得ようとすると局所解に陥るという問題が発生する. そのため, 局所解を回避する有効的な方法が最適解を得るために重要となる. 本研究では, 局所解を回避するために都市配置にカオスノイズを注入し解探索を行う手法を提案する. TSP の都市配置とは, 平面における座標である. 平面上の座標にノイズを注入するため, 縦軸・横軸の様に垂直に交わる 2 成分のノイズが必要となる. 同じパラメータでも異な
図 2 最適解 (TSP)

図 1, 2 の問題であれば解を求めるのは容易だが, TSP は都市数 N が増加することで, 組合せの数が極端に増大するので, 全ての組合せの数 (N − 1)!/2 を調べることは極めて困難である.
そのため, 様々な近似解法を用いて解を求められている. 本研
究では, 以下の手法を用いてこの問題についての解析を行う.

2. 2 2-opt
2-opt アルゴリズムは現在の巡回路において, 2 本の枝を交換して再び巡回路を作成し, 巡回路の長さがより短くなるなら, 枝を入れ替える. これを巡回路が短縮される枝がなくなるまで入れ替え繰り返す方法が 2-opt 法である. 例として, 図 2 に示すような都市配置における巡回路｛i − j − k − l｝が与えられた
場合, まず, 2 本の枝 i − j, k − l と i − k, j − l を比較する. そる初期条件のノイズを 2 つ用いて, 縦軸成分・横軸成分のそれぞれにノイズとして注入する. ノイズを注入する前に都市配置は正規化を行う. また, ノイズを注入する際には正規化を行った都市配置に対して値が大きすぎるので, ノイズの大きさをコントロールするパラメータとして,振幅 を設定する. 振幅とノイズの積を注入するノイズとし, 正規化を行った都市配置に注入する. 以下にシミュレーションでの提案手法の過程を示す.

Step1 2-opt 法, 2-opt+Or-opt 法にて枝交換を行い、より短い巡回路を生成する.

Step2 都市配置の正規化を行い, 正規化された都市配置にノイズを注入し, 都市配置を変化させる.

Step3 変化した都市配置で, 2-opt 法, 2-opt+Or-opt 法にて枝交換を行い, より短い巡回路を生成する.

—2—

Step4 都市配置をノイズ注入前と同じ正規化した都市配置状態に戻す.
上に示した Step2 から Step4 を数回繰り返し, 解探索を行う.

3. カオスノイズ
本研究では, 次のロジスティック写像から生成されるカオス
時系列をノイズとして用いる. ロジスティック写像は, カオスをt生み出す最も簡単な写像の一つである.
図7

xn (t + 1) = αxn (t)(1 − xn (t))(1)

4. シミュレーション

ノイズ注入の際には, 以下の式にて正規化を行う.

xn (t) − x̄x̂n (t) =σx

ランダムノイズ

本研究では, ベンチマークサイト TSPLIB [6] より選んだ,(2)x̄ は xn の平均, σx は xn の標準偏差値を示す. 分岐パラメー
タ α を変化させると式 (1) は周期倍分岐を経てカオス的に振る舞う. 本研究では, インターミッテンシーカオスを生成する
分岐パラメータ α = 3.828 と, 完全発達したカオスを生成する“kroE100”, “pr124”, “pr226”の 3 つの問題を使用する. 2-opt法での解探索を表１に, 2-opt+Or-opt 法による解探索を表 2 に示す. ノイズの振幅を 0.001 とし, 状態更新数を 100 回, 異なる初期値で 10 回の試行の平均を値とする.
表 1 2-opt 法でのカオスノイズ, ランダムノイズ比較

α = 4.0 を用いる. 分岐パラメータが α = 3.828 のときには, 周Problem

期的な振動をするラミナー部とカオス的な振る舞いをするバー

Optimal solution

22068

59030 80369

スト部から構成されるインターミッテンシーカオスとなる. 図

5 に 3 周期付近のインターミッテンシーカオスの例を示す. この図より, 3 周期のインターミッテンシーカオスが確認できる.

kroE100 pr124

pr226

2-opt algorithm

24303

62950 84415

Imtermittency chaos

23371

59847 82805

Fully-developed chaos

22848

60162 84101

Random noise

23575

61529 84220

図 6 に分岐パラメータ α = 4.0 での完全に発達したカオスを示
す. 完全に発達したカオスでは, ラミナー部, バースト部はなくなり, 一様のノイズのようになる. また, カオスノイズとの比較に乱数より生成したランダムノイズを用いる. ランダムノイズもノイズとして注入する際, 式 (2) で正規化を行う. 図 7 にランダムノイズを示す.

表 2 2-opt+Or-opt 法でのカオスノイズ, ランダムノイズ比較

ProblemkroE100 pr124

pr226

Optimal solution

22068

59030 80369

2-opt+Or-opt algorithm

22550

60512 84111

Imtermittency chaos

22092

59030 80735

Fully-developed chaos

22092

59034 80719

Random noise

22103

59049 80775

表 1, 2 より, 2-opt 法, 2-opt+Or-opt 法, どちらの近似解法に対してもノイズの有効性が確認できる. 2-opt+Or-opt 法では, 2-opt 法よりも強い解探索を発揮していることが確認でき,さらにノイズを注入することで, より小さな解を探索している

図5tので, 局所解を回避できていると考えられる. インターミッテ

インターミッテンシーカオス (α = 3.828)

ンシーカオスノイズ, 完全に発達したカオスノイズ, ランダムノイズの比較では差はごく僅かだが, カオスノイズがより最適解に近い解を得ることが出来る. また, 2-opt+Or-opt 法でインターミッテンシーカオスをノイズとして注入する手法では, 10回の平均値で最適解を得ていることが確認できる.
ここで, 100 回の状態更新中の解探索の状況を以下の図に示す. 最適解が 22068 の “kroE100”において 2-opt+Or-opt 法による解探索, それぞれインターミッテンシーカオス, 完全に発達したカオス, ランダムノイズでノイズの振幅は比較として0.001, 0.01 を示す. 横軸を更新数とし, 縦軸を解の大きさとすt
図6

完全発達したカオス (α = 4.0)

る. 縦軸の最小点は最適解である 22068 とする.
図 8-13 より, それぞれの振幅での解探索を比較して, この問—3—

図8

インターミッテンシーカオスノイズ (振幅 0.001)

図 13

ランダムノイズ (振幅 0.01)の間欠性が都市配置に影響を及ぼしていると考えられる. また,完全に発達したカオスにおいても, 都市配置にノイズとして注入するにあたって, カオス的な振る舞いしていると考えられる.

5. ま と め
本研究では, 近似解法である 2-opt 法, 2-opt+Or-opt 法を用いて, 組合せ最適化問題の TSP の解法として, TSP の要素数で図 9 完全に発達したカオスノイズ (振幅 0.001)ある都市配置にカオスノイズを注入し, 局所解の回避, 有効性の検証・比較を行った. シミュレーション結果より, 僅かではあるがノイズとしてインターミッテンシーカオス, 完全に発達したカオスの 2 種のカオスを注入する手法がより最適解に近い解を得られ, 探索力の強い 2-opt+Or-opt 法に対しても有効性が確認できた. 今後の課題としては, ノイズの注入方法での比較, さらに大きな都市配置の問題に対しての調査などがある.

謝辞

図 10 ランダムノイズ (振幅 0.001)

本 研 究 の 一 部 は, 日 本 学 術 振 興 会 の 科 学 研 究 費 補 助 金(22500203) により得られた成果である.
文

図 11

インターミッテンシーカオスノイズ (振幅 0.01)図 12 完全に発達したカオスノイズ (振幅 0.01)

献[1] K. Aihara, T. Takabe and M. Toyoda, “Chaotic neural networks,” Physics Letters A, vol. 144, pp. 330-340, 1990.
[2] M. Hasegawa, T. Ikeguchi and K. Aihara, “Combinationof chaotic neurodynamics with the 2-opt algorithm to solve
traveling salesman problems,” Physical Review Letters, vol.
79, pp. 2344-2347, 1997.
[3] Y. Hayakawa and Y. Sawada, “Eﬀects of the chaotic noise on
the performance of a neural network model for optimizationproblems,” Physical Review E, vol. 51, no. 4, pp. 2693-2696,
1995.
[4] T. Ueta, Y. Nishio and T. Kawabe, “Comparison between
Chaotic Noise and Burst Noise on Solving Ability of Hopﬁeld Neural Networks” Proceedings of NOLTA’97, vol. 1,pp. 409-412, 1997.
[5] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D.
B Shmoys, John Wiley and Sons, Chichester, “The travelingsalesman problem,” 1985.
[6] “TSPLIB,” http://www.iwr.uni-heidelberg.de/groups/ comopt/software/TSPLIB95/

題に最適なノイズの振幅が 0.001 に近いことが確認できる. 振幅の値が 0.001 において, インターミッテンシーカオスノイズ,完全に発達したカオスでは, 解探索の幅が広がっているのに対し, ランダムノイズでは解探索の幅が小さくなっているのが分かる. ラミナー部とバースト部から構成されるインターミッテ
ンシーカオスノイズにおいては, インターミッテンシーカオス—4—