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

摘要：

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

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

所属期刊栏目：28

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60573066;广东省自然科学基金5003346;教育部留学回国人员科研启动基金教外司留[2006]331

在线出版日期：2007-06-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：2408-2411