基于GPU的并行遗传算法求解TSP问题

摘要

旅行商问题(Traveling Salesman Problem,TSP)是组合优化领域著名的NP问题,具有较为广泛的工程应用和现实生活背景.遗传算法是一种基于自然选择和基因遗传学原理的随机搜索算法,是一种寻求全局最优解而不需要任何初始化信息的高效优化方法.该算法具有全局寻优能力、适应性强、解决非线性问题具有较强的鲁棒性、对问题没有特定限制、计算过程简单、对搜索空间没有特殊要求、易于与其他算法结合等特点,在求解NP完全问题方面是一种较为有效的全局方法.然而遗传算法是一种概率搜索算法,其性能受种群规模、杂交和变异概率等控制参数的影响,而且有时会有收敛到局部最优解的现象.由于算法需要较大的种群规模,种群进化则需要不断的进行适应度函数计算,计算量相当大,因此,本文使用Compute Unified Device Architecture(CUDA)技术在Graphics Processing Unit(GPU)上并行实现遗传算法的所有操作并用于求解TSP旅行商问题.实验证明,该方法相对于串行遗传算法具有更强全局寻优能力以及耗费更少的操作时间.