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

柳浦 睦憲  茨木 俊秀  

誌名
電子情報通信学会論文誌 D   Vol.J83-D1   No.1   pp.3-25
発行日: 2000/01/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: サーベイ論文 (情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
専門分野: 
キーワード: 
組合せ最適化,  近似解法,  メタ戦略,  局所探索法,  遺伝アルゴリズム,  アニーリング法,  タブー探索法,  

本文: PDF(469.3KB)>>
論文を購入




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