| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-07-21 14:55 Lin-Kernighan法をカオスダイナミクスで駆動する巡回セールスマン問題の解法とその性能について ○光岡高宏・長谷川幹雄（東京理科大）  NLP2014-35 |
|
| 抄録 | （和） | カオスを用いた組合せ最適化手法の有効性が示されている．本稿では，カオスダイナミクスで駆動するLin-Kernighan法の性能について調べる．本手法は，タブーサーチを基盤として構成しており，タブーサーチの有効性を含んだカオス的探索となる．まず，不応性を有するニューラルネットワーク用いて，基とするタブーサーチを実現する．さらに，このニューラルネットワークの出力関数を，アナログのシグモイド関数に置き換えることで，カオスニューラルネットに変形する．このカオスニューラルネットワークでLin-Kernighan法を駆動することにより，カオスダイナミクスとタブーサーチを有するゆらぎによって，探索の性能を向上することができる．2-opt法をカオスダイナミクスで駆動する手法と比較し，Lin-Kernighan法をカオスダイナミクスで駆動する手法がより高い性能を有することを示す． |
| （英） | Effectiveness of chaos for optimization has been shown by many previous researches. In this paper, a chaotic search based on the 2-opt for the Traveling Salesman Problem (TSP) is extended to the k-opt based version. A chaotic search based on the adaptive k-opt, whose k is adaptively changed in similar way to the Lin-Kernighan method, is proposed. Our proposed method is based on the tabu search. First, a conventional tabu search is implemented on a neural network model, which has refractory effects on each neuron. The tabu search neural network can be simply extended to chaotic neural network, by replacing the output function with analog sigmoidal function. 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. | |
| キーワード | （和） | カオス / 組合せ最適化 / ニューラルネットワーク / Lin-Kernighan法 / タブーサーチ / / / |
| （英） | Chaos / Combinatorial Optimization / Neural Networks / Lin-Kernighan Method / Tabu Search / / / | |
| 文献情報 | 信学技報, vol. 114, no. 145, NLP2014-35, pp. 23-26, 2014年7月. | |
| 資料番号 | NLP2014-35 | |
| 発行日 | 2014-07-14 (NLP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NLP2014-35 |
|
| 研究会情報 | |
| 研究会 | NLP |
| 開催期間 | 2014-07-21 - 2014-07-22 |
| 開催地（和） | 函館市中央図書館 |
| 開催地（英） | Hakodate City Central Library |
| テーマ（和） | 一般 |
| テーマ（英） | Nonlinear Problems, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NLP |
| 会議コード | 2014-07-NLP |
| 本文の言語 | 日本語 |
| タイトル（和） | Lin-Kernighan法をカオスダイナミクスで駆動する巡回セールスマン問題の解法とその性能について |
| サブタイトル（和） | |
| タイトル（英） | Solving Ability of Lin-Kernighan Method Driven by Chaotic Dynamics for Traveling Salesman Problems |
| サブタイトル（英） | |
| キーワード(1)（和/英） | カオス / Chaos |
| キーワード(2)（和/英） | 組合せ最適化 / Combinatorial Optimization |
| キーワード(3)（和/英） | ニューラルネットワーク / Neural Networks |
| キーワード(4)（和/英） | Lin-Kernighan法 / Lin-Kernighan Method |
| キーワード(5)（和/英） | タブーサーチ / Tabu Search |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 光岡 高宏 / Takahiro Mitsuoka / ミツオカ タカヒロ |
| 第1著者 所属（和/英） | 東京理科大学 (略称： 東京理科大) Tokyo University of Science (略称： Tokyo Univ. of Science) |
| 第2著者 氏名（和/英/ヨミ） | 長谷川 幹雄 / Mikio Hasegawa / ハセガワ ミキオ |
| 第2著者 所属（和/英） | 東京理科大学 (略称： 東京理科大) Tokyo University of Science (略称： Tokyo Univ. of Science) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-07-21 14:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NLP |
| 資料番号 | NLP2014-35 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.145 |
| ページ範囲 | pp.23-26 |
| ページ数 | 4 |
| 発行日 | 2014-07-14 (NLP) |
[研究会発表申込システムのトップページに戻る]