多核CPU环境下遗传算法求解TSP加速策略研究  

Acceleration strategies for solving TSP by genetic algorithm in multi-core CPU plat

作　　者：唐天兵[1] 谢祥宏[1] 黄柏雄[1] 

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004

出　　处：《广西大学学报（自然科学版）》2011年第2期292-296,共5页Journal of Guangxi University（Natural Science Edition）

基　　金：国家自然科学基金资助项目(50605010);广西教育厅科研资助项目(200911LX15);广西教育厅研究生创新资助项目(105931003038)

摘　　要：多核CPU已成为各类型计算机的主流配置,针对多核环境的软件设计与算法研究却相对滞后。遗传算法是一种鲁棒性极强的智能型算法,其在求解NP(NP-难、NP完全)问题时有着独特的优势。旅行商问题(TSP)是一个经典的NP-难问题,也是计算机学科理论研究中的热点。为促进遗传算法在多核平台上的应用,提高其求解TSP的适应性及效率,基于多核CPU环境对遗传算法求解TSP进行了研究,设计了通过多线程与考虑程序数据局部性的加速策略。多个TSP实例说明了设计算法的有效性,加速效果明显。Multi-core CPU has become the mainstream of all types of computer conngurauons, out software design and algorithm research for multi-core environment have lagged behind. Genetic Algo-rithm （GA） is a robust intelligent algorithm and has a unique advantage in solving NP （NP-hard or NP-complete） problem. Traveling salesman problem （TSP） is a classic NP-hard problem, where theoretical computer science research focus. To better implement GA in multi-core plat and further guarantee the adaptability and efficiency for solving TSP, an acceleration strategies, which considers the data locality and is achieved by multi-threaded, is proposed. Several TSP instances show the effectiveness of the algorithm with obvious acceleration ratio.

关 键 词：多核 遗传算法 旅行商问题 多线程 数据局部性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]