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

• 作者: 符一平 陈光喜
• 来源期刊: 桂林电子科技大学学报
• 学科: 工学
• 关键词: 遗传算法 TSP问题 贪婪变异算子 启发式杂交算子
• 年，卷（期）: 2007,（4）
• 所属期刊栏目: 学术论文
• 页码范围: 287-290
• 页数: 4页
• 分类号: TP18
• 字数: 3834字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-808X.2007.04.008

摘要

遗传算法(GA)是基于生物进化论的一种全局优化搜索算法,是求解TSP问题的一种方法,但它存在如何较快地找到最优解并防止"早熟"收敛的问题.结合TSP问题最优解一般包含城市与其最近城市的相连的特点,提出了贪婪两点插入变异算子,改进了启发式杂交算子,并根据个体适应度与群平均适应度根据个体的适应度赋予不同的变异概率,使得较好的个体探测路径,较差个体开发新个体.对初始群体作局部优化提高其质量加快算法的收敛速度,最优个体连续几代一直保留,则采用局部微调算子使子代中的最优个体跳离局部解.通过实验分析,改进的算法能较快的收敛到TSP问题的已知最优解;其测试结果与国际标准测试库TSPLIB中的最优路径相比,或接近或优于.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈光喜	桂林电子科技大学数学与计算科学学院	82	455	12.0	16.0
2	符一平	桂林电子科技大学数学与计算科学学院	1	8	1.0	1.0