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

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

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

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

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