| 講演名 | 2001/7/20 カオスニューロダイナミクスを用いたκ-opt法の有効性について 長谷川 幹雄, 池口 徹, 合原 一幸, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | カオスを用いた組み合わせ最適化問題の解法が提案されている.本研究では, 2-opt法を基盤とした, 大規模な巡回セールスマン問題に適用可能なカオスニューロダイナミクスを用いた解法を拡張し, κ-opt法を基盤とする手法を提案し, 有効性を検討する.更に, Lin-Kernighan法と類似した性質を持つ, κをアダプティブに変更する手法を基盤とするカオスサーチ法にこれを拡張し, 10の4乗のオーダの問題まで適用し, 性能を評価する.その結果, アダプティブにκを変化させる手法をベースにしたカオスサーチで, 11849都市問題に対しても5000イタレーションで既知最良解から1%程度の良好な解を求めることが可能となることを示す. |
| 抄録(英) | Recently, the effectiveness of the chaotic dynamics for combinatorial optimization has been shown. In this paper, the chaotic search based on the 2-opt for the Traveling Salesman Problem (TSP) is extended to the κ-opt based version. Furthermore, a chaotic search based on the adaptive κ-opt, whose κ is adaptively changed in similar way to the Lin-Kernighan method, is also proposed. By numerical simulations, it is shown that the proposed method solves good near optimum solutions which is about 1% different from the best known solutions, with only 5000 iterations even for an 11849-city TSP. |
| キーワード(和) | カオス / ニューラルネットワーク / 組み合わせ最適化問題 / 巡回セールスマン問題 / タブーサーチ / κ-opt法 |
| キーワード(英) | Chaos / Neural Networks / Combinatorial Optimization Problems / TSP / Tabu Search / κ-opt Method |
| 資料番号 | NLP2001-37 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2001/7/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | カオスニューロダイナミクスを用いたκ-opt法の有効性について |
| サブタイトル（和） | |
| タイトル（英） | On the Effects of the κ-opt method with Chaotic Neurodynamics |
| サブタイトル（和） | |
| キーワード(1)（和/英） | カオス / Chaos |
| キーワード(2)（和/英） | ニューラルネットワーク / Neural Networks |
| キーワード(3)（和/英） | 組み合わせ最適化問題 / Combinatorial Optimization Problems |
| キーワード(4)（和/英） | 巡回セールスマン問題 / TSP |
| キーワード(5)（和/英） | タブーサーチ / Tabu Search |
| キーワード(6)（和/英） | κ-opt法 / κ-opt Method |
| 第 1 著者 氏名（和/英） | 長谷川 幹雄 / Mikio Hasegawa |
| 第 1 著者 所属（和/英） | 通信総合研究所 横須賀無線通信研究センター Yokosuka Radio Communications Research Center, Communications Research Laboratory |
| 第 2 著者 氏名（和/英） | 池口 徹 / Tohru Ikeguchi |
| 第 2 著者 所属（和/英） | 埼玉大学 工学部 情報システム工学科 Department of Information and Computer Sciences, Saitama Univesity |
| 第 3 著者 氏名（和/英） | 合原 一幸 / Kazuyuki Aihara |
| 第 3 著者 所属（和/英） | 東京大学 新領域創成科学研究科 複雑理工学専攻 Department of Complexity Science and Engineering, University of Tokyo |
| 発表年月日 | 2001/7/20 |
| 資料番号 | NLP2001-37 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 229 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |