多軌道型タブサーチ

カテゴリ: 全国大会

論文No: 3-034

グループ名: 【全国大会】平成14年電気学会全国大会論文集

発行日: 2002/03/26

タイトル(英語): Multi-Trajectory Tabu Search

著者名: 金澤 貴彦(東京都立大学),安田 恵一郎(東京都立大学)

著者名(英語): Takahiko Kanazawa(Tokyo Metropolitan University),Keiichiro Yasuda(Tokyo Metropolitan University)

キーワード: 組合せ最適化問題|巡回セールスマン問題|タブサーチ|多点探索

要約(日本語): 最適化問題は，解を全て調べ尽くすことによって大域的最適性を厳密に証明することは可能であるが，実際には計算量の面からみて現実的な選択とはいえない。また，NP困難性が証明されているような問題に対して厳密な大域的最適解を現実的な時間内に求めることは，今後の飛躍的なコンピュータの性能向上を考慮してもほとんど絶望的であることが知られている。本研究では現在メタヒューリスティクス手法の中でも最も高速かつ高い探索能力を持つといわれるタブサーチを用い，タブサーチの性質を数値実験によって検証し，その問題点について考察する。そしてその問題点を解決するアルゴリズムとして，各探索軌道間に弱い相互作用を導入した多軌道型タブサーチを提案し，その有効性を従来のタブサーチと比較した数値実験で検証する。

原稿種別: 日本語

PDFファイルサイズ: 275 Kバイト