一种求解TSP问题的混合遗传算法

作者：张玉州; 梅俊; 徐廷政

来源：安庆师范大学学报(自然科学版), 2018, 24(03): 77-81.

DOI：10.13757/j.cnki.cn34-1328/n.2018.03.018

• TSP问题
• 遗传算法
• 最近邻域算法
• 局部搜索

解旅行商问题(TSP)局部寻优较好的算子有opt的各种形式(2-opt,3-opt等)以及Lin-Kernighan(LK)。然而,opt的各种形式的局部搜索算子都难较精细地对个体邻域进行搜索;LK的复杂性高,通常较少使用。鉴于此,本文将单点插入算子(SI)、交换算子(Swap)引入TSP问题的局部搜索,并结合2-opt,组成了一种局部搜索算子集合。同时,将上述算子集合嵌入遗传算法,从而形成混合遗传算法,用于求解TSP问题。通过对国际通用的TSPLIB中不同城市规模的数据进行测试,对比5种算法解的质量,结果证明该混合遗传算法是有效性的。

• 单位
  安庆师范大学