基于鳥群搜索行為和余弦變異的改進白鯊優(yōu)化算法

張超，楊 憶

（1.宿州職業(yè)技術(shù)學(xué)院計算機信息系,安徽 宿州 234000；2.淮北師范大學(xué)計算機科學(xué)與技術(shù)學(xué)院,安徽 淮北 235000）

優(yōu)化是為一組決策變量尋找最佳組合以解決特定問題的過程[1]?，F(xiàn)實世界很多復(fù)雜的科學(xué)和工程問題本質(zhì)上是困難的優(yōu)化問題。他們的目標函數(shù)大多是不可微、不連續(xù)、非線性和非凸的，涉及許多決策變量并受到各種約束的束縛?；谔荻鹊膫鹘y(tǒng)優(yōu)化技術(shù)，如牛頓法、序列二次規(guī)劃法等很難為其找到高質(zhì)量的解[2]。元啟發(fā)式算法不依賴于問題的梯度信息，其一般優(yōu)化框架是從一組隨機解開始，由多個智能體按照特定元啟發(fā)式算子協(xié)同求解問題[3]。元啟發(fā)式算法已經(jīng)成為求解現(xiàn)實世界復(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)實生活領(lǐng)域的諸多問題。

由于元啟發(fā)式算法的隨機性和搜索空間的未知性，這類算法存在缺陷：1）在搜索中無法精確控制種群的多樣性；2）算法易早熟收斂，陷入局部極值；3）無法適應(yīng)于求解所有現(xiàn)實問題。這些缺陷成為新算法提出和對現(xiàn)有算法改進研究的天然動機?？朔巳毕莸乃惴商岣呓鉀Q現(xiàn)實生活中特定問題的效率。

白鯊優(yōu)化（white shake optimizer，WSO）算法是Braik 等[1]在2022 年提出的一種新型的元啟發(fā)式算法，其靈感源自白鯊在深海中利用自己非凡的嗅覺、聽覺和視覺系統(tǒng)進行捕獵的行為。他們通過對白鯊捕獵時幾個典型行為的數(shù)學(xué)建模，仿生設(shè)計了WSO 算法。然而，與大多數(shù)基于種群的算法一樣，WSO 算法在處理高維優(yōu)化問題時亦存在容易早熟收斂、收斂精度低等問題。

為提高WSO 算法在處理高維優(yōu)化問題的收斂精度，本文提出一種改進的白鯊優(yōu)化（improved white shake optimizer，IWSO）算法。IWSO 算法使用3 種改進策略：1）引入Sinusoidal 混沌映射（Sinusoidal map）初始化策略，以提高初始解的多樣性，使其盡可能地覆蓋更多的潛在解空間，從而提高算法收斂速度；2）引入鳥群搜索行為，對白鯊個體的速度更新公式進行改進，賦予白鯊游動速度自適應(yīng)動態(tài)慣性權(quán)重，以提高算法的收斂速度；3）在WSO 開發(fā)階段，引入精英白鯊余弦變異策略，以加快算法向最優(yōu)解進化，以提高收斂精度。為了驗證IWSO 算法的性能，本文選取23 個著名基準函數(shù)和8 個CEC2014 測試函數(shù)做對比分析實驗。其結(jié)果表明，IWSO 算法優(yōu)于對比算法，具有良好的尋優(yōu)性能。

1 白鯊優(yōu)化（WSO）算法

大白鯊擁有非凡的視覺、嗅覺、聽覺和敏感的電磁場感受力，能很好地感知來自環(huán)境的各種復(fù)雜信息[1]，如圖1 所示。圖1 展示了白鯊各感官系統(tǒng)在搜尋獵物時能夠偵察的范圍。白鯊利用它們追蹤和狩獵。白鯊優(yōu)化算法主要是以白鯊的3 種典型行為進行數(shù)學(xué)建模仿生設(shè)計的。

圖1 白鯊及其感官系統(tǒng)[1]Fig.1 White shark and its sensory system[1]

1.1 朝向獵物移動的速度

大白鯊利用聽覺、視覺和嗅覺等非凡感官跟蹤獵物。大白鯊根據(jù)它在獵物移動時聽到的波浪聲音感知到獵物位置后，以波浪式向獵物游動，游動速度使用式（1）模擬計算。

式（2）—（5）中：n代表白鯊種群規(guī)模；rand(1,n)表示在[0,1]范圍內(nèi)，產(chǎn)生n個服從均勻分布的隨機數(shù)；k和K分別表示當前和最大迭代次數(shù)；pmin和pmax表示白鯊實現(xiàn)良好運動的最小和最大速度，一般取值為0.5 和1.5；τ表示加速度系數(shù)，一般取值為4.125。

1.2 朝向最優(yōu)獵物移動

當白鯊聽到獵物移動引起的波浪聲或聞到獵物的氣味時，會向其移動。某些情況下，當白鯊到達獵物原始位置時，獵物已經(jīng)離開，這時白鯊會進行搜索：1）根據(jù)獵物的氣味在當前區(qū)域進行局部探索；2）根據(jù)獵物制造的波浪聲進行全局搜索。這2 種搜索行為使用式（6）模擬計算。

式中sgn 是符號運算符。

式中 ⊕為異或運算。式（7）—（9）主要功能是將搜索空間上下邊界值賦予中溢出上下邊界的維度。

式中fmin和fmax分別表示波浪式運動的最小和最大頻率，一般取值為0.07 和0.75。

式中a0和a1是2 個正常數(shù)，用于管理探索和開發(fā)行為，一般取值為6.25 和100。

1.3 白鯊的集群行為

白鯊是一種高度社會化的動物。它們喜歡集群捕獵，捕獵時會保持高度合作，朝著最靠近獵物的白鯊移動。WSO 算法使用式（12）模擬群體朝著最佳白鯊移動行為。

式中：a2是一個正常數(shù)，控制開發(fā)和探索之間的平衡，一般取值為0.000 5。

WSO 算法使用式（15）模擬白鯊集群行為，白鯊個體根據(jù)到達最佳位置的白鯊的位置更新自己的位置，該位置非常接近獵物。

2 改進的白鯊優(yōu)化（IWSO）算法

WSO 算法在低維函數(shù)上具有良好的尋優(yōu)性能，但在高維函數(shù)上收斂精度較低，特別在問題維度大于100 維以上時，算法易陷入局部極值，早熟收斂。為此，本文使用3 種策略進行改進，以提高WSO 算法處理高維優(yōu)化問題的能力。

2.1 Sinusoidal 混沌映射初始化策略

由于初始解會對元啟發(fā)式算法的最終尋優(yōu)結(jié)果產(chǎn)生較大影響。WSO 算法的初始種群采用隨機化方式生成，易導(dǎo)致初始解在搜索域內(nèi)分布不均，缺乏多樣性。為此，引入Sinusoidal 混沌映射初始化種群，利用混沌系統(tǒng)的非線性、隨機性和遍歷性特點，提高初始種群的多樣性和在解空間的分布性，從而提高算法的尋優(yōu)性能。Sinusoidal 混沌映射的數(shù)學(xué)表達式為

其中，x∈[0,1]，本文a=2.3，x0=0.7。其300 次迭代映射產(chǎn)生的混沌序列值分布如圖2 所示。由圖2可見，混沌值在[0,1]之間分布均勻，使用其取代WSO 算法的偽隨機初始值，能夠有效提高初始種群的分布性。

圖2 Sinusoidal 混沌映射分布圖Fig.2 Distribution diagram of Sinusoidal chaos map

2.2 鳥群搜索行為的速度更新策略

白鯊向獵物游動的速度使用式（1）計算，其對WSO 算法至關(guān)重要。在WSO 算法全局搜索階段主要依賴速度進行位置更新計算。但式（1）使用收縮因子μ對速度更新規(guī)則進行整體縮放。μ的值取決于式（5）中加速度系數(shù)τ，根據(jù)文獻[1]的大量數(shù)值實驗后推薦的τ取值，μ實際值為0.703 46，是一個常數(shù)。對速度恒定的縮放，易使白鯊種群失去活性，導(dǎo)致算法在全局搜索時陷入極值，收斂停滯。

為了改進WSO 算法，本文首先刪除式（1）中μ縮放因子，并受粒子群優(yōu)化算法鳥群覓食行為啟發(fā)，將鳥群飛行速度的慣性權(quán)重思想引入式（1）中。改進后的速度更新策略使用式（17）計算。

式中：g是慣性權(quán)重參數(shù)，由式（18）計算；其他參數(shù)及取值和式（1）保持一致。

其中，gmax和gmin是慣性權(quán)重上下界，本文中g(shù)max=0.9，gmin=0.2。隨著迭代進程，g動態(tài)遞減。在迭代前期g取較大值，有利于白鯊種群在盡可能大的空間進行全局搜索，找到更多的潛在最優(yōu)解。在迭代過程中逐漸變小的g，可使得白鯊種群具備精細的局部開發(fā)能力，有利于在已找到的潛在最佳解中勘探到更好的最優(yōu)解。

2.3 精英白鯊余弦變異策略

每代最優(yōu)白鯊是種群中的精英，離獵物最近，在它的附近鄰域小空間內(nèi)進行精細化開發(fā)，能夠極大提升找到最佳解的概率，提高收斂精度。為此，本文在WSO 算法開發(fā)階段，引入精英白鯊余弦變異策略，利用余弦函數(shù)周期性振蕩特征，驅(qū)動算法在精英白鯊附近的小鄰域內(nèi)進行勘探。隨著算法的運行，精英白鯊更接近于獵物，開發(fā)的鄰域范圍應(yīng)逐漸收縮，因此，在本文中為余弦函數(shù)設(shè)計自適應(yīng)動態(tài)遞減的振幅。該過程使用式（19）模擬計算。

式中：B是cos(α)的振幅，由式（20）計算；α∈[0,2π]，是隨機數(shù)。em 為余弦變異控制參數(shù)，一般取0.2。rand 小于0.2 時進行精英白鯊余弦變異，反之，仍使用WSO 算法原開發(fā)策略。

其中，γ為形狀控制系數(shù)，B的值隨迭代次數(shù)非線性遞減。圖3 是不同γ值的B×cos(α)形狀對比圖，本文γ=100。從圖3 可見，在迭代開始，IWSO 算法在精英白鯊稍大鄰域內(nèi)進行搜索，隨著迭代進行，在精英白鯊微小鄰域內(nèi)進行開發(fā)，以此提高算法收斂速度和精度。

圖3 不同γ 值的B×cos(α)形狀對比圖Fig.3 Shape comparison of B×cos(α) for different values of γ

2.4 IWSO 算法

綜上，在Sinusoidal 混沌映射、動態(tài)慣性權(quán)重的鳥群搜索行為和精英白鯊余弦變異策略的有效集成，成為IWSO 算法。圖4 示出改進后的白鯊優(yōu)化算法的偽代碼。

圖4 IWSO 算法的偽代碼Fig.4 Pseudo-code of IWSO algorithm

3 仿真實驗

3.1 實驗設(shè)計

為充分驗證IWSO 算法的尋優(yōu)性能，仿真實驗在2 類領(lǐng)域內(nèi)普遍接受并能夠客觀評估元啟發(fā)式算法性能的函數(shù)上進行。一是著名的23 個基準函數(shù)，函數(shù)詳情可參閱文獻[8-10]。二是CEC2014中8 個復(fù)合函數(shù)，函數(shù)詳情可參閱文獻[16]。算法評價指標為尋優(yōu)結(jié)果的最好值、最差值、平均值和標準差。

本文選擇近年新興的5 種算法做對比實驗。5種算法分別是：SCA[7]、CHIO算法[8]、WOA[9]、HBA[10]和WHO 算法[11]。為保障算法比較的公平性，所有算法的種群規(guī)模設(shè)為30，最大迭代次數(shù)設(shè)為500。IWSO 算法參數(shù)使用第2 章已給出的值。對比算法的參數(shù)均使用對應(yīng)文獻推薦的設(shè)置，以保障其尋優(yōu)性能最佳。

3.2 在23 個函數(shù)上的實驗結(jié)果和分析

23 個函數(shù)分類情況如下：單峰函數(shù)，f1～f7；多峰函數(shù)，f8～f13；固定維度多峰函數(shù)，f14～f23。將f1～f13函數(shù)的維度設(shè)為30。

3.2.1 單峰函數(shù)實驗結(jié)果

表1 為算法的對比實驗結(jié)果。由表1 可知，IWSO 算法在f1～f4上每次皆能找到理論最優(yōu)值，而相應(yīng)的對比算法均不能。f5被稱為“香蕉”函數(shù)，一般的元啟發(fā)式算法在其上表現(xiàn)較差，而IWSO 算法最優(yōu)值可達1.555 3×10-3級別，平均值亦優(yōu)于對比算法，表現(xiàn)出優(yōu)越尋優(yōu)性能。在f6上：IWSO 算法優(yōu)于WSO 算法、CHIO 算法、WOA 和SCA；最好值不如HBA 和WHO 算法，但最差值、平均值和標準差均優(yōu)于它們。在f7上，IWSO 算法在4 個評價指標上亦均優(yōu)于其他算法。因此，IWSO 算法在單峰函數(shù)上的尋優(yōu)能力整體優(yōu)于所有對比算法。

表1 單峰函數(shù)上的對比實驗結(jié)果Tab.1 Comparative experimental results on unimodal functions

3.2.2 多峰函數(shù)實驗結(jié)果

表2 為算法在多峰函數(shù)上的對比實驗結(jié)果。由表2 可知，在f8上，IWSO 算法能收斂到理論最優(yōu)值，其他對比算法均不能，且IWSO 算法的均值和最差值好于所有對比算法。在f9和f11上，IWSO 算法和HBA 每次均能找到理論最優(yōu)值，整體略優(yōu)于WHO 算法，大幅優(yōu)于WSO 算法、CHIO 算法、WOA、SCA。在f10上：IWSO 算法、WOA、HBA 和WHO 算法最好值一樣，但從最差值、均值和標準差指標看，IWSO 算法更穩(wěn)定，魯棒性優(yōu)于它們；WSO 算法、CHIO 算法和SCA 表現(xiàn)較差。f12和f13函數(shù)較復(fù)雜，最優(yōu)值很難找到，但IWSO 算法整體上優(yōu)于所有對比算法。綜上所述，IWSO 算法在多峰函數(shù)上具有良好的收斂精度和魯棒性。

表2 多峰函數(shù)上的對比實驗結(jié)果Tab.2 Comparative experimental results on multimodal functions

3.2.3 固定維度多峰函數(shù)實驗結(jié)果

表3 為算法在固定維度多峰函數(shù)上的對比實驗結(jié)果。從找到理論最優(yōu)值維度分析：IWSO 算法、WSO 算法、HBA 和WHO 算法在所有10 個函數(shù)上都能找到理論最優(yōu)值；WOA 為5個，CHIO 算法為3個，SCA 為2個，表現(xiàn)相對較差。從算法的穩(wěn)定性維度分析：除了f14，從均值和標準差看，IWSO 算法表現(xiàn)出穩(wěn)健的魯棒性，整體好于對比算法。特別在f15、f21～f23上，IWSO 算法每次均能收斂到理論最優(yōu)值，表現(xiàn)出優(yōu)越的魯棒性，而對比算法均易陷入局部極值，魯棒性欠佳。因此，IWSO 算法提升了WSO 算法在固定維度多峰函數(shù)上尋優(yōu)的穩(wěn)定性，整體性能優(yōu)于其他對比算法。

表3 固定維度多峰函數(shù)上的對比實驗結(jié)果Tab.3 Comparison experimental results on fixed dimensional multimodal functions

綜上所述，IWSO 算法在3 種不同類型的函數(shù)上均表現(xiàn)出了優(yōu)越的尋優(yōu)性能，在收斂精度和穩(wěn)定性上較對比算法大幅提升，說明本文所提出的改進策略是可行和有效的。

3.2.4 收斂性分析

除了收斂精度和穩(wěn)定性外，衡量一個元啟發(fā)式算法性能優(yōu)劣的重要指標是收斂速度。收斂速度代表達到問題預(yù)設(shè)精度所耗費的迭代周期，在一定程度上反映了算法獲得最佳解時所花費時間的優(yōu)劣。圖5 為各算法在部分函數(shù)上的收斂曲線對比圖。橫坐標代表迭代次數(shù)，縱坐標代表到目前為止獲得的最佳解（做10 為底的對數(shù)處理）。

從圖5 可見，IWSO 算法的收斂曲線整體呈起伏前進形態(tài)，說明算法能夠有效跳出局部極值，不斷向最佳解收斂。在f1～f4上，IWSO 算法在100 次迭代左右即能收斂到函數(shù)的最優(yōu)值0，對比算法均不能。在f9和f11上，IWSO 算法找到最優(yōu)值0 僅需幾步迭代，較對比算法中表現(xiàn)較好的WOA、HBA、WHO 算法大幅提高。綜上說明所提Sinusoidal 混沌映射、動態(tài)慣性權(quán)重的鳥群搜索行為和精英白鯊余弦變異策略的有效集成，可提高IWSO 算法的收斂速度和精度。

圖5 收斂曲線對比圖Fig.5 Comparison of convergence curves

3.3 在CEC2014 復(fù)合函數(shù)上的實驗結(jié)果和分析

為了進一步驗證IWSO 算法在更復(fù)雜函數(shù)上的尋優(yōu)性能，本文做IWOS 算法和6 種對比算法在CEC2014 中8 個復(fù)雜復(fù)合函數(shù)上的實驗。以平均值、標準差作為評價指標。對實驗結(jié)果做p=5%顯著性水平下的Wilcoxon 秩和檢驗，以說明實驗真實性，以決策算法的性能優(yōu)劣，實驗結(jié)果如表4 所示。CEC2014 復(fù)合函數(shù)較復(fù)雜，理論最優(yōu)值很難獲得。從Wilcoxon 秩和檢驗結(jié)果看：IWSO算法在8 個函數(shù)上均優(yōu)于WSO 算法、CHIO 算法、WHO 算法和SCA；IWSO 算法在6 個函數(shù)上優(yōu)于WOA，在2 個函數(shù)上相當；IWSO 算法在6 個函數(shù)上優(yōu)于HBA，在f26上相當，在f27上略遜。特別地，在f30、f31上，IWSO 算法的收斂精度較對比算法提升4～6 個數(shù)量級。綜上，進一步驗證了所提3 種策略的有效性。

表4 CEC2014 復(fù)合函數(shù)上的對比實驗結(jié)果Tab.4 Comparison experimental results on the CEC2014 composite functions

4 IWSO 在更高維度上的尋優(yōu)性能

限于篇幅，本文選擇f1～f4這4 個函數(shù)做維度為300 和1 000 維的實驗，以充分展示IWSO 算法在更高維度時的優(yōu)越性能。對比實驗主要在IWSO 算法和基本W(wǎng)SO 算法之間進行，種群規(guī)模和最大迭代次數(shù)仍設(shè)為30 和500，獨立進行30 次實驗，實驗結(jié)果如表5 所示。表5 的平均值和標準差指標清晰地表明：IWSO 算法在300 維和1 000維時每次都能收斂到函數(shù)的最優(yōu)值0，不受維度變大的影響；基本W(wǎng)SO 算法在300 和1 000 維上收斂結(jié)果變得更差。這進一步說明，IWSO 算法充分解決了WSO 算法處理高維函數(shù)時性能較差的不足，達到了算法改進的目的。

表5 在更高維度上的對比實驗結(jié)果Tab.5 Comparison experimental results in higher dimensions

5 結(jié)論

針對白鯊優(yōu)化（WSO）算法在處理高維函數(shù)時存在早熟收斂，精度較差的不足，提出了一種改進的白鯊優(yōu)化（IWSO）算法。IWSO 算法集成了Sinusoidal 混沌映射初始化策略、基于鳥群搜索行為的速度更新策略和精英白鯊余弦變異策略。首先，在23 個基準函數(shù)和CEC2014 中8 個復(fù)合函數(shù)上進行了對比實驗，實驗結(jié)果表明，IWSO 算法在收斂精度、速度及其魯棒性上整體優(yōu)于WSO 算法、CHIO 算法、WOA、HBA、WHO 算法和SCA。其次，在300 和1 000 維度上做更高維度性能分析實驗，結(jié)果表明，IWSO 算法均能收斂到函數(shù)的理論最優(yōu)值，充分解決了WSO 算法處理高維函數(shù)時性能較差的不足。大量實驗結(jié)果表明，3 種策略的有效集成提高了初始解的多樣性及在解空間的分布，加快了白鯊向獵物游動的速度，有效維持了探索和開發(fā)之間的微平衡，進而達到了提升算法性能的目的。白鯊優(yōu)化（WSO）算法是2022 年新提出的元啟發(fā)式算法，相關(guān)研究和應(yīng)用尚處于起步階段，下一步的重點工作，將研究使用IWSO 算法解決現(xiàn)實世界的實際工程優(yōu)化問題。