熊大衛(wèi),胡 建,陳 園

(西南民族大學計算機科學與工程學院,四川 成都 610041)

群體智能算法已被應用于眾多領域,例如數(shù)據(jù)分析[1]、半結構化數(shù)據(jù)查詢優(yōu)化[2]、圖像分割[3]等.但是,由于群體中的個體間相互作用、包含多個隨機操作符等原因,導致群體智能算法具有復雜的隨機性和動態(tài)性,計算時間較長.因為個體間存在內在并行性,故可采用圖形處理器(Graphics Processing Unit,GPU)通過并行計算的方式[4]加速群體智能算法.

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是群體智能算法中最具代表性的一種,目前主要應用于如下幾個領域:神經網絡訓練,如文獻[5]利用PSO算法調整深度信念網絡的內部參數(shù),提出了一套輸電線路電暈損耗預測方法,文獻[6]基于PSO算法提出優(yōu)化BP神經網絡的PID控制算法;函數(shù)優(yōu)化,如文獻[7]提出多策略混合進化的PSO算法求解大規(guī)模函數(shù)優(yōu)化問題,文獻[8]提出一種利用種群進化的改進PSO算法求解多模態(tài)函數(shù)優(yōu)化問題;路徑規(guī)劃,文獻[9]提出利用差分進化算法改進的PSO算法,求解動態(tài)窗口法的動態(tài)路徑規(guī)劃問題,文獻[10]基于一種改進的PSO算法,求解多目標點路徑規(guī)劃問題.與其他群體智能算法一樣,可采用GPU的CUDA架構(Compute Unified Device Architecture,CUDA)[11],通過并行計算的方式加速PSO,例如文獻[12]以PSO算法為例,研究如何利用CUDA平臺進一步發(fā)揮群體智能算法的并行性優(yōu)勢;文獻[13]利用CUDA架構并行實現(xiàn)了柯西振蕩粒子群優(yōu)化算法(CO-PSO);文獻[14]應用PSO算法優(yōu)化克里金算法中的克里金參數(shù),并通過CUDA架構加速PSO算法以提高插值效率.

近年人工智能飛速發(fā)展,作為深度學習領域首選編程語言的Python語言使用率也隨之激增.照此趨勢,Python相較于其他程序語言的絕對主流地位與PSO在高維復雜優(yōu)化問題領域的卓越性能都預示這兩者的結合趨于必然.但據(jù)我們調研,未見PSO算法基于Python語言實現(xiàn)GPU加速的報道.

對此,本文基于Python語言,以CUDA架構、Numba庫[15]為工具提出了利用GPU加速的改進PSO算法,并經實驗證明能達到有效的加速效率.這將為基于GPU和Python的PSO并行加速提供有價值的參考.

1 PSO算法簡介

PSO算法稱解空間中的點為粒子,所有粒子構成種群.各粒子具有初始速度和位置,并根據(jù)種群的經驗來調整自己的運動,最終找到全局最優(yōu)位置[16],其偽代碼如下所示.

Algorithm PSO1: Initial Swarm in CPU //初始化種群2: For i←1 to Iterations:3: For j←1 to P:4: Evaluate Particle //粒子評價5: Check and Update Pbest //更新個體歷史最優(yōu)解6: Check and Update Gbest //更新全局最優(yōu)解7: Forj←1 to P:8: UpdateVelocity and Position //粒子升級9: Return the bestPosition and Fitness

其中,Swarm表示種群,Iterations為迭代代數(shù),P為種群大小,Particle表示粒子,Pbest和Gbest分別表示個體歷史最優(yōu)解和全局最優(yōu)解,Velocity和Position分別表示速度和位置,按照公式(1)與公式(2)進行更新,Fitness為適應度值.

(1)

(2)

上述公式中,當前維數(shù)d=1,2……D,D表示最大維數(shù);t為當前代數(shù);第i個粒子的速度向量記為Vi=(Vi1,Vi2……Vid),位置向量記為Xi=(Xi1,Xi2……Xid),其中i=1,2……P;待優(yōu)化問題邊界根據(jù)測試函數(shù)設定記為[Xmin,Xmax]D,速度和位置更新后,若Xid>Xmax,則Xid=Xmax;若Xid

在不同版本PSO算法中參數(shù)取值各有不同,但參數(shù)值的選取并不會在很大程度上影響本文所關注的算法運行時間.本文為簡便起見,參數(shù)設置如下:慣性因子w表示上一代粒子的速度對當代粒子速度的影響,使粒子保持運動的慣性和搜索擴展空間的趨勢,較大的w有利于全局搜索、跳出局部最優(yōu)解,而較小的w有利于局部搜索、讓算法快速收斂到最優(yōu)解,w的典型取值范圍是[0,1.5],本文按照基本粒子群算法將w設置為0.5[17];認知因子c1表示粒子下一步動作來源于自身經驗部分所占的權重,社會因子c2表示粒子下一步動作來源于其它粒子經驗部分所占的權重,當c1和c2都不為0時算法更容易保持收斂速度和搜索效果的均衡,本文將c1和c2分別設置為1和2[18];隨機數(shù)r1與r2為服從[0,1]上的均勻分布隨機數(shù),加入此項以提升算法搜索的隨機性.

2 基于GPU和Python的改進粒子群優(yōu)化算法

2.1 PSO-CUDA算法

Python作為一種解釋性語言運行速度較慢,本文選擇Numba庫通過即時編譯技術(Just In Time,JIT)[19]對程序進行加速.

相較于標準PSO算法,PSO-CUDA算法中種群初始化方式不變,將粒子評價、更新個體歷史最優(yōu)解、粒子升級三個部分改用GPU并行計算分別完成.由于全局最優(yōu)解的更新過程中涉及大量的邏輯判斷,雖然GPU有邏輯運算能力,但GPU不具備CPU的分支預測能力,只能順序執(zhí)行邏輯分支,且過程中可能因為Warp Divergence[20]產生不必要的時間開銷,故將更新全局最優(yōu)解的步驟置于CPU中完成.

PSO-CUDA算法流程可概括如下:1)于CPU中完成種群及所需參數(shù)初始化;2)拷貝種群至GPU;3)于GPU中調用核函數(shù)完成粒子評價、更新個體歷史最優(yōu)解、粒子升級;4)拷貝種群至CPU;5)更新全局最優(yōu)解.基于Python語言實現(xiàn)的CUDA版本改進PSO算法(簡稱PSO-CUDA)的偽代碼如下所示.

Algorithm PSO-CUDA1: Initial Swarm in CPU2: Set TPB as threads per block,BPG as blocks per grid3: Fori←1 to Iterations:4:cuda.to_device(Swarm) //拷貝種群至GPU5: @cuda.jit //添加JIT修飾符6: Kernel,TPB? //調用核函數(shù)完成粒子評價、更新個體歷史最優(yōu)解、粒子升級7:cuda.copy_to_host(Swarm) //拷貝種群回CPU8: Check and Update Gbest //更新全局最優(yōu)解9: Return the bestPosition and Fitness

其中:Kernel為GPU核函數(shù),TPB為線程塊大小,值為1 024,BPG為網格大小,其值由種群粒子數(shù)除以TPB向上取整得到.調用Kernel的執(zhí)行配置為,表示GPU并行啟動TPB*BPG個線程.

2.2 Kernel核函數(shù)

PSO-CUDA算法分配至GPU中的計算任務主要由Kernel控制,考慮到GPU的邏輯運算能力不及CPU,如何合理為GPU分配計算任務、避免復雜邏輯是算法設計的關鍵.按照標準PSO算法邏輯,種群中個體升級都需要當前Gbest,但PSO-CUDA中的Gbest更新于CPU中完成、個體升級于GPU中完成,這將導致個體升級過程中不可避免地存在一次數(shù)據(jù)拷貝.

為解決這一問題,PSO-CUDA算法將Kernel核函數(shù)中的粒子升級步驟前置,使當代粒子直接利用上代得到的Gbest進行升級(首次迭代除外),以此減少數(shù)據(jù)拷貝的時間開銷.PSO-CUDA算法中Kernel的流程如下所示.

Kernel(粒子升級、評價粒子、更新個體歷史最優(yōu)解)1: Launch threads as the number of BPG*TPB2: AssignSwarm to threads3: For eachParticle in thread (Parallelly) do:4: Whilet!= 0: //避免首次迭代中的粒子升級5: UpdateVelocity and Position //粒子升級7: Evaluate Particle //粒子評價8: Check and UpdatePbest //更新個體歷史最優(yōu)解

種群拷貝至GPU后被分配至不同線程,每個線程將獨立地調用Kernel核函數(shù)進行并行計算.Kernel流程可概括如下:1)粒子升級;2)粒子評價;3)更新個體歷史最優(yōu)解.Kernel完成上述處理后,將種群拷貝至CPU完成后續(xù)步驟.

3 實驗

3.1 實驗環(huán)境及參數(shù)設置

實驗旨在通過對比PSO算法與PSO-CUDA算法在同條件下的耗時,驗證后者加速效率.

實驗環(huán)境:CPU為Intel(R) Xeon(R) Gold-6130H 2.10 GHz,GPU為Tesla P100 16 GB,CUDA版本為11.4,操作系統(tǒng)為Ubuntu 18.04.

為進行充分驗證,實驗在不同粒子數(shù)、維數(shù)、測試函數(shù)下進行:粒子數(shù)P取值為10、100、1 000、4 000;維數(shù)D取值為10、100、1 000、5 000,測試函數(shù)邊界為[-10,10]D,迭代次數(shù)Iterations為100.實驗獨立運行10次,實驗結果取10次結果的均值.

為體現(xiàn)公平性與普適性,本實驗選取群體智能算法性能測試常用的四個基準測試函數(shù),其中,Sphere函數(shù)是常用的新算法的標準測試函數(shù),其特點是全局最優(yōu)解唯一,由D個定義域相同的自變量求平方和得到[21];Rosenbrock函數(shù)也稱山谷函數(shù)或香蕉函數(shù),是基于梯度的優(yōu)化算法的一個流行測試函數(shù),其函數(shù)圖像呈現(xiàn)為單峰,全局最小值位于圖像中最低點,但即使這個最低點很容易找到,其收斂到最低限度也比較困難[22];Rastrigin函數(shù)基于DeJong函數(shù),存在多個局部最優(yōu)解,增加了一個余弦調制傳遞函數(shù)來產生頻繁的局部最小值,其特點是函數(shù)極小值出現(xiàn)的位置是有規(guī)律的,常用于解決一些規(guī)律性問題[23];Schwefel函數(shù)同樣存在多個局部最優(yōu)解,很容易引導算法陷入局部最優(yōu)[24].測試函數(shù)表達式如表1所示.

表1 測試函數(shù)及表達式Table 1 Test functions and formulas

3.2 實驗結果與分析

實驗結果如表2和圖1所示,其表明:

表2 算法耗時表Table 2 Algorithm time table

圖1 算法耗時圖Fig.1 Algorithm time graph

1)當D和P較小時,如[D,P]=[10,10]、[10,100]、[100,10],PSO算法的計算速度快于PSO-CUDA算法.這種現(xiàn)象主要是因為CPU主頻高、Cache大,當計算規(guī)模較小時,CPU的浮點運算比GPU表現(xiàn)更好[25].此外CUDA core的啟動和終止、數(shù)據(jù)拷貝等也會造成時間開銷,故在計算規(guī)模較小時,出現(xiàn)CUDA程序計算速度慢于CPU程序的情況.

2)隨著D和P的增大:D=10時,PSO-CUDA算法的速度從P=1 000開始快于PSO算法;D=100時,PSO-CUDA算法的速度從P=100開始快于PSO算法;D≥1 000時的所有配置組,PSO-CUDA算法都體現(xiàn)出較好的速度優(yōu)勢.[D,P]=[100,4 000]時PSO-CUDA算法的速度優(yōu)勢最大,達到PSO算法的3.44倍.

4 總結

在PSO算法并行計算提速需求下,本文提出了基于GPU和Python的PSO算法,將計算量較大的粒子升級、粒子評價、更新個體歷史最優(yōu)解進行GPU加速,經實驗驗證, PSO-CUDA算法在維數(shù)和粒子數(shù)較小時速度表現(xiàn)差于PSO算法,PSO-CUDA算法的速度優(yōu)勢隨著維數(shù)、粒子數(shù)的增加而逐漸體現(xiàn),并在維數(shù)為100、粒子數(shù)為4 000時達到了PSO算法3.44倍的加速效果.

本文雖然研究了基于GPU的PSO加速問題,但由于群體智能算法的復雜性,該問題仍然是開放性的,仍有一些可研究的問題,例如:改變PSO算法的并行層面,從維度、核函數(shù)等方面并行;在其他版本的PSO算法中驗證GPU并行的有效性;把本文的并行方法擴展應用于其他群體智能算法中.