巡回セールスマン問題に対するカオスニューロダイナミクスを用いたヒューリスティック解法

概要

論文の詳細を見る
Recently, a novel approach for combinatorial optimization problems using chaotic neurodynamics has been discussed.In order to solve the local minimum problems intrinsic to Hopfield neural networks applied to the Traveling Salesman Problems(TSP), a new approach using chaotic dynamics has been proposed. However, this appraoch has two problems in case of applying to larger problems: the first is that the constraint terms should by satisfied is that the number of mutual connections gets huge. On the other hand, heuristic approaches, such as 2-opt, 3-opt and Lin-kerneighan methods, are applicable for the large scale TSPs, because the constraints of the problems are included in those algorithms themselves and they do not include the large number of mutual connections which is required on the approach with the mutual connection neural networks. Hpwever, since these heuristic methods also have steepest descent dynamics, they also have local minimum problems. Therfore in thi paper, we apply chaotic neurodynamics, which is effective for combinatorial optimization, to the local minimum problem on the heuristic algorithm.In this paper, we select the 2-opt as a basic algorithm from the heuristic algorithm, because very good near-optimum-solution can be obtained with this simple algorithm.
社団法人電子情報通信学会の論文
1996-09-18