張超,楊 憶
(1.宿州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)信息系,安徽 宿州 234000;2.淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 淮北 235000)
優(yōu)化是為一組決策變量尋找最佳組合以解決特定問題的過程[1]?,F(xiàn)實(shí)世界很多復(fù)雜的科學(xué)和工程問題本質(zhì)上是困難的優(yōu)化問題。他們的目標(biāo)函數(shù)大多是不可微、不連續(xù)、非線性和非凸的,涉及許多決策變量并受到各種約束的束縛?;谔荻鹊膫鹘y(tǒng)優(yōu)化技術(shù),如牛頓法、序列二次規(guī)劃法等很難為其找到高質(zhì)量的解[2]。元啟發(fā)式算法不依賴于問題的梯度信息,其一般優(yōu)化框架是從一組隨機(jī)解開始,由多個(gè)智能體按照特定元啟發(fā)式算子協(xié)同求解問題[3]。元啟發(fā)式算法已經(jīng)成為求解現(xiàn)實(shí)世界復(fù)雜優(yōu)化問題的流行方法。
目前,元啟發(fā)式算法中遺傳算法[4](genetic algorithm,GA)、粒子群優(yōu)化(particle swarm optimizer,PSO)算法[5]、蟻群優(yōu)化(ant colony optimization,ACO)算法[6]等經(jīng)典算法被廣泛利用。近幾年,一些新的元啟發(fā)式算法涌現(xiàn)出來,如正弦余弦算法(sine cosine algorithm,SCA)[7]、冠狀病毒群體免疫優(yōu)化(coronavirus herd immunity optimizer,CHIO)算法[8]、鯨魚優(yōu)化算法[9](whale optimization algorithm,WOA)、蜜獾算法[10](honey badger algorithm,HBA)、野馬優(yōu)化(wild horse optimizer,WHO)算法[11]等。這些算法幫助解決了圖像處理[12]、無線傳感器網(wǎng)絡(luò)優(yōu)化[13]、路徑規(guī)劃[14]、流水車間調(diào)度[15]等現(xiàn)實(shí)生活領(lǐng)域的諸多問題。
由于元啟發(fā)式算法的隨機(jī)性和搜索空間的未知性,這類算法存在缺陷:1)在搜索中無法精確控制種群的多樣性;2)算法易早熟收斂,陷入局部極值;3)無法適應(yīng)于求解所有現(xiàn)實(shí)問題。這些缺陷成為新算法提出和對(duì)現(xiàn)有算法改進(jìn)研究的天然動(dòng)機(jī)。克服了缺陷的算法可提高解決現(xiàn)實(shí)生活中特定問題的效率。
白鯊優(yōu)化(white shake optimizer,WSO)算法是Braik 等[1]在2022 年提出的一種新型的元啟發(fā)式算法,其靈感源自白鯊在深海中利用自己非凡的嗅覺、聽覺和視覺系統(tǒng)進(jìn)行捕獵的行為。他們通過對(duì)白鯊捕獵時(shí)幾個(gè)典型行為的數(shù)學(xué)建模,仿生設(shè)計(jì)了WSO 算法。然而,與大多數(shù)基于種群的算法一樣,WSO 算法在處理高維優(yōu)化問題時(shí)亦存在容易早熟收斂、收斂精度低等問題。
為提高WSO 算法在處理高維優(yōu)化問題的收斂精度,本文提出一種改進(jìn)的白鯊優(yōu)化(improved white shake optimizer,IWSO)算法。IWSO 算法使用3 種改進(jìn)策略:1)引入Sinusoidal 混沌映射(Sinusoidal map)初始化策略,以提高初始解的多樣性,使其盡可能地覆蓋更多的潛在解空間,從而提高算法收斂速度;2)引入鳥群搜索行為,對(duì)白鯊個(gè)體的速度更新公式進(jìn)行改進(jìn),賦予白鯊游動(dòng)速度自適應(yīng)動(dòng)態(tài)慣性權(quán)重,以提高算法的收斂速度;3)在WSO 開發(fā)階段,引入精英白鯊余弦變異策略,以加快算法向最優(yōu)解進(jìn)化,以提高收斂精度。為了驗(yàn)證IWSO 算法的性能,本文選取23 個(gè)著名基準(zhǔn)函數(shù)和8 個(gè)CEC2014 測(cè)試函數(shù)做對(duì)比分析實(shí)驗(yàn)。其結(jié)果表明,IWSO 算法優(yōu)于對(duì)比算法,具有良好的尋優(yōu)性能。
大白鯊擁有非凡的視覺、嗅覺、聽覺和敏感的電磁場(chǎng)感受力,能很好地感知來自環(huán)境的各種復(fù)雜信息[1],如圖1 所示。圖1 展示了白鯊各感官系統(tǒng)在搜尋獵物時(shí)能夠偵察的范圍。白鯊利用它們追蹤和狩獵。白鯊優(yōu)化算法主要是以白鯊的3 種典型行為進(jìn)行數(shù)學(xué)建模仿生設(shè)計(jì)的。
圖1 白鯊及其感官系統(tǒng)[1]Fig.1 White shark and its sensory system[1]
大白鯊利用聽覺、視覺和嗅覺等非凡感官跟蹤獵物。大白鯊根據(jù)它在獵物移動(dòng)時(shí)聽到的波浪聲音感知到獵物位置后,以波浪式向獵物游動(dòng),游動(dòng)速度使用式(1)模擬計(jì)算。
式(2)—(5)中:n代表白鯊種群規(guī)模;rand(1,n)表示在[0,1]范圍內(nèi),產(chǎn)生n個(gè)服從均勻分布的隨機(jī)數(shù);k和K分別表示當(dāng)前和最大迭代次數(shù);pmin和pmax表示白鯊實(shí)現(xiàn)良好運(yùn)動(dòng)的最小和最大速度,一般取值為0.5 和1.5;τ表示加速度系數(shù),一般取值為4.125。
當(dāng)白鯊聽到獵物移動(dòng)引起的波浪聲或聞到獵物的氣味時(shí),會(huì)向其移動(dòng)。某些情況下,當(dāng)白鯊到達(dá)獵物原始位置時(shí),獵物已經(jīng)離開,這時(shí)白鯊會(huì)進(jìn)行搜索:1)根據(jù)獵物的氣味在當(dāng)前區(qū)域進(jìn)行局部探索;2)根據(jù)獵物制造的波浪聲進(jìn)行全局搜索。這2 種搜索行為使用式(6)模擬計(jì)算。
式中sgn 是符號(hào)運(yùn)算符。
式中 ⊕為異或運(yùn)算。式(7)—(9)主要功能是將搜索空間上下邊界值賦予中溢出上下邊界的維度。
式中fmin和fmax分別表示波浪式運(yùn)動(dòng)的最小和最大頻率,一般取值為0.07 和0.75。
式中a0和a1是2 個(gè)正常數(shù),用于管理探索和開發(fā)行為,一般取值為6.25 和100。
白鯊是一種高度社會(huì)化的動(dòng)物。它們喜歡集群捕獵,捕獵時(shí)會(huì)保持高度合作,朝著最靠近獵物的白鯊移動(dòng)。WSO 算法使用式(12)模擬群體朝著最佳白鯊移動(dòng)行為。
式中:a2是一個(gè)正常數(shù),控制開發(fā)和探索之間的平衡,一般取值為0.000 5。
WSO 算法使用式(15)模擬白鯊集群行為,白鯊個(gè)體根據(jù)到達(dá)最佳位置的白鯊的位置更新自己的位置,該位置非常接近獵物。
WSO 算法在低維函數(shù)上具有良好的尋優(yōu)性能,但在高維函數(shù)上收斂精度較低,特別在問題維度大于100 維以上時(shí),算法易陷入局部極值,早熟收斂。為此,本文使用3 種策略進(jìn)行改進(jìn),以提高WSO 算法處理高維優(yōu)化問題的能力。
由于初始解會(huì)對(duì)元啟發(fā)式算法的最終尋優(yōu)結(jié)果產(chǎn)生較大影響。WSO 算法的初始種群采用隨機(jī)化方式生成,易導(dǎo)致初始解在搜索域內(nèi)分布不均,缺乏多樣性。為此,引入Sinusoidal 混沌映射初始化種群,利用混沌系統(tǒng)的非線性、隨機(jī)性和遍歷性特點(diǎn),提高初始種群的多樣性和在解空間的分布性,從而提高算法的尋優(yōu)性能。Sinusoidal 混沌映射的數(shù)學(xué)表達(dá)式為
其中,x∈[0,1],本文a=2.3,x0=0.7。其300 次迭代映射產(chǎn)生的混沌序列值分布如圖2 所示。由圖2可見,混沌值在[0,1]之間分布均勻,使用其取代WSO 算法的偽隨機(jī)初始值,能夠有效提高初始種群的分布性。
圖2 Sinusoidal 混沌映射分布圖Fig.2 Distribution diagram of Sinusoidal chaos map
白鯊向獵物游動(dòng)的速度使用式(1)計(jì)算,其對(duì)WSO 算法至關(guān)重要。在WSO 算法全局搜索階段主要依賴速度進(jìn)行位置更新計(jì)算。但式(1)使用收縮因子μ對(duì)速度更新規(guī)則進(jìn)行整體縮放。μ的值取決于式(5)中加速度系數(shù)τ,根據(jù)文獻(xiàn)[1]的大量數(shù)值實(shí)驗(yàn)后推薦的τ取值,μ實(shí)際值為0.703 46,是一個(gè)常數(shù)。對(duì)速度恒定的縮放,易使白鯊種群失去活性,導(dǎo)致算法在全局搜索時(shí)陷入極值,收斂停滯。
為了改進(jìn)WSO 算法,本文首先刪除式(1)中μ縮放因子,并受粒子群優(yōu)化算法鳥群覓食行為啟發(fā),將鳥群飛行速度的慣性權(quán)重思想引入式(1)中。改進(jìn)后的速度更新策略使用式(17)計(jì)算。
式中:g是慣性權(quán)重參數(shù),由式(18)計(jì)算;其他參數(shù)及取值和式(1)保持一致。
其中,gmax和gmin是慣性權(quán)重上下界,本文中g(shù)max=0.9,gmin=0.2。隨著迭代進(jìn)程,g動(dòng)態(tài)遞減。在迭代前期g取較大值,有利于白鯊種群在盡可能大的空間進(jìn)行全局搜索,找到更多的潛在最優(yōu)解。在迭代過程中逐漸變小的g,可使得白鯊種群具備精細(xì)的局部開發(fā)能力,有利于在已找到的潛在最佳解中勘探到更好的最優(yōu)解。
每代最優(yōu)白鯊是種群中的精英,離獵物最近,在它的附近鄰域小空間內(nèi)進(jìn)行精細(xì)化開發(fā),能夠極大提升找到最佳解的概率,提高收斂精度。為此,本文在WSO 算法開發(fā)階段,引入精英白鯊余弦變異策略,利用余弦函數(shù)周期性振蕩特征,驅(qū)動(dòng)算法在精英白鯊附近的小鄰域內(nèi)進(jìn)行勘探。隨著算法的運(yùn)行,精英白鯊更接近于獵物,開發(fā)的鄰域范圍應(yīng)逐漸收縮,因此,在本文中為余弦函數(shù)設(shè)計(jì)自適應(yīng)動(dòng)態(tài)遞減的振幅。該過程使用式(19)模擬計(jì)算。
式中:B是cos(α)的振幅,由式(20)計(jì)算;α∈[0,2π],是隨機(jī)數(shù)。em 為余弦變異控制參數(shù),一般取0.2。rand 小于0.2 時(shí)進(jìn)行精英白鯊余弦變異,反之,仍使用WSO 算法原開發(fā)策略。
其中,γ為形狀控制系數(shù),B的值隨迭代次數(shù)非線性遞減。圖3 是不同γ值的B×cos(α)形狀對(duì)比圖,本文γ=100。從圖3 可見,在迭代開始,IWSO 算法在精英白鯊稍大鄰域內(nèi)進(jìn)行搜索,隨著迭代進(jìn)行,在精英白鯊微小鄰域內(nèi)進(jìn)行開發(fā),以此提高算法收斂速度和精度。
圖3 不同γ 值的B×cos(α)形狀對(duì)比圖Fig.3 Shape comparison of B×cos(α) for different values of γ
綜上,在Sinusoidal 混沌映射、動(dòng)態(tài)慣性權(quán)重的鳥群搜索行為和精英白鯊余弦變異策略的有效集成,成為IWSO 算法。圖4 示出改進(jìn)后的白鯊優(yōu)化算法的偽代碼。
圖4 IWSO 算法的偽代碼Fig.4 Pseudo-code of IWSO algorithm
為充分驗(yàn)證IWSO 算法的尋優(yōu)性能,仿真實(shí)驗(yàn)在2 類領(lǐng)域內(nèi)普遍接受并能夠客觀評(píng)估元啟發(fā)式算法性能的函數(shù)上進(jìn)行。一是著名的23 個(gè)基準(zhǔn)函數(shù),函數(shù)詳情可參閱文獻(xiàn)[8-10]。二是CEC2014中8 個(gè)復(fù)合函數(shù),函數(shù)詳情可參閱文獻(xiàn)[16]。算法評(píng)價(jià)指標(biāo)為尋優(yōu)結(jié)果的最好值、最差值、平均值和標(biāo)準(zhǔn)差。
本文選擇近年新興的5 種算法做對(duì)比實(shí)驗(yàn)。5種算法分別是:SCA[7]、CHIO算法[8]、WOA[9]、HBA[10]和WHO 算法[11]。為保障算法比較的公平性,所有算法的種群規(guī)模設(shè)為30,最大迭代次數(shù)設(shè)為500。IWSO 算法參數(shù)使用第2 章已給出的值。對(duì)比算法的參數(shù)均使用對(duì)應(yīng)文獻(xiàn)推薦的設(shè)置,以保障其尋優(yōu)性能最佳。
23 個(gè)函數(shù)分類情況如下:?jiǎn)畏搴瘮?shù),f1~f7;多峰函數(shù),f8~f13;固定維度多峰函數(shù),f14~f23。將f1~f13函數(shù)的維度設(shè)為30。
3.2.1 單峰函數(shù)實(shí)驗(yàn)結(jié)果
表1 為算法的對(duì)比實(shí)驗(yàn)結(jié)果。由表1 可知,IWSO 算法在f1~f4上每次皆能找到理論最優(yōu)值,而相應(yīng)的對(duì)比算法均不能。f5被稱為“香蕉”函數(shù),一般的元啟發(fā)式算法在其上表現(xiàn)較差,而IWSO 算法最優(yōu)值可達(dá)1.555 3×10-3級(jí)別,平均值亦優(yōu)于對(duì)比算法,表現(xiàn)出優(yōu)越尋優(yōu)性能。在f6上:IWSO 算法優(yōu)于WSO 算法、CHIO 算法、WOA 和SCA;最好值不如HBA 和WHO 算法,但最差值、平均值和標(biāo)準(zhǔn)差均優(yōu)于它們。在f7上,IWSO 算法在4 個(gè)評(píng)價(jià)指標(biāo)上亦均優(yōu)于其他算法。因此,IWSO 算法在單峰函數(shù)上的尋優(yōu)能力整體優(yōu)于所有對(duì)比算法。
表1 單峰函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果Tab.1 Comparative experimental results on unimodal functions
3.2.2 多峰函數(shù)實(shí)驗(yàn)結(jié)果
表2 為算法在多峰函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果。由表2 可知,在f8上,IWSO 算法能收斂到理論最優(yōu)值,其他對(duì)比算法均不能,且IWSO 算法的均值和最差值好于所有對(duì)比算法。在f9和f11上,IWSO 算法和HBA 每次均能找到理論最優(yōu)值,整體略優(yōu)于WHO 算法,大幅優(yōu)于WSO 算法、CHIO 算法、WOA、SCA。在f10上:IWSO 算法、WOA、HBA 和WHO 算法最好值一樣,但從最差值、均值和標(biāo)準(zhǔn)差指標(biāo)看,IWSO 算法更穩(wěn)定,魯棒性優(yōu)于它們;WSO 算法、CHIO 算法和SCA 表現(xiàn)較差。f12和f13函數(shù)較復(fù)雜,最優(yōu)值很難找到,但I(xiàn)WSO 算法整體上優(yōu)于所有對(duì)比算法。綜上所述,IWSO 算法在多峰函數(shù)上具有良好的收斂精度和魯棒性。
表2 多峰函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果Tab.2 Comparative experimental results on multimodal functions
3.2.3 固定維度多峰函數(shù)實(shí)驗(yàn)結(jié)果
表3 為算法在固定維度多峰函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果。從找到理論最優(yōu)值維度分析:IWSO 算法、WSO 算法、HBA 和WHO 算法在所有10 個(gè)函數(shù)上都能找到理論最優(yōu)值;WOA 為5個(gè),CHIO 算法為3個(gè),SCA 為2個(gè),表現(xiàn)相對(duì)較差。從算法的穩(wěn)定性維度分析:除了f14,從均值和標(biāo)準(zhǔn)差看,IWSO 算法表現(xiàn)出穩(wěn)健的魯棒性,整體好于對(duì)比算法。特別在f15、f21~f23上,IWSO 算法每次均能收斂到理論最優(yōu)值,表現(xiàn)出優(yōu)越的魯棒性,而對(duì)比算法均易陷入局部極值,魯棒性欠佳。因此,IWSO 算法提升了WSO 算法在固定維度多峰函數(shù)上尋優(yōu)的穩(wěn)定性,整體性能優(yōu)于其他對(duì)比算法。
表3 固定維度多峰函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果Tab.3 Comparison experimental results on fixed dimensional multimodal functions
綜上所述,IWSO 算法在3 種不同類型的函數(shù)上均表現(xiàn)出了優(yōu)越的尋優(yōu)性能,在收斂精度和穩(wěn)定性上較對(duì)比算法大幅提升,說明本文所提出的改進(jìn)策略是可行和有效的。
3.2.4 收斂性分析
除了收斂精度和穩(wěn)定性外,衡量一個(gè)元啟發(fā)式算法性能優(yōu)劣的重要指標(biāo)是收斂速度。收斂速度代表達(dá)到問題預(yù)設(shè)精度所耗費(fèi)的迭代周期,在一定程度上反映了算法獲得最佳解時(shí)所花費(fèi)時(shí)間的優(yōu)劣。圖5 為各算法在部分函數(shù)上的收斂曲線對(duì)比圖。橫坐標(biāo)代表迭代次數(shù),縱坐標(biāo)代表到目前為止獲得的最佳解(做10 為底的對(duì)數(shù)處理)。
從圖5 可見,IWSO 算法的收斂曲線整體呈起伏前進(jìn)形態(tài),說明算法能夠有效跳出局部極值,不斷向最佳解收斂。在f1~f4上,IWSO 算法在100 次迭代左右即能收斂到函數(shù)的最優(yōu)值0,對(duì)比算法均不能。在f9和f11上,IWSO 算法找到最優(yōu)值0 僅需幾步迭代,較對(duì)比算法中表現(xiàn)較好的WOA、HBA、WHO 算法大幅提高。綜上說明所提Sinusoidal 混沌映射、動(dòng)態(tài)慣性權(quán)重的鳥群搜索行為和精英白鯊余弦變異策略的有效集成,可提高IWSO 算法的收斂速度和精度。
圖5 收斂曲線對(duì)比圖Fig.5 Comparison of convergence curves
為了進(jìn)一步驗(yàn)證IWSO 算法在更復(fù)雜函數(shù)上的尋優(yōu)性能,本文做IWOS 算法和6 種對(duì)比算法在CEC2014 中8 個(gè)復(fù)雜復(fù)合函數(shù)上的實(shí)驗(yàn)。以平均值、標(biāo)準(zhǔn)差作為評(píng)價(jià)指標(biāo)。對(duì)實(shí)驗(yàn)結(jié)果做p=5%顯著性水平下的Wilcoxon 秩和檢驗(yàn),以說明實(shí)驗(yàn)真實(shí)性,以決策算法的性能優(yōu)劣,實(shí)驗(yàn)結(jié)果如表4 所示。CEC2014 復(fù)合函數(shù)較復(fù)雜,理論最優(yōu)值很難獲得。從Wilcoxon 秩和檢驗(yàn)結(jié)果看:IWSO算法在8 個(gè)函數(shù)上均優(yōu)于WSO 算法、CHIO 算法、WHO 算法和SCA;IWSO 算法在6 個(gè)函數(shù)上優(yōu)于WOA,在2 個(gè)函數(shù)上相當(dāng);IWSO 算法在6 個(gè)函數(shù)上優(yōu)于HBA,在f26上相當(dāng),在f27上略遜。特別地,在f30、f31上,IWSO 算法的收斂精度較對(duì)比算法提升4~6 個(gè)數(shù)量級(jí)。綜上,進(jìn)一步驗(yàn)證了所提3 種策略的有效性。
表4 CEC2014 復(fù)合函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果Tab.4 Comparison experimental results on the CEC2014 composite functions
限于篇幅,本文選擇f1~f4這4 個(gè)函數(shù)做維度為300 和1 000 維的實(shí)驗(yàn),以充分展示IWSO 算法在更高維度時(shí)的優(yōu)越性能。對(duì)比實(shí)驗(yàn)主要在IWSO 算法和基本W(wǎng)SO 算法之間進(jìn)行,種群規(guī)模和最大迭代次數(shù)仍設(shè)為30 和500,獨(dú)立進(jìn)行30 次實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表5 所示。表5 的平均值和標(biāo)準(zhǔn)差指標(biāo)清晰地表明:IWSO 算法在300 維和1 000維時(shí)每次都能收斂到函數(shù)的最優(yōu)值0,不受維度變大的影響;基本W(wǎng)SO 算法在300 和1 000 維上收斂結(jié)果變得更差。這進(jìn)一步說明,IWSO 算法充分解決了WSO 算法處理高維函數(shù)時(shí)性能較差的不足,達(dá)到了算法改進(jìn)的目的。
表5 在更高維度上的對(duì)比實(shí)驗(yàn)結(jié)果Tab.5 Comparison experimental results in higher dimensions
針對(duì)白鯊優(yōu)化(WSO)算法在處理高維函數(shù)時(shí)存在早熟收斂,精度較差的不足,提出了一種改進(jìn)的白鯊優(yōu)化(IWSO)算法。IWSO 算法集成了Sinusoidal 混沌映射初始化策略、基于鳥群搜索行為的速度更新策略和精英白鯊余弦變異策略。首先,在23 個(gè)基準(zhǔn)函數(shù)和CEC2014 中8 個(gè)復(fù)合函數(shù)上進(jìn)行了對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,IWSO 算法在收斂精度、速度及其魯棒性上整體優(yōu)于WSO 算法、CHIO 算法、WOA、HBA、WHO 算法和SCA。其次,在300 和1 000 維度上做更高維度性能分析實(shí)驗(yàn),結(jié)果表明,IWSO 算法均能收斂到函數(shù)的理論最優(yōu)值,充分解決了WSO 算法處理高維函數(shù)時(shí)性能較差的不足。大量實(shí)驗(yàn)結(jié)果表明,3 種策略的有效集成提高了初始解的多樣性及在解空間的分布,加快了白鯊向獵物游動(dòng)的速度,有效維持了探索和開發(fā)之間的微平衡,進(jìn)而達(dá)到了提升算法性能的目的。白鯊優(yōu)化(WSO)算法是2022 年新提出的元啟發(fā)式算法,相關(guān)研究和應(yīng)用尚處于起步階段,下一步的重點(diǎn)工作,將研究使用IWSO 算法解決現(xiàn)實(shí)世界的實(shí)際工程優(yōu)化問題。