Local Search における近傍に関する基礎検討

カテゴリ: 部門大会

論文No: OS5-5

グループ名: 【C】平成19年電気学会電子・情報・システム部門大会講演論文集

発行日: 2007/09/04

タイトル(英語): A Basics Study on the Neighborhood Structure of Local Search

著者名: 青木 祐太(東京都立大学),安田 恵一郎(首都大学東京)

著者名(英語): Yuta Aoki(Tokyo Metropolitan University),Keiichiro Yasuda(Tokyo Metropolitan University)

キーワード: 局所探索法|近傍|メタヒューリスティクスメタヒューリスティクス|Local Search|Neighborhood|Meta-Heuristics

要約(日本語): 現在の工学における組合せ最適化問題の多くはNP困難な問題として知られており、その有効な手法として、特定の問題に限定されず、どのような問題に対しても汎用的に適用できる、発見的手法であるメタヒューリスティクスが注目を浴びている。しかし、より大規模複雑な問題に対しては、メタヒューリスティクスをもってしても、実用時間内によい解を求めることは難しい。そこで、本研究ではメタヒューリスティクスに代表されるTabu SearchやSimulated Annealingに用いられているLocal Searchの近傍構造に関する検討を行い、大規模複雑な問題に対しても実用時間内によい解が得られるような改良を目指す。

PDFファイルサイズ: 3,477 Kバイト