上位M個の解が得られる疎結合モデルの離散最適化手法(一般,複雑系とニューロコンピューティング)

スポンサーリンク

概要

論文の詳細を見る
本研究では一般的な多体疎結合モデルの離散最適化問題(組合せ最適化問題)において,上位M種類の解を効率的かつ厳密に求める手法を提案する.従来手法では最上位の解のみを,また,最上位の解が複数ある場合は,その内の一つのみを求める手法が一般的であったが,本手法では,最上位の解集合(最適解集合),上位2番目の解集合と,上位M番目の解集合までを厳密に求めることができる.また,最適化の目的関数は,複数の任意の離散実数関数の和で表せるような広いクラスを想定した.目的関数の構造が密な結合を持っている場合は,提案手法を適用することは可能だが,全ての解候補を列挙するのに必要な指数的な計算量が必要となるため,メリットがない.また,本手法は予めどの程度の計算量,メモリ消費量が必要となるかを見積もることができる.更に,上位M番目までの解集合の要素数が指数的に増加する場合でも,このこと自体が直接にはトータルの計算量やメモリ消費量が指数的に増加させることにはならない手法である.
2012-01-19

著者

関連論文

もっと見る

スポンサーリンク