組合せ最適化問題に対するメタ戦略について

柳浦 睦憲, 茨木 俊秀
アブストラクト
組合せ最適化問題に対する効率的な近似解法の一般的枠組みとして, 近年,遺伝アルゴリズム,アニーリング法,タブー探索法やそれらの変形版など, 様々なアルゴリズムが提案されてきた.これらを総称してメタ戦略 あるいはメタヒューリスティクスと呼んでいる. 本稿では,これらメタ戦略にあらわれる様々なアイディアを, 近似解法の基本戦略である局所探索法の一般化ととらえることで, 体系的にまとめる. メタ戦略の一つの魅力は,その手軽さとロバスト性にある. この観点から,次に,メタ戦略の基本的なアイディアのみで構成した シンプルなアルゴリズムを,計算実験により比較した結果を述べる. これをもとに,手軽なツールとしてのメタ戦略の設計指針を与える. そのあと, より多くの手間をかけても,さらに性能の高いアルゴリズムを構成したい場合に 有効となる,やや複雑なアイディアについても簡単に紹介する. 最後に,メタ戦略の理論的解析の話題にも言及する.

キーワード: 組合せ最適化,近似解法,メタ戦略,局所探索法, 遺伝アルゴリズム,アニーリング法,タブー探索法

電子情報通信学会論文誌, Vol. J83-D-I, No.1, pp. 3-25, Jan. 2000.

PSファイル


論文リストへ