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

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

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

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