基于CUDA的并行離散粒子群圖頂點(diǎn)著色算法研究.pdf

1、圖的頂點(diǎn)著色問題是離散數(shù)學(xué)和圖論的一個(gè)熱門課題，也是一個(gè)經(jīng)典的NP完全問題，目前仍然沒有精確的算法可以在多項(xiàng)式時(shí)間內(nèi)求解該問題。但是，圖頂點(diǎn)著色算法在頻率分配，最短路徑，醫(yī)學(xué)圖像加密等諸多領(lǐng)域都具有廣泛的應(yīng)用。因此，圖頂點(diǎn)著色問題的算法研究具有重要的理論意義和應(yīng)用價(jià)值。
　　近年來，基于群智能的粒子群優(yōu)化算法得到了許多學(xué)者的關(guān)注，粒子群優(yōu)化算法憑借極強(qiáng)的全局尋優(yōu)能力在許多研究領(lǐng)域得到廣泛應(yīng)用。本文將粒子群算法應(yīng)用于求解圖頂點(diǎn)著色問

2、題，提出了一種離散粒子群圖頂點(diǎn)著色算法。該算法改進(jìn)了傳統(tǒng)的粒子群算法只能求解連續(xù)型問題的限制，在離散型問題的解空間內(nèi)重新定義了粒子的位置，粒子的速度以及其更新方式，以及粒子群算法中的加法、減法以及乘法等運(yùn)算。采用美國(guó)離散數(shù)學(xué)與理論計(jì)算研究中心(DIMACS)的64個(gè)圖例對(duì)算法進(jìn)行了驗(yàn)證，并通過與HPGA等其它啟發(fā)式算法比較，證明了本文算法的有效性，可以高效搜索DIMACS圖例的最小著色數(shù)。
　　此外，由于圖的頂點(diǎn)著色問題擁有指數(shù)級(jí)

3、的解空間，假如圖G有N個(gè)頂點(diǎn)，用K種顏色進(jìn)行頂點(diǎn)著色，著色方案的解空間為K的N次方。因此，當(dāng)求解問題規(guī)模N較大時(shí)，必須提高粒子群算法的速度才能高效的搜索指數(shù)級(jí)的解空間。本文利用基于GPU的并行計(jì)算平臺(tái)CUDA對(duì)算法進(jìn)行加速，提出基于CUDA的并行離散粒子群圖頂點(diǎn)著色算法。算法實(shí)現(xiàn)了并行的粒子種群初始化，粒子速度、位置更新，適應(yīng)度值計(jì)算，并行歸約求解全局最優(yōu)粒子，很大程度上提高了算法的效率。尤其相比于串行比較歸約出全局最優(yōu)粒子的時(shí)間復(fù)雜度