近似解法からメタ戦略へ ー巡回セールスマン問題を例としてー 東京商船大学 久保 幹雄 近似解法からメタ戦略へ ー巡回セールスマン問題を例としてー 東京商船大学 久保　幹雄 巡回セールスマン問題って何？ ー数学の時間 なぜこんな問題を研究するの？ ー歴史の時間 良い近似解法ってどんなの？ ー哲学の時間 メタヒューリスティクスって何？ ー物理，生物などの時間

巡回セールスマン問題って何？ Traveling Salesman Problem (TSP)

Definition otherwise Asymmetric TSP Given n points (cities) and a distance function between two points, find a minimum length Hamiltonian circuit |ab|=|ba| Symmetric　TSP a b |ab|=|ba| otherwise Asymmetric TSP ΔTSP a b c |ac|≦|ab|+|bc| points are in d-dim. Euclidean space Euclidean TSP

なぜ巡回セールスマン問題 を研究するの？ 難しいから（と評判だから） ー登山家の立場 暇つぶしに最適 ーパズル愛好者の立場 暇つぶしに最適 ーパズル愛好者の立場 応用がたくさんあるから ー実務家の立場 組合せ最適化の代表例だから ー最適化リサーチャーの立場

TSPは難しい？ 最も `naïve’ な解法（全列挙法） 某新聞曰く：３０都市の巡回セールスマン問題になると総あたり法は高性能計算機でも約３日かかる!　（本当？） (n-1)×(n-2)×…×3×2×1=(n-1)! 1 PIPS (Peta Instruction Per Second) 1015 29!/1015 　（秒）　≧ π×1014 （秒） ≒ 105 （世紀） James Stiringの公式 n! ≒2√πn(n/e)n Tom Duffの格言 π秒は1ナノ世紀

World Records of Exact Algorithms for Euclidean Benchmarks (TSPLIB) Dantzig, Fulkerson & Johnson 49 cities (1954) Held & Karp 65 cities (1971) Grotschel 120 cities (1977) Crowder & Padberg 318 cities (1980) Padberg & Rinaldi 532 cities (1987) Grotschel & Holland 666 cities (1991) Padberg & Rinaldi 2392 cities (1991) Applegate, Bixby, Chvatal & Cook 7392 cities (1996) Applegate, Bixby, Chvatal & Cook 13509 cities (1998) Applegate, Bixby, Chvatal & Cook 15112 cities (2001) Applegate, Bixby, Chvatal & Cook 1904771 cities (????)

DANTZIG42 solved by George Dantzig, Ray Fulkerson and Selmer Johnson (1954)

GR120 solved by Groetschel (1977)

The optimal tour of ATT532 (532 AT&T switch locations in the USA) found by Padberg and Rinaldi (1987)

The optimal tour of GR666 (666 cities in the world) found by Groetschel and Holland (1987)

The optimal tour through a layout of 2,392 (PR2392) found byPadberg and Rinaldi (1991)

PLA7397 (a programmed logic array application containing 7,397 cities)

The optimal tour of PLA7397 found by David Applegate, Robert Bixby, Vasek Chvátal and William Cook (1994)

USA13509 (13,509 cities in the United States having a population of at least 500)

The optimal tour of USA13509 found by Applegate, Bixby, Chvátal, and Cook (1998)

D15112 (15,112 cities in Germany)

The optimal tour of D15112 found by Applegate, Bixby, Chvátal, and Cook (2001) CPU time used is 22.6 years of computer time, adjusted to a 500 MHz, EV6 Alpha processor

1,904,711-city instance

パズルとＴＳＰ（１） Knight Tour

A Knight Tour (by Leonhard Euler：1707-1783)

パズルとＴＳＰ（２） Icosian Game (Origin of Hamiltonian Circuit) Invented by W パズルとＴＳＰ（２） Icosian Game (Origin of Hamiltonian Circuit) Invented by W. R. Hamilton (1805-1865)

Icosian Game (1) １ ２ ４ ３ ２０

Icosian Game (2) １ ２ ７ ６ ５ ４ ３ ２０

Icosian Game (3) １ ２ ７ ６ ５ ４ ３ ９ ８ ２０

Icosian Game (4) １ ２ ７ ６ ５ ４ ３ ９ ８ １４ １３ １２ １１ １０ ２０

Icosian Game (5) １ ２ ７ ６ ５ ４ ３ １９ ９ ８ １８ １７ １６ １５ １４ １３ １２ １１ １０ ２０

Applications of TSP 基盤配線 配送計画 タンパク質構造解析

10 P Applications clustering a data array circuit board assembly 2 circuit board assembly computer wiring 3 circuit board drilling vehicle routing 4 protein conformations x-ray crystallography 5 VLSI Scan Chain Optimization 6 VLSI fabrication 7

良いアルゴリズムとは？ アルゴリズムの評価尺度 性能 速さ（CPU時間，仮想実行時間，メモリアクセス回数），メモリ使用量，解の良さ（性能比率，相対誤差） 一般性 頑強性，パラメータに対する頑強性，汎用性 利便性 単純性，実装の容易さ，拡張の容易さ，モジュール化のし易さ 報道価値性 新規性，重要性

アルゴリズム評価のパラダイム 最悪値解析 確率的解析 実験的解析 すべての問題例に対する悲観値（Christofides’ algorithm） 確率的解析 特定の問題例の分布に対する期待値（Karp’s algorithm） 実験的解析 代表的な問題例に対する実験値

Theoretical Results（最悪値解析） Assuming P ≠NP no polynomial-time algorithm can guarantee A(I)/OPT(I) ≦ 2 p(n) for any fixed polynomial p Symmetric TSP △TSP A(I)/OPT(I) ≦ 1+ε for an ε>0 A(I)/OPT(I) ≦1.5 (Christofides’ O(n3) algorithm) d-dimensional Euclidean TSP A(I)/OPT(I) ≦ 1+ε for an ε>0 if d is Θ(n) for any ε>0 if d is O(1) (Arora’s O(n 12 2 13 log n/ε) algorithm)

Approximate Algorithms Construction Algorithms Nearest Neighbour Greedy Christiofides’ Insertion Karp’s Bucket Improvement Algorithm 2,3,..k-opt Lin-Kernighan opt

適当な点から出発し、まだ訪問していない最も近い点へ移動する Nearest Neighbor 全ての点を訪問したら出発点へもどる 適当な点から出発し、まだ訪問していない最も近い点へ移動する

Nearest Neighbor (Worst Case Results) Running Time : NN(I) OPT(I) ∀I NN(I) OPT(I) ∃I

Greedy （Multiple Fragment) 閉路ができたり、次数が２を超えないように、枝を短い順に加えていく

Greedy (Worst Case Results) Running Time : Greedy(I) OPT(I) ∀I ∃I Greedy(I) OPT(I)

奇数次数を持つ頂点に対して最小マッチングを求める Christofides’ 　（１） 奇数次数を持つ頂点を赤く塗りつぶす 奇数次数を持つ頂点に対して最小マッチングを求める 最小木を作る

Christofides’ （２） 一度通過した点をスキップすることにより、順回路をえる まだ通過していない枝をグラフ非連結にならないようにたどる

Christofides’ (Worst Case Results) Running Time : Christofides(I) OPT(I) ∀I ∃I Christofides(I) OPT(I)

Karp’s Partitioning Method (1) 各小領域に対する最適巡回路を求める 長方形で、p個の点が入るように分割する

Karp’s Partitioning Method (2) 長方体と交わる点の枝を非連結にならないようにたどる

Bucket Running Time : 決められた順序（小領域内では任意）で点を訪問する 全ての点を含む単位正方形で小領域に分割し、適当な順序をつける

Karp’s Partitioning Method Probabilisitcs Analysis（確率的解析） BHH Theorem (Beardwood, Halton and Hammersley, 1959) 面積Aの正方領域にランダムにばらまかれた n個の点に対する lim OPT(I) ＝　　　　　　　 (β≒0.7124) β=0.749 BHH (1959) too optimistic! β=0.765 Stein (1977)

実験的解析 特定の応用（実務）のためのアルゴリズムに対する実験 (application paper） （標準的な問題に対する）アルゴリズムの優越性を示すための実験 (salespitch paper) アルゴリズムの平均的・実際的な振る舞いについての知識を得るための実験 (experimental paper)

どんな問題例を使うべきか？ Application paper（検証実験） Salespitch paper（競争的実験） 実際問題もしくはそれに類似した問題 Salespitch paper（競争的実験） ベンチマーク問題（なければ自分で作成；開発したアルゴリズムで解きやすいクラスだけ生成しないように！） Experimental paper （分析的実験） ランダム問題生成プログラム（E.g., U(0,1] for bin packing) ->漸近値解析 特に有効なのはパラメータで制御可能なランダム問題生成プログラム（E.g., U(a,b] for bin packing) ベンチマーク問題は補完的（頑強性を調べるため）

Implementaion for solving 108 TSP within 1% of optimum Geometric data structure Bucket Delaunay Triangulation K-d tree Tour data structure Array Two-level Tree Segment Tree Splay Tree for solving 108 TSP within 1% of optimum

実験的解析の結果 Karp’s Percent Excess over OPT(I) 30% Bucket Insertion 25% Nearest Neighbor Christofides’ 15% Greedy 2-opt 5% SA,GA Tabu Search 3% 3-opt 2% Lin-Kernighan Iterated-LK 1% 0% n nlogn Running　Time

メタヒューリスティクスって何? 自由な発想から生まれた（他分野からのアイディアをもとにした）ものが多い 計算機資源をやたらと食う 時間をかければ良好な近似解が得られる場合が多い（保証はあまりない） 作り手によって性能が大きく変わる 理論的な評価がしずらい Sexyな名前がついている（場合が多い） 改善法（local search）とよばれる古典的な方法をベース（もしくはサブルーチン）にする場合が多い

組合せ最適化問題(概念図) 大域的最適解 目的関数 f(x) 実行可能解の集合 F

山頂を目指す闇夜の登山者 ｘ 近傍 N(x)

2-opt,3-opt neighborhood

Local Search

闇夜の登山者(ここが山頂?) 局所最適解

Lin-Kernigan opt (=3-opt + Depth-first Tabu Search using 2-opt neighborhood)

LK Search (Depth-first Tabu Search using 2-opt neighborhood)

LK Search (Depth-first Tabu Search using 2-opt neighborhood)

2-opt,3-opt,k-opt (Worst Case Results) Running Time : ∃I PLS-complete ∃I A k-opt(I) OPT(I) A 2-opt(I) A 3-opt(I) A 2,3,k-opt(I) OPT(I) ∀I

Simulated Annealing 法 （模擬焼きなまし法） 温度Ｔが高い 温度 T＝0 徐々に冷却

Simulated Annealing法 低温期 高温期 徐々に冷却

温度による受理確率の変化 受理確率 1 高温 低温 Δ=f(y)-f(x) 目的関数値の変化量

Genetic Algorithm (遺伝的アルゴリズム) 遺伝（ダーウインの進化論）にアナロジーをもつ． 複数の実行可能解（集団:population）を保持する点が特徴． 新たな集団を生成するために，交叉(crossover)および突然変異(mutation)と呼ばれる操作を用いる．

交叉と突然変異 交叉(crossover) 親世代 子孫 突然変異 (mutation)

Tabu Search (禁断探索法) 人間の記憶過程にアナロジーを持つ． 別名 最急上昇・最緩下降法 (steepest ascent mildest descent method) 適応型記憶計画(adaptive memory programming) 同じ場所を巡回しないように，記憶を頼りに，常に最も高い方向(下りの場合は最も勾配の緩やかな方向)を目指す．

Tabu Search(概念図） |TL|=2

Tabu Search　1 に戻らないように 一番高い地点へ移動しよう！

Tabu Search　2 |TL|=2

Tabu Search　3 |TL|=2 FIFO

Tabu Search　4

Tabu Search 5

Tabu Search 6

Tabu Search 7

Tabu Search 8

Tabu Search 9

Tabu Search 10

アルゴリズム工学の将来 異分野との積極的な情報交換 自由な発想による新しい研究体系の受け入れ 理論，応用，実務との間の橋渡し 実際問題，応用，アルゴリズムのアイディア 自由な発想による新しい研究体系の受け入れ 理論，応用，実務との間の橋渡し