李寧,高鷹,翁金塔,曹燦,郭曉語,周燦基
(1.廣州大學(xué)計算機科學(xué)與網(wǎng)絡(luò)工程學(xué)院,廣州 510000;2.中國科學(xué)院信息工程研究所,北京 100000)
群體智能算法[1]是受到自然界生物啟發(fā),通過生物的生活方式和生活特性模擬設(shè)計的一種算法,可以解決經(jīng)濟、社會和自然科學(xué)等領(lǐng)域中各種復(fù)雜的優(yōu)化問題。常見的有粒子群優(yōu)化(par?ticle swarm optimization,PSO)算法[2-3],通過模擬鳥群的捕食行為來尋找最優(yōu)解;人工魚群算法(artificial fish swarm algorithm,AFSA)[4-5]是通過模仿魚類在水中的活動方式,總結(jié)出魚群的隨機、覓食、聚群、追尾等四種典型的行為來實現(xiàn)尋優(yōu);近年來也有許多新的群智能算法被提出,如象群優(yōu)化(elephant herding optimization,EHO)算法[6-7]源于自然界中大象的畜牧行為,可以用于解決全局無約束優(yōu)化問題。群智能算法具有簡單性、可擴展性和運行時間短等特點,在解決各種尋優(yōu)問題時,具有良好的操作性和強大的表現(xiàn)力。
緞藍(lán)園丁鳥優(yōu)化(satinbower bird optimization,SBO)算法[8]是Moosavi和Vahid Khatibi Bardsiri于2017年模擬自然界成年雄性緞藍(lán)園丁鳥的求偶行為而提出的一種新型群智能算法,并與自適應(yīng)神經(jīng)模糊推理系統(tǒng)(adaptive network-based fuzzy in?ference system,ANFIS)組合,有效地提高了軟件開發(fā)工作評估的準(zhǔn)確性。目前國內(nèi)對于該算法的改進(jìn)主要有基于自適應(yīng)t分布變異的緞藍(lán)園丁鳥優(yōu)化(satin bower bird optimization based on adaptive t-distribution mutation,tSBO)算法[9]和自適應(yīng)權(quán)重緞藍(lán)園丁鳥優(yōu)化(satin bower bird optimization based on adaptive weight,WSBO)算法[10]。t SBO引入了自適應(yīng)t分布變異算子,使用算法的迭代次數(shù)作為t分布的自由度參數(shù)來增強種群的多樣性,避免原算法陷入局部最優(yōu);WSBO通過自適應(yīng)權(quán)重的方法和改進(jìn)原算法中高斯布函數(shù)來提高原算法的搜索能力。這兩種改進(jìn)都在一定程度上提高了SBO算法的性能,但是這些改進(jìn)算法在求解精度和收斂速度上仍有很大的缺陷。
為了進(jìn)一步提高SBO算法的收斂精度,搜索能力和收斂速度,本文提出了一種基于PSO算法改進(jìn)的SBO(particle satin bower bird optimization,PSBO)算法。PSBO算法中引入了速度因子來增加算法的搜索速度和搜索能力;采用固定的慣性權(quán)重因子來提高算法的收斂性以及避免算法陷入局部最優(yōu)。通過求解8個典型復(fù)雜函數(shù)的最優(yōu)解來驗證PSBO算法的尋優(yōu)能力,并將其應(yīng)用到支持向量機(support vector machines,SVM)內(nèi)部參數(shù)優(yōu)化的問題中,驗證其有效性,拓寬了應(yīng)用范圍。
在自然界中,成熟的緞藍(lán)園丁雄鳥在其各自的領(lǐng)地上建造求偶亭,并配以各種裝飾來吸引雌鳥,然而并不是所有的成年雄鳥都能成功的構(gòu)建和維護求偶亭,存在求偶亭被破壞的情況[11]。根據(jù)緞藍(lán)園丁鳥求偶的原理,在自然界中,成熟的緞藍(lán)園丁雄鳥在其各自的領(lǐng)地上建造求偶亭,并配以各種裝飾來吸引雌鳥,然而并不是所有的成年雄鳥都能成功的構(gòu)建和維護求偶亭,存在求偶亭被破壞的情況[12]。根據(jù)緞藍(lán)園丁鳥求偶的原理,可以將SBO算法分為以下五個步驟:
(1)初始化種群。在可行域內(nèi)隨機生成一個包含N個求偶亭的初始種群,每個求偶亭的位置定義為D維,當(dāng)前迭代次數(shù)為t,最大迭代次數(shù)為Max It。
(2)計算每個求偶亭的吸引力。每個求偶亭的吸引力P i由公式(1)或得,fiti通過公式(2)計算:
式中:fiti表示i個求偶亭的適應(yīng)度值,f(xi)是第i個求偶亭的目標(biāo)函數(shù),每次迭代保證目標(biāo)函數(shù)的函數(shù)值不斷減小。
(3)更新種群位置。雄性園丁鳥根據(jù)歷史經(jīng)驗并利用信息共享機制,不斷調(diào)整求偶亭的位置,其位置更新公式如式(3)所示:
式中:為第t代第i個個體的第k維分量;x j通過輪盤賭選擇機制確定;xelite,k為整個種群當(dāng)前的最優(yōu)位置的第k維分量;λk是步長因子,通過式(4)計算:
式中:α為最大步長,P j是目標(biāo)求偶亭被選中的概率,概率值在0到1之間,步長與目標(biāo)位置的概率成反比,目標(biāo)位置的被選中概率越大時,步長越小。
(4)個體變異。根據(jù)緞藍(lán)園丁雄鳥的求偶習(xí)慣,強壯的雄鳥會從較弱的雄鳥那里偷取材料,甚至破壞其求偶亭。因此算法以一定的概率隨機變異,在這個過程中,xi k服從正態(tài)分布,如公式(5)所示:
在(6)式中,δ為標(biāo)準(zhǔn)差,通過公式(7)計算:
式中:z是縮放比例因子,varmax和varmin分別是變量xi的上限和下限。
(5)組合種群。在每次循環(huán)的最后,對舊種群和從變異獲得的群體進(jìn)行組合,形成組合種群,并對組合種群中的所有個體的代價函數(shù)值從小到大進(jìn)行排序,保留函數(shù)值最小的個體,淘汰其他個體。若此時滿足終止條件,則輸出最佳位置及其對應(yīng)的最優(yōu)值,否則繼續(xù)進(jìn)行迭代。
PSO算法是一種模仿鳥類捕食的群體智能的隨機全局優(yōu)化算法,其參數(shù)簡單易于實現(xiàn),收斂速度快且全局搜索能力較強[13]。在PSO算法中,設(shè)計了一種無質(zhì)量的粒子來模擬鳥群中的鳥,每個粒子可視為D維搜索空間中的一個搜索個體,并且具有速度和位置兩個屬性。粒子的當(dāng)前位置即為對應(yīng)優(yōu)化問題的一個候選解,粒子的飛行速度可根據(jù)粒子歷史最優(yōu)位置和種群歷史最優(yōu)位置進(jìn)行動態(tài)調(diào)整,通過群體中粒子之間的協(xié)作和信息共享來尋找最優(yōu)解。
假設(shè)PSO算法中粒子的數(shù)量為pop,在t次迭代中,對于粒子i=1,2,3,…,pop,在D維搜索空間中,每個粒子i的速度用vi=(vi1,vi2,vi3,…,vin)t表示,位置用xi=(xi1,xi2,xi3,…,xin)n表示,則第i個粒子的速度用用公式(8)進(jìn)行計算,位置用公式(9)進(jìn)行計算:
式中:vti是粒子第t次迭代的速度,xti是粒子第t次迭代的當(dāng)前位置,pti是粒子i搜索到的歷史最優(yōu)位置,ptg是粒子搜索到的全局最優(yōu)位置;c1和c2都是加速常數(shù);r1,r2∈[ 0,1],ω是慣性權(quán)重系數(shù)。
在基本的SBO算法中,種群位置的更新依賴于輪盤賭選擇機制和整個種群當(dāng)前的最優(yōu)位置,這樣種群的隨機性很小,緞藍(lán)園丁鳥個體的位置更新容易受到適應(yīng)度較好的位置的影響,導(dǎo)致算法的搜索能力很差,本文引入了粒子群算法中的速度因子,來增加算法的搜索能力,使每個種群朝著更好的方向更新,提高算法的收斂精度和收斂速度。具體的更新策略為:在每次迭代時,將種群中每只雄性緞藍(lán)園丁鳥的求偶亭視為粒子群中的每個粒子,給每個粒子一個速度因子,如公式(10):
式中:是粒子第t次迭代的速度,為第t代第i個個體的第k維分量,x j通過輪盤賭選擇機制確定,xelite,k為整個種群當(dāng)前的最優(yōu)位置的第k維分量;c1和c2為學(xué)習(xí)因子;r為常數(shù);ω是慣性權(quán)重系數(shù);則改進(jìn)的位置更新操作為:
式中:λk是步長因子。
速度因子引入改進(jìn)的緞藍(lán)園丁鳥優(yōu)化算法在搜索能力和速度上都有一定的提高,但是收斂精度不夠理想,基于PSO算法速度因子中引入慣性權(quán)重的啟發(fā),本文給種群中每只雄性緞藍(lán)園丁鳥的求偶亭一個速度因子中的固定慣性權(quán)重,來提高種群的多樣性。結(jié)合速度因子的引入,最終改進(jìn)算法的位置更新操作如公式(12)。
為了驗證PSBO算法的有效性,本文對8個基準(zhǔn)測試函數(shù)進(jìn)行仿真實驗來檢驗算法的改進(jìn)效果,選取的測試函數(shù)中包含單峰、多峰等不同特征的測試函數(shù),其中f1~f5為單峰函數(shù),f6~f8為峰函數(shù),如表1所示。
表1 測試函數(shù)
續(xù)表1
為了更進(jìn)一步驗證PSBO算法在收斂速度和收斂精度上的優(yōu)越性,本文將其與SBO算法、WSBO算法、t SBO算法和PSO算法進(jìn)行比較,實驗環(huán)境為Window 10操作系統(tǒng),算法用Matlab R2021a編寫。實驗的最大迭代次數(shù)為500,xmax和xmin分別為每個測試函數(shù)定義域的上限和下限,種群數(shù)為20,維度為30,各算法其余的參數(shù)設(shè)置如表2所示。
表2 算法參數(shù)設(shè)置
為減少實驗中隨機性的影響,在對每個測試函數(shù)獨立運行30次,計算其最優(yōu)值、均值和標(biāo)準(zhǔn)差,實驗結(jié)果如表3所示。對于每個測試函數(shù),在固定迭代次數(shù)下,最優(yōu)值反映了算法的尋優(yōu)能力和收斂精度,均值和標(biāo)準(zhǔn)差反映了算法的魯棒性和穩(wěn)定性。
表3 五種算法實驗結(jié)果
從表3的數(shù)據(jù)可以看出,對于所有測試函數(shù),本文提出的PSBO算法的最優(yōu)值、平均值和標(biāo)準(zhǔn)差均明顯優(yōu)于SBO、WSBO、tSBO和PSO。對于函數(shù)f1、f4、f6和f7這四個函數(shù),PSBO算法都能找到其理論最優(yōu)值,且其中f1、f6和f7的標(biāo)準(zhǔn)差都是0;對于其他的測試函數(shù),PSBO算法的性能在很大也程度上優(yōu)于其他算法。
為了能更直觀地顯示PSBO算法的優(yōu)化效果,圖1到圖8給出了5種算法在8個標(biāo)準(zhǔn)測試函數(shù)f1~f8上搜索函數(shù)最優(yōu)值過程中隨迭代次數(shù)增加的收斂曲線。從圖中可以看出,不管是多峰函數(shù)還是單峰函數(shù),PSBO算法的收斂精度和收斂速度都是最好的。
圖1 f 1函數(shù)收斂曲線
圖8 f 8函數(shù)收斂曲線
從圖中可以看出,除了測試函數(shù)f8,PSBO算法尋優(yōu)過程的變化近似于直線,這充分表明,PSBO算法的尋優(yōu)速度更高,收斂速度更快,全局搜索能力更強;其中,從f6和f7這2個函數(shù)收斂曲線可以看出,雖然WSBO算法和tSBO算法也能找到理論最優(yōu)值,但是它們的收斂速度遠(yuǎn)不如PSBO算法,在迭代次數(shù)不到50時,PSBO算法已經(jīng)找到了理論最優(yōu)值;從f8的函數(shù)收斂曲線可以看出,雖然PSBO最終找到的最優(yōu)值并不是很理想,但是對比其它算法已經(jīng)有了很大提升,特別是在收斂速度上,在迭代次數(shù)不到50時就已經(jīng)找到了比其它算法都要精確的值;從f1、f2、f3、f4和f5的函數(shù)收斂曲線可以看出,在迭代過程中,PSBO算法能夠快速接近于理論最優(yōu)值。
圖2 f 2函數(shù)收斂曲線
圖3 f 3函數(shù)收斂曲線
圖4 f 4函數(shù)收斂曲線
圖5 f 5函數(shù)收斂曲線
圖6 f 6函數(shù)收斂曲線
圖7 f 7函數(shù)收斂曲線
在以往的SBO算法應(yīng)用中,如2017年Moosavi等人提出了SBO算法并將其與ANFIS結(jié)合,用來提高軟件開發(fā)工作評估的準(zhǔn)確性;2018年,El-Hay等[14]用SBO算法來實現(xiàn)固體氧化物燃料電池的精確參數(shù)測量;Jagadeeswar等[15]將SBO用于電力系統(tǒng)的阻塞管理,計算最小的阻塞代價,采用基于發(fā)電量重調(diào)度的方法來緩解輸電線路的阻塞等,還未有基于機器學(xué)習(xí)函數(shù)參數(shù)優(yōu)化方面的相關(guān)應(yīng)用。為此,本文提出了一種利用BSO及其改進(jìn)算法PSBO來優(yōu)化SVM參數(shù)的應(yīng)用方向,并驗證了PSBO的有效性和可行性。
SVM由Vapnik等[16]于1995年提出,是一類按監(jiān)督學(xué)習(xí)方式對數(shù)據(jù)進(jìn)行二元分類的廣義線性分類器。SVM的基本思想是使用內(nèi)核函數(shù)把輸入樣本空間映射到高維特征空間,在高維空間中求得一個最優(yōu)分類面,支持向量則是指在間隔區(qū)邊緣的訓(xùn)練樣本點。
以二分類為例子,假設(shè)給定一個特征空間上的訓(xùn)練集數(shù)據(jù)T={(x1,y1),(x2,y2),(x3,y3),…,(xN,y N)},其中,xi表示第i個特征向量,y i∈{1,-1},y i為類標(biāo)記,當(dāng)它等于1時為正例,為-1時為負(fù)例,如果數(shù)據(jù)是線性可分的,則存在分類超平面ωx+b=0,能對所有樣本進(jìn)行正確的劃分。為了使SVM的分類效果最佳,需要尋找最優(yōu)超平面,可以將最優(yōu)分類面的問題轉(zhuǎn)化為如下的約束優(yōu)化問題:
式中:ω是超平面的法向量,b是超平面的常數(shù)項。
當(dāng)數(shù)據(jù)集線性不可分時,SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射,在低維空間上進(jìn)行計算,在高維空間進(jìn)行分類效果表征,減少了計算的復(fù)雜度。
參數(shù)優(yōu)化是SVM研究中的一個重要問題,參數(shù)選擇的不同會直接影響SVM模型的分類預(yù)測精度和泛化能力,影響SVM性能的主要參數(shù)就是核參數(shù)g和懲罰因子C。分類問題中,g越小,低維空間中選擇的曲線越復(fù)雜,容易出現(xiàn)過擬合;g越大,分類的精確度越低,容易出現(xiàn)欠擬合;懲罰因子C越大,經(jīng)驗風(fēng)險越小,結(jié)構(gòu)風(fēng)險越大,容易出現(xiàn)過擬合;C越小,模型復(fù)雜度越低,容易出現(xiàn)欠擬合[17]。因此需要選擇更優(yōu)的參數(shù)C和g,來提高SVM的分類性能。
本文將PSBO算法與支持向量機結(jié)合,用求偶亭位置的更新來尋找SVM中最優(yōu)的核參數(shù)g和懲罰因子C,將wine數(shù)據(jù)集中第一類的1-30,第二類的60-95,第三類的131-153做為訓(xùn)練集,第一類的31-59,第二類的96-130,第三類的154-178做為測試集,利用K折交叉驗證的方法算出驗證結(jié)果準(zhǔn)確率的均值作為目標(biāo)函數(shù),找出目標(biāo)函數(shù)的最優(yōu)值對應(yīng)的核參數(shù)g和懲罰因子C,具體步驟如下所示:
(1)對wine數(shù)據(jù)集進(jìn)行預(yù)處理,將將訓(xùn)練集和測試集歸一化到[0,1]區(qū)間,并初始化PSBO的各項參數(shù)。
(2)初始化核參數(shù)g和懲罰因子C,將它們看做PSBO算法中的求偶亭,用訓(xùn)練集訓(xùn)練模型,對數(shù)據(jù)進(jìn)行分類,計算出目標(biāo)函數(shù)和全局最優(yōu)的求偶亭位置。
(3)根據(jù)公式(1)和公式(2),計算每個求偶亭的吸引力。
(4)根據(jù)公式(12)來更新每個求偶亭的位置。
(5)隨機變異,并判斷求偶亭的位置是否溢出,如果位置溢出,對位置進(jìn)行處理。
(6)再對數(shù)據(jù)進(jìn)行分類,重新獲得個體的適應(yīng)度值。
(7)更新求偶亭的個體最優(yōu)位置和群體最優(yōu)位置。
(8)計算每一代的個體全局最優(yōu)適應(yīng)度值。
(9)判斷迭代次數(shù)是否為最大迭代次數(shù),若是,結(jié)束算法并輸出核參數(shù)g和懲罰因子C的最優(yōu)解和最優(yōu)目標(biāo)函數(shù)。
(10)用計算出的參數(shù)g和懲罰因子C構(gòu)建分類模型,對測試數(shù)據(jù)進(jìn)行分類預(yù)測并計算其準(zhǔn)確率。
在實驗中,將SVM分別與PSBO算法、SBO算法和PSO算法結(jié)合,以驗證本文改進(jìn)的PSBO算法在SVM參數(shù)優(yōu)化中的性能。其中,設(shè)置迭代次數(shù)為100,種群規(guī)模為20,其中懲罰因子C的最大值設(shè)定為1015,最小值為10-1,核參數(shù)g的最大值設(shè)定為103,最小值設(shè)定為10-4,則VarMax為1015,VarMin為為10-4,設(shè)置5次K折交叉驗證,其他參數(shù)如表4所示。
表4 參數(shù)設(shè)置
為了防止實驗的偶然性,對每個算法進(jìn)行獨立的30次試驗,記錄模型分類最高的準(zhǔn)確率和最低的準(zhǔn)確率和對應(yīng)的核參數(shù)g和懲罰因子C的數(shù)值,以及測試集準(zhǔn)確率,如表5所示。
表5 SVM參數(shù)優(yōu)化結(jié)果
從實驗結(jié)果可以看出,SBO算法并不適用于SVM參數(shù)的優(yōu)化,沒有辦法對目標(biāo)函數(shù)進(jìn)行優(yōu)化;而改進(jìn)的PSBO算法和PSO算法都可以對核參數(shù)g和懲罰因子C進(jìn)行較好的尋優(yōu),實現(xiàn)95%以上的準(zhǔn)確率。為了更進(jìn)一步的驗證這兩種算法的差異,對算法的收斂速度進(jìn)行了比較,通過在搜索目標(biāo)函數(shù)最優(yōu)值過程中達(dá)到達(dá)到相同適應(yīng)度值所需的迭代次數(shù)作為指標(biāo)。
從圖9中的隨機收斂曲線可以看出,雖然PSBO算法尋優(yōu)的收斂精度和PSO算法差不多,但是PSBO算法在收斂速度上明顯有更好的表現(xiàn)力,在達(dá)到最佳適應(yīng)值的目標(biāo)上,PSBO算法能提高SBO算法4倍以上的收斂速度,進(jìn)一步說明了PSBO算法應(yīng)用于SVM參數(shù)優(yōu)化的有效性。
圖9 收斂曲線
本文在標(biāo)準(zhǔn)SBO算法的基礎(chǔ)上,結(jié)合PSO算法,提出了PSBO算法,引入了速度因子和固定慣性權(quán)重,在很大程度上提高了基本SBO算法的收斂精度、收斂速度,以及全局尋優(yōu)能力。并且通過8個測試函數(shù)進(jìn)行了仿真實驗,其結(jié)果表明了PSBO算法的優(yōu)越的性能。
在應(yīng)用上,本文提出了PSBO算法優(yōu)化SVM內(nèi)部參數(shù),驗證了PSBO的有效性,且與原SBO算法和PSO算法比較的結(jié)果表明,PSBO算法的收斂精度和速度都要更快。
此外,PSBO算法仍然有不足之處,其全局尋優(yōu)能力上還可以進(jìn)一步完善,在應(yīng)用領(lǐng)域上也可以進(jìn)一步擴展,這也是下一步的研究工作。