改进的嵌套分区算法求解旅行商问题

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (24): 54-57.

改进的嵌套分区算法求解旅行商问题

宗德才1，王康康2

1.常熟理工学院计算机科学与工程学院，江苏常熟 215500
2.江苏科技大学数理学院，江苏镇江 212003

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-08-21 发布日期:2011-08-21

Improved nested partitions method for traveling salesman problem

ZONG Decai1，WANG Kangkang2

1.College of Computer Science and Engineering，Changshu Institute of Technology，Changshu，Jiangsu 215500，China
2.School of Mathematics and Physics，Jiangsu University of Science and Technology，Zhenjiang，Jiangsu 212003，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-08-21 Published:2011-08-21

摘要/Abstract

摘要： 嵌套分区算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分区算法（NPM）的基本思想，将其应用于求解旅行商问题。分析确定了嵌套分区算法各个算子的策略，提出了一种改进的嵌套分区算法。该算法采用加权抽样法求得初始最可能域，用全局数组记录下每个区域的历史最优解，用3-opt局部搜索算法改进每个区域解的质量。对TSPLIB中部分实例仿真结果表明，所提出的结合3-opt算法的改进嵌套分区算法在求解 TSP问题时可以获得高质量的解。

关键词: 嵌套分区算法, 旅行商问题, 3-opt算法

Abstract: The Nested Partitions Method（NPM） is a new global optimization method recently proposed，which can be applied to solve many large-scale discrete optimization problems.The main idea of this method is introduced and its application to the traveling salesman problem is proposed.Based on the analysis and determination of the strategy of the four arithmetic operators of NPM，an improved NPM is proposed.The initial most promising region is improved by weighted sampling method，the historical optimal solution of every region is recorded in a global array and the 3-opt algorithm is combined in the local search for improving the quality of solution for every region.Some experimental results of TSPLIB show that the proposed improved NPM combined with 3-opt algorithm can find solutions of high quality when applied to the traveling salesman problem.

Key words: nested partitions algorithm, traveling salesman problem, 3-opt

宗德才1，王康康2. 改进的嵌套分区算法求解旅行商问题[J]. 计算机工程与应用, 2011, 47(24): 54-57.

ZONG Decai1，WANG Kangkang2. Improved nested partitions method for traveling salesman problem[J]. Computer Engineering and Applications, 2011, 47(24): 54-57.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[4]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[5]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[6]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[7]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[8]	李娟，游晓明，刘升，陈佳. 自适应模糊蚁群系统[J]. 计算机工程与应用, 2019, 55(15): 75-81.
[9]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[10]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[11]	陈雷，张红梅，张向利. 自适应动态邻域布谷鸟混合算法求解TSP问题[J]. 计算机工程与应用, 2018, 54(23): 42-50.
[12]	白景波，李宏伟，陈亮，冯玉芳，刘建永. 双链量子蚁群系统及应用[J]. 计算机工程与应用, 2018, 54(21): 1-6.
[13]	徐小平，张东洁. 基于猴群算法求解旅行商问题[J]. 计算机工程与应用, 2018, 54(2): 144-148.
[14]	林敏，钟一文，刘必雄，林晓宇. 基因-表现型的布谷鸟算法求解旅行商问题[J]. 计算机工程与应用, 2017, 53(24): 172-181.
[15]	郑明1，2，3，卓慕瑰1，2. 四点三线遗传算法求解旅行商问题[J]. 计算机工程与应用, 2017, 53(14): 148-154.