多策略金槍魚群算法及其應用

吳榮生

(漳州職業(yè)技術(shù)學院,福建漳州 363000)

0 引言

最優(yōu)化問題是工程實踐中常遇到的一類問題,這些實際問題通常是非線性、多變量、具有復雜約束的[1],因此需要算法去求解.傳統(tǒng)的優(yōu)化方法,諸如梯度下降法、牛頓迭代法等,需要被求解問題的梯度信息,難以高效地求解這些復雜問題.為了解決這些復雜優(yōu)化問題,受自然界動物群體行為的啟發(fā),研究人員提出了多種群智能優(yōu)化算法.群智能優(yōu)化算法不需要待解問題的梯度信息,能夠很好地平衡計算成本和計算精度之間的關(guān)系,因此受到廣大研究人員的關(guān)注并被用于各種優(yōu)化模型求解.最常見的群智能優(yōu)化算法是粒子群算法(Particle swarm optimization,PSO)[2],它模擬了鳥群捕食行為.隨著群智能優(yōu)化算法的不斷發(fā)展,越來越多的研究人員不斷提出并發(fā)展新的群智能優(yōu)化算法,例如鯨魚優(yōu)化算法(Whale optimization algorithm,WOA)[3]、灰狼優(yōu)化算法(Grey wolf optimization,GWO)[4]、旗魚優(yōu)化算法(The sailfish optimizer,SFO)[5]等,這些群智能算法被廣泛用于各類工程問題的求解.

金槍魚群算法(Tuna swarm optimization,TSO)是一種啟發(fā)于金槍魚合作覓食機制的群智能優(yōu)化算法,由Xie等人于2021年提出[6].TSO在金槍魚合作行為的基礎上,模擬其兩種不同覓食方式達到最優(yōu)捕食的目的.TSO相比其他算法,結(jié)構(gòu)簡單,可調(diào)參數(shù)少,具有不錯的性能.但TSO也存在一些不足,同其它群智能算法類似,TSO也會在優(yōu)化后期種群多樣性減弱,存在陷入局部最優(yōu)的可能,以及種群個體間的信息交流程度不夠.

為了解決金槍魚群算法存在的不足,本工作提出一種多策略金槍魚群算法(Multi-strategy tuna swarm optimization,MSTSO).首先,引入局部搜索策略,增強算法開發(fā)能力.將混沌算子和局部搜索策略結(jié)合,利用混沌算子的遍歷性和隨機性,進一步提升局部搜索策略的開發(fā)能力.其次,提出偏移分布估計策略,使個體能夠和優(yōu)勢種群以及最優(yōu)個體之間充分交流,引導個體進化方向,進一步提升算法搜索能力.為驗證改進算法的性能,使用CEC2017測試集對其進行檢驗,并和多個優(yōu)化算法進行比較,此外將改進算法應用于求解機器人路徑規(guī)劃問題,實驗說明了改進算法MSTSO具有更好的尋優(yōu)能力,能協(xié)調(diào)算法的開發(fā)和探索能力.

1 金槍魚群算法

金槍魚作為頂級的海洋捕食者,是一種群居動物.它們會根據(jù)覓食對象選擇對應的捕食策略.第一個策略是螺旋式覓食,當金槍魚進食時,它們會形成螺旋形游泳將獵物帶到淺水中,進行攻擊從而捕獲獵物.第二種策略是拋物線型覓食,每條金槍魚跟隨前一個個體,形成拋物線形狀來包圍獵物.金槍魚通過上述兩種方法成功覓食.TSO是基于這些自然覓食行為進行建模,該算法遵循的基本規(guī)則流程如下:

(1)種群初始化,TSO通過在搜索空間中均勻地隨機生成初始群來開始優(yōu)化過程,進行位置更新.

(1)

(2)a.螺旋覓食,金槍魚群通過形成緊密的螺旋來追逐獵物,除了追逐獵物,成群的金槍魚還相互交換信息.每一條金槍魚都跟在前一條魚的后面,因此可以在相鄰的金槍魚之間共享信息.基于上述原理,螺旋覓食策略的數(shù)學公式如下:

(2)

(3)

特別地,元啟發(fā)式算法通常在早期階段進行廣泛的全局探索,然后逐漸過渡到精確的局部開發(fā).因此,隨著迭代次數(shù)的增加,TSO將螺旋覓食的參考點從隨機個體更改為最優(yōu)個體.綜上所述,螺旋覓食策略的最終數(shù)學模型如下:

(4)

(2)b.拋物線式覓食,除了通過螺旋形成進食,金槍魚還可以形成拋物線合作進食.其中之一是金槍魚以食物為參考點,形成拋物線形進行進食.另外一種是金槍魚可以通過在自己周圍尋找食物進行覓食.并假設兩者的選擇概率均為50%的情況下兩種方式同時執(zhí)行.金槍魚通過以上兩種覓食策略協(xié)同捕獵,然后找到它們的獵物.

(5)

(3)終止條件,該算法通過對金槍魚的所有個體進行不斷的更新和計算,直到達到最大迭代次數(shù)或者滿足允許誤差后,返回最優(yōu)個體和相應的適應度值.

2 多策略金槍魚群算法

2.1 混沌局部搜索策略

混沌局部搜索策略通過搜索每一個解決方案的附近區(qū)域,從而找到更好的解決方案.因此該策略能夠有效提高算法的開發(fā)能力.混沌映射具有隨機性和遍歷性的特點,所以利用混沌映射可以進一步提高局部搜索策略的有效性.在MSTSO中,混沌局部搜索策略只應用于種群的優(yōu)勢種群.混沌局部搜索策略的公式具體如下:

(6)

(7)

2.2 偏移分布估計策略

分布估計策略通過概率模型表示個體之間的關(guān)系.該策略利用當前優(yōu)勢種群計算概率分布模型,并在概率分布模型抽樣的基礎上生成新的子代種群,通過不斷迭代最終得到最優(yōu)解.本工作選取表現(xiàn)較好的前一半個體進行采樣,并對較差個體使用該策略.該策略的數(shù)學模型描述如下.

3 仿真實驗與結(jié)果分析

3.1 算法性能驗證

為說明提出的MSTSO算法性能,選取CEC2017測試集進行驗證,包括1個單峰函數(shù)、7個多峰函數(shù)、10個混合函數(shù)和10個組合函數(shù).所有仿真在MATLAB R2016b軟件上運行,實驗環(huán)境為Inter(R)Core(TM)i7-8700 CPU,16 GB內(nèi)存的電腦.通過選取蝴蝶優(yōu)化算法(Butterfly optimization algorithm,BOA)[7]、爬行者搜索算法(Reptile search algorithm,RSA)[8]、算術(shù)優(yōu)化算法(Arithmetic optimization algorithm,AOA)[9]、被囊群優(yōu)化算法(Tunicate swarm algorithm,TSA)[10]和麻雀搜索算法(Sparrow search algorithm,SSA)[11]同改進算法MSTSO比較來說明其性能,為確保實驗的公平性,所有算法的種群數(shù)為300,最大迭代次數(shù)為1 000,其余算法的參數(shù)設置均采用原論文參數(shù)值,每種算法獨立運行51次,統(tǒng)計平均值如表1所示.

表1 七種算法在CEC2017上的測試結(jié)果Tab.1 Test results of seven algorithms on CEC2017

分析表1的結(jié)果可知,MSTSO在大多數(shù)測試函數(shù)上表現(xiàn)優(yōu)異.具體來說,對于單峰測試函數(shù)F1,MSTSO雖未能穩(wěn)定取得最優(yōu)解,但相比其他算法,MSTSO尋優(yōu)精度明顯優(yōu)于其他算法,達到9個數(shù)量級,這說明MSTSO具有優(yōu)異的局部搜索能力.多峰函數(shù)F2～F8常用于檢驗算法的全局搜索能力,這類函數(shù)通常有多個局部最小值,因此優(yōu)秀的算法能夠跳出局部最小值,得到全局最優(yōu)值.MSTSO在其中7個函數(shù)上均表現(xiàn)最好,僅在F8上排在RSA的后面,對于TSO來說,MSTSO在所有多峰函數(shù)上都表現(xiàn)好于TSO,這說明MSTSO的改進策略顯著改善了TSO的全局搜索能力.F9～F18和F19～F28分別是混合函數(shù)和組合函數(shù),這兩類函數(shù)結(jié)構(gòu)復雜,能夠更好地測試算法解決復雜優(yōu)化問題的能力,由表1可知,MSTSO僅在F19上排名第二,在剩下的混合函數(shù)和組合函數(shù)中,MSTSO均表現(xiàn)最優(yōu),取得了較好的結(jié)果,明顯優(yōu)于TSO,這說明本文提出的改進策略很好地提升了算法解決復雜結(jié)構(gòu)問題的能力,具有較好地解決現(xiàn)實世界復雜優(yōu)化問題的潛力.綜上所述,MSTSO能夠很好地平衡算法的開發(fā)和探索能力,具有較好的局部最優(yōu)規(guī)避能力,能夠有效避免算法早熟收斂.

3.2 機器人路徑規(guī)劃

為了進一步說明改進策略的有效性,檢驗算法解決具體問題的性能,應用MSTSO來解決機器人路徑規(guī)劃問題.機器人路徑規(guī)劃可被用于多個領(lǐng)域,比如果園噴霧[12]、煤礦救援[13]、物流倉儲[14]等.對于該問題,每只金槍魚代表一條可能的路徑.假設有N條可能的路徑,維度D由起點到目的點的連接數(shù)決定.環(huán)境是用柵格法建模的,柵格值用來等同位置上的障礙物.機器人的工作環(huán)境被等效為一個平面,類似于柵格效應,然后根據(jù)柵格值來確定可行區(qū)和障礙物區(qū).網(wǎng)格編號0被定義為可行區(qū),1被定義為障礙區(qū).機器人可以在指定為0的網(wǎng)格上行走.第i只金槍魚的適應度函數(shù)如下所示.

(8)

其中,j表示每只金槍魚的第j維.在機器人路徑規(guī)劃中,種群大小為300,迭代數(shù)為50.選擇在測試函數(shù)中表現(xiàn)較好的RSA、TSA以及TSO作為對比算法.每個算法都在10×10的模型中工作,最佳路線如圖1所示.為了避免偶然性,每種算法都運行了10次,并記錄了每種算法的平均值、最優(yōu)值和最差值.每種算法的統(tǒng)計結(jié)果顯示在表2中.

圖1 四種算法路徑規(guī)劃示意圖Fig.1 Diagram of four algorithms for path planning

如圖1所示,MSTSO的路線最短,其次是RSA和TSO,而TSA顯然陷入了局部最優(yōu).從表2可以看出,MSTSO在最優(yōu)成本、平均成本和最大成本方面是所有算法中最好的.這表明MSTSO相比TSO,能夠穩(wěn)定持續(xù)地給出更好的解決方案.圖2顯示了四種算法的收斂曲線,MSTSO雖然在前期收斂速度較慢,但在后期收斂速度提升,且收斂精度更高.圖3是四種算法多次求解路徑規(guī)劃問題的箱式圖,再次說明了MSTSO具有更穩(wěn)定取得更好解的能力.因此,多種策略的引入使算法的搜索更加全面,這大大提高了MSTSO的搜索能力,規(guī)劃出成本更低的路線.

圖2 四種算法收斂曲線圖Fig.2 Four algorithms convergence curve 圖3 四種算法箱式圖Fig.3 Four algorithms box diagram

4 結(jié)論

為了解決金槍魚群算法存在的開發(fā)和探索不平衡、易于陷入局部最優(yōu)等問題,提出融合了混沌局部搜索策略和偏移分布估計策略的多策略金槍魚群算法.混沌局部搜索策略將局部搜索策略和混沌算子進行結(jié)合,有效提升了算法的開發(fā)能力;偏移分布估計策略考慮最優(yōu)個體和優(yōu)勢種群的有效信息,成功引導種群更新,增強種群多樣性,提升了算法的尋優(yōu)性能.仿真實驗部分使用五種優(yōu)化算法在CEC2017測試集上對改進算法性能進行了驗證,結(jié)果表明本工作提出的MSTSO具有更高的精度和更好的穩(wěn)定性,性能相比TSO具有顯著提升.

此外,使用機器人路徑規(guī)劃問題對MSTSO解決實際問題的潛力進行了測試,仿真結(jié)果表明MSTSO能夠較好地解決具體問題,具有很好地解決現(xiàn)實世界優(yōu)化問題的潛力.在接下來的研究中,計劃將MSTSO擴展為二進制版本解決特征選擇問題,以及修改為多目標版本解決多目標工程優(yōu)化問題.