进化算法是人们从大自然的生物进化过程所得到的灵感中发展起来的一种现代优化方法,它作为一种新型的、模拟生物进化过程的随机化搜索、优化方法,具有全局优化,隐并行性,鲁棒性强,操作简单等特点,近十几年来在组合优化领域得到了相当广泛的应用,并已在解决诸多典型的组合优化问题(如旅行商问题)中显示了良好的性能和效果。首先,针对一类特殊的大规模旅行商问题,比如说城市可以分为若干组、而且各组内城市之间的距离较小的问题,本文提出了一种基于聚类以及局部搜索技术的新进化策略来进行求解,并且证明了该算法的全局收敛性。其次,针对对称型的旅行商问题,本文设计了一个新的进化算法进行求解,该算法设计了新的交叉算子和变异算子来产生后代以及一种局部搜索方法来改善解的质量,同时被证明是全局收敛的。最后,数值模拟实验结果表明,本文所提出的这两个算法都是有效的。