| 講演名 | 1996/12/14 巡回セールスマン問題の従来アルゴリズムの評価と新しいニューラルネットワークアルゴリズムの提案 四方 康人, 船曳 信生, 西川 清史, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | NP困難の組合せ最適化問題である巡回セールスマン問題を解くために,多くの近似アルゴリズムが提案されている.本論文では,まず,主要な近似アルゴリズムの特徴比較を行う.次に,解収束時にエネルギー関数値が0となる新しいニューラルネットワークアルゴリズムを提案する.各アルゴリズムの性能比較は,ベンチマーク問題を用いたシミュレーションにより行う.その結果,遺伝的アルゴリズム等,解表現が1次元であるアルゴリズムが計算時間,解精度の両面で優れていることが分かった.提案するアルゴリズムは,従来のニューラルネットワークアルゴリズムよりは優れているものの,前者のアルゴリズムより劣ることが分かった. |
| 抄録(英) | The traveling salesman problem is a well-known NP-hard combinatorial optimization problem. To solve the problem many researchers have developed algorithms. In this paper, first, we compare the features of 4 main algorithms. Second, we propose a new neural network algorithm whose energy function takes 0 when the neuron outputs represent a tour. At last, we compare their performance with 5 bench mark problems .The results show that It is found that a proposal algorithm is superior to trivial neural network but inferior to these algorisms. |
| キーワード(和) | 巡回セールスマン問題 / NP困難 / 漸進的ニューラルネットワーク / 組合せ最適化問題 / 遺伝的アルゴリズム |
| キーワード(英) | Traveling salesman problem / NP-hard / Gradual Neural Network / Combinatorial optimization problem / Genetic Algorithm |
| 資料番号 | NC96-62 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 1996/12/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 巡回セールスマン問題の従来アルゴリズムの評価と新しいニューラルネットワークアルゴリズムの提案 |
| サブタイトル（和） | |
| タイトル（英） | An Evaluation of Four Existing Algorithms and a New Neural Network Algorithm for Traveling Salesman Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 巡回セールスマン問題 / Traveling salesman problem |
| キーワード(2)（和/英） | NP困難 / NP-hard |
| キーワード(3)（和/英） | 漸進的ニューラルネットワーク / Gradual Neural Network |
| キーワード(4)（和/英） | 組合せ最適化問題 / Combinatorial optimization problem |
| キーワード(5)（和/英） | 遺伝的アルゴリズム / Genetic Algorithm |
| 第 1 著者 氏名（和/英） | 四方 康人 / Yasuhito Shikata |
| 第 1 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Sciences, Graduate School of Engineering Science, Osaka University |
| 第 2 著者 氏名（和/英） | 船曳 信生 / Nobuo Funabiki |
| 第 2 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Sciences, Graduate School of Engineering Science, Osaka University |
| 第 3 著者 氏名（和/英） | 西川 清史 / Seishi Nishikawa |
| 第 3 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Sciences, Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 1996/12/14 |
| 資料番号 | NC96-62 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 430 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |