Keal H. Sahn A R. Crc: A dual teperature sulated annealng approach for solvng blevel prograng probles Coputers and Checal Engneerng Vol. 23 pp. 11-251998. 第 12 回論文ゼミ 2013/07/12( 金 ) #4 M1 今泉孝章
2 段階計画問題とは 2 段階計画問題 (BLPP: Blevel Prograng Probles) 最適化問題の制約条件に別の最適化問題が含まれている問題 例 ) 上位問題 (an proble outer proble など ) a a 1 2 3 制約条件 0 8 1 1 2 2 下位問題 (sub proble nner proble など ) 制約条件 4 16 2 1 2 8 3 22 2 32 0 1 4 1 1 12 48
2 段階計画問題とは 2 段階計画問題 (BLPP: Blevel Prograng Probles) 最適化問題の制約条件に別の最適化問題が含まれている問題一般化 上位問題 (an proble outer proble など ) a F 制約条件 G 0 H 0 下位問題 (sub proble nner proble など ) a f 制約条件 g 0 h 0 不等式制約等式制約不等式制約等式制約 NP hard の問題で現在までに様々なアプローチがなされてきたが離散 非線形非凸な問題を扱えないなど手法ごとに扱える問題の種類に制限があった あらゆる種類の問題の近似解を得るための手法を提案
Sulated Annealng 模擬焼きなまし法 (Sulated Annealng Method) ランダム性を用いて局所最適解からの脱出を試みる手法 初期解 f () 局所最適解から抜け出すために確率的に解の改悪を許す : 現在の解 : の近傍 f N f T: 温度パラメータ 0 確率 ep T で改悪を許す
Sulated Annealng 1 1 : 適当な実行可能解 2 for k 1 to do 3 を N k からランダムに選択 4 確率 ep f f k T k で : k 1 ( を受理 ) 5 それ以外のときは ( を棄却 ) : k 1 k BLPP は制約条件が厳しい 適当な実行可能解や近傍 N k を選択するのが難しい 制約条件を満たす集合をあらかじめ生成しておく
集合の定義 Y g h 下位問題の変数 例 ) 1 : 1 4 についての実行可能領域 0 * * : f f 下位問題の任意の例 ) 1 1 f 2 2 についての解の集合 下位問題の解の候補 6 2 2 0 6 f f をパラメータ Tn を使って緩和した集合 2 4 2
集合の定義 : G H 上位問題の実行可能領域 上位問題と下位問題の両方共通の実行可能領域 BLPP 全体の実行可能領域 BLPP 全体の解実行可能解 ( 上位 下位問題の両方の制約を満たす解 ) の領域 0 T n 全体 を次々とつくりだし探索を行う 近傍を実行制約範囲内につくりだして解の検証を行う
初期実行可能解の生成 ( ) k w u t s r n 制約条件 r G 0 t s H k k u g 0 w h 0 k w u t s r 制約条件に対応するスラック変数この問題の解が 0 k w u t s r のとき元の制約条件と同じ 実行可能解が存在それ以外のとき 実行可能解はない 結局適当な初期値を与えてそれが実行可能解かどうか確かめている?
と の要素の生成 ( 実行可能解の生成 ) I D I : 独立変数 D : 従属変数 : 等式制約 と分解して考える 0 0 I I ar I h : 現在の独立変数 a : 初期値 1のスカラー変数 r : -1 から1の値をとるランダム変数 h I 0 If が満たされている をに入れる else を 1/2 する. 5 回を更新したらをランダムに生成し同じ試行を繰り返す D を解くことで得る このときはどうしているのか? 具体的に与えているのか? g g I 0 a a r における D も同じ手順で生成する
の要素の生成 ( 下位問題の解の生成 ) f f f f and f f T 中の要素を用いる. f or マルコフ連鎖に追加する ( 解を受理する ) : 0 から 1 の値をとる乱数 このときはどうしているのか? 具体的に与えているのか? n
の要素の生成 (BLPPの解の生成) 中の要素 を用いる M f F * F 中の要素 と を合わせると 各について長さのマルコフ連鎖の要素を用いて * を計算し最小値をとる を とし f or * F * and F F F マルコフ連鎖に追加する ( 解を受理する ) ここでもし受理された解が に含まれていなければ a を2 倍し 5 回 a を更新したらをランダムに発生させ同じ試行を繰り返す r T 全体 out M
初期温度との生成 T out について長さのマルコフ連鎖を生成し連続する2 点の関数の差の最大値をとする. a f F 受理確率が95% 程度になるように初期解を設定する L L T ln 0.95a 得られた初期解によって下位問題 1 回につき何回上位問題を解くのか決定する K a 2 log T out T new K 1 下位問題一回につき回上位問題を解く ( 上位問題 下位問題 ). T out T new が大きければ下位問題が局所最適解のところで停滞するのを. 避けることができる
冷却スケジュールと終了判定 上位下位のそれぞれの最適化において T new T 1 ln 1 T 3 L 1 のマルコフ連鎖がつくられたら温度を更新 : パラメータ : マルコフ連鎖における目的関数の標準偏差 終了判定 上位下位それぞれにおいて得られた解と前の解のユークリッドノルムが err out out T err n n n T out より小さくなる
全体フロー 初期値の設定 n r s t u k w T 0.95a 初期化 ln K a 2 log T out T new 下位問題の最適化? いいえ はい 長さのマルコフ連鎖を生成 ( 解の探索 ) 長さのマルコフ連鎖を長さのマルコフ連鎖の要素を使って生成 ( 解の探索 ) L L M 最適化 T の更新の更新 n T out T new T ln 1 T 1 3 1 いいえ 収束判定 T err out out out T err n n n 収束判定
初期化フェイズアルゴリズム ステップ 1: スタートポイント生成 (ⅲ) f f t t (ⅳ) dela a dela f f n r s t u w からスタートポイント を生成 ステップ 2: 温度の初期化 (a) パラメータ を決定し count 1 (b) For 1... L do the followng (c) (d) (ⅰ) dela (ⅱ) 生成手順によりを生成 k t t ln 0. 95 dela を最適化ステップの初期値として保持 を とする out out n n (e) For 1... L do the followng (ⅰ) dela (ⅱ) 生成手順によりを生成 (ⅲ) F F (ⅳ) dela (f) T out ln 0. 95dela (g) K a 2 logt out は初期値? 最後の? 上位問題にも同じのを与えていいのか? t t t t a dela F F
最適化フェイズアルゴリズム ステップ3: 温度 Tでの最適化 (a) f count od K 0 (b) へ (c) へ else (b) 上位問題最適化 (ⅰ) For 1... L (A) (B) do the 生成手順によりを生成 If F F or followng t t ran# F F t t n opt F F t t n opt F 2 F out T とし 受理されなければ 0 (ⅱ)0でないの分散を求める 1 (ⅲ) new ln1 T を計算する T out T out 1 3 (ⅳ) count count 1 (b) 下位問題最適化 (ⅰ) For 1... L do the followng (A) 生成手順により t t を生成 (B) If f f or ran# f f t t n opt f f t t n opt T とし 受理されなければ f 0 2 (ⅱ)0でない f の分散 n を求める 1 (ⅲ) new ln1 T を計算する T n T n 1 3 (ⅳ) count count 1 n
最適化フェイズフロー それぞれにランダム変数 r を発生させる カウント変数初期化 z 1 p 1 r r t t 上位問題最適化? はい長さ M のマルコフ連鎖を使って下位問題の最適解を探索 内の点か? 制約は破られたかはい z a a / 2 z z 1 関数の値の評価を行いマルコフ連鎖の次の点へ z 5? いいえ はい はい a p a* 2 p p 1 p 5? いいえ
収束判定フェイズアルゴリズム ステップ4: 収束判定 (a) f count 1 od K 0 (b) へ (c) へ else (b) 上位問題 (ⅰ) T err out out out (ⅱ) ( 最新の最良解に更新 ) out とする (d) If 終了 checkn true and else optcheck false outcheck true ステップ 3 へ (ⅲ) If err out outcheck true ncheck false nn f (c) 下位問題 (ⅰ) T err n n n (ⅱ) ( 最新の最良解に更新 ) n (ⅲ) If err n or f ncheck true nn ( 下位問題の値が十分小さくなるか上位問題における下位問題最適化の結果と一致すれば )
収束判定フェイズフロー 上位問題最適化? はい err out を計算する err n を計算する err out? はい Outcheck true err n? いいえ はい いいえ Outcheck false OutCheck true? はい 計算を終了 K によって上位 下位どちらを最適化するか決定し計算を継続
イメージ 上位問題 下位問題の最適解である可能性のある点について SA を行っている 下位問題 下位問題の実行可能領域の点について SA を行っている 十分な回数探索を行えば上位問題における下位問題の解と下位問題の解が近づいていき近似解に辿りつく 全体
DTSA の検証 上位問題制約条件下位問題制約条件 a 2 5 0 1 10 3 2 2 3 1 2 2 2 1 2 42 1 2 2 1 2 1 2 2 1 1 0 2 10 2 3 3 2 2 8 14 5 5 4 1 8 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1 1 1 1 01 1 2 1 2 2 2 初期解 大域解への収束率 (%) 平均 CPU(s) 大域解への平均距離 (1.01.01.1) 80 0.75 0.14 (5.05.05.0) 80 0.75 0.04 (9.09.01.0) 80 0.89 0.09