| 講演名 | 1998/3/19 相互結合型ニューラルネットワークを用いた大規模巡回セールスマン問題の解法 梶谷 俊治, 小林 邦和, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 相互結合型ニューラルネットワーク(RNN)を用いて大規模な巡回セールスマン問題(TSP)を解くことは収束性や計算コストの上で大きな問題がある.本研究ではRNNを用いた際に実用的な解が得られない規模のTSPを大規模なTSPと位置付け, このようなTSPを解くためのアルゴリズムを提案する.提案法は大規模なTSPを解く場合に, 与えられたTSPの各都市をクラスタリングによりいくつかのサブ問題に分割し, その問題毎にRNNを用いて解を得る手法である.またより都市数の多いTSPに対しては, 再帰的にクラスタリングを行い対応することができる.提案法の有効性は, 計算機実験によって確認された. |
| 抄録(英) | It is difficult to solve large traveling salesman problems (TSPs) by recurrent neural networks (RNNs). Because computational cost and required memory space increase remarkably as the number of cities does and also the solutions are not practical. In this paper, the large TSPs are assumed that RNNs cannot provide us the practical solutions. An algorithm to solve the large TSPs is proposed. Introducing a clustering method, a large TSP is divided into small TSPs, which can be easily solved by RNNs. If necessary this process is continued recursively. Then, such small TSPs are solved by each RNN. Finally, a whole route of the large TSP is derived from combining the routes of small TSPs. Through computer experiments, it is verified that the proposed method is effective for large TSPs. |
| キーワード(和) | 巡回セールスマン問題 / NP困難 / 相互結合型ニューラルネットワーク / クラスタリング |
| キーワード(英) | Traveling Salesman Problems / NP-hard / Recurrent Neural Network / Clustering |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 1998/3/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 相互結合型ニューラルネットワークを用いた大規模巡回セールスマン問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving Large Traveling Salesman Problems Using Recurrent Neural Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 巡回セールスマン問題 / Traveling Salesman Problems |
| キーワード(2)（和/英） | NP困難 / NP-hard |
| キーワード(3)（和/英） | 相互結合型ニューラルネットワーク / Recurrent Neural Network |
| キーワード(4)（和/英） | クラスタリング / Clustering |
| 第 1 著者 氏名（和/英） | 梶谷 俊治 / Syunji Kajitani |
| 第 1 著者 所属（和/英） | 山口大学大学院理工学研究科 Graduate School of Science & Engineering, Yamaguchi University |
| 第 2 著者 氏名（和/英） | 小林 邦和 / Kunikazu Kobayashi |
| 第 2 著者 所属（和/英） | 山口大学工学部 Faculty of Engineering, Yamaguchi University |
| 発表年月日 | 1998/3/19 |
| 資料番号 | |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 623 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |