The Lin-Kernighan Algorithm Driven by Chaotic Neurodynamics for Large Scale Traveling Salesman Problems
The Lin-Kernighan Algorithm Driven by Chaotic Neurodynamics for Large Scale Traveling Salesman Problems
复制标题
混沌神经动力学驱动的 Lin-Kernighan 算法解决大规模旅行商问题
DOI：
10.1007/978-3-642-04277-5_57
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
K. Aihara
中科院分区：
文献类型：
--
作者：
Shun Motohashi;Takafumi Matsuura;T. Ikeguchi;K. Aihara
旅行商问题（TSP）是典型的难题之一。那么，开发一种有效的近似算法就势在必行。我们已经提出了一种使用混沌神经动力学的有效算法。该算法驱动局部搜索方法，例如2-opt算法和adaptivek-opt算法，以避免不期望的局部最小值。在本文中，我们提出了一种使用 Lin-Kernighan 算法的新混沌搜索方法。 Lin-Kernighan 算法是求解 TSP 最有效的算法之一。此外，为了使搜索状态多样化，我们引入了双桥算法。因此，所提出的方法表现出比传统算法更高的性能。我们验证了所提出的方法对于超大规模实例（例如 105 阶 TSP）的适用性。
The traveling salesman problem (TSP) is one of the typical-hard problems. Then, it is inevitable to develop an effective approximate algorithm. We have already proposed an effective algorithm which uses chaotic neurodynamics. The algorithm drives a local search method, such as the 2-opt algorithm and the adaptivek-opt algorithm, to escape from undesirable local minima. In this paper, we propose a new chaotic search method using the Lin-Kernighan algorithm. The Lin-Kernighan algorithm is one of the most effective algorithms for solving TSP. Moreover, to diversify searching states, we introduce the double bridge algorithm. As a result, the proposed method exhibits higher performance than the conventional algorithms. We validate the applicability of the proposed method for very large scale instances, such as 105order TSPs.