求解TSP问题的改进模拟退火遗传算法

• 作者: 王银年 葛洪伟
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 巡回旅行商问题 遗传算法 模拟退火算法 贪心交叉算子 退火选择
• 年，卷（期）: 2010,（5）
• 所属期刊栏目: 研究、探讨
• 页码范围: 44-47,85
• 页数: 5页
• 分类号: TP18
• 字数: 5396字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.05.014

摘要

巡回旅行商问题(TSP)是最典型的NP的难题,遗传算法(GA)是解决这类问题的有效方法之一.由于该问题的解是一种特殊的序列,一般的交叉算子在该问题的求解效果方面并不理想,提出了贪心的3PM交叉算子,同时又引入退火选择方法,形成一种新的模拟退火遗传算法GCBSAGA(Greed Cross-3PM Based on Simulmed Annealing Genetic Algorithms).该算法还将模拟退火算法与遗传算法相结合,使得遗传算法在前期发挥着全局搜索的强大功能,很容易收敛到全局较优解;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能,最终收敛到全局最优解.经过国际公认的TSPLIB提供的实验数据的验证,GCBSAGA在实例eil76、eil101、pr144、st70均找到了比TSPLIB提供的最优路径更优的解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	葛洪伟	江南大学信息工程学院	86	456	11.0	17.0
2	王银年	江南大学信息工程学院	2	89	2.0	2.0