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