| 一种求解TSP问题的改进遗传算法 |
| |
| 引用本文： | 杨华芬,魏延.一种求解TSP问题的改进遗传算法[J].重庆工学院学报,2007,21(9):86-90. |
| |
| 作者姓名： | 杨华芬 魏延 |
| |
| 作者单位： | [1]重庆师范大学数学与计算机科学学院,重庆400047 [2]曲靖师范学院,云南曲靖655000 |
| |
| 基金项目： | 重庆市教委科学研究基金资助项目（KJ050809）. |
| |
| 摘 要： | 旅行商问题（Traveling Salesman Problem TSP）是一个典型的组合优化问题，但应用基本遗传算法求解TSP问题时存在许多不足．结合TSP问题的特点，提出一种改进的遗传算法：应用贪心策略初始化种群，用2-opt对其进行优化，使得在初始个体中就包含较优子路径，在一定程度上加快算法收敛性，防止早熟和近亲繁殖．对交叉算子和变异算子进行改进后，既能维持种群的多样性，也保留了父代个体大部分优良性能．应用改进的算法对20个城市的TSP问题进行求解，结果表明该算法求解速度快而且求解的质量较好．
|
| 关 键 词： | TSP 交叉算子 2-opt搜索优化 遗传算法 变异算子 |
| 文章编号： | 1671-0924（2007）05-0086-05 |
| 收稿时间： | 2007-03-12 |
| 修稿时间： | 2007-03-12 |
Improved Genetic Algorithm for TSP |
| |
| YANG Hua-fen, WEI Yan.Improved Genetic Algorithm for TSP[J].Journal of Chongqing Institute of Technology,2007,21(9):86-90. |
| |
| Authors: | YANG Hua-fen WEI Yan |
| |
| Affiliation: | 1. School of Mathematics and Computer Science, Chongqing Normal University, Chongqing 400047, China; 2. Qujing Normal College, Qujing 655000, China |
| |
| Abstract: | |
| |
| Keywords: | TSP cross operator 2-opt search optimization genetic algorithm mutation operator |
| 本文献已被 维普 等数据库收录！ |
