法政大学大学院理工学・工学研究科紀要 Vol.55(2014 年 3 月） 法政大学 改良最近追加法による TSP 解法 A solution of the improved Nearest-Addition Method for TSP 稲葉 和也 Kazuya Inaba 指導教員 李 磊 法政大学大学院工学研究科情報電子工学専攻修士課程 Traveling Salesman Problem(TSP) is one of the NP-hard. This is a problem of finding the shortest path in the route to visit once each all of the cities given. The number of cities increases, the combination of directions will increase rapidly. In this paper, I propose a solution using the improved Nearest-Addition Method for TSP. In addition, from the result of the comparison experiments conducted, and show its effectiveness. Key Words : Nearest-Addition TSP １． はじめに 巡 回 セ ー ル ス マ ン 問 題 (Traveling Salesman Problem:TSP)は与えられた都市すべてを 1 回ずつ通って d(T, i) = min 𝑑 (3.1) 元の都市に戻ってくる巡回路のうち,移動距離が最短に なる経路を求める問題のことである.巡回路の選び方は (1) アルゴリズム (n-1)!/2 通りで,全ての巡回路を列挙して,総距離が最小 1. 部分巡回路 T に都市を１つずつ加える操作を行う であるものを調べたら原理的には解ける. 2. 部分巡回路 T からの距離 d(T,i)が最小となる都 巡回セールスマン問題は NP 困難の問題であり,準最適 解を現実的な時間で求めるための近似算法またはヒュー 市 i を選ぶ 3. 都市 j と隣接する都市 k の間の枝(k,j)を繋ぎ替え リスティック手法と呼ばれる手法が多く提案されている. て新たな部分巡回路作り,全ての都市が結ばれる また,それらの手法の中で大きく分けて構築法と改善法 まで 1 から繰り返す の 2 つに分けられており,本稿では,構築法の一つである 最近追加法を改良したものの有効性と改善法の一つであ る 2-opt 法と or-opt 法を組み合わせものの研究結果を示 す. ２． 近傍都市 近傍都市とは,それぞれの都市から距離の近い都市を 何都市か選んだ集まりのことを近傍都市と呼ぶ.これ 図 1 最近追加法 は,TSP において計算量を削減する目的で設定している. 解の性質上,都市間を結ぶとき,絶対に探索しないであろ う都市を,TSP を解く前に各都市の距離を計算しておくこ とで,計算量を削減出来る. (2) 改良最近追加法 最近追加法では部分巡回路の一つである都市の最も近 い都市との距離を部分巡回路の都市数分だけ調べていく が,最短距離の都市を見つけた後,巡回路にするため,都 ３． 最近追加法 構築法に分類される手法の一つである.ランダムな,都 市の繋ぎ替えが行われるため,実際に一番総距離が短く なる保証がありません. 市順を改善するのではなく,規則を設けることで短時間 その欠点を補うため,都市 i の候補を距離順で最も短い で良質な解を得ることが出来る.この手法は部分巡回路 ものから２つ選び都市の繋ぎ変えを行い,最も短くなっ と呼ばれる小規模な巡回路を生成し,その巡回路から総 たものを採用する手法を提案する. 距離が短くなるように都市を一つずつ加えていく手法で ある.(3.1 式) ４． 最近近傍法 ７． 実験 最近追加法とは次のような構築法である. 実験では性能評価の対象問題として TSPLIB から表 1 を用意した.また,様々な規模の問題も解き,各手法との性 1． 適当な都市を選び,出発点とする 能比較を行った.なお,問題番号は都市数を示している. 2． すべての都市を訪問するまで以下を繰り返す ・まだ来訪間の都市で,現在いる都市から最も近い都市 を選ぶ 表 1 ベンチマーク ・視在いる都市と選んだ都市を接続し,選んだ都市に移 動する 問題 最適解 pr1002 259045 ・現在いる都市と出発点を接続する (1) 実験手法 この方法は,部分的に最適巡回路と同じ辺を多く含む傾 最初に,改良最近追加法の有用性を確認するために,構 向があり,改善法にかかりやすい.また,この方法も構築の 築法である改良最近追加法,最近追加法と最近近傍法で 最終段階で極端にコストの大きい辺を選ぶ傾向があり,解 そ れ ぞ れ 初 期 解 を 生 成 し , 改 善 法 で あ る 2-opt 法 と の精度は良くない. Or-opt 法の 2 つを用いて最終的に解を出した.結果は全 て 5 回解いた平均値である. ５． 2-opt 法 全ての構築法において,近傍都市数を 20 とした. 2-opt 法は ,TSP の巡回路に対して ,適当な 2 本の枝 (2) 実験結果 を選び ,枝の先を交換する手法である .交換前と交換後 の巡回路長を比較し ,巡回路が改善されるようであれば 表 2 手法比較 交換後の巡回路を新たな解とする局所改善法の一つとし 手法 平均(誤差率) て知られ ,広く利用されている.しかしながら,問題のサ 2-opt 398771(53.1%) 9.2 イズが大きくなる場合 ,アルゴリズムが就職する時間が 2opt+Or-opt 279785(8.0%) 1347.1 増大するという問題がある.計算時間の短縮や計算精度 最近追加法 274985(5.7%) 1532 269111(3.8%) 1600 274739(6.0%) 1414 向上を目的に,並列計算の利用や各種発見的解法を併用 した手法が多く提案されている. (1) アルゴリズム 時間(s) 2opt+Or-opt 改良最近追加 法 1. 1 つの巡回路を用意する. 2.巡回路中の 2 つの枝 (ab,cd)を取り除く. 3.生成された部分枝のうち一つの順序を逆にする. 4. ac+bd < ab+cd となっていれば,ac,bd を結合す 2opt+Or-opt 最近近傍法 2opt+Or-opt る. 5. 4.を満たす枝がなくなれば終了. 2-4 を繰り返す． 表 3 構築法の距離比較 問題 最近 最近 近傍法 追加法 提案手法 最適解 d493 52466 50210 47897 35002 nrw1379 84321 78940 76000 56638 fl3793 51212 44997 40294 28772 図 2 2-opt 法 表 4 構築法に改善法を施した距離比較 ６． Or-opt 法 Or-opt 法は ,2-opt 法と似ており ,巡回路の一部の辺 を固定して,それをほかの部分に挿入し,交換前と交換後 で改善されるようであれば解とする.Or-opt 法は,2-opt 法などで得られた局所最適解をさらに改良するためによ く用いられる. d493 nrw1379 fl3793 2opt 法 49322 75820 48902 最近近傍法 36115 58678 33097 提案手法 36123 58562 30980 ８． 考察 今回は,改良最近追加法の実装及び従来手法との性能 比 較 を 行 っ た .2-opt,2-opt+Or-opt, 最 近 追 加 法 +2opt+Or-opt 法,改良最近追加法 ,最近近傍法の 5 試行 の平均計算結果を求めた.距離を比べると ,大規模な問 題と小規模な問題の結果を総合すると改良最近追加法の 結果が最も良くなったと言える .しかし距離と計算時間 の関係はトレードオフの関係あるため,大規模な問題に は有効であるが小規模な問題にはあまり適していないこ とが分かった. 謝辞：本研究を遂行するにあたり多大なるご指導を頂き ました法政大学教授 李 磊教授に厚くお礼を申し上げ ますまた本研究室の班諸氏にも感謝いたしますさらに 様々な助言を頂きました本研究室の大学院生の諸先輩方 並びに年生諸氏にも感謝いたします. 参考文献 1)野剛教,松本直樹:巡回セールスマン問題の近似解法の 比 較 : 電 子 情 報 通 信 学 会 論 文 誌 D, J80-D, 127136 (2006). 2)加地太一:AR（１）モデルによる組合せ最適化問題の近 傍に対する解析:日本オペレーションズ・リサーチ学会 和論文誌 2008 年 51 巻 112-135 3)山本芳嗣,久保幹夫,=巡回セールスマン問題への招待 日,朝倉首尾 1997 4)H.M.M. Eikelder, M.G.A. Verhoeven, T.W.M. Vossen and E.H.L. Aarts: A probabilisticanalysis of local search. In I.H. Osman and J.P. Kelly (eds.): Meta-Heuristics: Theory& Applications (Kluwer, 1996), 605–618.
© Copyright 2024 ExpyDoc
