一种混合局部搜索算法的遗传算法求解旅行商问题

• 作者: 宗德才 王康康
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 遗传算法 加权最近邻法 K-近邻法 Lin-Kernighan 算法 3-opt 算法 旅行商问题
• 年，卷（期）: 2015,（3）
• 所属期刊栏目: 算 法
• 页码范围: 266-270,305
• 页数: 6页
• 分类号: TP301.6
• 字数: 6877字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2015.03.063

摘要

针对遗传算法容易产生早熟现象以及局部寻优能力较差的缺点，提出一种求解旅行商问题的高效混合遗传算法。该算法首先用加权最近邻法产生初始种群，对种群中相同的个体，用 K-近邻法产生新的个体代替相同的个体，然后淘汰适应性较差的个体，用交叉操作产生新的个体，最后，对部分个体进行3-opt 优化变异，对种群中优秀个体用改进的 Lin-Kernighan 算法进行优化。对TSPLIB 中部分实例的仿真结果表明，所提出的混合局部搜索算法的改进遗传算法在求解 TSP 问题时可以高效地获得高质量的解。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宗德才	常熟理工学院计算机科学与工程学院	26	116	5.0	10.0
2	王康康	江苏科技大学数理学院	52	217	8.0	11.0