共 4 条
一种求解TSP问题的改进遗传算法
被引：6
作者：
杨华芬
魏延
机构：
[1] 重庆师范大学数学与计算机科学学院
[2] 重庆师范大学数学与计算机科学学院 重庆
[3] 曲靖师范学院
[4] 云南曲靖
来源：
关键词：
TSP;
交叉算子;
2-opt搜索优化;
遗传算法;
变异算子;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ;
0812 ;
0835 ;
1405 ;
摘要：
旅行商问题(Traveling Salesman Problem TSP)是一个典型的组合优化问题,但应用基本遗传算法求解TSP问题时存在许多不足.结合TSP问题的特点,提出一种改进的遗传算法:应用贪心策略初始化种群,用2-opt对其进行优化,使得在初始个体中就包含较优子路径,在一定程度上加快算法收敛性,防止早熟和近亲繁殖.对交叉算子和变异算子进行改进后,既能维持种群的多样性,也保留了父代个体大部分优良性能.应用改进的算法对20个城市的TSP问题进行求解,结果表明该算法求解速度快而且求解的质量较好.
引用
收藏
页码：86 / 90
页数：5
相关论文