Solving Traveling Salesman Problem Using 2-opt and Or-opt Algorithms Driven by Chaotic Neurons

摘要

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法の実行をカオスニューロンの内部状態で制御することにより，局所最適解からの脱出を行っている．その結果，効果的な探索が可能となり優れた性能を有することが示されている．本稿では，2-opt法とOr-opt法の実行を，異なるカオスニューロンで駆動する探索法を提案する．具体的には，（1）2-opt法とOr-opt法を制御するカオスニューロンが独立な手法，（2）2-opt法とOr-opt法を制御するカオスニューロンが相互に影響を及ぼす手法を提案する，計算機シミュレーションを行った結果，これまでに提案されているカオスサーチ法を凌駕する性能を有することを確認した．