吳榮生

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

0 引言

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

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

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

1 金槍魚群算法

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

(1)種群初始化,TSO通過(guò)在搜索空間中均勻地隨機(jī)生成初始群來(lái)開(kāi)始優(yōu)化過(guò)程,進(jìn)行位置更新.

(1)

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

(2)

(3)

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

(4)

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

(5)

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

2 多策略金槍魚群算法

2.1 混沌局部搜索策略

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

(6)

(7)

2.2 偏移分布估計(jì)策略

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 算法性能驗(yàn)證

為說(shuō)明提出的MSTSO算法性能,選取CEC2017測(cè)試集進(jìn)行驗(yàn)證,包括1個(gè)單峰函數(shù)、7個(gè)多峰函數(shù)、10個(gè)混合函數(shù)和10個(gè)組合函數(shù).所有仿真在MATLAB R2016b軟件上運(yùn)行,實(shí)驗(yàn)環(huán)境為Inter(R)Core(TM)i7-8700 CPU,16 GB內(nèi)存的電腦.通過(guò)選取蝴蝶優(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]同改進(jìn)算法MSTSO比較來(lái)說(shuō)明其性能,為確保實(shí)驗(yàn)的公平性,所有算法的種群數(shù)為300,最大迭代次數(shù)為1 000,其余算法的參數(shù)設(shè)置均采用原論文參數(shù)值,每種算法獨(dú)立運(yùn)行51次,統(tǒng)計(jì)平均值如表1所示.

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

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

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

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

(8)

其中,j表示每只金槍魚的第j維.在機(jī)器人路徑規(guī)劃中,種群大小為300,迭代數(shù)為50.選擇在測(cè)試函數(shù)中表現(xiàn)較好的RSA、TSA以及TSO作為對(duì)比算法.每個(gè)算法都在10×10的模型中工作,最佳路線如圖1所示.為了避免偶然性,每種算法都運(yùn)行了10次,并記錄了每種算法的平均值、最優(yōu)值和最差值.每種算法的統(tǒng)計(jì)結(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ī)劃問(wèn)題的箱式圖,再次說(shuō)明了MSTSO具有更穩(wěn)定取得更好解的能力.因此,多種策略的引入使算法的搜索更加全面,這大大提高了MSTSO的搜索能力,規(guī)劃出成本更低的路線.

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

4 結(jié)論

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

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