摘要：对旅行商（TSP）问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例（城市规模从14到1000）进行了计算机仿真,结果表明算法是有效的.

关键词：遗传算法 旅行商问题 全局收敛性 

单位：西安电子科技大学理学院数学系; 西安710071; 西安电子科技大学计算机学院; 西安710071