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

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

多核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.