講演抄録/キーワード |
講演名 |
2012-01-27 15:00
上位M個の解が得られる疎結合モデルの離散最適化手法 ○加藤真志・井上真郷(早大) NC2011-118 |
抄録 |
(和) |
本研究では一般的な多体疎結合モデルの離散最適化問題(組合せ最適化問題)において,上位M種類の解を効率的かつ厳密に求める手法を提案する.従来手法では最上位の解のみを,また,最上位の解が複数ある場合は,その内の一つのみを求める手法が一般的であったが,本手法では,最上位の解集合(最適解集合),上位2番目の解集合と,上位$M$番目の解集合までを厳密に求めることができる.また,最適化の目的関数は,複数の任意の離散実数関数の和で表せるような広いクラスを想定した.目的関数の構造が密な結合を持っている場合は,提案手法を適用することは可能だが,全ての解候補を列挙するのに必要な指数的な計算量が必要となるため,メリットがない.また,本手法は予めどの程度の計算量,メモリ消費量が必要となるかを見積もることができる.更に,上位$M$番目までの解集合の要素数が指数的に増加する場合でも,このこと自体が直接にはトータルの計算量やメモリ消費量が指数的に増加させることにはならない手法である. |
(英) |
In this report, we propose an efficient method for obtaining exact M-best solutions of a discrete optimization problem (a combinatorial optimization problem) of a general sparsely connected multi-body model. Most of the conventional methods are intended for obtaining one of the best solutions, while the proposed method can answer all the sets of the top M solutions rigorously, e.g., the sets of the best solutions, the second best solutions, ..., and the M-best solutions. The class of the objective function of the proposed method is quite wide; which is defined as the summation of some discrete real functions. Even if the objective function has a densely connected structure, the proposed method is applicable, but its calculation cost would be of exponential order, thus having no advantage. Also, the proposed method can estimate both the calculation cost and the memory cost in advance. Furthermore, if the number of the solutions is of exponential order, it does not directly mean the calculation cost and/or the memory cost are of exponential order. |
キーワード |
(和) |
離散最適化 / 多体疎結合モデル / 厳密解 / / / / / |
(英) |
discrete optimization problem / combinatorial optimization problem / sparsely connected multi-body model / exact enumeration / / / / |
文献情報 |
信学技報, vol. 111, no. 419, NC2011-118, pp. 125-130, 2012年1月. |
資料番号 |
NC2011-118 |
発行日 |
2012-01-19 (NC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NC2011-118 |
研究会情報 |
研究会 |
NC |
開催期間 |
2012-01-26 - 2012-01-27 |
開催地(和) |
公立はこだて未来大学 |
開催地(英) |
Future University Hakodate |
テーマ(和) |
一般、複雑系とニューロコンピューティング |
テーマ(英) |
General, Complex Systems and Neurocomputing |
講演論文情報の詳細 |
申込み研究会 |
NC |
会議コード |
2012-01-NC |
本文の言語 |
日本語 |
タイトル(和) |
上位M個の解が得られる疎結合モデルの離散最適化手法 |
サブタイトル(和) |
|
タイトル(英) |
The M-best Discrete Optimization Method for Sparsely Connected Multi-body Model |
サブタイトル(英) |
|
キーワード(1)(和/英) |
離散最適化 / discrete optimization problem |
キーワード(2)(和/英) |
多体疎結合モデル / combinatorial optimization problem |
キーワード(3)(和/英) |
厳密解 / sparsely connected multi-body model |
キーワード(4)(和/英) |
/ exact enumeration |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
加藤 真志 / Masashi Kato / カトウ マサシ |
第1著者 所属(和/英) |
早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.) |
第2著者 氏名(和/英/ヨミ) |
井上 真郷 / Masato Inoue / イノウエ マサト |
第2著者 所属(和/英) |
早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2012-01-27 15:00:00 |
発表時間 |
25分 |
申込先研究会 |
NC |
資料番号 |
NC2011-118 |
巻番号(vol) |
vol.111 |
号番号(no) |
no.419 |
ページ範囲 |
pp.125-130 |
ページ数 |
6 |
発行日 |
2012-01-19 (NC) |
|