組合せ最適化における近接最適性原理の検証と応用

カテゴリ: 部門大会

論文No: GS5-1

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

発行日: 2013/09/04

タイトル(英語): Verification and Application of Proximate Optimality Principle in Combinatorial Optimization

著者名: 落合 広樹(首都大学東京),田村 健一(首都大学東京),安田 恵一郎(首都大学東京)

著者名(英語): Hiroki Ochiai(Tokyo Metropolitan University),Kenichi Tamura(Tokyo Metropolitan University),Keiichiro Yasuda(Tokyo Metropolitan University)

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

要約(日本語): 本稿では，組合せ最適化問題における近接最適性原理の成立について数値実験的検証を行った。そして，近接最適性原理に基づく最適化手法の戦略を提案した。
近年のシステムの大規模化・複雑化に伴い，探索性能と汎用性を兼ね備えた最適化手法の構築は重要な課題となっている。メタヒューリスティクスは実用性の高い最適化手法の枠組みとして期待されており，探索の構造を解析してみると，多くの手法が近接最適性原理を根幹としていると考えられる。近接最適性原理は，“良い解同士は似通った構造を持っている”という漠然とした原理であり多くの最適化問題に成り立つことが経験的に知られている。著者らは，組合せ最適化問題の解空間に距離の概念が容易に導入できることを指摘した上で，近接最適性原理の成立を数値実験により確かめた。さらに，導入した距離関数を利用することで近接最適性原理に基づく戦略を提案し，その有用性を検証した。

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