作为一种重要的优化算法,进化算法是借鉴生物进化机制形成的一种随机搜索算法.因不需目标函数的可微信息,又有隐并行性,故用于求解一些传统优化算法难解决的问题.旅行商问题(TSP)正是经典的NP-hard组合优化问题之一,许多实际问题经过简化均可建模为TSP,因此,具有全局收敛性的遗传算法成为人们解决TSP的主要方法之一.本文首先提出了一个新的求解TSP的进化算法,设计了一种简单的整数编码方式,使得路径与某整数一一对应,优点是每个个体都可行,运算量少,便于设计遗传算子;其次,量子遗传算法(QIGA)利用其高效的搜索能力和较好维持种群多样性的能力被运用到许多难求解的优化问题,因此,深入研究QIGA是必要的.本文通过引入新的可控旋转门操作及终止条件来进一步改善QIGA的性能.改进的QIGA不仅可以有效地跳出局部最优解,而且保持了解的质量与运行时间的一种平衡;再次,借助前面的工作,提出了一种求解TSP的新的QIGA,利用几率幅值编码,使得种群规模只有常规遗传算法的1/10~1/5,并适时引入了从边寻优的两阶段局部搜索,大大加快了算法的收敛速度;最后,不仅从理论上证明各新算法以概率1收敛,而且数值试验也表明了它们的有效性.