多核CPU经过多年的发展,现已在市场中占据主导地位。多核CPU具有很高的性能,它的应用普及,给我们用户带来了机遇,但也带来了挑战。过去大部分的算法与软件并没有针对多核CPU进行优化,因此并不能充分利用其蕴藏的计算能力;要从多核CPU中真正获得好处,程序线程化为一个可行的途径。多核计算技术较硬件技术落后不少,但众多学者仍在孜孜研究中,并在多核并行技术及“低碳”绿色计算等方面取得一些成果。本文基于多核CPU对遗传算法求解旅行商问题(TSP)进行了研究。　　 TSP是组合优化问题领域一个经典的NP-难问题,它的难解性致使学者们不得不寻找更先进的算法对其进行求解。近年来利用智能算法求解TSP成为研究的热点,遗传算法即为其中之一。针对遗传算法求解TSP的特点及存在的缺陷,笔者基于多核平台对其进行优化与改进。　　 求解TSP的遗传算法具有良好内在并行性,构成算法的各算子内均具有强独立性,不存在或存在较少的数据相关,稍作优化即可进行并行计算,并以多线程形式于多核平台上执行。通过对基本算子的线程化对算法进行初步优化。高速缓存(cache)是CPU重要的片上资源,而程序具有良好空间局部性好是cache效用得以发挥的前提,否则争用问题将严重影响程序的效率。利用遗传算法求解TSP时需进行大量的内存访问,这使cache的争用在所难免,在多线程环境下犹为如此。通过对算法访存顺序的改变来提高其算法的程序空间局部性,降低对cache的争用,减少cache缺失,从而提高程序效率,实现对算法再提速。　　 标准遗传算法存在“早熟”及局部搜索能力差的缺点,利用其求解TSP极易求得次优解。提出一个求解TSP的改进遗传算法,其通过小生境技术来维护种群的多样性,防止“早熟”;利用一个针对TSP改进的模拟退火算子增强算法的局部搜索能力。多组实例表明,改进算法效果明显,求解质量有较大提高。在此基础上,重新对算法并行性进行分析,对模拟退火部分进行了并行化优化,实现新算法对多核环境的适应,保证对其的有效加速。　　 考虑多种群算法求解TSP的有效性,提出一个基于多核CPU环境的多种群算法方案。其于每一个CPU内核中部署一个或多个种群,并使各种群独立地执行遗传算法。种群间通过抽取各自最优个体构建共享基因库的方式进行信息交流,共享基因库则通过作用于遗传操作算子的方式影响算法的执行。实验结果表明,相对于传统的多种群算法,本文算法在求解质量有一定的提高,而在效率上有较大优势。