相関係数を用いた近接最適性の評価に基づく組合せ最適化手法

カテゴリ: 全国大会

論文No: 3-061

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

発行日: 2015/03/05

タイトル(英語): Combinatorial Optimization Method Based on Evaluation of Proximate Optimality Using Correlation Coefficient

著者名: 森田 真英(首都大学東京),落合 広樹(東日本旅客鉄道),田村 健一(首都大学東京),安田 恵一郎(首都大学東京)

著者名(英語): Masahide Morita(Tokyo Metropolitan University),Hiroki Ochiai(East Japan Railway Company),Kenichi Tamura(Tokyo Metropolitan University),Keiichiro Yasuda(Tokyo Metropolitan University)

キーワード: 組合せ最適化|メタヒューリスティクス|近接最適性原理|相関係数

要約(日本語): 近年，実用的な組合せ最適化手法としてTabu Searchをはじめとするメタヒューリスティクスが注目されている。組合せ最適化における効率的な探索の実現には，解空間の性質の把握・活用が重要となる。代表的な解空間の性質として近接最適性原理（POP）があり，多くの組合せ最適化問題において成り立つことが経験的に知られている。本稿では，POPに関して新たな解釈をし，この解釈に基づく解空間の性質を近接最適性と表現し，定量的に評価する。さらに，アルゴリズム構築指針を提案し，近接最適性の評価を活用した新たな組合せ最適化手法を構築する。最後に，代表的なベンチマーク問題を用いて数値実験を行い，提案手法の有用性を検証する。

原稿種別: 日本語

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