旅行商问题(TSP)的改进模拟退火算法

被引：13

作者：

苗卉 ^{[1
]}

杨韬 ^{[2
]}

机构：

[1] 昆士兰大学

[2] 西南交通大学

来源：

微计算机信息 | 2007年 / 33期

关键词：

模拟退火; 旅行商问题; 多种算子; 最优化问题;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

旅行商问题是一种典型的求解多局部最优的最优化问题:有n个城市,一个旅行者从其中的一个城市出发,经过所有的城市一次并返回出发的城市,求最短的路线。在使用普通的模拟退火算法解决TSP时,一般采用2-opt算法来产生新的解空间,导致算法效率低下。本文提出引入多种算子(如:移位,交换,倒置等等)来产生新解空间。算法的分析和测试结果表明,改进后的模拟退火算法效率明显提高,在收敛性和运算结果上都有较大的进步。

引用

页码：241 / 242+236 +236

页数：3