旅行商问题(TSP)在现实生活中的各种工程实践中都得到了广泛的应用,它属于一种组合优化问题,也是一个NP问题,由于其具有广泛的实用性,TSP问题也越来越得到了学术界的关注。虽然已经有许多针对TSP问题的解决方法,但传统的方法求解效果不太理想,而遗传算法却已经被证明是一种很高效的TSP求解算法。本文提出了一种称为并行模拟退火遗传算法的改进遗传算法,用来解决TSP问题,具体研究内容如下:首先介绍了遗传算法的理论基础,主要描述了遗传算法的模式定理、积木块假设欺骗问题、隐形并行性问题和对遗传算法的收敛性分析,描述了遗传算法的基本流程。其次描述了典型的组合优化问题TSP问题的数学模型与主要的求解算法;介绍了粗粒度并行遗传算法的概念,参数及影响其并行性能的几个主要因素,设计了解决TSP问题的粗粒度并行遗传算法的实现流程,并通过仿真算例验证该改进算法的有效性。最后引入了模拟退火算法并结合粗粒度并行遗传算法提出了并行模拟退火遗传算法来改进现有的遗传算法。该算法利用了种群熵和基因座多样性来测试种群的多样性,并在遗传算法的复制操作过程中调整适应度值以提高种群的多样性。模拟退火遗传算法具有高效的局部搜索能力,可以在一定程度上提高遗传算法的收敛速度,并且Metropolis接受准则也可以帮助遗传算法避免过早收敛于局部最优解。