| 一种求解TSP问题的改进遗传算法 |
| |
| 引用本文： | 符一平,陈光喜. 一种求解TSP问题的改进遗传算法[J]. 桂林电子科技大学学报, 2007, 27(4): 287-290 |
| |
| 作者姓名： | 符一平 陈光喜 |
| |
| 作者单位： | 桂林电子科技大学,数学与计算科学学院,广西,桂林,541004;桂林电子科技大学,数学与计算科学学院,广西,桂林,541004 |
| |
| 摘 要： | 遗传算法(GA)是基于生物进化论的一种全局优化搜索算法,是求解TSP问题的一种方法,但它存在如何较快地找到最优解并防止"早熟"收敛的问题.结合TSP问题最优解一般包含城市与其最近城市的相连的特点,提出了贪婪两点插入变异算子,改进了启发式杂交算子,并根据个体适应度与群平均适应度根据个体的适应度赋予不同的变异概率,使得较好的个体探测路径,较差个体开发新个体.对初始群体作局部优化提高其质量加快算法的收敛速度,最优个体连续几代一直保留,则采用局部微调算子使子代中的最优个体跳离局部解.通过实验分析,改进的算法能较快的收敛到TSP问题的已知最优解;其测试结果与国际标准测试库TSPLIB中的最优路径相比,或接近或优于.
|
| 关 键 词： | 遗传算法 TSP问题 贪婪变异算子 启发式杂交算子 |
| 文章编号： | 1673-808X（2007）04-0287-04 |
| 修稿时间： | 2007-06-08 |
An improved genetic algorithm for solving TSP problem |
| |
| FU Yi-ping,CHEN Guang-xi. An improved genetic algorithm for solving TSP problem[J]. Journal of Guilin University of Electronic Technology, 2007, 27(4): 287-290 |
| |
| Authors: | FU Yi-ping CHEN Guang-xi |
| |
| Affiliation: | School of Mathematics and Computing Selenee, Guilin University of Eleetronle Teehnology,Guilin 541004, China |
| |
| Abstract: | |
| |
| Keywords: | genetic algorithm TSP problem greed mutation operator heuristic crossover operator |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
