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

被引：4

作者：

宗德才 ^{[1
]}

王康康 ^{[2
]}

机构：

[1] 常熟理工学院计算机科学与工程学院

[2] 江苏科技大学数理学院

来源：

计算机工程与应用 | 2011年 / 24期

关键词：

嵌套分区算法; 旅行商问题; 3-opt算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：54 / 57

页数：4

共 5 条

[1] 求解TSP问题的改进模拟退火遗传算法 [J].