多核CPU環(huán)境遺傳算法求解TSP研究.pdf

1、多核CPU經(jīng)過多年的發(fā)展,現(xiàn)已在市場中占據(jù)主導地位。多核CPU具有很高的性能,它的應用普及,給我們用戶帶來了機遇,但也帶來了挑戰(zhàn)。過去大部分的算法與軟件并沒有針對多核CPU進行優(yōu)化,因此并不能充分利用其蘊藏的計算能力;要從多核CPU中真正獲得好處,程序線程化為一個可行的途徑。多核計算技術較硬件技術落后不少,但眾多學者仍在孜孜研究中,并在多核并行技術及“低碳”綠色計算等方面取得一些成果。本文基于多核CPU對遺傳算法求解旅行商問題(TSP)

2、進行了研究。
　　 TSP是組合優(yōu)化問題領域一個經(jīng)典的NP-難問題,它的難解性致使學者們不得不尋找更先進的算法對其進行求解。近年來利用智能算法求解TSP成為研究的熱點,遺傳算法即為其中之一。針對遺傳算法求解TSP的特點及存在的缺陷,筆者基于多核平臺對其進行優(yōu)化與改進。
　　 求解TSP的遺傳算法具有良好內在并行性,構成算法的各算子內均具有強獨立性,不存在或存在較少的數(shù)據(jù)相關,稍作優(yōu)化即可進行并行計算,并以多線程形式于多核

3、平臺上執(zhí)行。通過對基本算子的線程化對算法進行初步優(yōu)化。高速緩存(cache)是CPU重要的片上資源,而程序具有良好空間局部性好是cache效用得以發(fā)揮的前提,否則爭用問題將嚴重影響程序的效率。利用遺傳算法求解TSP時需進行大量的內存訪問,這使cache的爭用在所難免,在多線程環(huán)境下猶為如此。通過對算法訪存順序的改變來提高其算法的程序空間局部性,降低對cache的爭用,減少cache缺失,從而提高程序效率,實現(xiàn)對算法再提速。
　　

4、 標準遺傳算法存在“早熟”及局部搜索能力差的缺點,利用其求解TSP極易求得次優(yōu)解。提出一個求解TSP的改進遺傳算法,其通過小生境技術來維護種群的多樣性,防止“早熟”;利用一個針對TSP改進的模擬退火算子增強算法的局部搜索能力。多組實例表明,改進算法效果明顯,求解質量有較大提高。在此基礎上,重新對算法并行性進行分析,對模擬退火部分進行了并行化優(yōu)化,實現(xiàn)新算法對多核環(huán)境的適應,保證對其的有效加速。
　　 考慮多種群算法求解TSP的有