求解TSP问题的一种改进遗传算法  

an Improved Genetic Algorithm for Solving TSP Problem

作　　者：李晓英[1] 万剑怡[1] 何首武[1] 

机构地区：[1]江西师范大学计算机信息工程学院,南昌330022

出　　处：《科技广场》2006年第2期10-12,共3页Science Mosaic

摘　　要：TSP问题是典型的NP完全问题,遗传算法是基于生物进化论的一种全局优化搜索算法。文中针对TSP问题传统遗传算法的缺点,提出了一种改进的遗传算法,并且给出选择、交叉和变异操作的设计。最后,以该算法求解中国旅行商问题(C-TSP)为例,表明该改进遗传算法具有更好的收敛性,可以得到更好的最优解。Traveling Salesman Problem （YSP） is a typical NP-Complete problem. Genetic Algorithm （GA） is a global optimal searching algorithm based on the biological evolutionism.in order to overcome the disadvantage of the traditional GA for solving the TSP problem, we＇present an improved GA and design Selection Operation Crossover Operation and Mutation Operation of the improved GAoIn the end, the experimental results of China TSP（C-TSP） based on the improved GA indicate that the improved GA has a better convergence property and can induce better optimal results.

关 键 词：遗传算法 TSP问题 C-TSP(中国旅行商问题) 

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