メタヒューリスティクス 東京海洋大 久保　幹雄 http://www.e.kaiyodai.ac.jp/~kubo/

Presentation on theme: "メタヒューリスティクス 東京海洋大 久保　幹雄 http://www.e.kaiyodai.ac.jp/~kubo/"— Presentation transcript:

1 メタヒューリスティクス 東京海洋大 久保　幹雄

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

3 組合せ最適化問題 F = 実行可能解の集合（有限） f: F → R (Z) (目的関数) 最大化 or 最小化 f(x) 条件 x ∈ F
(大域的)最適解（の集合） F* ={ x∈F: f(x)≧f(y), ∀y∈F }

4 メタヒューリスティクスとは 別名 定義（その１） メタ戦略，メタ解法，モダンヒューリスティクス ヒューリスティクスを有機的に結合
近似解法（理論的な保証をもつ） ヒューリスティクス（保証をもたない）

5 メタヒューリスティクスとは 定義（その２） 定義（その３） 流行物（なんらかのアナロジーをもつ）
Simulated Annealing法 (焼きなまし現象) Tabu Search （脳の思考） Genetic Algorithm （遺伝） 定義（その３） パラメータを変えることによって様々な近似解法になる ‘any time’ アルゴリズム （停止条件をユーザーが定め，時間をかければかける程良い解を探索する．

6 近傍と局所最適解（概念図） 局所最適解 近傍 N(x) 実行可能解ｘ

7 N: F → 2 F 近傍の定義 局所最適解の集合 { x∈F: f(x)≧f(y), ∀y ∈ N(x) }

8 簡単な例 一機械総納期遅れスケジューリング問題
ジョブの集合 {1,2,3,4} ジョブ i 処理時間 pi 納期 di 実行可能解の集合 {1,2,3,4}から構成される4!個の順列

9 目的関数 一機械総納期遅れスケジューリング問題
目的関数　納期遅れ時間の合計（最小化） =6 実行可能解（順列） 1234 の目的関数 J4の納期 J3の納期 J1の納期 J2の納期 J1 J2 J3 J4 6

10 近傍 一機械総納期遅れスケジューリング問題
近傍　隣接するジョブを交換 実行可能解 の近傍

11 一機械総納期遅れスケジューリング問題近傍グラフ
1234 点は解に対応 2134 6 6 目的関数値 1243 7 1324 7 7 6 5 6 5 8 7 4 10 4 5 6 10 8 3 7 8 5

12 Local Search （局所探索法，改善法）

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

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

15 Local Search Local Search x := 適当な初期実行可能解 while 改良(x) ≠ {} do
改良(x)= {y∈ N(x):f(y)＞f(x) } Local Search x := 適当な初期実行可能解 while 改良(x) ≠ {} do x := 改良(x)の中の適当な要素

16 Local Searchの探索経路 近傍グラフの枝 {(x,y): f(x)>f(y)}

17 Local Searchの探索経路 目的関数（最小化）

18 Multiple Start Local Search （多出発局所探索法）

19 Multiple Start Local Search （多出発局所探索法）
while 終了判定基準 ≠ yes do x := 適当な初期実行可能解 while 改良(x) ≠ {} do x := 改良(x)の中の適当な要素 集中化・多様化を組み込む 良いメタ解法のための定石

20 集中化と多様化 集中化(intensification) 多様化(diversification)
良い解に近いところには良い解が存在するという性質(proximate optimality property)を信じて，良い解の回りを集中的に探索すること． 多様化(diversification) 悪い解のまわりで探索が停滞することを避けるために，今までに探索していない解を強制的に探索させること．

21 集中化 intensification この辺は良い解が多いから もう少し探してみるか

22 多様化 diversification この辺はさんざん探したので， そろそろ違う場所を探しに行くか

23 GRASP (Greedy Randomized Adaptive Search Procedure)
集中化 多様化 φ

24 Iterated Local Search （反復局所探索法）
集中化 拡張された近傍 多様化

25 Iterated Local Search （反復局所探索法）
x := 適当な初期実行可能解 while 終了判定基準 ≠ yes do while 改良(x) ≠ {} do x := 改良(x)の中の適当な要素 x:= 拡張された近傍 N'(x)の中の適当な要素

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

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

28 Simulated Annealing法 温度 T1≧T2≧ … ≧T∞ =0 x1 := 適当な初期実行可能解
for k=1 to ∞ do y := N(x)のランダムな要素 Δ = min. { f(y)-f(xk),0} 確率 exp {Δ/Tk}で xk+1 :=y (受理) それ以外なら xk+1 :=xk (棄却) 温度 T1≧T2≧ … ≧T∞ =0

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

30 冷却法 対数冷却法 (logarithmic cooling) Tk = T1/log2 (1+k)
幾何学的冷却法 (geometric cooling) 一定温度で 近傍の大きさ×定数(16が推奨値)回繰り返す その後で T := T × 定数(0.95が推奨値)倍する．

31 Simulated Annealing法の 弱点
探索した解の情報をもたないので，同じ解を何度も探索してしまう． それゆえ盲目の探索法(blind search)と呼ばれる． ランダム性のみに頼っているので，小高い丘から脱出できない場合が多い． 収束が遅い．(特に最終段階で空回りする．）

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

33 Genetic Algorithm P(0) :=初期解の集合 for t=0 to T do Y:=生成( P(t) )
生成(X) =集団 X から交叉または突然変異によって生成された新しい集団． 選択(X) =集団 X から優秀な子孫のみを残すこと(自然淘汰)によって選ばれた集団． Genetic Algorithm P(0) :=初期解の集合 for t=0 to T do Y:=生成( P(t) ) P(t+1) := 選択( Y )

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

35 Genetic Algorithmの弱点 集中化が取入れられていない． 未成熟な収束(premature convergence)
Local Searchを組み込む 未成熟な収束(premature convergence) 探索を多様化させる工夫の導入が必要． 交叉・突然変異は実行可能解を生成しにくい． パス接続法，トンネル法

36 パス接続法 複数の解から新たな実行可能解を生成する操作

37 トンネル法

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

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

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

41 Tabu Search　2 |TL|=2

42 Tabu Search　3 |TL|=2 FIFO

43 Tabu Search　4

44 Tabu Search 5

45 Tabu Search 6

46 Tabu Search 7

47 Tabu Search 8

48 Tabu Search 9

49 Tabu Search 10

50 Tabu Search x := 適当な初期実行可能解 while 終了判定基準≠ yes do x := Best(x)
TL (Tabu List): 禁断リスト 同じ解に戻らないように記憶された解の集合． 古い情報は新しいもので上書きされるので，短期メモリ(short term memory)とも呼ばれる． Best(x)= arg max.{f(y): y∈ N(x)-TL} x := 適当な初期実行可能解 while 終了判定基準≠ yes do x := Best(x) xをTLに記憶し，最も古い要素を忘れる．

51 属性 attribute 乗り物 植物

52 属性 attribute TLに保存する「もの」． 解自身を保存するのではなく，解の変化を表す何らかの目印を属性とする．
　　Tabu Searchの曖昧さの一因 提案 問題の構造を決めるなるべく小さい集合をとる

53 Tabu Searchの探索経路 1 初期解 1234 6 1243 6 7 1234 1243 7 7 6 5 6 5 8 7 4 10 3と4を交換する全ての 動きを封じる 4 5 10 6 10 8 3 7 8 5

54 Tabu Searchの探索経路 2 6 7 7 8 7 10 10 6 10 8 8 6

55 Tabu Searchの探索経路 3 6 7 8 10 6 8 6

56 Tabu Searchの探索経路 4 6 6 7 |TL|=３なので 枝が復活 8 4 10 6 8 3 5

57 Tabu Searchの探索経路 5 6 6 7 8 4 6 8 3 5

58 長期メモリ FIFO 短期メモリ ＴＬ ×３ 多様化

59 禁断リストクリア（再出発）

60 Snapshot of Guided Local Search (2)

61 Snapshot of Guided Local Search (3)

62 Guided Local Search (GLS)
Penalty (≒long term memory) p: U → R Modified Cost Function g(x)=Σu∈x c(u) + λΣu∈x p(u) GLS　（ｘ） 1 p(u) := 0 (∀ u ∈U) 2 while STOP ≠ TRUE do x := LS (x, g) u* := arg max u∈x c(u)/(p(u)+1) p(u*) :=p(u*)+1

63 適用例 二次割当 グラフ分割 巡回セールスマン 最大クリーク グラフ彩色 ジョブショップスジューリング 運搬経路 N-Queen

64 二次割当問題 3回 5km 2km 2回 1回 1km 移動量行列 (Fij) (週に何回遊びに行くか) 距離行列 (Dij)

65 二次割当問題 2回 5km 2km 1回 1km 3回 2×5＋2×1＋1×3＝15km 順列π

66 二次割当問題 V={1,2,…,n}, n×n 行列(Fij),(Dij)が与えられたとき，Ｖ上の順列πで Σi,j Fij Dπ(i)π(j)を最小にするものを求める問題． 応用 工場，レイアウト設計，キーボードの 配列，自己テスト可能な回路，回路配線 問題集(QAPLIB)あり．

67 二次割当問題の近傍 (swap近傍) 3回 1回 2回 2km 5km 1km 2×5＋2×1＋1×3＝15km 3回 1回 2回 2km

68 二次割当問題の属性 人と家のペア 交換した人のペア

69 なぜペア属性が悪いか 禁止リストの 長さによらず 巡回が発生する！

70 人と家のペアにする理由 数理計画による自然な定式化 変数 Xij = 人iが家jに割り当てられたとき １ それ以外 ０
それ以外 ０ min. ΣΣ Fij Dkl Xik Xjl s.t. Σ Xij = 1 for all i Σ Xij = 1 for all j Xij : 0 or 1

71 グラフ分割問題 半分に分けたい! 仲良し！

72 グラフ分割問題 目的関数値＝２

73 グラフ分割問題 無向グラフ G=(V,E)が与えられたとき，|L|=|R|を満たすVの分割(L,R)で，LとRの間の枝の本数を最小にするものを求める問題． 応用 VLSI 設計, プログラム分割 JohnsonらがSimulated Annealing法の実験のために採用した第１の問題．

74 グラフ分割問題に対する近傍 (swap近傍)

75 交叉の例 グラフ分割問題に対する単性生殖交叉 Ａ1 Ｂ1 Ａ2 Ｂ2 Ａ1 Ｂ1 Ａ2 Ｂ2

76 通常の解の表現の弱点 実行可能解のみ を探索する

77 擬似実行可能解 （グラフ分割問題） 各グループ内の人数が 多少は違ってもよい！

78 擬似実行可能解上の近傍 （グラフ分割問題）

79 ペナルティ関数法 実行可能 目的関数

80 ペナルティ関数法(失敗例) 実行可能 目的関数

81 擬似実行可能解探索法 擬似実行可能解の集合 実行可能解の集合 F

82 戦略的振動 strategic oscillation

83 巡回セールスマン問題 Aberdeen Edinburgh Belfast Liverpool Dublin Cardiff London

84 巡回セールスマン問題 Aberdeen Edinburgh Belfast Liverpool Dublin Cardiff London

85 巡回セールスマン問題 グラフ G=(V,E), E上の重み関数 d が与えられたとき重みの合計が最小のHamilton閉路を求める問題．
応用 基盤配線，配送計画，スケジューリング，基盤穿孔，Ｘ線構造解析実験，タンパク質構造解析，ＤＮA 並べ替え，ＶＬＳＩ設計, etc. 問題集(TSPLIB)あり．

86 近傍の例 (2-opt) a c d b |ac|＜|ab|を満たすcに限定する！

87 Local Search (2-opt) Aberdeen Edinburgh Belfast Liverpool Dublin
Cardiff London

88 Local Search (2-opt) Aberdeen Edinburgh Belfast Liverpool Dublin
Cardiff London

89 近傍の例 (3-opt)

90 近傍の例 (挿入-opt)

91 交叉の例 巡回セールスマン問題に対する挿入-optの利用 親世代 子孫

92 擬似実行可能解上での近傍 （巡回セールスマン問題）

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

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

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

96 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

97 最大クリーク問題 なるべく大人数でピクニックに行きたい！ 仲良し！

98 最大クリーク問題

99 最大クリーク問題 (最大安定集合問題) 応用 1993年度DIMACSチャレンジ問題の一つ
無向グラフ G=(V,E)が与えられたとき，最大位数の安定集合 S (Vの部分集合で間に枝のないもの)を求める問題． 応用 プリント基板テスト，パターンマッチング，符号理論，考古学および生物学のデータ解析，グラフ彩色問題の近似アルゴリズムおよび下界，多面体論(Kellerの予想)，故障診断，etc. 1993年度DIMACSチャレンジ問題の一つ

100 最大安定集合問題 仲が悪い！

101 擬似実行可能解 （最大クリーク問題） 仲が悪い！

102 擬似実行可能解上の近傍 （最大クリーク問題）
Drop Add

103 グラフ彩色問題 ・・・ クラス分けしたい！ 仲が悪い!

104 グラフ彩色問題

105 グラフ彩色問題 無向グラフG=(V,E)が与えられたとき，Vの安定集合への分割で分割数最小のものを求める問題． 応用
時間割作成，スケジューリング，周波数割当，レジスタ配分，プリント基板テスト，パターンマッチグ． 1993年度DIMACSチャレンジ問題の一つ Johnsonらの実験的解析の第2の問題

106 ４色問題 色数が少ない問題は 最適化問題としては 簡単！

107 グラフ彩色問題の近傍 1 悪い枝！

108 グラフ彩色問題の近傍 2 （Kempe Chain近傍）

109 ジョブショップスケジューリンング問題 仕事 作業 機械 ５分 ３分 ８分 ７分 ２分 ６分 ４分

110 離接グラフ表現 有向枝 離接枝 開始 終了

111 解＝離接枝に向きをつける 5 5 3 8 7 2 6 3 9 5

112 クリティカルパス（最長路） 5 5 3 8 7 2 6 3 9 5

113 （制限付き）離接枝反転近傍 5 6 8 3 2 9 7 5 6 8 3 2 9 7 5 6 8 3 2 9 7 を反転させる クリティカルパス上の離接枝

114 ジョブショップスケジューリンング問題 離接グラフ上で最長路の長さが最小になるように離接枝に向きをつける問題．
数あるスケジューリング問題の中でも最も悪名が高い． 実際問題に近い（らしい） 問題集あり（OR-Libから得られる）

115 運搬経路問題 5t ルート 3t 6t 6t 5t 5t デポ 4t 3t 5t 2t 20t 10t 運搬車の容量 顧客(需要点)

116 運搬経路問題の近傍 (1,1)-opt 青いルートには 属性 当分戻らない！ デポ デポ
(p,q)-opt: 二つのルートからp，q人ずつの顧客を交換

117 Neighborhood for VRP with Time Window Constraints
Or-opt neighborhood Cross-opt neighborhood

118 Evaluation of a Neighbor
… … Path P =(p1,p2,…,pk) Path Q =(q1,q2,…,qh) By keeping 1. Total Time, TT(P) 2. Earliest Departure Time of pk, Departure(P) 3. Latest Arrival Time of p1, Latest_Arrival(P), the neighborhood can be evaluated in O(1) time (if an appropriate search sequence is used). Furthermore, TT(P+Q), Departure(P+Q) , Latest_Arrival(P+Q) can be computed in O(1) time.

119 N-クイーン問題

120 pi[i] Position of the i-th queen

121 select randomly from [1..m]
int Random_Position(int i) // find a random position randomly (it may fail) {int t, k, index; int mode=0; for(t=1;t<=theta;t++){ // try θ times …O(1) expected time index = (int)(rand() * m) + 1; k =feasible[index]; if(b[i+k-1] == 0 && c[n-i+k] == 0){ pi[i] = k; b[i+k-1]++; c[n-i+k]++; feasible[index]=feasible[m--]; mode=1; break; 　　　　　　} } return mode;} feasible[1..n] 1 2 3 4 5 m index select randomly from [1..m] If it’s safe, set queen of i-th row to column k 1 2 5 4 m

122 A simple construction algorithm using Random_Position
void Construct() for(i=1;i<=n;i++){ mode =0; mode = Random_Position(i); if(mode==0) // if Random_Position fails Greedy(i); }

123 int Safety_Position(int i) {int k, j, count=0;
for(k=1;k<=m;k++){ j = feasible[k]; if(b[i+j-1] == 0 && c[n-i+j] == 0){ temp[++count] = j; position[count] = k;　}} return count; }

124 Greedy algorithm … O(n) in the worst case
but it usually called in the last few iterations of the construction phase void Greedy(int i) {int temp_number, k, index, index2; temp_number = Feasible_Position(i); if (temp_number==0){ index = (int)(rand() *m) +1; k = feasible[index]; } else { 　　　　　　 index2 = (int)(rand() *temp_number)+1; k = temp[index2]; index = position[index2]; } feasible[index]=feasible[m--]; pi[i]=k; b[i+k-1]++; c[n-i+k]++;

125 Subroutine for tabu seach: find a bad (dangerous queen)
…search from the last row to the first row int Find_Dangerous_Queen() {int i, j, dangerous_queen=0; for(i=n;i>0;i--){ j=pi[i]; if( (b[i+j-1]+c[n-i+j]) >2){ dangerous_queen=i; break; } return dangerous_queen;}

126 Find the best queen for a dangerous queen to be swapped
int Find_Swap_Queen(int istar) {int i, j, k, k2, swap_queen=0, max=-9999, tmp; for(j=1;j<=n;j++){ if(tabu[j]) continue; // if j is not tabu k = pi[j]; k2 = pi[istar]; tmp= b[k2+istar-1]+c[n-istar+k2]+b[k+j-1]+c[n-j+k] -b[k2+j-1]-c[n-j+k2]-b[k+istar-1]-c[n-istar+k]; if(tmp>=max){ //find a maximum improvement max = tmp; swap_queen = j; } return swap_queen;

127 void Tabu_Search() {int istar, jstar; while(1){ istar=Find_Dangerous_Queen(); if(!istar) break; // if istar=0,all the queens are safe; exit jstar=Find_Swap_Queen(istar); if(jstar==0){ // if no candidate to be swapped, tabu list is cleared for(i=1;i<=n;i++) tabu[i]=0; continue; } Update(istar, jstar); for(i=1;i<=n;i++) if(tabu[i]) tabu[i]--; tabu[istar] = tabu[jstar] = TL; //set istar and jstar to be tabu for TL iterations

128 参考図書 １　 組合せ最適化のおへそである 巡回セールスマン問題を 対話形式で解説した本

129 参考図書 ２ 組合せ最適化問題をテーマに したお笑い短編集 プログラミングや メタヒューリスティクスの入門
N-Queenの記録 5000万クイーン の開発