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

摘要

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