作　　者： ; ; ; ; ;

机构地区： 中山大学信息科学与技术学院计算机科学系

出　　处： 《计算机工程与设计》 2007年第10期2408-2411,共4页

摘　　要： 旅行商问题(TSP)是一类典型的NP完全问题,遗传算法(GA)是求解这类问题的常用方法之一。由于该问题的解是一种特殊的序列,一些典型的GA交配方法在求解该问题时的性能并不理想。通过多次对比两种常用的GA交配方法与3种专门为TSP作优化的交配方法,总结了一种对旅行商问题的交配算子的设计策略,即注重对双亲的边继承以及加入适当的贪心控制策略。通过对Gr17、Oliver30、Eil51、Eil76和Krob100等测试数据进行实验,证明了在该策略的指导下改进的两种交配算子具有更好的表现。 The traveling salesman problem （TSP） is a well-known NP complete problem, while the genetic algorithm （GA） is one of the ideal methods in solving it. Because the solution of TSP is a special gene permutation, GA with some representative crossover operators is quite unsatisfied in solving it. By comparing two common crossover methods and the other three for TSP specially, a strategy for designing the crossover operators for TSP is proposed, which is inheriting the edges from parents and selecting better edges greedy. And it is proved that with the strategies, the two improved crossover operators performs much better than before, by the benchmarks of Gr17, Oliver30, Eil51, Ei176andKrob100.

关 键 词： 难题 旅行商问题 进化计算 遗传算法 交配算子

领　　域： [自动化与计算机技术] [自动化与计算机技术]