求解TSP的交配算子设计策略

旅行商问题(TSP)是一类典型的NP完全问题,遗传算法(GA)是求解这类问题的常用方法之一。由于该问题的解是一种特殊的序列,一些典型的GA交配方法在求解该问题时的性能并不理想。通过多次对比两种常用的GA交配方法与3种专门为TSP作优化的交配方法,总结了一种对旅行商问题的交配算子的设计策略,即注重对双亲的边继承以及加入适当的贪心控制策略。通过对Gr17、Oliver30、Eil51、Eil76和Krob100等测试数据进行实验,证明了在该策略的指导下改进的两种交配算子具有更好的表现。