Download presentation
Presentation is loading. Please wait.
1
情報基盤アルゴリズムとして のメタヒューリスティクスの 研究 茨木俊秀、巳波弘佳、藤原洋志、 千葉英史、関口良行（関西学院大 学）、 藤重悟（京都大学）、 柳浦睦憲（名古屋大学）、 野々部宏司（法政大学）、 梅谷俊治（電気通信大学）
2
メタヒューリスティクスの枠組 ( 初期解生成） 初期解 x を生成 ( 局所探索） x を ( 一般化 ) 局所探索によって改善。 ( 反復） 終了条件がみたされれば、暫定解を出力 して 終了； さもなければ初期解生成へ戻る。 初期解生成： ランダム。過去の良質解を記憶しておき、 それら を変形。交叉あるいはパス再結合。 終了条件： 計算時間。改善状況の利用。
3
局所探索 (Local Search) 適当な初期解 x (1) から出発 x (i) の近傍 N(x (i) ) 内に改善解が存在すればそれ に置き換えるという操作を、変化が生じなく なるまで反復する
4
局所探索の設計 近傍： サイズと改善能力、問題固有の構 造 の有効利用。 近傍内の探索順序： ランダム、固定順序 。 移動先： 最初の改善解、最良解、改悪解 も許 す。確率的移動（確率のパラメータ調 節）。 目的関数： ペナルティの利用、適応的変 形。 その他： 複数の近傍の利用、近傍サイズ の 組織的制御、タブーリスト。
5
メタヒューリスティクスの実現 タブー探索 アニーリング法 遺伝アルゴリズム 反復局所探索 ・・・
6
箱詰め問題 与えられた n 個の図形（たとえば長方形 ）を重ねずに小さな領域に詰める。 長方形の方向： 固定、９０度回転可能
7
メタヒューリスティクスによる 解法 長方形の相対的位置の指定 順序対その他の方法 良い順序対の探索は局所探索で 近傍の設計 与えられた順序対の下での最適配置 動的計画法、線形計画法、非線形計 画法 などの利用
8
計算例 利用領域の最小化 計算例１ 計算例２ 配置制約下の最小化
9
箱詰め問題（変形１） 長方形のサイズは可変 高さの上下限、幅の上下限 長方形の面積、周長の上下限 ９０度回転：有、なし 領域の高さは指定、幅を最小にする Strip Packing
10
Area minimization
11
箱詰め問題（変形２） 長方形には重さがある すべての長方形を領域に詰める 全体の重心を領域の中心へ置く 重心周りのモーメントを最小にする
13
箱詰め問題（変形３） 一般の形をした n 個の多角形 詰める領域は長方形 多角形の回転角度 : 固定、自由
15
配送計画問題 最小コストの配送計画を求めよ depot 顧客集合 V={1,2,…,n}, 距離行列 D=(d ij ), 負荷量 q i, 車両 M={1,2,…,m}, 容量 Q k, 移動時間行列 T=(t ij ).
16
標準タイプ VRP 問題例 時間枠制約付き問題例 Example 1 ExampleExample 2 計算例
17
一般化、変形、実用化 時間枠制約：単枠、複枠、一般化 所要時間の可変性 集配と配達（ Pickup and delivery ） 応用からのさまざまな制約条件 確率的モデリング
18
NP 困難 手に負えない 少々手ごわい、 しかし何とかなる （ただし近似解） 結論、今後の課題 現実の多くの問題を解決できる可能性 アルゴリズムの開発の困難さ 標準問題による汎用アルゴリズム
Similar presentations
