旅行商问题(Travel salesman problem,TSP)是一个具有广泛应用价值和重要理论意义的组合优化难题,目前被广泛地应用到工业、农业、国防、商业,特别是交通等领域,引起了数学、物理、计算机等诸多研究者的关注,而用遗传算法解决TSP问题成为当前研究热点问题之一。　　 用遗传算法求解TSP问题的基本思想是在一个大的空间范围内搜索和产生较优个体,这就产生了巨大时间复杂度和空间复杂度,而且收敛速度也受到巨大的影响。本文针对算法中这两个缺陷,用以下两种方法解决:一是用并行化以加速遗传算法的求解速度和加快收敛速度；二是提高算法搜索空间的能力。　　 首先,针对遗传算法中初始化种群操作的不确定性,提出一种基于经典遗传算法的初始化种群的方法。该方法按照随机搜索和启发式搜索相结合的方式,保证对空间搜索能力和种群中个体收敛速度。实验证明,该方法比传统遗传算法空间搜索能力更好,用以解决TSP问题得到的解更优。　　 其次,针对传统并行遗传算法通信时间较大,提出一种改进并行遗传算法模型。该模型通过主处理器接收从处理器中部分较优解作为初始化种群的部分个体,然后再进行遗传操作；减少了经典算法中每次迭代的通信时间,并通过迁移较优解确保了算法的收敛性并加速了最优解的产生。　　 最后,在改进遗传算法基础上,设计三种并行遗传算法求解TSP问题。该实验基于主从式模型、粗粒度模型、改进模型,利用实验室机群环境,利用消息传递接口(Message Passing Interrace,MPI),通过给出不同实验参数,验证在不同处理器数目下,改进模型的并行遗传算法的运行时间、收敛性、加速比和效率较之经典并行模型更优。