一种适用于求解TSP问题的改进的禁忌算法

摘要：

利用传统的禁忌算法的基本思想,针对TSP问题,提出了一种改进的禁忌算法(MTS).该算法在初始解的生成,邻域结构及禁忌策略方面进行了大的改进,充分地利用了问题本身的启发式信息与禁忌算法的优点.算法首先通过对城市分区,然后对区域连接,生成初始解;同时生成每个城市的k邻居列表,利用k邻居列表和改进的禁忌策略来突破局部最优.通过对CHN144问题及若干TSPLIB中问题的求解,结果表明所提算法能够以较快速度求得较好的满意解.

关键词：禁忌算法、启发式算法、旅行商问题

所属期刊栏目：44

分类号：TP181;TP301.6(自动化基础理论)

在线出版日期：2008-04-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：57-59