一种混合局部搜索算法的嵌套分区算法.docx

宗德才1 ，王康康2( 1． 常熟理工学院 计算机科学与工程学院，江苏 常熟 2155 宗德才1 ，王康康2 ( 1． 常熟理工学院 计算机科学与工程学院，江苏 常熟 215500; 2． 江苏科技大学 数理学院，江苏 镇江 212003) 摘 要: 提出了一种混合多种局部搜索算法的嵌套分区算法用于求解中小规模旅行商问题。该算法使用加权 抽样法产生初始最可能域，用带约束的 3-opt 局部搜索算法搜索每个子域的最优解，然后对 Lin-Kernighan 算法进 行了改进，并且用改进的 Lin-Kernighan 算法搜索每个裙域的最优解，最后通过实验分析法确定了子域和裙域最 优的抽样个数及初始最可能域的长度。对 TSPLIB 中 15 个问题实例的仿真结果表明，所提出的混合局部搜索算 法的改进嵌套分区算法在求解旅行商问题时可以获得高质量的解。 关键词: 嵌套分区算法; 局部搜索算法; Lin-Kernighan 算法; 带约束的 3-opt 算法; 旅行商问题 中图分类号: TP301． 6 文献标志码: A 文章编号: 1001-3695( 2015) 03-0752-07 doi: 10． 3969 / j． issn． 1001-3695． 2015． 03． 026 Combined nested partitions method based on local search algorithm ZONG De-cai1 ，WANG Kang-kang2 ( 1． College of Computer Science ＆ Engineering，Changshu Institute of Technology，Changshu Jiangsu 215500，China; 2． School of Mathematics ＆ Physics，Jiangsu University of Science ＆ Technology，Zhenjiang Jiangsu 212003，China) Abstract: This paper put forward an improved nested partitions method using multiple local search algorithms to solve the small and medium scale traveling salesman problem． The algorithm adopted weighted sampling method to generate the initial most promising region and used the restricted 3-opt local search algorithm to search the optimal solution of each subregion． Then this algorithm used an improved Lin-Kernighan algorithm to search the optimal solution of each surrounding region ． Final- ly，it analyzed and determined the optimal sampling number of each subregion and each surrounding region and the optimal length of the initial most promising region through experiments． The simulation results for the 15 problems in TSPLIB show that the proposed improved nested partitions method using multiple local search algorithms can find solutions of high quality when applied to the traveling salesman problem． Key words: nested partitions algorithm; local search algorithm; Lin-Kernighan algorithm; restricted 3-opt algorithm; trave- ling salesman problem( TSP) 题规模的扩大，将产生组合爆炸; b) 随机优化算法或局部搜索 算法，能够在多项式时