李寧，高鷹，翁金塔，曹燦，郭曉語，周燦基

（1.廣州大學(xué)計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院，廣州 510000；2.中國(guó)科學(xué)院信息工程研究所，北京 100000）

0 引言

群體智能算法［1］是受到自然界生物啟發(fā)，通過生物的生活方式和生活特性模擬設(shè)計(jì)的一種算法，可以解決經(jīng)濟(jì)、社會(huì)和自然科學(xué)等領(lǐng)域中各種復(fù)雜的優(yōu)化問題。常見的有粒子群優(yōu)化（par?ticle swarm optimization，PSO）算法［2-3］，通過模擬鳥群的捕食行為來尋找最優(yōu)解；人工魚群算法（artificial fish swarm algorithm，AFSA）［4-5］是通過模仿魚類在水中的活動(dòng)方式，總結(jié)出魚群的隨機(jī)、覓食、聚群、追尾等四種典型的行為來實(shí)現(xiàn)尋優(yōu)；近年來也有許多新的群智能算法被提出，如象群優(yōu)化（elephant herding optimization，EHO）算法［6-7］源于自然界中大象的畜牧行為，可以用于解決全局無約束優(yōu)化問題。群智能算法具有簡(jiǎn)單性、可擴(kuò)展性和運(yùn)行時(shí)間短等特點(diǎn)，在解決各種尋優(yōu)問題時(shí)，具有良好的操作性和強(qiáng)大的表現(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ā)工作評(píng)估的準(zhǔn)確性。目前國(guó)內(nèi)對(duì)于該算法的改進(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ù)來增強(qiáng)種群的多樣性，避免原算法陷入局部最優(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個(gè)典型復(fù)雜函數(shù)的最優(yōu)解來驗(yàn)證PSBO算法的尋優(yōu)能力，并將其應(yīng)用到支持向量機(jī)（support vector machines，SVM）內(nèi)部參數(shù)優(yōu)化的問題中，驗(yàn)證其有效性，拓寬了應(yīng)用范圍。

1 緞藍(lán)園丁鳥優(yōu)化算法

在自然界中，成熟的緞藍(lán)園丁雄鳥在其各自的領(lǐng)地上建造求偶亭，并配以各種裝飾來吸引雌鳥，然而并不是所有的成年雄鳥都能成功的構(gòu)建和維護(hù)求偶亭，存在求偶亭被破壞的情況［11］。根據(jù)緞藍(lán)園丁鳥求偶的原理，在自然界中，成熟的緞藍(lán)園丁雄鳥在其各自的領(lǐng)地上建造求偶亭，并配以各種裝飾來吸引雌鳥，然而并不是所有的成年雄鳥都能成功的構(gòu)建和維護(hù)求偶亭，存在求偶亭被破壞的情況［12］。根據(jù)緞藍(lán)園丁鳥求偶的原理，可以將SBO算法分為以下五個(gè)步驟：

（1）初始化種群。在可行域內(nèi)隨機(jī)生成一個(gè)包含N個(gè)求偶亭的初始種群，每個(gè)求偶亭的位置定義為D維，當(dāng)前迭代次數(shù)為t，最大迭代次數(shù)為Max It。

（2）計(jì)算每個(gè)求偶亭的吸引力。每個(gè)求偶亭的吸引力P i由公式（1）或得，fiti通過公式（2）計(jì)算：

式中：fiti表示i個(gè)求偶亭的適應(yīng)度值，f(xi)是第i個(gè)求偶亭的目標(biāo)函數(shù)，每次迭代保證目標(biāo)函數(shù)的函數(shù)值不斷減小。

（3）更新種群位置。雄性園丁鳥根據(jù)歷史經(jīng)驗(yàn)并利用信息共享機(jī)制，不斷調(diào)整求偶亭的位置，其位置更新公式如式（3）所示：

式中：為第t代第i個(gè)個(gè)體的第k維分量;x j通過輪盤賭選擇機(jī)制確定；xelite,k為整個(gè)種群當(dāng)前的最優(yōu)位置的第k維分量；λk是步長(zhǎng)因子，通過式（4）計(jì)算：

式中：α為最大步長(zhǎng)，P j是目標(biāo)求偶亭被選中的概率，概率值在0到1之間，步長(zhǎng)與目標(biāo)位置的概率成反比，目標(biāo)位置的被選中概率越大時(shí)，步長(zhǎng)越小。

（4）個(gè)體變異。根據(jù)緞藍(lán)園丁雄鳥的求偶習(xí)慣，強(qiáng)壯的雄鳥會(huì)從較弱的雄鳥那里偷取材料，甚至破壞其求偶亭。因此算法以一定的概率隨機(jī)變異，在這個(gè)過程中，xi k服從正態(tài)分布，如公式（5）所示：

在（6）式中，δ為標(biāo)準(zhǔn)差，通過公式（7）計(jì)算：

式中：z是縮放比例因子，varmax和varmin分別是變量xi的上限和下限。

（5）組合種群。在每次循環(huán)的最后，對(duì)舊種群和從變異獲得的群體進(jìn)行組合，形成組合種群，并對(duì)組合種群中的所有個(gè)體的代價(jià)函數(shù)值從小到大進(jìn)行排序，保留函數(shù)值最小的個(gè)體，淘汰其他個(gè)體。若此時(shí)滿足終止條件，則輸出最佳位置及其對(duì)應(yīng)的最優(yōu)值，否則繼續(xù)進(jìn)行迭代。

2 基于粒子群改進(jìn)的緞藍(lán)園丁優(yōu)化算法

2.1 粒子群優(yōu)化算法

PSO算法是一種模仿鳥類捕食的群體智能的隨機(jī)全局優(yōu)化算法，其參數(shù)簡(jiǎn)單易于實(shí)現(xiàn)，收斂速度快且全局搜索能力較強(qiáng)［13］。在PSO算法中，設(shè)計(jì)了一種無質(zhì)量的粒子來模擬鳥群中的鳥，每個(gè)粒子可視為D維搜索空間中的一個(gè)搜索個(gè)體，并且具有速度和位置兩個(gè)屬性。粒子的當(dāng)前位置即為對(duì)應(yīng)優(yōu)化問題的一個(gè)候選解，粒子的飛行速度可根據(jù)粒子歷史最優(yōu)位置和種群歷史最優(yōu)位置進(jìn)行動(dòng)態(tài)調(diào)整，通過群體中粒子之間的協(xié)作和信息共享來尋找最優(yōu)解。

假設(shè)PSO算法中粒子的數(shù)量為pop，在t次迭代中，對(duì)于粒子i=1,2,3,…,pop，在D維搜索空間中，每個(gè)粒子i的速度用vi=(vi1,vi2,vi3,…,vin)t表示，位置用xi=(xi1,xi2,xi3,…,xin)n表示，則第i個(gè)粒子的速度用用公式（8）進(jìn)行計(jì)算，位置用公式（9）進(jìn)行計(jì)算：

式中：vti是粒子第t次迭代的速度，xti是粒子第t次迭代的當(dāng)前位置，pti是粒子i搜索到的歷史最優(yōu)位置，ptg是粒子搜索到的全局最優(yōu)位置；c1和c2都是加速常數(shù)；r1,r2∈[ 0,1]，ω是慣性權(quán)重系數(shù)。

2.2 改進(jìn)的緞藍(lán)園丁鳥優(yōu)化算法

在基本的SBO算法中，種群位置的更新依賴于輪盤賭選擇機(jī)制和整個(gè)種群當(dāng)前的最優(yōu)位置，這樣種群的隨機(jī)性很小，緞藍(lán)園丁鳥個(gè)體的位置更新容易受到適應(yīng)度較好的位置的影響，導(dǎo)致算法的搜索能力很差，本文引入了粒子群算法中的速度因子，來增加算法的搜索能力，使每個(gè)種群朝著更好的方向更新，提高算法的收斂精度和收斂速度。具體的更新策略為：在每次迭代時(shí)，將種群中每只雄性緞藍(lán)園丁鳥的求偶亭視為粒子群中的每個(gè)粒子，給每個(gè)粒子一個(gè)速度因子，如公式（10）：

式中：是粒子第t次迭代的速度，為第t代第i個(gè)個(gè)體的第k維分量，x j通過輪盤賭選擇機(jī)制確定，xelite,k為整個(gè)種群當(dāng)前的最優(yōu)位置的第k維分量；c1和c2為學(xué)習(xí)因子；r為常數(shù)；ω是慣性權(quán)重系數(shù)；則改進(jìn)的位置更新操作為：

式中：λk是步長(zhǎng)因子。

速度因子引入改進(jìn)的緞藍(lán)園丁鳥優(yōu)化算法在搜索能力和速度上都有一定的提高，但是收斂精度不夠理想，基于PSO算法速度因子中引入慣性權(quán)重的啟發(fā)，本文給種群中每只雄性緞藍(lán)園丁鳥的求偶亭一個(gè)速度因子中的固定慣性權(quán)重，來提高種群的多樣性。結(jié)合速度因子的引入，最終改進(jìn)算法的位置更新操作如公式（12）。

3 PSBO算法性能分析

3.1 測(cè)試函數(shù)以及參數(shù)設(shè)置

為了驗(yàn)證PSBO算法的有效性，本文對(duì)8個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)來檢驗(yàn)算法的改進(jìn)效果，選取的測(cè)試函數(shù)中包含單峰、多峰等不同特征的測(cè)試函數(shù)，其中f1～f5為單峰函數(shù)，f6～f8為峰函數(shù)，如表1所示。

表1 測(cè)試函數(shù)

續(xù)表1

為了更進(jìn)一步驗(yàn)證PSBO算法在收斂速度和收斂精度上的優(yōu)越性，本文將其與SBO算法、WSBO算法、t SBO算法和PSO算法進(jìn)行比較，實(shí)驗(yàn)環(huán)境為Window 10操作系統(tǒng)，算法用Matlab R2021a編寫。實(shí)驗(yàn)的最大迭代次數(shù)為500，xmax和xmin分別為每個(gè)測(cè)試函數(shù)定義域的上限和下限，種群數(shù)為20，維度為30，各算法其余的參數(shù)設(shè)置如表2所示。

表2 算法參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果及其分析

為減少實(shí)驗(yàn)中隨機(jī)性的影響，在對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次，計(jì)算其最優(yōu)值、均值和標(biāo)準(zhǔn)差，實(shí)驗(yàn)結(jié)果如表3所示。對(duì)于每個(gè)測(cè)試函數(shù)，在固定迭代次數(shù)下，最優(yōu)值反映了算法的尋優(yōu)能力和收斂精度，均值和標(biāo)準(zhǔn)差反映了算法的魯棒性和穩(wěn)定性。

表3 五種算法實(shí)驗(yàn)結(jié)果

從表3的數(shù)據(jù)可以看出，對(duì)于所有測(cè)試函數(shù)，本文提出的PSBO算法的最優(yōu)值、平均值和標(biāo)準(zhǔn)差均明顯優(yōu)于SBO、WSBO、tSBO和PSO。對(duì)于函數(shù)f1、f4、f6和f7這四個(gè)函數(shù)，PSBO算法都能找到其理論最優(yōu)值，且其中f1、f6和f7的標(biāo)準(zhǔn)差都是0；對(duì)于其他的測(cè)試函數(shù)，PSBO算法的性能在很大也程度上優(yōu)于其他算法。

為了能更直觀地顯示PSBO算法的優(yōu)化效果，圖1到圖8給出了5種算法在8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)f1～f8上搜索函數(shù)最優(yōu)值過程中隨迭代次數(shù)增加的收斂曲線。從圖中可以看出，不管是多峰函數(shù)還是單峰函數(shù)，PSBO算法的收斂精度和收斂速度都是最好的。

圖1 f 1函數(shù)收斂曲線

圖8 f 8函數(shù)收斂曲線

從圖中可以看出，除了測(cè)試函數(shù)f8，PSBO算法尋優(yōu)過程的變化近似于直線，這充分表明，PSBO算法的尋優(yōu)速度更高，收斂速度更快，全局搜索能力更強(qiáng)；其中，從f6和f7這2個(gè)函數(shù)收斂曲線可以看出，雖然WSBO算法和tSBO算法也能找到理論最優(yōu)值，但是它們的收斂速度遠(yuǎn)不如PSBO算法，在迭代次數(shù)不到50時(shí)，PSBO算法已經(jīng)找到了理論最優(yōu)值；從f8的函數(shù)收斂曲線可以看出，雖然PSBO最終找到的最優(yōu)值并不是很理想，但是對(duì)比其它算法已經(jīng)有了很大提升，特別是在收斂速度上，在迭代次數(shù)不到50時(shí)就已經(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ù)收斂曲線

4 基于PSBO算法的SVM參數(shù)優(yōu)化

在以往的SBO算法應(yīng)用中，如2017年Moosavi等人提出了SBO算法并將其與ANFIS結(jié)合，用來提高軟件開發(fā)工作評(píng)估的準(zhǔn)確性；2018年，El-Hay等［14］用SBO算法來實(shí)現(xiàn)固體氧化物燃料電池的精確參數(shù)測(cè)量；Jagadeeswar等［15］將SBO用于電力系統(tǒng)的阻塞管理，計(jì)算最小的阻塞代價(jià)，采用基于發(fā)電量重調(diào)度的方法來緩解輸電線路的阻塞等，還未有基于機(jī)器學(xué)習(xí)函數(shù)參數(shù)優(yōu)化方面的相關(guān)應(yīng)用。為此，本文提出了一種利用BSO及其改進(jìn)算法PSBO來優(yōu)化SVM參數(shù)的應(yīng)用方向，并驗(yàn)證了PSBO的有效性和可行性。

4.1 SVM基本原理

SVM由Vapnik等［16］于1995年提出，是一類按監(jiān)督學(xué)習(xí)方式對(duì)數(shù)據(jù)進(jìn)行二元分類的廣義線性分類器。SVM的基本思想是使用內(nèi)核函數(shù)把輸入樣本空間映射到高維特征空間，在高維空間中求得一個(gè)最優(yōu)分類面，支持向量則是指在間隔區(qū)邊緣的訓(xùn)練樣本點(diǎn)。

以二分類為例子，假設(shè)給定一個(gè)特征空間上的訓(xùn)練集數(shù)據(jù)T={(x1,y1),(x2,y2),(x3,y3),…,(xN,y N)}，其中，xi表示第i個(gè)特征向量，y i∈{1,-1}，y i為類標(biāo)記，當(dāng)它等于1時(shí)為正例，為-1時(shí)為負(fù)例,如果數(shù)據(jù)是線性可分的，則存在分類超平面ωx+b=0，能對(duì)所有樣本進(jìn)行正確的劃分。為了使SVM的分類效果最佳，需要尋找最優(yōu)超平面，可以將最優(yōu)分類面的問題轉(zhuǎn)化為如下的約束優(yōu)化問題：

式中：ω是超平面的法向量，b是超平面的常數(shù)項(xiàng)。

當(dāng)數(shù)據(jù)集線性不可分時(shí)，SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射，在低維空間上進(jìn)行計(jì)算，在高維空間進(jìn)行分類效果表征，減少了計(jì)算的復(fù)雜度。

參數(shù)優(yōu)化是SVM研究中的一個(gè)重要問題，參數(shù)選擇的不同會(huì)直接影響SVM模型的分類預(yù)測(cè)精度和泛化能力，影響SVM性能的主要參數(shù)就是核參數(shù)g和懲罰因子C。分類問題中，g越小，低維空間中選擇的曲線越復(fù)雜，容易出現(xiàn)過擬合；g越大，分類的精確度越低，容易出現(xiàn)欠擬合；懲罰因子C越大，經(jīng)驗(yàn)風(fēng)險(xiǎn)越小，結(jié)構(gòu)風(fēng)險(xiǎn)越大，容易出現(xiàn)過擬合；C越小，模型復(fù)雜度越低，容易出現(xiàn)欠擬合［17］。因此需要選擇更優(yōu)的參數(shù)C和g，來提高SVM的分類性能。

4.2 PSBO算法優(yōu)化SVM參數(shù)

本文將PSBO算法與支持向量機(jī)結(jié)合，用求偶亭位置的更新來尋找SVM中最優(yōu)的核參數(shù)g和懲罰因子C，將wine數(shù)據(jù)集中第一類的1-30，第二類的60-95，第三類的131-153做為訓(xùn)練集，第一類的31-59，第二類的96-130，第三類的154-178做為測(cè)試集，利用K折交叉驗(yàn)證的方法算出驗(yàn)證結(jié)果準(zhǔn)確率的均值作為目標(biāo)函數(shù)，找出目標(biāo)函數(shù)的最優(yōu)值對(duì)應(yīng)的核參數(shù)g和懲罰因子C，具體步驟如下所示：

（1）對(duì)wine數(shù)據(jù)集進(jìn)行預(yù)處理，將將訓(xùn)練集和測(cè)試集歸一化到［0，1］區(qū)間，并初始化PSBO的各項(xiàng)參數(shù)。

（2）初始化核參數(shù)g和懲罰因子C，將它們看做PSBO算法中的求偶亭，用訓(xùn)練集訓(xùn)練模型，對(duì)數(shù)據(jù)進(jìn)行分類，計(jì)算出目標(biāo)函數(shù)和全局最優(yōu)的求偶亭位置。

（3）根據(jù)公式（1）和公式（2），計(jì)算每個(gè)求偶亭的吸引力。

（4）根據(jù)公式（12）來更新每個(gè)求偶亭的位置。

（5）隨機(jī)變異，并判斷求偶亭的位置是否溢出，如果位置溢出，對(duì)位置進(jìn)行處理。

（6）再對(duì)數(shù)據(jù)進(jìn)行分類，重新獲得個(gè)體的適應(yīng)度值。

（7）更新求偶亭的個(gè)體最優(yōu)位置和群體最優(yōu)位置。

（8）計(jì)算每一代的個(gè)體全局最優(yōu)適應(yīng)度值。

（9）判斷迭代次數(shù)是否為最大迭代次數(shù)，若是，結(jié)束算法并輸出核參數(shù)g和懲罰因子C的最優(yōu)解和最優(yōu)目標(biāo)函數(shù)。

（10）用計(jì)算出的參數(shù)g和懲罰因子C構(gòu)建分類模型，對(duì)測(cè)試數(shù)據(jù)進(jìn)行分類預(yù)測(cè)并計(jì)算其準(zhǔn)確率。

4.3 實(shí)驗(yàn)結(jié)果及其分析

在實(shí)驗(yàn)中，將SVM分別與PSBO算法、SBO算法和PSO算法結(jié)合，以驗(yàn)證本文改進(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折交叉驗(yàn)證，其他參數(shù)如表4所示。

表4 參數(shù)設(shè)置

為了防止實(shí)驗(yàn)的偶然性，對(duì)每個(gè)算法進(jìn)行獨(dú)立的30次試驗(yàn)，記錄模型分類最高的準(zhǔn)確率和最低的準(zhǔn)確率和對(duì)應(yīng)的核參數(shù)g和懲罰因子C的數(shù)值，以及測(cè)試集準(zhǔn)確率，如表5所示。

表5 SVM參數(shù)優(yōu)化結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出，SBO算法并不適用于SVM參數(shù)的優(yōu)化，沒有辦法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化；而改進(jìn)的PSBO算法和PSO算法都可以對(duì)核參數(shù)g和懲罰因子C進(jìn)行較好的尋優(yōu)，實(shí)現(xiàn)95%以上的準(zhǔn)確率。為了更進(jìn)一步的驗(yàn)證這兩種算法的差異，對(duì)算法的收斂速度進(jìn)行了比較，通過在搜索目標(biāo)函數(shù)最優(yōu)值過程中達(dá)到達(dá)到相同適應(yīng)度值所需的迭代次數(shù)作為指標(biāo)。

從圖9中的隨機(jī)收斂曲線可以看出，雖然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 收斂曲線

5 結(jié)語

本文在標(biāo)準(zhǔn)SBO算法的基礎(chǔ)上，結(jié)合PSO算法，提出了PSBO算法，引入了速度因子和固定慣性權(quán)重，在很大程度上提高了基本SBO算法的收斂精度、收斂速度，以及全局尋優(yōu)能力。并且通過8個(gè)測(cè)試函數(shù)進(jìn)行了仿真實(shí)驗(yàn)，其結(jié)果表明了PSBO算法的優(yōu)越的性能。

在應(yīng)用上，本文提出了PSBO算法優(yōu)化SVM內(nèi)部參數(shù)，驗(yàn)證了PSBO的有效性，且與原SBO算法和PSO算法比較的結(jié)果表明，PSBO算法的收斂精度和速度都要更快。

此外，PSBO算法仍然有不足之處，其全局尋優(yōu)能力上還可以進(jìn)一步完善，在應(yīng)用領(lǐng)域上也可以進(jìn)一步擴(kuò)展，這也是下一步的研究工作。