探索点の分布を考慮した近接最適性の定量的評価に基づく組合せ最適化手法

カテゴリ: 部門大会

論文No: GS4-5

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

発行日: 2014/09/03

タイトル(英語): Combinatorial Optimization Method Based on Quantitative Evaluation of Proximate Optimality Considering Distribution of Search Points

著者名: 森田 真英(首都大学東京),田村 健一(首都大学東京),安田 恵一郎(首都大学東京)

著者名(英語): Masahide Morita(Tokyo Metropolitan University),Kenichi Tamura(Tokyo Metropolitan University),Keiichirou Yasuda(Tokyo Metropolitan University)

キーワード: 組合せ最適化|メタヒューリスティクス|近接最適性原理|集中化|多様化|Combinatorial Optimization|Meta-heuristics|Proximate Optimality Principle|Intensification|Diversification

要約(日本語): 近年，システムの大規模化・複雑化に伴い，高い汎用性と性能を有する最適化手法の開発が重要な課題となっている。また，離散構造を有する実問題の多くは組合せ最適化問題として定式化できる。以上を踏まえ，実用性の高い最適化手法の枠組みとしてメタヒューリスティクスが注目されている。著者らは，メタヒューリスティクスの探索の根幹には近接最適性原理（POP）である考え，POPを効率的に活用することで優れた最適化手法の構築が期待できると考えた。POPは多くの組合せ最適化問題で成立することが知られているが，POPの成立度合いは対象問題や各問題の解空間の領域によって異なることが予想される。本稿では，POPの成立度合いを新たに近接最適性と定義した。そして，探索点の分布を考慮にいれ，探索領域の近接最適性を定量的に評価し，その評価に基づく新たな組合せ最適化手法を提案した。ベンチマーク問題を用いて，性能の比較・検討を行った。

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