大規模組合せ最適化問題に対する複数の近傍を用いた探索手法

カテゴリ: 部門大会

論文No: GS2-4

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

発行日: 2012/09/05

タイトル(英語): A Search Method for Large Scale Combinatorial Optimization Problem by Means of Many Neighborhoods

著者名: 重弘 裕二(大阪工業大学),増田 達也(大阪工業大学)

著者名(英語): Yuji Shigehiro(Osaka Institute of Technology),Tatsuya Masuda(Osaka Institute of Technology)

キーワード: 組合せ最適化|多数の近傍|確率分布確率分布|combinatorial optimization|many neighborhoods|probability distribution

要約(日本語): 本稿では、遺伝的アルゴリズムにおける交叉のような操作を用いず、近傍操作のみを用いて、大規模な組合せ最適化問題に対して効率良く解探索を行う方法について考察する。具体的には、単位近傍操作の反復からなる近傍を用いて探索を行う方法について考える。以下では、近傍解の評価値と元の解の評価値の差を近傍解改善量と呼ぶ。また、近傍解の評価値がその時点の最良解の評価値より優る量を最良解改善量と呼ぶ。本稿では、近傍探索法の枠組みの中で考察を進めるものとするが、従来の手法と異なるのは、複数の近傍操作の中から最も最良解改善量の期待値が大きな近傍操作を選択して適用するという点である。そのために、解探索の過程において近傍操作を行う際、解の評価値や単位近傍操作の反復回数といった情報を収集し、そこから単位近傍操作に関する近傍解改善量の平均と分散を、さらには近傍操作に関する近傍解改善量の平均と分散を推定する。

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