用一种含正交设计交叉算子的遗传算法求解TSP  

With a Orthogonal Design Crossover Operator for Genetic Algorithms in Solving Traveling Salesman Problem

作　　者：张晓玲[1] 刘洪基[2] 雷连敏[1] 

机构地区：[1]大理学院数学与计算机科学学院,云南大理671003 [2]楚雄师范学院学报编辑部,云南楚雄675000

出　　处：《楚雄师范学院学报》2010年第9期1-7,共7页Journal of Chuxiong Normal University

摘　　要：本文通过分析TSP问题的特征,结合正交设计的思想,引入了一个遗传算法中新的交叉算子用于TSP求解。对新算子的有效性进行了证明并且给出了具体的实现方案,同时通过TSP Lib上的测试样例将该交叉算子和传统的交叉算子进行了比较。比较结果表明了本文的新交叉策略具有更大的优势。This paper analyzes the characteristic of TSP,combined with the ideas of orthogonal design,and presents a novel crossover operator in genetic algorithm for solving TSP.Validity proof of the proposed crossover operator is given and the implementation is presented.What is more,the crossover operator of orthogonal designing is compared with the traditional crossover operators based on cases which are from the TSP lib.The results demonstrate the proposed method in this paper has the greater advantage.

关 键 词：遗传算法(GAs) 旅行商问题(TSP) 正交设计 交叉算子 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]