一种求解TSP问题的改进遗传算法

• 作者: 杨华芬 魏延
• 来源期刊: 重庆工学院学报（自然科学版）
• 学科: 工学
• 关键词: TSP 交叉算子 2-opt搜索优化 遗传算法 变异算子
• 年，卷（期）: 2007,（5）
• 所属期刊栏目: 计算机与信息工程
• 页码范围: 86-90
• 页数: 5页
• 分类号: TP301.6
• 字数: 3397字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-8425-B.2007.05.023

摘要

旅行商问题(Traveling Salesman Problem TSP)是一个典型的组合优化问题,但应用基本遗传算法求解TSP问题时存在许多不足.结合TSP问题的特点,提出一种改进的遗传算法:应用贪心策略初始化种群,用2-opt对其进行优化,使得在初始个体中就包含较优子路径,在一定程度上加快算法收敛性,防止早熟和近亲繁殖.对交叉算子和变异算子进行改进后,既能维持种群的多样性,也保留了父代个体大部分优良性能.应用改进的算法对20个城市的TSP问题进行求解,结果表明该算法求解速度快而且求解的质量较好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨华芬	重庆师范大学数学与计算机科学学院	27	133	6.0	10.0
3	魏延	重庆师范大学数学与计算机科学学院	44	283	10.0	15.0