用于求解TSP问题的改进遗传算法

• 作者: 文艺 潘大志
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: TSP 遗传算法 改进交叉算子 相似度
• 年，卷（期）: 2016,（z1）
• 所属期刊栏目: 智能计算
• 页码范围: 90-92
• 页数: 3页
• 分类号: TP301
• 字数: 3440字
• 语种: 中文

摘要

TSP问题是一个典型的组合优化问题,也是一个NP难题,一般很难精确地求出其最优解,因而找出有效的近似解算法具有重要意义.针对基本遗传算法在解决TSP问题时所存在的收敛速度慢、容易“早熟”的问题,在选择算子中引入选择因子,同时提出一种改进的交叉算子和基于种群相似度的更新策略.改进的交叉算子是先比较两个城市间距离再进行交换城市序号,因此加快了收敛的速度,而基于种群的相似度更新策略则在算法的后期可以有效地防止早熟.通过对实例144进行测试,证明该算法在解决该类问题上取得了较好的效果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘大志	西华师范大学数学与信息学院	50	194	9.0	11.0
2	文艺	西华师范大学数学与信息学院	4	17	1.0	4.0