著者

柳浦 睦憲 茨木 俊秀

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.83, no.1, pp.3-25, 2000-01-25

被引用文献数

35

---

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