組合せ最適化問題の特徴を考慮したTabu Searchの探索効率改善

カテゴリ: 部門大会

論文No: MC1-5

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

発行日: 2002/09/02

タイトル(英語): Improvement of Search Efficiency of Tabu Search Considering the Feature of Combinatorial Optimization Problems

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

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

キーワード: 最適化|メタヒューリスティクスProximate Optimality Principle|Proximate Optimality Principle|タブサーチ|Optimization|Meta heuristics|Combinatorial Optimization|Proximate Optimality Principle|Tabu Search

要約(日本語): 本研究ではTabu Searchを基にして，POPを陽に考慮した集中化のメカニズムの強化によって探索能力を改善したアルゴリズムを提案する。Tabu Searchでは解の評価基準として目的関数値のみを用いるが，本研究の提案手法では目的関数値の他に，POPを陽に考慮したオペレーションの評価基準を導入する。これによって大域的な探索において重要な要素である多様化を強化し，探索性能を向上させることを狙いとしている。また，探索過程においてアルゴリズムの振る舞いを適応的に変化させることで集中化と多様化の両立をさせ，さらに探索軌道を多軌道化し，探索の効率化を計った。このアルゴリズムを典型的な組合せ最適化問題に適用し，性能の検証を行った。

PDFファイルサイズ: 4,407 Kバイト