| 講演名 | 2003/1/28 非加法的統計力学により拡張された確定的アニーリングEMアルゴリズムの巡回セールスマン問題への応用 田伏 克巳, 井上 純一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | EMアルゴリズムは不完全データから最尤推定値を求めるための代表的手法である.しかし,このアルゴリズムは収束点が初期値に依存し,局所最適解に収束してしまう問題を有している.我々はこの問題を解決するためにTsallisによる非加法的エントロピーを最大化する分布を事後確率に選び,この分布に含まれる非加法性の程度を示すパラメータqを1へ制御するアルゴリズムを提案したが,本編ではこの提案手法を巡回セールスマン問題に応用した結果を報告する.具体的には自己組織化マップを作成する手法であるKohonenのアルゴリズムはEMアルゴリズムによる定式化が可能であるが,我々は自己組織化マップによる解法が知られている巡回セールスマン問題に対し提案手法を適用した.本稿では得られる解の精度,パラメータqの制御法,アルゴリズムの収束速度等を議論する. |
| 抄録(英) | EM-algorithm is one of the major tools to obtain maximum likelihood estimates from incomplete data sets. However the EM-algorithm has the problem that the solution converges to a local optimal on account of the dependence of the initial state of parameters in the posterior distribution. In order to avoid this difficulty, we modified the posterior distribution by means of non-extensive Tsallis entropy. In our posterior distribution, a parameter q, which represents non-extensivity of the entropy, is controlled as q ↗ 1 to reduce the strong dependence of the initial conditions. In this paper, we apply our algorithm to the traveling salesman problem (TSP) . As well-known, the TSP can be solved by self-organizing map (SOM) of elastic neural networks. The key point of our method for the TSP is reformulating the SOM in terms of our modified EM-algorithm. Quality of the solution, suitable annealing schedule for the parameter q, speed of the convergence, etc., are discussed. |
| キーワード(和) | EMアルゴリズム / 非加法的統計力学 / Tsallisエントロピー / 巡回セールスマン問題 / 自己組織化マップ |
| キーワード(英) | EM-algorithm / non-extensive statistical mechanics / Tsallis entropy / traveling salesman problem / self organizing map |
| 資料番号 | NC2002-127 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 2003/1/28(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非加法的統計力学により拡張された確定的アニーリングEMアルゴリズムの巡回セールスマン問題への応用 |
| サブタイトル（和） | |
| タイトル（英） | Application of the deterministic annealing EM algorithm extended by means of non-extensive statistical mechanics to the traveling salesman problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | EMアルゴリズム / EM-algorithm |
| キーワード(2)（和/英） | 非加法的統計力学 / non-extensive statistical mechanics |
| キーワード(3)（和/英） | Tsallisエントロピー / Tsallis entropy |
| キーワード(4)（和/英） | 巡回セールスマン問題 / traveling salesman problem |
| キーワード(5)（和/英） | 自己組織化マップ / self organizing map |
| 第 1 著者 氏名（和/英） | 田伏 克巳 / Katsumi TABUSHI |
| 第 1 著者 所属（和/英） | 北海道大学大学院工学研究科 Graduate School of Engineering, Hokkaido University |
| 第 2 著者 氏名（和/英） | 井上 純一 / Jun-ichi INOUE |
| 第 2 著者 所属（和/英） | 北海道大学大学院工学研究科 Graduate School of Engineering, Hokkaido University |
| 発表年月日 | 2003/1/28 |
| 資料番号 | NC2002-127 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 628 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |