最適化アルゴリズムの動向 ーメタヒューリスティックスを中心としてー （基礎編）

Presentation on theme: "最適化アルゴリズムの動向 ーメタヒューリスティックスを中心としてー （基礎編）"— Presentation transcript:

1 最適化アルゴリズムの動向 ーメタヒューリスティックスを中心としてー （基礎編）
東京商船大学 流通情報工学 久保　幹雄

2 メニュー（基礎編） 組合せ最適化問題 近傍の概念 Local Searchとその変形 Simulated Annealingとその変形
Genetic Algorithm Tabu Search Quicker

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

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

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

6 メタヒューリスティックとは 定義（その２） 定義（その３） 流行物（なんらかのアナロジーをもつ）
Simulated Annealing法 (焼きなまし現象) Tabu Search （脳の思考） Genetic Algorithm （遺伝） 定義（その３） パラメータを変えることによって様々な近似解法になる ‘any time’ アルゴリズム KnuthのMETAFONTの精神

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

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

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

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

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

12 一機械総納期遅れスケジューリング問題近傍グラフ
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29 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

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

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

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

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

34 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 )

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

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

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

38 トンネル法

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

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

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

42 Tabu Search　2 |TL|=2

43 Tabu Search　3 |TL|=2 FIFO

44 Tabu Search　4

45 Tabu Search 5

46 Tabu Search 6

47 Tabu Search 7

48 Tabu Search 8

49 Tabu Search 9

50 Tabu Search 10

51 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に記憶し，最も古い要素を忘れる．

52 属性 attribute 乗り物 植物

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

54 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

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

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

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

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

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

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

61 Quicker 解を過去の履歴も含めたk組に拡張(Tabu Searchの概念の利用)
重複要素なし, 突然変異なしの Genetic Algorithm 突然変異のかわりに履歴をもたない解を　ランダムに生成する 棄却なし(rejection free)かつ対数冷却のSimulated Annealing

62 Quicker Simulated Annealing 漸近的最適性 多様化 Tabu Search 拡張された解 履歴をもたない解
最良解との距離を ペナルティとする 多様化 拡張された解 Tabu Search 複数の解をもつ Genetic Algorithm

63 より詳しい情報は．．． 室田一雄編 離散構造とアルゴリズムIV （近代科学社） 第５章　メタヒューリスティックス をご参照下さい．