非均勻變異的互利自適應緞藍園丁鳥優化算法*

王依柔，張達敏，樊 英

(貴州大學大數據與信息工程學院，貴州 貴陽 550025)

1 引言

近年來，在工程、經濟學等多個領域出現許多復雜優化問題，這些問題通過傳統方法在一定的時間或精度內得到最優解較為困難。運用群智能算法可以處理這類優化問題。近幾年比較新穎的群智能算法包括樽海鞘群算法SSA(Salp Swarm Algorithm)、蝴蝶優化算法BOA(Butterfly Optimization Algorithm)、常用的粒子群優化PSO(Particle Swarm Optimization)算法等都具有簡單易行、參數少、運行時間短等特點，因此在解決眾多非線性和多模態的現實尋優問題中，群智能算法呈現出了優良的可操作性和尋優能力[1-5]。

緞藍園丁鳥優化算法SBO(Satin Bowerbird Optimizer)是由Moosavi等人[6]提出的一種新的全局優化群智能算法，是受緞藍園丁鳥求偶行為的啟發而提出的。雖然這種算法在經典工程設計問題上具有優越性，但與其它群智能算法一樣，其仍然存在求解精度低和收斂速度慢等缺陷。文獻[7]利用SBO算法來實現固體氧化物燃料電池的精確參數測量，SBO能夠為固體氧化物燃料電池的穩態和動態模型生成有競爭力的參數，這表明了SBO算法的有效性。文獻[8] 針對無管制電力系統中的擁塞管理問題，提出使用SBO算法，該方法在擁塞代價和損失方面具有更好的效果。文獻[9]采用復數編碼增加了園丁鳥種群的多樣性，增強了標準SBO算法的全局搜索能力，但是收斂速度不太理想。文獻[10]為避免算法陷入局部最優，在SBO算法中引入自適應t分布變異算子，使用算法的迭代次數作為t分布的自由度參數來增強種群的多樣性，但是搜索精度依然不算高。文獻[11]提出了一種用非均勻變異算子代替高斯或柯西變異算子的進化規劃算法，提高了算法跳出局部陷阱的概率。文獻[12]為了提高路徑規劃的精度，在傳統的粒子群優化算法中對慣性權重因子采用三角函數的變化方式進行自適應調整，以有效平衡算法的全局探索能力和局部開發能力。

為了解決標準緞藍園丁鳥優化算法存在的求解精度不高和收斂速度慢等問題，本文提出一種非均勻變異的互利自適應SBO算法。改進的SBO算法引入非均勻變異算子，避免算法陷入局部最優；采用互利因子以增加種群多樣性，獲取更好的最優解；引入自適應慣性權重，平衡算法的局部與全局搜索能力。通過求解8個典型復雜函數的最優解、Wilcoxon檢驗統計和平均絕對誤差來驗證改進的緞藍園丁鳥優化ISBO(Improve Satin Bowerbird Optimizer)算法的有效性和魯棒性。

2 緞藍園丁鳥優化算法

在緞藍園丁鳥優化(SBO)[6]算法中，成年雄性園丁鳥在交配季節開始在自己的區域上用不同的材料建造涼亭。他們利用的各種各樣的材料(如鮮花、水果)以及戲劇性的姿態，都是吸引雌性園丁鳥的變量。成年雌性園丁鳥由于涼亭的美麗和戲劇性的姿態，被吸引到涼亭。值得注意的是，雄鳥利用它們的自然本能和對其他雄鳥的模仿來筑窩。根據園丁鳥生活的著色原則，將SBO算法分為以下5個階段：

(1)隨機生成初始種群。在可行域內隨機生成一個包含N個求偶亭的初始種群，每個求偶亭的位置定義為D維，當前進化代數為q。

(2)計算每個個體的適應度值，然后計算出此適應度值在群體適應度值總和中所占的比例，表示該個體在選擇過程中被選中的概率。求偶亭被選中的概率通過式(1)和式(2)計算：

(1)

(2)

其中，fiti代表第i個求偶亭的適應度值，通過式(2)計算，f(xi)是第i個求偶亭的目標函數，每次迭代保證目標函數的函數值不斷減小。

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

(3)

(4)

其中，α為步長的最大閾值；Pj是目標求偶亭的被選中概率，取值為0～1。當目標位置被選中概率越大時，步長越小；當目標位置被選中概率為0時，步長最大為α；當目標位置的被選中概率為1時，步長最小，為α/2。

(4)個體變異。在大多數情況下，強壯的雄鳥會從其它雄鳥那里偷材料，甚至破壞它們的求偶亭，因此在算法循環的最后，以一定的概率隨機變異，在變異過程中，xik服從正態分布，如式(5)所示：

(5)

(6)

在式(6)中，標準差σ的計算公式如式(7)所示：

σ=z×(varmax-varmin)

(7)

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

(5)組合舊種群和從變異中獲得的種群。在每次循環的最后，對舊種群和從變異獲得的群體進行組合，形成組合種群，并對組合種群中的所有個體的目標函數值從小到大進行排序，保留函數值最小的個體，其余個體被淘汰掉。此時若滿足終止條件，則輸出最佳位置及其對應的最優值；反之，則繼續進行迭代.

3 改進緞藍園丁鳥優化算法

3.1 非均勻變異

在SBO算法早期的迭代中，園丁鳥個體的求偶亭位置通常是遠離最優解的，搜索半徑太小會造成群體陷入局部最優。在算法后期，園丁鳥個體的求偶亭位置接近最優解，只需要一個非常小的范圍進行解向量的微調。標準算法的個體變異尋優方式不利于快速高效地尋求全局最優值。本文引入非均勻變異[11]算子，在前期尋優時，整個種群大范圍地搜索，伴隨著迭代次數的增加，逐步地縮小搜索范圍，動態地調整每次迭代每個園丁鳥個體的求偶亭的搜索步長。

假設對求偶亭位置xi={xi1,xi2,…,xid,…xiD}T的第k個分量執行變異運算，xik的下限和上限分別記為varmin和varmax，則變異后的分量由式(8)計算：

(8)

其中，q是當前迭代次數；r是均勻產生的[0,1]隨機數；Δ(q,y)由式(9)給出，它是一種自適應調節步長的變異算子，在迭代前期它能在定義域內搜索較大范圍，以期發現可能的潛在區域，隨著算法的進行，搜索半徑依概率減小，算法臨近結束時僅在當前解的狹小鄰域內搜索，這樣就能避免位置矢量陷入局部最優。

Δ(q,y)=y·(1-r(1-q/Q)b)

(9)

其中，q是當前迭代次數；Q是最大迭代次數；b是決定變異運算非均勻度的系統參數，本文參照文獻[11]取值為5。

3.2 互利因子

標準SBO算法的求偶亭位置更新公式產生的新求偶亭位置會直接替換原求偶亭位置，存在以下缺點：第i個求偶亭位置會根據由輪盤賭方式選擇的第j個求偶亭位置和當前種群最優求偶亭位置進行更新，對隨機選擇的第j個求偶亭個體依懶性較強，缺乏與其它個體學習的部分。為增加SBO算法的種群多樣性，本文引入互利因子[13]對園丁鳥的求偶亭位置進行更新，如式(10)所示：

(10)

其中，φ是(0,1)的隨機數；C為互利因子，代表園丁鳥種群中2個求偶亭的關系特征;R為受益參數，隨機選取1或2。由式(10)產生的新位置需判斷其適應度值優劣后才能替換原有位置。

在式(10)所示的園丁鳥求偶亭位置更新策略中，增加了社會部分φ×(xbest,k-C×R)，使種群中的隨機2個求偶亭參與進化，實現較優位置的共享。與原來的位置更新公式(3)只使用由輪盤賭方式選擇的第j個求偶亭位置和當前種群最優求偶亭位置進行信息交流的方式相比，社會部分引入更多組合模式，使其不再單一圍繞前一個園丁鳥附近搜索，即增加了園丁鳥的種群多樣性，以獲得更好的全局最優解。

3.3 自適應慣性權重

(11)

ω(q)=(ωmin+ωmax)/2+(ωmax-ωmin)cos(qπ/T)

(12)

其中，ωmax為初始慣性權重。ωmin為迭代結束時的慣性權重。慣性權重ωmax=0.95，ωmin=0.4時算法具有最佳性能。因此，隨著迭代的進行，慣性權重從0.95非線性遞減至0.4，迭代初始階段較大的慣性權重能使算法保持較好的搜索能力，而迭代后期較小的慣性權重則有助于提高算法的開發能力。

3.4 ISBO算法步驟

結合3.1節～3.3節對算法的改進，即引入非均勻變異算子避免算法陷入局部最優；采用互利因子以增加種群多樣性，獲取更好的最優解；引入自適應慣性權重，平衡算法的局部與全局搜索能力。非均勻變異的互利自適應優化SBO算法ISBO流程圖如圖1所示，其中rand是[0,1]的隨機數。ISBO步驟如下所示：

Step1設置算法參數，初始化園丁鳥個體求偶亭的位置。根據搜索空間的上下限，隨機生成一個N×D的矩陣。

Step2計算初始適應度值。根據式(2)計算N個園丁鳥求偶亭位置的適應度值。

Step3選定最優求偶亭。把Step 2中得到的適應度值進行升序排列，適應度值最好的求偶亭位置選定為最優求偶亭位置，并根據式(1)計算每個求偶亭位置被選中的概率。

Step4求偶亭位置更新。根據式(8)、式(10)和式(11)對應更新每個園丁鳥求偶亭的位置。

Step5計算適應度值。計算更新后每個求偶亭所處位置的適應度值，并更新最優位置。

Step6重復Step 4和Step 5的迭代過程，如果達到設置的精度要求或規定的最大迭代次數，則終止算法，輸出全局最優解。

Figure 1 Flow chart of ISBO algorithm圖1 算法流程圖

4 仿真實驗與結果分析

為驗證ISBO算法在求解優化問題上的有效性和魯棒性，用ISBO算法與SBO[6]、SSA[2]、BOA[3]、PSO[4]、加入非均勻變異算子的緞藍園丁鳥優化(NSBO)算法、加入互利因子的緞藍園丁鳥優化(MSBO)算法和加入自適應權重的緞藍園丁鳥優化(WSBO)算法，利用8個典型的標準測試函數在不同的維度下對最優值進行求解，然后獨立進行50次對比實驗。本文采用如表1所示的8個復雜函數作為適應度函數，選取的測試函數中包含單峰、多峰等不同特征的測試函數。單峰函數為在定義上下限內只有一個嚴格上的極大值(或極小值)，通常用來檢測算法收斂速度。多峰函數為含有多個局部最優解或全局最優解的函數，經常用于檢測算法探索能力和開發能力。

Table 1 Benchmark functions表1 基準函數

實驗環境為：Windows 10操作系統，CPU為Intel Core i5-8300H，主頻2.3 GHz，內存8 GB，算法基于Matlab R2014b用M語言編寫。

實驗最大迭代次數為500，種群數為40，各算法其余的參數設置如表2所示。

實驗1函數優化結果比較。

為了更好地研究ISBO算法的優化性能，各算法分別在不同的維度下進行50次獨立尋優，并記錄這50次的最佳值、平均值、最差值和標準差進行比較，結果如表3所示。

Table 2 Algorithm parameter setting表2 算法參數設置

Table 3 Analysis of experimental results表3 實驗結果分析

續表

表3中的最佳值和平均值都可以反映算法的收斂精度和尋優能力。ISBO在求解單峰函數(f1～f5)時精度最高達到1e-188，隨著搜索空間維度的增加，5種算法的尋優收斂精度有所下降，對于函數f4，ISBO求解的精度為1e-90，相較于函數f2降低了5個數量級。因為伴隨求解維度的增加，算法求解難度也呈指數級別遞增，所以算法的收斂精度有所降低屬于正常現象。另外，當維度增加到120維(函數f2)和200維(函數f4)時，SSA、BOA和PSO算法的求解精度較差，并與理論最優值存在最大1e-3級的誤差。而ISBO相對于其它幾種算法尋優精度要高很多，且與其它算法精度最大能達到1e-182級的差距。對于f6～f8這一類復雜的多峰函數，算法求解精度相對于單峰函數要稍微低一些。在求解函數f8時，相較于SSA、BOA和PSO算法，SBO算法表現出更強的尋優能力。對于NSBO、MSBO和WSBO，加入一個改進點以后收斂精度都比原始算法、SSA、BOA和PSO的要高。這是因為SBO容易陷入局部極值，在算法中加入了非均勻變異算子、互利因子和自適應權重，一定程度上使得算法擁有跳出局部最優區域的能力，而伴隨著維度的增加時，ISBO的精度是最高的，說明不同的改進策略對算法的尋優能力都有促進作用，從而達到了良好的尋優效果，進而證明了本文所提的改進思想的可行性。ISBO算法求解函數f6和f8時均達到理論最優值0。ISBO算法比其他算法的精度都要高。由此可見，ISBO算法在求解單峰、多峰和高維的基準函數時都有明顯的優勢。

其次，表3中的標準差和最差值也反映了算法在求解中的穩定性和跳出局部最優的能力。ISBO算法的最差值在8個函數的求解中都是最好的，說明有效改善了原始算法易陷入局部最優的缺點。ISBO算法求解的標準差相較于PSO、BOA、SSA、SBO、NSBO、MSBO和WSBO都要優秀，甚至求解函數f1和f7時均達到理論最優值，進一步說明其穩定性更好。

實驗2統計檢驗。

基于50次獨立運行的平均值和標準差的算法不會比較每次運行的結果。因此，盡管在50次運行中發生偶然優勢的概率很低，但仍需用其他方法對算法有效性進行校驗。Derrac等在文獻[14]中提出，對于改進進化算法性能的評估，僅基于平均值和標準偏差值來比較是不夠的，需要進行統計檢驗以證明所提出的改進算法比特定問題的其他現有算法具有顯著的改進。為了判斷ISBO的每次結果是否與統計上顯著的其他算法的最佳結果不同，在5%的顯著性水平下進行Wilcoxon統計檢驗[15]。表4給出了所有基準函數的ISBO和其他算法的Wilcoxon秩和檢驗中計算的p值。例如，如果最佳算法是ISBO，則在ISBO/BOA、ISBO/SSA等之間進行成對比較。由于最佳算法無法與自身進行比較，因此，針對每個函數中的最佳算法標記為N/A，表示“不適用”，這意味著相應的算法可以在秩和檢驗中沒有統計數據與自身進行比較。根據Derrac等人的研究，那些p<0.05的算法(即算法進行秩和檢驗計算出的p值)可以被認為是拒絕零假設的有力證據。根據表4中的結果，ISBO的p值基本小于0.05，這表明該算法的優越性在統計上是顯著的。

Table 4 p value of Wilcoxon rank sum test表4 Wilcoxon 秩和檢驗的p值

所有算法的定量分析基于8個基準函數的平均絕對誤差MAE(Mean Absolute Error)。MAE[16]是一種有效的性能指標，用于對優化算法進行排序。表5給出了這些基準函數的MAE，其計算如式(13)所示：

(13)

其中，mi為算法產生的最優結果的平均值，oi為相應基準函數的理論最優值，Nf為基準函數個數。由表5可知，ISBO排名為1，因為它提供了最小的MAE。與其它優化算法相比，進一步說明了ISBO的有效性。

Table 5 MAE algorithm ranking表5 MAE算法排名

實驗3收斂迭代曲線對比。

圖2給出了8個基準函數的平均收斂曲線圖，各函數分圖圖例同圖2a一致。由于ISBO收斂精度較高，為了便于觀察收斂情況，本文對尋優適應度值(縱坐標)取10為底的對數。由圖2a～圖2h可看出，SSA和BOA算法作為較新的算法，也依然存在容易陷入局部最優的缺點。原始SBO算法的收斂曲線下降緩慢，出現不同程度的停滯，基本陷入局部極值且收斂精度較低。NSBO、MSBO和WSBO算法性能都比SBO算法更好。而無論單峰、多峰，還是低維和高維，對于每個基準函數，ISBO比其他算法的收斂速度和尋優精度都要好,隨著迭代次數的增加，ISBO的曲線下降非常快，并且在迭代后期具有持續尋優的能力。對于函數f1，ISBO在300代左右搜索到函數的最佳值0，所以圖2a中，ISBO的曲線后面部分沒有顯示。圖2f～圖2h是多峰函數的平均收斂曲線，ISBO算法的尋優適應度值是8個算法中最好的。對于函數f7，ISBO算法在150代左右即搜索到全局最優解，表現了較強的魯棒性。由此說明對于這一類的多峰函數，ISBO具有很強的搜索能力，可以快速跳出局部最優值束縛向全局最優點靠近。

Figure 2 Average convergence curves of benchmark functions圖2 基準函數平均收斂曲線

綜上可知，ISBO算法對于所有基準函數都有很好的尋優結果。特別是對于高維、多峰的函數，具有較好的穩定性和尋優能力，有效地解決了原始緞藍園丁鳥優化算法收斂速度緩慢、求解精度不高的問題。

實驗4在認知無線電中的應用。

隨著無線電通信技術的飛速發展和人們對高傳輸速率的需求，頻譜資源匱乏的問題越顯突出，而導致頻譜資源缺乏的原因之一是無線接入技術的不合理。近年來，認知無線電CR(Cognitive Radio)[17]技術是解決當前頻譜供需矛盾的有效方法。針對傳統算法容易早熟、收斂速度慢等缺陷，本文采用改進緞藍園丁鳥優化算法優化頻譜分配效率，以最大化系統效益為評價指標，進而驗證算法的性能。其中最大化系統效益表示為：

(14)

其中，al,m∈{0，1}表示認知用戶l是否分配到信道，bl,m表示認知用戶l在使用信道m能獲得的最大收益,L表示認知用戶數，M表示可用信道數。值得注意的是，本文算法為十進制，而認知無線電頻譜分配系統中al,m∈{0，1}，所以本文使用常用的Sigmoid函數[18]來實現十進制到二進制的轉換。

(15)

(16)

在實驗中，將認知無線電系統分別與改進緞藍園丁鳥優化算法(ISBO)、原始緞藍園丁鳥優化算法(SBO)、粒子群優化算法(PSO)和遺傳算法(GA)結合，以驗證本文改進算法是否在通信系統中同樣有良好的性能。30次系統效益比較結果如表6所示。

Table 6 30 times system benefit comparison表6 30次系統效益比較

如圖3所示是ISBO與SBO、PSO和GA算法的一次迭代速度對比圖。系統總效益隨著迭代次數的增加而增大，ISBO算法在53代時，系統總效益達到最大，即此刻為認知智能電網的鄰域網中頻譜分配問題的最優解，在此以后系統總效益不再改變；ISBO算法的最優解明顯大于SBO算法的，說明了改進算法的有效性；PSO算法和GA算法分別在第178代和第211代時系統總效益才達到最大值，而且它們的效益值明顯低于ISBO算法的。

Figure 3 Convergence rate of different algorithms圖3 不同算法的收斂速度

為了說明ISBO算法在不同頻譜環境下均具有更好的優化性能，將4種算法在30種不同的頻譜環境下進行仿真，得到不同頻譜環境下的系統總效益圖，如圖4所示。從表6可以看出，ISBO算法最終的系統總效益比GA算法分別高出31.8%，比PSO算法高出14.6%，比未改進前的SBO算法高出8.8%。這也進一步說明了本文所提算法在頻譜分配當中的有效性。

Figure 4 Total systematic benefit of different spectrum environments圖4 不同頻譜環境的系統總效益

5 結束語

本文在標準緞藍園丁鳥優化算法的基礎上，引入非均勻變異算子、互利因子和自適應慣性權重，提出一種非均勻變異的互利自適應SBO算法ISBO。并將ISBO算法應用于復雜函數的尋優問題中，使用最優值、標準差等指標對算法進行檢驗，使用Wilcoxon秩和檢驗以及MAE對算法顯著性水平進行驗證，而且將ISBO算法應用于認知無線電頻譜分配問題中。研究表明，ISBO算法可以獲得更好的全局搜索和局部搜索能力，且能收斂到質量更好的最優解，算法的有效性和魯棒性也得到了驗證。ISBO算法在頻譜分配當中也表現出了較好的性能。