文档名：基于GPU的并行遗传算法求解TSP问题
旅行商问题(TravelingSalesmanProblem,TSP)是组合优化领域著名的NP问题,具有较为广泛的工程应用和现实生活背景.遗传算法是一种基于自然选择和基因遗传学原理的随机搜索算法,是一种寻求全局最优解而不需要任何初始化信息的高效优化方法.该算法具有全局寻优能力、适应性强、解决非线性问题具有较强的鲁棒性、对问题没有特定限制、计算过程简单、对搜索空间没有特殊要求、易于与其他算法结合等特点,在求解NP完全问题方面是一种较为有效的全局方法.然而遗传算法是一种概率搜索算法,其性能受种群规模、杂交和变异概率等控制参数的影响,而且有时会有收敛到局部最优解的现象.由于算法需要较大的种群规模,种群进化则需要不断的进行适应度函数计算,计算量相当大,因此,本文使用ComputeUnifiedDeviceArchitecture(CUDA)技术在GraphicsProcessingUnit(GPU)上并行实现遗传算法的所有操作并用于求解TSP旅行商问题.实验证明,该方法相对于串行遗传算法具有更强全局寻优能力以及耗费更少的操作时间.
作者：江建文王纪凯陈宗海
作者单位：中国科学技术大学自动化系,安徽合肥,中国,230000
母体文献：第20届中国系统仿真技术及其应用学术年会(20thCCSSTA2019)论文集
会议名称：第20届中国系统仿真技术及其应用学术年会(20thCCSSTA2019)
会议时间：2019年8月1日
会议地点：合肥
主办单位：中国自动化学会,中国系统仿真学会
语种：chi
分类号：
关键词：旅行商问题 并行遗传算法 图形处理器
在线出版日期：2020年7月21日
基金项目：
相似文献
相关博文
- 文件大小:
- 1.2 MB
- 下载次数:
- 60
-
高速下载
|
|
