| 講演名 | 2017-03-10 Coherent Ising Machineを用いた非対称巡回セールスマン問題の解法 村田 侑雄(東京理科大), 安田 裕之(東大), 黒田 佳織(東京理科大), 合原 一幸(東大), 長谷川 幹雄(東京理科大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Coherent Ising Machine (CIM) を用いた高速な組合せ最適化手法の有効性が示されている．一方，CIMと同様に相互結合ネットワーク用いた最適化アルゴリズムとしてHopfield-Tank Neural Network (HTNN)が巡回セールスマン問題などに適用されており，HTNNをCIM上で動作させることで組合せ最適化問題を解く手法が既に提案されている．本稿ではヒューリスティック解法で最適解を得ることが難しい非対称巡回セールスマン問題(ATSP)をHTNN上にマッピングし，HTNNをCIM上で動作させることでATSPを高速に解くことを目指す．シミュレーションによる性能評価を行い，提案手法によりATSPの最適解を得られることを示す． |
| 抄録(英) | The effectiveness of high-speed combinatorial optimization method using Coherent Ising Machine (CIM) has been shown. Hopfield-Tank Neural Network (HTNN) is applied to the traveling salesman problem as an optimization algorithm using a mutual coupling network like CIM. The method of solving the combinatorial optimization problem by running HTNN on CIM has been proposed. In this paper, we aim to solve asymmetric traveling salesman problem (ATSP) at high speed by mapping the problem to the HTNN, which is difficult to obtain optimal solution by heuristic algorithms. Performance evaluations by simulation show that the optimum solution of ATSP can be obtained by the proposed method. |
| キーワード(和) | Coherent Ising Machine / 非対称巡回セールスマン問題 / 組合せ最適化 |
| キーワード(英) | Coherent Ising Machine / Asymmetric Traveling Salesman Problem / Combinatorial Optimization |
| 資料番号 | CCS2016-46 |
| 発行日 | 2017-03-03 (CCS) |
| 研究会情報 | |
| 研究会 | CCS |
|---|---|
| 開催期間 | 2017/3/10(から2日開催) |
| 開催地（和） | 東京工業大学・地球生命研究所 |
| 開催地（英） | ELSI, TITECH |
| テーマ（和） | 自然計算, 一般 |
| テーマ（英） | Natural Computing, etc. |
| 委員長氏名（和） | 坪 泰宏(立命館大) |
| 委員長氏名（英） | Yasuhiro Tsubo(Ritsumeikan Univ.) |
| 副委員長氏名（和） | 若宮 直紀(阪大) / 長谷川 幹雄(東京理科大) |
| 副委員長氏名（英） | Naoki Wakamiya(Osaka Univ.) / Mikio Hasegawa(Tokyo Univ. of Science) |
| 幹事氏名（和） | 鳥飼 弘幸(京都産大) / 寺前 順之介(阪大) |
| 幹事氏名（英） | Hiroyuki Torikai(Kyoto Sangyo Univ.) / Junnosuke Teramae(Osaka Univ.) |
| 幹事補佐氏名（和） | 木村 貴幸(日本工大) / Song-Ju Kim(物質・材料研究機構) / 高橋 亮(京大) / 中野 秀洋(東京都市大) |
| 幹事補佐氏名（英） | Takayuki Kimura(Nippon Inst. of Tech.) / Song-Ju Kim(NIMS) / Ryo Takahashi(Kyoto Univ.) / Hidehiro Nakano(Tokyo City Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Complex Communication Sciences |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Coherent Ising Machineを用いた非対称巡回セールスマン問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving Asymmetric Traveling Salesman Problems by Coherent Ising Machine |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Coherent Ising Machine / Coherent Ising Machine |
| キーワード(2)（和/英） | 非対称巡回セールスマン問題 / Asymmetric Traveling Salesman Problem |
| キーワード(3)（和/英） | 組合せ最適化 / Combinatorial Optimization |
| 第 1 著者 氏名（和/英） | 村田 侑雄 / Yukio Murata |
| 第 1 著者 所属（和/英） | 東京理科大学(略称：東京理科大) Tokyo University of Science(略称：Tokyo Univ. of Science) |
| 第 2 著者 氏名（和/英） | 安田 裕之 / Hiroyuki Yasuda |
| 第 2 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. of Tokyo) |
| 第 3 著者 氏名（和/英） | 黒田 佳織 / Kaori Kuroda |
| 第 3 著者 所属（和/英） | 東京理科大学(略称：東京理科大) Tokyo University of Science(略称：Tokyo Univ. of Science) |
| 第 4 著者 氏名（和/英） | 合原 一幸 / Kazuyuki Aihara |
| 第 4 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. of Tokyo) |
| 第 5 著者 氏名（和/英） | 長谷川 幹雄 / Mikio Hasegawa |
| 第 5 著者 所属（和/英） | 東京理科大学(略称：東京理科大) Tokyo University of Science(略称：Tokyo Univ. of Science) |
| 発表年月日 | 2017-03-10 |
| 資料番号 | CCS2016-46 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | CCS-514 |
| ページ範囲 | pp.7-12(CCS), |
| ページ数 | 6 |
| 発行日 | 2017-03-03 (CCS) |