基于多策略改進的蜜獾優化算法

徐碧陽,覃 濤,魏 巍,范圓成,楊 靖

1(貴州大學 電氣工程學院,貴陽 550025)

2(中國電建集團 貴州電力設計研究院有限公司,貴陽 550025)

3(中國電建集團 貴州工程有限公司,貴陽 550025)

0 引 言

在過去的幾十年里,隨著優化問題的復雜性和難度不斷增加,眾多學者對優化技術的研究變得越來越深入[1].優化方法主要基于數學方法和隨機方法[2]兩種,數學方法在解決高維問題時容易受到約束條件的影響陷入維度災難,而基于隨機方法尋優的元啟發式算法在解決高維問題時能夠跳出局部限制,找到全局最優解.因此,元啟發式算法目前廣泛應用于工程應用、交通運輸、智能醫療和經濟管理等領域中的復雜優化問題.

近些年來,大量元啟發式的仿生優化算法被提出,如根據鳥群和魚群的覓食行為提出的粒子群算法(Particle Swarm Optimization,PSO)[3]、根據灰狼群體中的社會等級機制和捕獵行為提出的灰狼算法(Grey Wolf Optimization,GWO)[4]、根據鯨魚圍捕獵物的行為提出的鯨魚優化算法(Whale Optimization Algorithm,WOA)[5]、根據麻雀的覓食行為和反捕食行為提出的麻雀搜索算法(Sparrow Search Algorithm,SSA)[6]、根據白骨頂雞在水面上的兩種不同運動模式提出的白骨頂優化算法(Coot Optimization Algorithm,COOT)[7]、根據北方蒼鷹的捕獵過程提出的北方蒼鷹算法(Northern Goshawk Optimization,NGO)[8]等.

2021年Fatma A等人通過模擬蜜獾的覓食行為提出一種新型的仿生優化算法—蜜獾算法(Honey Badger Algorithm,HBA)[9].HBA算法尋優能力強,收斂精度高,穩定性強,解決優化問題具有一定的優勢,但在尋優過程中,存在收斂速度慢,容易陷入局部最優等問題.針對上述問題,部分學者對HBA進行了優化,文獻[10]在初始化階段采用邏輯映射,使種群分布更加合理,并通過反向學習對個體進行選擇,找到最好的個體;文獻[11]在位置更新階段引入交叉變異原則,使得搜索范圍更廣,收斂速度更快.文獻[12]在局部搜索階段引入維度學習策略,平衡勘探與開發的能力.上述改進算法相比原始蜜獾算法在性能上有了一定的提升,但仍存在一些不足:1)部分改進算法的優化策略單一,只對種群初始化階段進行優化,沒有深層次考慮HBA收斂緩慢和陷入局部最優的原因;2)現有優化策略并沒有從根本上優化蜜獾的挖掘尋優機制,算法收斂速度和跳出局部最優的能力沒有得到提升;3)改進算法的測試實驗不充分,未對高維度條件下的測試函數和實際應用進行分析,未能充分體現算法的優越性與魯棒性.

綜上所述,現有針對HBA的改進算法還存在不足,因此本文提出一種基于多策略改進的蜜獾優化算法(Improved Honey Badger Optimization Algorithm based on Multi-strategies,IHBA).首先,通過Sobol序列對蜜獾種群進行初始化,提升種群的多樣性;其次,采用優化的動態自適應密度因子,平衡全局探索與局部探索的能力;并在挖掘階段引入黃金正弦策略,按照黃金分割系數切割解空間,提升蜜獾的搜索速度;最后,利用柯西變異因子對最優位置進行擾動,提升算法跳出局部最優的能力.本文采用10個經典測試函數對IHBA和7種優化算法進行尋優對比和Wilcoxon秩和檢驗,同時將8種算法應用到2個工程設計優化問題中進行對比測試,實驗結果驗證了IHBA的優越性與魯棒性.

1 蜜獾算法(HBA)

蜜獾具有獨特的狩獵方式,其擅長用嗅覺估計獵物的位置,用挖掘確定獵物的位置,從而完成對獵物的抓捕.蜜獾喜歡以蜂蜜為食,但不善于定位蜂巢.而蜂蜜向導鳥擅長定位蜂巢,但得不到蜂蜜.因而蜜獾在導蜜鳥的引導下找到并打開蜂巢,使二者共同享受蜂蜜.Fatma A等[9]將上述的兩種行為抽象為挖掘階段和采蜜階段,通過建立數學模型提出了蜜獾算法(HBA).

1)初始化種群

根據式(1)初始化蜜獾的數量及位置.

xi=lbi+r1×(ubi-lbi)

(1)

式中,r1∈(0,1)內的隨機數,xi是種群中第i個蜜獾的位置,lbi和ubi分別是搜索域的下界和上界.

2)定義強度

蜜獾的嗅覺強度不僅與獵物的集中強度有關,還與獵物和蜜獾之間的距離有關.Ii是獵物的氣味強度,氣味強度越高,蜜獾運動越快,反之亦然.定義如下:

(2)

S=(xi-xi+1)2

(3)

di=xprey-xi

(4)

式中,r2∈(0,1)內的隨機數,S為源強度或獵物集中強度,di表示獵物與第i只蜜獾之間的距離.

3)更新密度因子

密度因子w控制時變隨機化,以確保勘探到開發的平穩過渡.當更新隨著迭代次數減少時,密度因子w也會減少隨機化.定義如下:

(5)

式中,tmax是迭代最大次數,C為一個大于1的常數,一般設置為2.

4)挖掘階段

在挖掘階段,蜜獾運動范圍類似于心形,定義如下:

xnew=xprey+F×β×I×xprey+F×r3×w×di×
|cos(2πr4)×[1-cos(2πr5)]|

(6)

式中,xprey是獵物的全局最優位置,β是蜜獾獲取食物的能力,取大于等于1的數,一般設為6,di是獵物與第i只蜜獾之間的距離,r3、r4和r5是(0,1)3個不同的隨機數,F是改變搜索方向的標志,由式(7)所確定:

(7)

式中,r6∈(0,1)內的隨機數.在挖掘階段中,蜜獾對嗅覺強度Ii、與獵物之間的距離di、更新密度因子w的依賴性很強,同時挖掘期間會受F的干擾,以便找到更好的獵物位置.

5)采蜜階段

蜜獾跟隨導蜜鳥找到蜂巢的情況定義如下:

xnew=xprey+F×r7×w×di

(8)

式中,xnew是蜜獾的新位置,xprey是獵物的位置.由式(8)可知,蜜獾在搜尋獵物時根據距離信息di在xprey附近的位置進行搜索.搜索過程中也會受到密度因子w和搜索方向F的影響.

2 基于多策略改進的蜜獾優化算法(IHBA)

針對原始的蜜獾算法在解決高維優化問題時存在收斂速度慢、容易陷入局部最優的問題,本文在HBA的基礎上做了如下改進:1)引入Sobol序列初始化種群;2)在位置更新處引入優化的動態自適應密度因子和黃金正弦策略;3)引入柯西變異對最優位置進行擾動.

2.1 Sobol序列初始化種群

種群初始化方式對仿生優化算法的尋優過程有一定的影響,均勻合理的種群分布可以保證算法尋優過程中解的多樣性.HBA采用隨機分布的方式進行種群初始化,造成蜜獾在初始階段位置不能均勻分布,進而導致搜索范圍不全面,種群多樣性變差.因此,本文在初始化階段中引入了Sobol序列.

Sobol[13]序列是一種低差異序列,在高維數上具有優勢,并且在初始化時按照序列產生數字,其具有分布均勻,收斂速度快的優點.圖1為隨機序列與Sobol序列,在二維空間內種群數為N=300,產生范圍為[0,1]的條件下生成的種群分布圖.可以看出Sobol序列在給定條件下分布更均勻,空間利用率更高.通過使用Sobol序列改變蜜獾的初始化方式,提升了種群的多樣性和解的多樣性,有利于算法后期全局勘探和局部開發的平衡.

圖1 隨機序列與Sobol序列分布對比Fig.1 Comparison of distribution between random sequence and Sobol sequence

2.2 動態自適應密度因子

蜜獾在進行挖掘或采蜜時都會受到密度因子w的影響,隨著迭代次數的增加,蜜獾的搜索范圍會被限制,不能夠遍歷最優值,導致算法容易陷入局部最優值,搜索精度變差.為解決此類問題,現有研究采用了多種策略.文獻[14]引入了動態自適應權重,通過自適應地調整搜索空間,達到平衡勘探與開發的目的.文獻[15]提出非線性控制參數組合調整策略,通過選擇權重系數的最佳參數值得到最優的動態自適應權重,從而更好的均衡全局搜索和局部搜索的能力.本文通過以上兩種策略對HBA原有的密度因子公式進行優化,文獻[14]的密度因子為w1,如式(9)所示,文獻[15]的密度因子為w2,如式(10)所示.式中,rand為[0,1]內的隨機數.

w1=2×exp(-5.×rand×(t/tmax))

(9)

(10)

為驗證3種密度因子的性能,本文對3種密度因子進行對比,如圖2所示.

圖2 3種密度因子的變化曲線Fig.2 Variation curves of three density factors

由圖2可知,w1在迭代前期遞減速度較快,導致對全局搜索不完整,后期遞減速度緩慢,導致對局部搜索不完整,并且其自身具有一定的隨機性,會導致在迭代結束時收斂因子未能收斂到0.w2在迭代前期變化速率較慢,在搜尋中保持較大的距離,因此蜜獾在尋優時能夠擴大搜索范圍,增強全局搜索能力;在迭代中期w2變化速度較快,提高了算法的收斂速度和跳出局部最優的能力;在迭代后期w2的變化速率減慢,蜜獾對現有解空間進行尋優,提升了算法的局部搜索能力.因此,為平衡算法勘探和開發的能力,本文采用式(10)對挖掘階段和采蜜階段進行位置更新.

2.3 黃金正弦策略更新位置

黃金正弦算法(Golden Sine Algorithm,Gold-SA)是由Tanyildizi等人[16]于2017年提出的一種元啟發式算法,該算法依據單位圓與正弦函數的關系,遍歷單位圓上所有的點即正弦函數上所有的點,以此增強算法的全局勘探能力.此外,該算法在每次迭代中引入黃金分割系數切割并探索解空間,提升了算法的局部開發能力.

Gold-SA將黃金分割系數c1和c2引入位置更新中切割解空間,從而平衡勘探與開發的能力,數學表達式如下:

c1=a(1-h)+bh

(11)

c2=ah+b(1-h)

(12)

黃金分割系數每經一次迭代就會切割一次解空間,位置更新公式如下:

xgnew=xi|sin(r1)|-r2sin(r2)|c1xb-c2xi|

(13)

式中,xgnew為迭代后個體的位置;xb為個體的最優位置;r1∈(0,2π)內的隨機數,r2∈(0,π)內的隨機數.

因此,本文將Gold-SA算法作為局部算子引入挖掘階段的位置更新公式,使尋優空間縮小,尋優時間減少,收斂速度加快.改進后的式(6)如下:

xnew=xprey+F×β×I×xprey+F×r3×α×di×
|cos(2πr4)×[1-cos(2πr5)]|×xgnew

(14)

通過引入Gold-SA算法,從根本上改變了蜜獾算法的挖掘搜索機制,在獵物范圍不變的情況下,蜜獾在探索階段的搜索空間減小,大幅度縮短了蜜獾尋優的時間,如圖3所示.

圖3 蜜獾的原運動軌跡與加入黃金正弦后的運動軌跡圖Fig.3 Original trajectory of the honey badger and the trajectory after adding the golden sine

2.4 融合柯西變異策略

蜜獾算法在尋優后期容易陷入局部最優值,因此本文引入柯西變異算子.柯西變異來源于柯西分布,柯西分布是一種在概率論中常見的連續型概率分布[17],其中間概率密度大,兩端概率密度小.由于柯西分布具有兩端形狀又長又扁的特點,因此柯西變異的擾動能力很強.標準柯西分布的概率密度公式如下:

(15)

圖4為高斯分布與柯西分布的概率密度曲線.柯西分布的峰值在原點處,并且從峰值向兩端延伸的過程平緩,而高斯變異在原點的峰值較高,會導致擾動能力變差.因此將柯西變異引入蜜獾算法中,對蜜獾的最優位置進行擾動變異得到新解,從而改善原始算法跌入局部區域的缺陷[18].使用式(16)對最優位置進行擾動:

圖4 標準柯西分布和高斯分布的概率密度函數曲線Fig.4 Probability density function curves of standard Cauchy distribution and Gaussian distribution

xnew=xbest+xbest×Cauchy(0,1)

(16)

2.5 IHBA算法

IHBA算法執行的流程如下:

Step 1.初始化種群數N,最大迭代次數tmax,蜜獾獲取食物的能力β等參數;

Step 2.根據Sobol序列對種群進行初始化;

Step 3.計算每只蜜獾的適應度值并進行排序;

Step 4.根據式(2)～式(4)計算蜜獾的嗅覺強度;

Step 5.在蜜獾的挖掘階段根據式(6)、式(7)、式(10)～式(14)更新蜜獾的位置;

Step 6.在蜜獾的采蜜階段根據式(4)、式(8)、式(10)更新蜜獾的位置;

Step 7.根據式(16)對當前最優解進行擾動,得到新解;

Step 8.判斷是否滿足最大迭代次數,若滿足條件則進入下一步,反之跳轉Step 4;

Step 9.程序結束,輸出最優解.

2.6 IHBA算法時間復雜度分析

原始HBA算法的時間復雜度為O(T×N×D),其中N為種群規模,T為最大迭代次數,D為維度.引入Sobol序列初始化種群的時間復雜度為O(N×D),引入動態自適應權重雖然改變了原算法中的更新密度因子,但沒有增加額外操作,因此該階段的時間復雜度仍為O(N×D),引入黃金正弦策略的時間復雜度為O(N×D),引入柯西變異策略的時間復雜度為O(N×D).綜上所述,IHBA總的時間復雜度為O(T×N×D),與基礎的HBA算法時間復雜度一致,改進后的算法并沒有使原算法的運行時間增加.

3 實驗仿真與結果分析

3.1 實驗環境

本文仿真環境采用Windows11 64bit操作系統,其中內存為16GB,CPU為Intel(R)Core(TM)i5-11400HU@2.70GHz,仿真軟件為MATLAB R2016a.

3.2 實驗設計

為測試IHBA算法在優化問題中的性能,本文選取PSO、WOA、GWO、SSA、COOT、HBA、NGO與IHBA進行對比.

本文選取10個經典的測試函數[19]進行尋優測試,f1～f5為單峰函數,用于考察算法的局部搜索能力,f6～f10為多峰函數用于考察算法的全局搜索能力,測試函數的詳細信息如表1所示.實驗中每個算法的種群數為30,迭代次數為1000次,其它參數設置如表2所示.

表1 基準測試函數Table 1 Benchmark function

表2 實驗中算法的參數設置Table 2 Parameter setting of algorithm in experiment

3.3 IHBA與智能算法的尋優性能分析

為了測試算法在不同維度下的尋優能力,本文將8種算法分別在維度為30、50和100的情況下進行試驗.為了保證實驗結果的可靠性,8種算法在每個測試函數下獨立運行30次,并且選擇每個算法的平均值、標準差、最差值以及最優值為評價指標.其中,最優值和最差值反映解的質量,平均值和標準差反映算法的收斂精度和穩定性,具體結果如表3～表5所示.

表3 單峰和多峰函數測試結果(D=30)Table 3 Test results of unimodal and multimodal functions(D=30)

表5 單峰和多峰函數測試結果(D=100)Table 5 Test results of unimodal and multimodal functions(D=100)

由表3～表5分析可知:

1)在10個測試函數中,IHBA在低維度下具有很好的尋優性能,與其他算法相比,改進后的算法在高維度下的優越性更大.從單個表分析,IHBA在測試函數f1～f4、f6、f8下均收斂到理論值0,并且最差值、最優值、標準差都為0,說明IHBA具有較高的收斂精度和較好的魯棒性.雖然改進后的算法在其他的測試函數下未能收斂到理論值,但相對于其他算法,IHBA的各個指標具有一定的優勢.對于函數f5,SSA、WOA、HBA、IHBA都具有較好的收斂能力,但HBA、IHBA具有輕微的優勢,并且IHBA比HBA高1個數量級,比SSA高2個數量級,這表明HBA本身具有一定的優勢;對于函數f7,除了PSO和GWO,其他算法都收斂到一定值,但IHBA和SSA的標準差精度遠遠高于其他算法;對于函數f9,除SSA、PSO算法外,IHBA的收斂精度高于其它算法至少4個數量級,比HBA的平均值精度高于5個數量級,說明了IHBA改進策略的有效性;對于函數f10,PSO、HBA和IHBA的收斂精度較高,但IHBA的魯棒性更好.通過該角度分析,可以看出IHBA保持了HBA原有的優勢,增加了尋優精度.

2)隨著維度的增加,IHBA無論在30維、50維還是100維,都能夠跳出局部最優值,達到理想最優值,這說明改進的效果是可行的.隨著維度的增加,對于函數f1～f4、f6、f8,IHBA依然能收斂到理論最優值0,在其它函數的測試下,雖然所有算法未收斂到最優值,但IHBA在尋優時,仍然保持著較高水平,向理論最優值無限靠近;對于函數f7,IHBA在高維上的尋優精度和標準差都未發生改變,且在其他函數上,IHBA在尋優精度和穩定性方面始終具有優勢.通過該角度分析,可以看出IHBA在高維度下的優勢很大,并且能夠跳出局部最優值找到最優解,提高了算法解決高維問題的能力,為解決工程應用問題打下良好的基礎.

3.4 IHBA與智能算法的收斂曲線分析

為了更好地反映IHBA的動態收斂特性,本文給出了8種算法在10個測試函數(維度D=30)下的收斂曲線,如圖5(a)～圖5(j)所示,其中橫坐標為迭代次數,縱坐標為適應度值.對于單峰函數f1～f4,IHBA的收斂速度和尋優精度明顯優于其它算法,并且在算法初期的全局搜索能力和后期的局部搜索能力上具有明顯的優勢.對于多峰函數f5～f10,IHBA的收斂速度和尋優精度仍然優于其他算法,與原算法HBA相比,IHBA由于引入柯西變異,種群跳出局部最優能力增強,引入黃金正弦策略,算法的尋優速度大幅度增加.通過對收斂曲線的分析,可以看出IHBA的收斂速度得到很大的提升,IHBA在很大程度上改善了HBA算法的缺陷,并且提升了尋優精度,在維持原有的優勢下提升了算法的性能.

圖5 測試函數收斂曲線Fig.5 Test function convergence curve

綜上所述,IHBA算法能平衡勘探和開發的能力,在低維和高維問題上都具有較好的尋優性能.在求解不同的測試函數時,IHBA算法的尋優精度、求解速度、魯棒性均優于其它7種算法.

3.5 Wilcoxon秩和檢驗

為進一步驗證IHBA算法的優越性,保證算法評估的客觀性,對算法進行數據統計學分析.本文對測試函數集進行Wilcoxon秩和檢驗[20],顯著性水平為P=5%.原假設H0:兩種算法不存在顯著性差異.若檢驗結果P<5%時,原假設不成立,說明算法存在顯著性差異;若檢驗結果P>5%時,原假設成立,說明算法差異不明顯.用檢驗符號Q表示結果,若Q=0,說明H0假設成立;若Q=1,說明H0假設不成立;若出現NaN標記,說明算法性能相當.在維度為30,獨立運行30次條件下,本文選取IHBA在10個測試函數下的運行結果與其他算法的運行結果進行Wilcoxon秩和檢驗,“+/-/=”分別表示“優/劣/相當”,具體結果見表6.

表6 測試函數下的秩和檢驗P值Table 6 P-value of rank sum test under test function

由表6可知,大部分算法的秩和檢驗P值均小于0.05,表明IHBA算法與其余7種算法之間存在顯著性差異,且具有良好的尋優性能,進一步表明IHBA具有較好的魯棒性和穩定性.

4 IHBA算法的工程應用分析

元啟發式優化算法主要解決實際的工程應用問題,工程應用的結果也是評價一個算法優越性的指標之一.本文將IHBA與上述7種算法應用于壓縮彈簧設計問題和壓力容器設計問題中.這2個工程問題采用文獻[21]中的罰函數作為非線性約束條件,使算法能夠拋棄差值.在尋優過程中,每個算法獨立運行30次,取最優值的平均值,參數設置與3.2節相同.

4.1 壓縮彈簧設計問題

壓縮彈簧設計是最小約束優化問題,其目的主要是減輕彈簧的重量.該優化問題根據最小撓度、剪切應力、振蕩頻率以及外徑限制4個約束條件來設計3個變量-彈簧圈平均直徑(D)、彈簧金屬絲直徑(d)、以及彈簧有效圈數(N).該問題的數學描述如下所示:

1)變量

壓縮彈簧的3個屬性用x1、x2、x3來表示.

x=[x1x2x3]=[dDN]

(17)

2)目標函數

(18)

3)決策變量取值范圍

(19)

4)約束條件

(20)

由表7可知,IHBA算法在d=0.0519,D=0.3633,N=10.9089處得到最輕質量0.012664.這說明與SSA、COOT等尋優能力很強的算法相比,IHBA算法在壓縮彈簧設計問題上具有更好的搜索能力,也說明本文提出的優化策略提升了原始HBA算法跳出局部最優的能力,充分驗證了改進策略的有效性.

4.2 壓力容器設計問題

壓力容器設計問題的主要目的是在滿足生產的前提下使總費用最少.該優化問題的4個設計變量為外殼厚度(Ts)、封頭厚度(Th)、內半徑(R)、以及容器長度(L).其中Ts和Th為0.625的整數倍,R和L為連續變量.該問題的數學描述如下所示:

1)變量

壓力容器的4個屬性用x1、x2、x3和x4來表示.

x=[x1x2x3x4]=[TsThRL]

(21)

2)目標函數

(22)

3)決策變量取值范圍

(23)

4)約束條件

(24)

由表8可知,IHBA算法在Ts=0.5133,Th=0.2497,R=45.2658,L=200處得到最低費用5835.577,與其它7種算法相比,費用是最低的.這表明IHBA在解決壓力容器設計問題時能夠在最優值的范圍內搜索,在搜索過程中能夠憑借較好的搜索能力得到最優解,以達到更好的優化效果.這說明改進后的動態自適應密度因子擴大搜索范圍的能力很強,柯西變異策略跳出局部最優值的能力很強,驗證了改進策略的有效性.

通過對上述2個工程問題的求解,表明了本文所提出的算法IHBA提升了HBA算法的性能,在解決典型工程優化問題時具有較大的優勢,彌補了HBA算法在工程應用中的不足.

5 總 結

本文針對原始HBA算法在解決大規模問題存在收斂速度慢、容易陷入局部最優的不足,提出了一種基于多策略改進的蜜獾優化算法(IHBA).使用Sobol序列初始化種群,增加種群的多樣性;引入改進的動態自適應密度因子,平衡勘探與開發;在蜜獾的挖掘階段引入黃金正弦策略提高算法的尋優效率;引入柯西變異策略,對最優位置進行擾動,進一步優化種群和提升解的質量.采用10個經典測試函數對IHBA和7種優化算法進行的尋優對比和Wilcoxon秩和檢驗,結果表明IHBA具有更好的尋優能力和魯棒性.最后,將IHBA應用到2種實際的工程應用中,進一步驗證了算法的有效性和優越性.未來將對IHBA的改進策略進行優化,更大地提升算法的延展性.