| 講演名 | 1995/6/30 巡回セールスマン問題における解の分岐 石井 信, 佐藤 雅昭, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | アナログホップフィールドモデルおよびボルツマンマシンの平均場近似モデルにおいてはアニーリングする際にエネルギー関数の対称性に応じた解の分岐が起きる。本報告では、巡回セールスマン問題を課題として、この分岐現象について述べる。巡回セールスマン問題は巡回対称性と反転対称性という二種の対称性を持ち、これらが分岐の構造に影響を与える。次に、これら分岐の構造によって、平均場アニーリングのアルゴリズムとしての性質が分かることを示す。結果として、平均場アニーリングは一般に「準」最適解を求めるアルゴリズムであり、非決定論的性質を有する。最後にこれらの性質を踏まえて、修正アルゴリズムを提案する。 |
| 抄録(英) | In the analog Hopfield network and the mean field theory (MFT) of the Boltzmann machine, bifurcations of solutions occur during the course of the annealing procedure. In this report, we investigate the bifurcation processes of MFT solutions when MFT is applied to traveling salesman problems (TSPs). A TSP has two types of symmetries, i.e., cyclic and reverse. These symmetries affect the bifurcation structure. Next, some features of the MFT annealing procedure, which are dependent on the bifurcation processes, are shown. The MFT annealing has "non-deterministic" and "non-optimal" properties, which implies some procedural limitations. To overcome these, we also propose a couple of modified algorithms. |
| キーワード(和) | 最適化問題 / 巡回セールスマン問題 / ホップフィールドモデル / 平均場近似 / アニーリング / 分岐理論 |
| キーワード(英) | optimization problem / traveling salesman problem / Hopfield network / mean field theory / annealing / bifurcation theory |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 1995/6/30(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 巡回セールスマン問題における解の分岐 |
| サブタイトル（和） | |
| タイトル（英） | Bifurcations in traveling salesman problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最適化問題 / optimization problem |
| キーワード(2)（和/英） | 巡回セールスマン問題 / traveling salesman problem |
| キーワード(3)（和/英） | ホップフィールドモデル / Hopfield network |
| キーワード(4)（和/英） | 平均場近似 / mean field theory |
| キーワード(5)（和/英） | アニーリング / annealing |
| キーワード(6)（和/英） | 分岐理論 / bifurcation theory |
| 第 1 著者 氏名（和/英） | 石井 信 / Shin Ishii |
| 第 1 著者 所属（和/英） | ATR人間情報通信研究所 ATR Human Information Processing Research Laboratories |
| 第 2 著者 氏名（和/英） | 佐藤 雅昭 / Masaaki Sato |
| 第 2 著者 所属（和/英） | ATR人間情報通信研究所 ATR Human Information Processing Research Laboratories |
| 発表年月日 | 1995/6/30 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 135 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |