巡回旅行商问题(简称TSP)是一个具有广泛应用背景和重要理论价值的组合优化NP难题。遗传算法是一种模拟自然界生物进化的搜索算法,由于它简单易行、鲁棒性强,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且已在众多领域得到了实际应用,取得了令人瞩目的成果,引起了广大学者和工程人员的关注。在遗传算法研究中,TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。众所周知,遗传算法有两个严重的缺点,即容易过早收敛,以及在进化后期搜索效率较低。本文针对遗传算法上述的两个缺点,对传统的遗传算法进行改进,提出了多种群自适应模拟退火遗传算法求解巡回旅行商问题。该算法采用自适应交叉概率进行轮盘赌最优个体保留和自适应变异概率进行多种变异方法相结合的混合变异,将全局搜索能力较强的遗传算法引入局部搜索能力较强的模拟退火算法,并且同多种群并行遗传进化思想有机地结合起来。各个子种群独立进化到一定代数后,通过种群间的相互交叉和迁移,实现种群分级,这种分级的方法可以使优秀个体中的优良基因片通过相互之间的交叉从而得到保留和优化组合,又可以使低劣个体中的优良基因片通过低劣个体之间大概率的交叉得到保留,甚至通过大概率的变异使低劣的基因片得到改良。做这样处理时,可以选取和保留每个子种群的优秀个体,并在保持优秀个体进化的稳定性的同时加快进化速度,避免单种群进化过程中出现的过早收敛现象。本文使用改进后的算法,针对CHN31、ATT48和EIL51的旅行商问题进行求解,仿真结果表明,该算法避免了遗传算法中存在的过早收敛收敛的问题,增强了算法的全局收敛性,并且提高了算法的收敛速度。