基于GPU的并行智能算法.pdf

1、大部分智能優(yōu)化算法在求解各種優(yōu)化問題時，隨著問題規(guī)模即維數(shù)的增加，性能迅速惡化，而現(xiàn)實世界中許多大規(guī)模全局優(yōu)化問題隨著科技的發(fā)展其問題的規(guī)模不斷增加。因此，如何提高智能算法在求解復(fù)雜函數(shù)優(yōu)化問題上的性能是當(dāng)前計算智能領(lǐng)域的研究熱點。串行的智能優(yōu)化算法，面對大規(guī)模復(fù)雜優(yōu)化問題具有挑戰(zhàn)性，設(shè)計一種快速穩(wěn)定高精度的算法勢在必行。
　　圖形處理器(GPU)在數(shù)值計算能力和存儲器帶寬上相對CPU有明顯的優(yōu)勢，而它在成本和功耗上也不需要付出太

2、大代價，從而為這些復(fù)雜函數(shù)問題的快速求解提供了一種新的解決方案。當(dāng)前，計算機(jī)行業(yè)正在從只使用CPU向 CPU與 GPU異構(gòu)并行的“協(xié)同處理”方向發(fā)展。CPU和GPU分工合作，由 GPU處理數(shù)值并行計算的任務(wù)，由 CPU進(jìn)行復(fù)雜邏輯和事務(wù)處理等串行計算，從而可以最大限度地利用計算機(jī)的處理能力，既提高了程序性能，又節(jié)省了成本和資源，是一種革命性的進(jìn)步。
　　由于復(fù)雜函數(shù)具有各種復(fù)雜的特征，即使將這些基本算法進(jìn)行改進(jìn)之后能夠找到最優(yōu)解，

3、計算時間也是非常長。因此，本文首先將這些基本的智能算法進(jìn)行改進(jìn)，設(shè)計了四種改進(jìn)的串行算法，然后將這些改進(jìn)的串行算法在GPU設(shè)備上使用CUDA編程實現(xiàn)，既加快了算法的計算速度，也提高了算法的計算精度。
　　本文所作的工作主要有以下幾點：
　?。?）本文提出了一種基于自適應(yīng)變異策略的混沌布谷鳥搜索算法，利用混沌機(jī)制初始化種群和處理超過界限值的新生個體；利用自適應(yīng)變異策略根據(jù)選擇概率選擇部分解變量進(jìn)行動態(tài)調(diào)整；提出維更新策略和自適

4、應(yīng)發(fā)現(xiàn)概率。通過對20個著名的復(fù)雜函數(shù)進(jìn)行測試，實驗結(jié)果表明:當(dāng)GPU為 NVIDIA GeForce310時，PAMSCCS和串行算法相比，平均加速比達(dá)到3倍左右，最高加速比達(dá)到8倍以上；當(dāng)GPU為NVIDIA GeForce GTX970時，PAMSCCS的平均加速比為26，最高加速比為81，使算法性能得到大幅度提升。
　?。?）針對智能算法在求解復(fù)雜高維函數(shù)問題時易出現(xiàn)收斂速度慢或局部最優(yōu)的問題，本文引入一種改進(jìn)的入侵雜草優(yōu)

5、化算法(IIWO)，將基本IWO算法進(jìn)行改進(jìn)和相應(yīng)地調(diào)整：將每株雜草新生種子個數(shù)設(shè)置為固定參數(shù)，將初始步長和最終步長改成自適應(yīng)步長，對超過界限值的解重新初始化，同時將該算法用于GPU平臺，提出了基于GPU并行的改進(jìn)的雜草優(yōu)化算法(PIIWO)。通過對CEC’2010多個高維函數(shù)的求解，結(jié)果表明，與同類算法相比，本文所設(shè)計的IIWO性能更佳，具有更高的收斂速度和計算精度；而并行算法PIIWO比串行算法IIWO不僅尋優(yōu)迭代次數(shù)更少，而且有更

6、好的尋優(yōu)精度和顯著的加速比，在低端GPU上能獲得平均3倍左右的加速比，在高端GPU上能獲得平均22倍、最高38倍以上的加速比。
　?。?）針對遺傳算法易陷入局部最優(yōu)和后期尋優(yōu)精度不高等缺陷，本文對遺傳算法進(jìn)行改進(jìn)和完善，引入兩階段選擇操作、隨機(jī)多演化交叉算子、自適應(yīng)高斯變異算子、量子行為算子，提出一種基于GPU的并行量子行為遺傳算法(PQBGA)。通過對25個高維復(fù)雜函數(shù)的優(yōu)化，結(jié)果顯示，QBGA的性能不僅遠(yuǎn)遠(yuǎn)優(yōu)于基本遺傳算法，在

7、收斂精度和穩(wěn)定性方面也優(yōu)勝于其它8個著名的智能優(yōu)化算法，表明該算法的可行性和有效性；將QBGA在 GPU平臺上實現(xiàn)，并在兩種GPU上與CPU算法進(jìn)行比較，最高加速比分別達(dá)到了18倍和626倍，大大提高了算法的運(yùn)行速度和執(zhí)行效率，獲得了非常滿意的加速效果。
　?。?）本文使用樣條差分方法離散一維熱傳導(dǎo)方程，從而轉(zhuǎn)化為線性方程組的形式，然后將線性方程組轉(zhuǎn)化為一個無約束的優(yōu)化問題，最后通過使用并行混合粒子群(PHPSO)算法進(jìn)行求解。P