一个基于填充函数变换的对称TSP问题的局部搜索算法

• 作者: 傅清祥 朱文兴
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 对称TSP问题 局部搜索算法 填充函数变换 近似最优解
• 年，卷（期）: 2002,（7）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 701-707
• 页数: 7页
• 分类号: TP18
• 字数: 7452字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.07.005

摘要

该文提出了求对称TSP问题近优解的填充函数算法. 首先, 在用局部搜索算法求得对称TSP问题的一个局部极小解后, 对该问题作填充函数变换得到一新的组合优化问题, 新问题的局部极小解和最优解分别是原问题的局部极小解和最优解, 而且在对称TSP问题的目标函数值大于或等于其目标函数当前极小值的区域中, 新问题只有一个已知的局部极小解. 随后用局部搜索算法求新问题的一个局部极小解, 它或者是已知的局部极小解, 或者是对称TSP问题的更好的局部极小解. 对多个标准实例的计算试验表明,该文所构造的算法优于直接求解对称TSP问题的局部搜索算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	傅清祥	福州大学计算机科学与技术系	25	174	6.0	12.0
2	朱文兴	福州大学计算机科学与技术系	44	465	10.0	21.0