遗传算法是模仿生物进化和自然选择机理,模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。近年来,遗传算法由于在解决各类最优化问题时表现出的鲁棒性、全局性、隐含并行性和自适应性而成为一种应用日益广泛的智能优化算法。旅行商问题(TSP)是组合优化领域中的一个典型NP完全问题,是诸多领域内出现的多种复杂问题的集中概括和简化形式。快速、有效地解决TSP问题有着较高的理论意义和实际应用价值。本文根据TSP问题的特点和当前研究情况,选用遗传算法对它进行求解。介绍了遗传算法的原理及基本实现技术,着重阐述了遗传算法的特性和影响遗传算法性能的因素,针对TSP问题对遗传算法进行相应的改进。首先针对传统遗传算法中初始种群平均适度度低的缺点,设计了一种贪婪选择策略代替随机化生成初始种群,从而提高初始种群的质量；然后根据TSP问题种群个体编码的特点,结合贪婪算法,设计了一种贪婪交叉算子,使之既能有效地保留父代个体的优良基因,又能以较大的概率产生新的优良个体；在变异算子设计上,采用了两种变异算子相结合的方法,以提高种群的多样性；此外,在进化过程中算法引入了自适应策略来控制遗传参数的变化。本文使用改进的遗传算法对国际通用的TSP测试库TSPLIB中不同城市规模的数据进行测试,实验结果表明了该算法具有较高的执行效率。在以上改进遗传算法的基础上,结合主从式并行程序设计的特点,提出了工作站机群环境中基于MPI求解TSP问题的并行遗传算法。该算法采用按城市结点编号分配种群,并定期在主从进程中交换优良个体。最后利用VC++和MPICH并行库对算法进行了实现,通过分析多组实验数据表明该算法在求解速度和精度上均有所提高。