巡回セールスマン問題入門 Introduction to Traveling Salesman Problems

Presentation on theme: "巡回セールスマン問題入門 Introduction to Traveling Salesman Problems"— Presentation transcript:

1 巡回セールスマン問題入門 Introduction to Traveling Salesman Problems
東京大学工学部計数工学科 松井知己

2 巡回セールスマン問題 (Traveling Salesman Problem)
●定式化が困難な問題 ●新聞記事等で有名な問題 ●様々な解法の試金石

3 セールスマンが全ての都市を1回ずつ通過して, 出発地に戻って来る経路で最も短いものを捜す. ６都市ならば,
巡回セールスマン問題 セールスマンが全ての都市を1回ずつ通過して, 出発地に戻って来る経路で最も短いものを捜す. ６都市ならば, 5!/2= 5×4×3×2 / 2 =60通り. ｎ 都市ならば, （ｎ - 1）! /2 通り. 近年, 新聞や科学雑誌でも 取り上げられて有名になった. TSP（Traveling Salesman Problem） 原型：ハミルトン閉路問題

4 電子基盤に穴をあける （部品を埋め込む）順序を決定する問題． 総移動距離を最小化する = 単位時間当たりの生産量最大化.
ドリル穴あけ計画問題 電子基盤に穴をあける （部品を埋め込む）順序を決定する問題． 総移動距離を最小化する = 単位時間当たりの生産量最大化.

5 全ての都市を1回ずつ通過して,出発地に戻って来る経路で最も短いものを捜す. ただし，都市間の移動時間は, 移動方向に依存して異なる．
非対称巡回セールスマン問題 全ての都市を1回ずつ通過して,出発地に戻って来る経路で最も短いものを捜す. ただし，都市間の移動時間は, 移動方向に依存して異なる． （移動時間の非対称性） 実際の道路網では， 良く見かける状況. 3 5 6 2 7 8 9 1 4

6 鉄板の圧延計画 部品によってブレード位置を 設定する必要がある． ブレードの設定変更の費用は, 変更前後の部品種類によって異なる,
一機械スケジューリング問題 鉄板の圧延計画 部品によってブレード位置を 設定する必要がある． ブレードの設定変更の費用は, 変更前後の部品種類によって異なる, （幅を狭めるのは難しい）． ブレード設定変更の総費用最小化. 非対称TSPへの帰着 都市 = 生産する部品 セールスマン = 圧延機械 距離 = ブレード設定変更費用

7 非対称TSP 都市間の距離が向きにより異なる 一般 対称TSP 都市間の距離が向きに寄らない 平面TSP 都市が平面上の点,
巡回セールスマン問題のヴァリエーション 都市間距離 非対称TSP 都市間の距離が向きにより異なる 一般 対称TSP 都市間の距離が向きに寄らない 平面TSP 都市が平面上の点, 都市間距離は2点間の直線距離 特殊 他の制約 m人TSP 出発点から出たm人で都市全体を回る 各都市を丁度1回ずつ通過→1回以上通過 各枝を1回以上通過=中国人郵便配達人問題 (Chinese Postman Problem)

8 Hamilton 閉路問題 ●セールスマン問題の原型 ●難しさの原点

9 グラフ：頂点とそれを結ぶ枝からなるもの 頂点：①, ②, ③, ④, ⑤ 枝：a, b, c, d, e, f
１ ４ ｆ d a c ５ e ２ ３ b

10 Hamilton 閉路：すべての頂点を丁度1回づつ通過して, 出発点に戻る路(閉路). 与えられたグラフにHamilton閉路がありますか？
YES:Hamilton 閉路有り NO:Hamilton 閉路無し

11 William Rowan Hamilton (1805-1865) Icosian Game: 正12面体の頂点全て（20個）を，
1人目： 最初の4歩 （5個の頂点）を指定． 2人目： 5歩目以降を探索． 正12面体の頂点全てを， 丁度1回ずつ通過して戻る道を， 見つければ，勝利． ？ ６ ７ ５ 20 ４ ２ １ ３

12 参考図書

13 The Traveling Salesman Problem,
参考図書 The Traveling Salesman Problem, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, Wiley, 1985.

14 参考図書 「巡回セールスマン問題への招待」, 山本芳嗣, 久保幹雄, 朝倉書店.

15 参考図書 「整数計画法と組合せ最適化」, 今野浩, 鈴木久敏, 日科技連.

16 組合せ的爆発 ●セールスマン問題の難しさ ●計算量

17 （対称）TSP：都市n個のとき, (n‐1)!／2通り. 組合せの数は有限だが， 沢山あるので,最適解を見つけるのが難しい.
組合せ最適化の難しさ （対称）TSP：都市n個のとき, (n‐1)!／2通り. 組合せの数は有限だが， 沢山あるので,最適解を見つけるのが難しい. 組合せ錠 (Combination Lock)： 組合せは有限だが, 最適を見つける（錠を開ける） のは難しい. 錠の性質を知って, 効率的に開ける. 有限時間で解ける事は分かっているので， 解くのにかかる時間の議論は本質的な議論. 9 1 2 3 4 5 6 7 １

18 5つの基本演算はすべて1stepで実行できる. Q1. a1, ...,an の2倍の和を求める.
計算量 ＋,－,×,÷, 比較： 5つの基本演算はすべて1stepで実行できる. (実際は,×は＋より時間がかかる.） Q1. a1, ...,an の2倍の和を求める. (1) 2×a1+･･･+ 2×an , 2n-1 steps→ O(n)算法. (2) 2×(a1+･･･+an) , n steps→ O(n)算法. Q2. a1b1+･･･+anbnの計算. 2n-1 steps → O(n)算法. Q3.ｎ×ｎ行列2つの掛け算. 定義通りの計算 n2(2n-1) steps → O(n3)算法. 注: Strassen の算法は O(n2.7).

19 最悪値評価： 最悪のケースの時間を算定する. : O(n) O(n log n ) 多項式時間算法
アルゴリズムの速さ アルゴリズムの実行時間は， 入力に依存する事が多い. 最悪値評価： 最悪のケースの時間を算定する. : O(n) O(n log n ) 多項式時間算法 O(n2) polynomial time algorithm O(n3) O(2n) 指数時間算法 O(n!) exponential time algorithm O(n log2 n ) = O(n log10 n )

20 （対称）TSP：都市n個のとき, (n‐1)!／2通り. 100MIPS (mega instructions per second)
組合せ的爆発 （対称）TSP：都市n個のとき, (n‐1)!／2通り. 100MIPS (mega instructions per second) 1秒間に100万回の計算＝1回 に 10-6秒 光速 3.0×1010cm/秒 (10-6秒 に 300m進む) n , ,000 n 秒 秒 秒 秒 n 秒 秒 秒 秒 n 秒 秒 分 時間 2n 秒 1014世紀 世紀 ‐‐‐‐‐‐‐ n! 秒 世紀 世紀 ‐‐‐‐‐‐‐ 実感しよう! 宇宙の年齢 1.5×108 世紀 （１５０億年）

21 5mm四方のチップ：1.7×10‐11 秒に光は0.5cm進む．
計算機スピードと組合せ的爆発 計算機が速くなれば，むしろ差は広がる！ 10秒間にできる計算量は？ 100MIPS 10倍 倍 倍 n n 千 万 万 万 n 千 千 2n n! 1000倍⇒ 1step に 10-9秒 ⇒ 10-9秒 に光は30cm進む 5mm四方のチップ：1.7×10‐11 秒に光は0.5cm進む．

22 100MIPSの計算機に比べ，どのくらい速いか？ n 100 1,000 .
並列計算機ならば 5 mm 四方 のチップ： 光が5mmを動くには 1.7×10‐11 秒より, 1stepには1.7×10‐11 秒かかる. 地球表面を全て上記チップで覆う： 2.0×1019個. 100MIPSの計算機に比べ，どのくらい速いか？ n , 2n 世紀 → 0.85 秒 世紀 → 世紀 n! 世紀 → 10120世紀 世紀 → 世紀 有限で解けるのだから, 「計算の速さ」の議論は本質的.

23 計算の複雑さ (Computational Complexity )

24 答がYESとNOで，納得させる難しさが異なる． 「すべてのカラスは黒い」 ＝「黒くないカラスがいるか？」
存在の判定問題の難しさ 何かが存在する事を判定する問題： 答がYESとNOで，納得させる難しさが異なる． 「すべてのカラスは黒い」 ＝「黒くないカラスがいるか？」 YES：（簡単）そのカラスを連れてくる．（反例を挙げる） NO：（困難）すべてのカラスをチェックしてみせる？ 「宇宙人はいるか？」 YES :（簡単）宇宙人を連れてくる． NO：（困難）宇宙中をすべて探索してみせる？ 計算可能性や反証可能性とも関連

25 YES:Hamilton 閉路有り NO:Hamilton 閉路無し
Hamiton 閉路問題 Hamilton 閉路： すべての頂点を丁度1回ずつ通過して, 出発点に戻る路(閉路). Hamilton閉路が存在するか？ YES:Hamilton 閉路有り NO:Hamilton 閉路無し 証拠は？

26 割当問題 4っの仕事を4台の機械に割り当てる. YES

27 割当ては存在しない(NO!) → 存在しない証拠は？
2n頂点： O(n2.5)時間で存在をチェックできる.

28 クラスNP ：YESの時に証拠のある問題のクラス クラスco-NP：NOの時に証拠のある問題のクラス
NP‐完全 (NP-complete) 決定問題：YES-NO を答える問題 クラスNP ：YESの時に証拠のある問題のクラス クラスco-NP：NOの時に証拠のある問題のクラス クラスP：多項式時間算法の存在する問題のクラス クラスNP‐完全：多項式時間算法の存在が 絶望視されている問題のクラス クラスco-NP クラスNP クラスNP-完全 Hamilton閉路問題 クラスP 割当問題

29 最小包囲円問題 最小包囲円問題：与えられた点集合を含む, 半径最小の円を求める 最適でない 最適である n点：O(n)時間解法が存在.

30 与えられた巡回路は最適解(最も短い)か？ 最適でない 最適？ 最適でないときは，より短い解を証拠とできる．
平面TSP 与えられた巡回路は最適解(最も短い)か？ 最適でない 最適？ 最適でないときは，より短い解を証拠とできる． 最適である証拠は？

31 TSPを解く算法 ●厳密解法 ●近似解法 ●発見的解法

32 厳密解法 (exact algorithm)： 最適解を1つ求める解法 近似解法 (approximation algorithm)：
TSPの解法の種類 厳密解法 (exact algorithm)： 最適解を1つ求める解法 近似解法 (approximation algorithm)： 求められる解の精度に（何らかの）保証のあるもの． 発見的解法 (heuristic algorithm)： 良いと思われる解を探索する解法．解の精度に保証は無い．

33 ●分枝カット法 ＝分枝限定法＋組合せ的多面体論
厳密解法 ●分枝カット法 ＝分枝限定法＋組合せ的多面体論

34 1954: 49都市： 切除平面法 1971: 65都市： ラグランジュ双対法 1980: 318都市: 分枝カット法
厳密解法の歴史（平面TSP) 厳密解法について，今日は話しません！ 1954: 49都市： 切除平面法 Dantzig, Fulkerson and Johnson 1971: 65都市： ラグランジュ双対法 Held and Karp 1980: 318都市: 分枝カット法 Christofides and Padberg 1991: 666都市： 分枝カット法 Grotschel and Holland 1991: 2,392都市： 分枝カット法 Padberg and Rinaldi 1993: 4,461都市： 並列計算機＋分枝カット法 Applegate, Bixby, Chvatal and Cook 1994: 7,397都市： 並列計算機＋分枝カット法

35 近似解法 ●近似の困難さ ●簡単な２近似解法

36 「与えられた（対称）TSPにおいて，最短巡回路の長さのM倍以下の巡回路が存在するか？」 という問題はNP‐完全である．
近似の難しさ 定理： 任意の正の数 Mに対し，以下が成り立つ． 「与えられた（対称）TSPにおいて，最短巡回路の長さのM倍以下の巡回路が存在するか？」 という問題はNP‐完全である． 最適解のM倍以内の近似解を求める問題も，元の問題（TSP)と同程度に難しい． 三角不等式が成り立つときは，近似算法がある．

37 枝の短いものから順に（サイクルが出来ない限り）取り入れて行く．
巡回セールスマン問題の2‐近似解法 全域木：頂点全体を連結にする枝集合 最短全域木：貪欲算法で求められる． 枝の短いものから順に（サイクルが出来ない限り）取り入れて行く． 最短全域木の長さ≦最短巡回路 1 2 4 5 7 8

38 三角不等式が成り立つときは，近似算法がある：
2重全域木法 三角不等式が成り立つときは，近似算法がある： 最短全域木にそって， 一度通過した頂点は， 全ての頂点を回る． スキップする． 2×最短巡回路の長さ ≧2×最短全域木の長さ≧得られた巡回路の長さ

39 ●局所探索 ● Simulated Annealing ● Tabu Search
発見的解法（平面TSP） ●局所探索 ● Simulated Annealing ● Tabu Search

40 構築法 (construction method) nearest neighbor 法 nearest addition 法
発見的解法 構築法 (construction method) nearest neighbor 法 nearest addition 法 farthest insertion 法 改善法 (improvement method) 局所探索法 (local search method) 模擬焼き鈍し法 (simulated annealing method) 禁断探索法 (tabu search method) 遺伝的アルゴリズム(genetic algorithm) ニューラルネットワーク (neural network)： （TSPに向かない．最近は使われていない）

41 ● nearest neighbor 法 ● nearest addition 法 ● farthest insertion 法
構築法 ● nearest neighbor 法 ● nearest addition 法 ● farthest insertion 法

42 nearest neighbor 法：（最適値との誤差 15％ 程度）
構築法 nearest neighbor 法：（最適値との誤差 15％ 程度） nearest addition 法： （最適値との誤差 20％ 程度） farthest insertion 法： （最適値との誤差 5％ 程度）

43 改善法 ●局所探索法 (local search method) ●模擬焼き鈍し法 (simulated annealing method)
●禁断探索法 (tabu search method)

44 ●最も簡単な改善法 ●改善法の基礎 ●最も強力な改善法となることも多い
局所探索法 (Local Search) ●最も簡単な改善法 ●改善法の基礎 ●最も強力な改善法となることも多い

45 局所探索法 (local search method)
最も基本的な改善法 山登り法 (hill climbing method) とも呼ばれる． 現在の解の近傍（良く似ている解の集合）で，目的関数値がより良いものがあれば，現在の解をそれに更新する． （大域的）最適解 局所的最適解 良い 目的関数値

46 現在の巡回路から2本枝を付け替えて， より短かくなる巡回路が有るならば, （1つとは限らない），巡回路をそのうちのどれかに更新する．
2-opt近傍を用いた局所探索法 2-opt近傍：2本の枝の付け替えで 得られる巡回路の集合 現在の巡回路から2本枝を付け替えて， より短かくなる巡回路が有るならば, （1つとは限らない），巡回路をそのうちのどれかに更新する． Nearest Neighbor + 2-opt =(最適値から2.5%程度） etc.

47 一般的な局所探索法（図） 目的関数値 局所的最適解 局所的最適解 良い （大域的）最適解 近傍

48 2-opt 近傍：枝を2本付替えて得られる巡回路． 3-opt 近傍：枝を3本付替えて得られる巡回路．
近傍の決定 巡回セールスマン問題の近傍 2-opt 近傍：枝を2本付替えて得られる巡回路． 3-opt 近傍：枝を3本付替えて得られる巡回路． 4-opt 近傍：枝を4本付替えて得られる巡回路．

49 得られる解：悪い局所最適解⇔良い局所最適解 近傍の決定は，得られる解の良さと，使用できる計算時間の釣り合いに依存．
例 ： 2-opt opt opt ‥‥ 近傍の広さ： 狭い ⇔ 広い 近傍探索 ： 短時間 ⇔ 長時間 得られる解：悪い局所最適解⇔良い局所最適解 近傍の決定は，得られる解の良さと，使用できる計算時間の釣り合いに依存． Nearest neighbor =(最適値から15％程度） Nearest neighbor + 2-opt =(2.5％程度） Nearest neighbor + 2,3-opt =(0.3％程度）

50 探索する解空間を，許容領域から少し広げる事により，性能の良い探索法を構築する．
探索空間の設定 Lin and Kernighan の解法 探索する解空間を，許容領域から少し広げる事により，性能の良い探索法を構築する． 擬似許容解解：許容解に近い解集合を，擬似許容解として定義し，擬似許容解中を探索． δパス （e パス，のパス‥？）：

51 探索する領域を，許容解集合（巡回路集合）から，少し広げる．対応する巡回路
Lin and Kernighan の算法 探索する領域を，許容解集合（巡回路集合）から，少し広げる．対応する巡回路 擬似許容解 許容解

52 局所最適解からの脱出

53 (multiple start local search) ●広い近傍の一時的な導入 (iterated local search)
局所最適解の脱出 局所探索法は，局所最適解で停止する． ⇒局所最適解からの脱出法が必要 ●初期解を変えて，局所探索法を再適用 (multiple start local search) ●広い近傍の一時的な導入 (iterated local search) ●ランダム性の導入 模擬焼き鈍し法 (simulated annealing method) ●最急降下‐最緩上昇 タブー探索法 (tabu search method)

54 ●一時的に広い近傍を用いて， 局所最適解から脱出する． （1ページ）
Iterated Local Search ●一時的に広い近傍を用いて， 局所最適解から脱出する． （1ページ）

55 iterated local search：一時的に広い近傍を用いて， 現在いる局所最適解から脱出する．
例：巡回セールスマン問題の Lin and Kernighan探索法において，局所最適解が得られた際，(無作為に) 4-opt 操作を行って，局所最適解から脱出する．

56 模擬焼き鈍し法 (Simulated Annealing)
●ランダム性を用いて 局所最適解を脱出する． ●解の改善量を導入して， ランダム性に偏向を与える． （３ページ）

57 金属やガラスの内部の歪みを除くため，ある程度まで熱してから徐々に冷ますこと． 以下の方法で山を登る：
simulated annealing annealing: 焼き鈍し： 金属やガラスの内部の歪みを除くため，ある程度まで熱してから徐々に冷ますこと． 以下の方法で山を登る： 現在地 x の近傍内から適当に１点ｙ を選ぶ． if (x より ｙ が高い), then (x から ｙ に移動)． else (ある確率 pで x から ｙ に移動)． x と ｙ の標高差が小 ⇒ 移動する確率 pが大． 気温が高い（熱い） ⇒ 移動する確率 pが大． 気温は時間と共に徐々に下がって行く．

58 各反復で以下を行う．（目的関数 f (x) ） 現在の解を x，現在の温度をTとする． x の近傍内から適当に１点ｙ を選ぶ．
simulated annealing 各反復で以下を行う．（目的関数 f (x) ） 現在の解を x，現在の温度をTとする． x の近傍内から適当に１点ｙ を選ぶ． if (x より ｙ が良い解), then (x を ｙ で更新)． else (確率 exp｛-| f(x)-f(ｙ)| / T｝で x を ｙで更新)． 変化量|f(x)-f(ｙ)|が小 ⇒ 更新する確率が大． 温度Tが高い ⇒ 更新する確率が大． （温度が高いと，局所最適解を脱出する可能性が有る．） 温度は反復と共に下がって行く． 例：対数冷却：第k反復の温度Tk∝1/log(k+1)

59 simulated annealing の特徴
近傍より1点を選んで計算する． 近傍全域を探索しない． 局所探索に比べ広い近傍を用いる事ができる． ２~４opt 近傍を用いる事が可能． 定理[Hajek] simulated annealing の挙動を表現するMarkov chainが既約で弱可逆ならば，対数冷却を用いた simulated annealing で生成される解の列は，確率1で最適解に収束する． 注：上の定理が保証する収束時間は，O(ｎ !）より長い．

60 ●最急降下最緩上昇で 局所最適解を脱出する． ●タブーリストを用いて，循環を避ける． （４ページ）
禁断探索法 (Tabu Search) ●最急降下最緩上昇で 局所最適解を脱出する． ●タブーリストを用いて，循環を避ける． （４ページ）

61 最急降下：下がれる時は最も下がる方向へ． 最緩上昇：下がれないときは，最も緩やかな登りの方向へ．
最急降下最緩上昇 （最小化問題の）局所最適を脱出する： 最急降下：下がれる時は最も下がる方向へ． 最緩上昇：下がれないときは，最も緩やかな登りの方向へ． これだけでは， いくつかの解を巡回するだけ． タブーリストを用いて， 後戻りを「しばらくの間」禁止する． （次ページで例示）

62 e または f を使った 2-opt 交換を禁止する． tabu list：交換に用いる事が禁止されている枝リスト．
tabu search 2‐opt 近傍：2つの枝を交換 tabu：ある反復で 枝 eと枝 f の交換を行ったら， その後数回の反復では， e または f を使った 2-opt 交換を禁止する． tabu list：交換に用いる事が禁止されている枝リスト． tabu search: 可能な 2-opt 交換の中で， 最急降下最緩上昇の交換を選ぶ． tabu length：tabu の状態に留める期間． 要素毎に 5~11 の値を無作為に選ぶ．

63 頻度メモリ：解の更新方法それぞれにつき， それが実行された頻度（回数）を記憶しておく． 頻度の大きな更新は，余り行わないようにする．
頻度メモリ（長期メモリ）の導入 解の一部分での局所的な交換で， 目的関数値をあまり変えない物があれば， 多数回起こる可能性がある． 頻度メモリ：解の更新方法それぞれにつき， それが実行された頻度（回数）を記憶しておく． 頻度の大きな更新は，余り行わないようにする．

64 近傍内の全探査をする： あまり広い近傍は取れない． 解法の枠組みが単純： 問題依存の規則を多数加える事が出来る．
tabu search の特徴 近傍内の全探査をする： あまり広い近傍は取れない． 解法の枠組みが単純： 問題依存の規則を多数加える事が出来る． ヴァリエーションが広い（広すぎる）． 良い解法の構築の「定石」が少ない．

65 おわり