講演抄録/キーワード |
講演名 |
2009-11-11 14:50
2-opt法とOr-opt法をカオスニューロンで駆動する巡回セールスマン問題の解法 ○松浦隆文・池口 徹(埼玉大) NLP2009-93 |
抄録 |
(和) |
カオスダイナミクスを用いた,巡回セールスマン問題の解法が提案されている.この解法は,局所探索法である2-opt法とOr-opt法の実行をカオスニューロンの内部状態で制御することにより, 局所最適解からの脱出を行っている.その結果,効果的な探索が可能となり優れた性能を有することが示されている.本稿では,2-opt法とOr-opt法の実行を,異なるカオスニューロンで駆動する探索法を提案する.具体的には,(1) 2-opt法とOr-opt法を制御するカオスニューロンが独立な手法,(2) 2-opt法とOr-opt法を制御するカオスニューロンが相互に影響を及ぼす手法を提案する.計算機シミュレーションを行った結果,これまでに提案されているカオスサーチ法を凌駕する性能を有することを確認した. |
(英) |
To find near optimum solutions of TSPs, a method with chaotic neurodynamics for solving TSPs has already been proposed. To avoid local minima, in the method, 2-opt algorithm and Or-opt algorithm for solving TSP are driven by chaotic neurodynamics. In the method, two local searches are driven by the same chaotic neuron. As a result, this method shows good performance, even though the 2-opt and the Or-opt algorithms are simple local search. In this report, to improve the performance of this method, we propose a new method. In the proposed method, the 2-opt and Or-opt algorithms are driven by different chaotic neurons. As a result, the proposed method shows higher performance than the previous chaotic search methods. |
キーワード |
(和) |
巡回セールスマン問題 / カオスニューラルネットワーク / 2-opt法 / Or-opt法 / / / / |
(英) |
Traveling Salesman Problem / Chaotic Neural Network / 2-opt algorithm / Or-opt algorithm / / / / |
文献情報 |
信学技報, vol. 109, no. 269, NLP2009-93, pp. 61-66, 2009年11月. |
資料番号 |
NLP2009-93 |
発行日 |
2009-11-04 (NLP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NLP2009-93 |