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

• 作者: 周欣 武妍
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 禁忌算法 启发式算法 旅行商问题
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 学术探讨
• 页码范围: 57-59
• 页数: 3页
• 分类号: TP181|TP301.6
• 字数: 3223字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008.01.018

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	武妍	同济大学计算机科学与工程系	58	726	15.0	24.0
2	周欣	同济大学计算机科学与工程系	15	184	7.0	13.0