| 講演名 | 1996/10/28 都市隣接性に基づく巡回セールスマン問題のニューラルネットによる解法とその評価 田中 敏雄, 松田 聖, 古谷 立美, 樋口 哲也, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では, まず都市隣接性に基づく巡回セールスマン問題(TSP)の解の漸近安定条件と非解の不安定条件を示す. そして, この条件に従って重みの係数の値を設定すれば, いずれの都市配置でも解が得られることを示す. 次に, 都市隣接性に基づくTSPの定式化と従来の都市の訪問順序に基づくTSPの定式化の性能比較を行なう. その結果, 都市の訪問順序に基づく定式化のエラーは都市数と共に増加する傾向があるが, 都市隣接性に基づく定式化のエラーは都市数に依存しないことがわかった. また, 都市隣接性に基づく定式化のl個の解を得るまでの計算時間の優位性はl30都市までであり, これ以上の都市数では, 都市の訪問順序に基づく定式化の方が計算時間が短くなることがわかった. |
| 抄録(英) | A stability condition of solutions and an instability condition of nonsolutions are derived for Hop-field network for TSP based on city adjacency. By setting weights to satisfy these conditions, it is actually shown that we can always obtain solutions for many TSP instances. We also make, by simulations, performance comparisons of this network with the network based on city position in tour. For the network based on city position, errors in solutions obtained have a tendency to increase as the problem size increases, but, for one based on city adjacency, does not depend on the problem size. Also we show that, for TSPs with less than 130 cities, the network based on city adjacency takes shorter computation time than the one based on city position, but, for TSPs with more than 130 cities, the contrary is observed. |
| キーワード(和) | ホップフィールドネット / 巡回セールスマン問題 / 都市隣接性 / 部分巡路 |
| キーワード(英) | Hopfield network / Travelling Salesman Problem / city adjacency / subtour |
| 資料番号 | NC96-39 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 1996/10/28(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 都市隣接性に基づく巡回セールスマン問題のニューラルネットによる解法とその評価 |
| サブタイトル（和） | |
| タイトル（英） | Neural Network Approch to Travelling Salesman Problem Based on City Adjacency and Its Evaluation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ホップフィールドネット / Hopfield network |
| キーワード(2)（和/英） | 巡回セールスマン問題 / Travelling Salesman Problem |
| キーワード(3)（和/英） | 都市隣接性 / city adjacency |
| キーワード(4)（和/英） | 部分巡路 / subtour |
| 第 1 著者 氏名（和/英） | 田中 敏雄 / Toshio TANAKA |
| 第 1 著者 所属（和/英） | 電子技術総合研究所 Electrotechnical Laboratory |
| 第 2 著者 氏名（和/英） | 松田 聖 / Satoshi MATSUDA |
| 第 2 著者 所属（和/英） | 東京電力 Tokyo Electric Power Company |
| 第 3 著者 氏名（和/英） | 古谷 立美 / Tatsumi FURUYA |
| 第 3 著者 所属（和/英） | 東邦大学 Toho University |
| 第 4 著者 氏名（和/英） | 樋口 哲也 / Tetsuya HIGUCHI |
| 第 4 著者 所属（和/英） | 電子技術総合研究所 Electrotechnical Laboratory |
| 発表年月日 | 1996/10/28 |
| 資料番号 | NC96-39 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 331 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |