求解高維復(fù)雜函數(shù)的兩類新型蝗蟲優(yōu)化算法

王 倩，李風(fēng)軍

(寧夏大學(xué) 數(shù)學(xué)統(tǒng)計(jì)學(xué)院，寧夏 銀川 750021)

為特定問題的變量尋找最佳值以最小化或最大化目標(biāo)函數(shù)的過程稱為最優(yōu)化。近年來，隨著越來越多群智能優(yōu)化算法的提出[1-5]，用于高維復(fù)雜函數(shù)的優(yōu)化算法也層出不窮[6-10]。Saremi等[11]于2017年提出蝗蟲優(yōu)化算法(grasshopper optimisation algorithm，GOA)，通過模擬自然界中蝗蟲的成群行為來解決相關(guān)優(yōu)化問題。其優(yōu)勢在于能夠有效搜索給定空間的潛在區(qū)域，即具有較好的全局尋優(yōu)能力。但隨著研究的不斷深入，GOA收斂速度慢，收斂精度不高的缺點(diǎn)逐漸暴露。針對(duì)這一問題，Ewees等[12]提出一種基于反向?qū)W習(xí)策略的GOA，通過計(jì)算當(dāng)前解的反向解，增加了種群的多樣性。Azar等[13]提出基于反向?qū)W習(xí)和價(jià)值函數(shù)方法的GOA，收斂精度有所提高，但沒有達(dá)到最優(yōu)值的情況。Jie等[14]提出基于高斯變異和Levy飛行策略的GOA，增強(qiáng)了搜索的隨機(jī)性，從而提高了全局搜索能力。Xu等[15]引入了正交學(xué)習(xí)和混沌開發(fā)2種策略，結(jié)論表明這2種機(jī)制對(duì)于緩解不成熟收斂具有重要意義。

文獻(xiàn)[12-15]對(duì)GOA的改進(jìn)主要是通過結(jié)合某種策略以平衡探索和開發(fā)能力，盡管取得了一定效果，但是GOA的尋優(yōu)性能仍具有提升的空間，值得繼續(xù)探究。Arora等[16]引入了混沌映射代替線性自適應(yīng)參數(shù)c，顯著地提升了算法的尋優(yōu)性能。李洋州等[17]提出了基于曲線自適應(yīng)的蝗蟲優(yōu)化算法，對(duì)線性自適應(yīng)參數(shù)的改進(jìn)提供了新的思路。

受文獻(xiàn)[16-17]的啟發(fā)，本文將構(gòu)建2種新型的蝗蟲優(yōu)化算法(novel grasshopper optimization algorithm，NGOA)。NGOA1的主要思想是將提出的非線性自適應(yīng)參數(shù)作為當(dāng)前最佳位置的權(quán)重，進(jìn)而提升全局搜索能力。NGOA2是在此基礎(chǔ)上，提出精英蝗蟲位置更新策略，即選用當(dāng)前最優(yōu)蝗蟲指導(dǎo)其他蝗蟲的位置更新，用以加快算法的收斂速度。最后，利用NGOA1、NGOA2求解9個(gè)常用測試函數(shù)。實(shí)驗(yàn)結(jié)果表明：本文提出的算法具有出色的尋優(yōu)性能。NGOA2對(duì)于4個(gè)單模態(tài)基準(zhǔn)函數(shù)和2個(gè)多模態(tài)基準(zhǔn)函數(shù)，在30次模擬中均能達(dá)到全局最優(yōu)值，這在其他改進(jìn)的GOA中是少見的。即NGOA2不僅能達(dá)到較高的收斂精度，且具有良好的穩(wěn)健性。

1 蝗蟲優(yōu)化算法

蝗蟲優(yōu)化算法的基本思想是通過不斷更新蝗蟲位置，最終達(dá)到全局最優(yōu)值或接近全局最優(yōu)值的近似解。對(duì)應(yīng)的蝗蟲位置向量即為函數(shù)的自變量，并假定影響蝗蟲位置Xi更新的因素包括其他蝗蟲的社會(huì)作用力Si、該蝗蟲受到的重力Gi和風(fēng)力Ai。用來模擬蝗蟲成群行為的數(shù)學(xué)模型如下：

Xi=Si+Gi+Ai

(1)

其中Si，Gi，Ai的表達(dá)式分別為：

(2)

(3)

(4)

(5)

(6)

dij=|xj-xi|

(7)

其中:f表示吸引力的強(qiáng)度；l表示吸引力的長度。GOA算法中取f=0.5和l=1.5。

將Si，Gi，Ai代入式(1)，則有

(8)

(9)

(10)

2 兩類新型蝗蟲優(yōu)化算法

2.1 非線性自適應(yīng)參數(shù)及NGOA1

GOA在位置更新公式中采用線性遞減參數(shù)，不利于算法有效地進(jìn)行全局搜索和局部搜索，從而使得算法的收斂精度不高。為改善GOA的尋優(yōu)性能，文獻(xiàn)[17]提出了圓弧自適應(yīng)參數(shù)，表達(dá)式如下：

(11)

圓弧自適應(yīng)參數(shù)在迭代前期遞減速度較慢，使得算法在離最優(yōu)值較遠(yuǎn)處停留時(shí)間過長，進(jìn)而影響算法整體的收斂速度；在迭代后期遞減速度較快，不利于算法充分地進(jìn)行局部搜索，因此可能會(huì)導(dǎo)致算法收斂精度不高。針對(duì)以上問題，本文構(gòu)造出非線性自適應(yīng)參數(shù)，旨在通過改進(jìn)線性自適應(yīng)遞減參數(shù)，提升蝗蟲優(yōu)化算法的尋優(yōu)性能，表達(dá)式如下：

(12)

線性自適應(yīng)參數(shù)、圓弧自適應(yīng)參數(shù)及非線性自適應(yīng)參數(shù)隨迭代次數(shù)變化的趨勢如圖1。

圖1 3種自適應(yīng)參數(shù)曲線

由圖1可以看出：與線性自適應(yīng)參數(shù)相比，非線性自適應(yīng)參數(shù)在每次迭代中的值均低于線性自適應(yīng)參數(shù)值，加快了整個(gè)種群趨于最優(yōu)值的速度。與圓弧自適應(yīng)參數(shù)相比，非線性自適應(yīng)參數(shù)在迭代前期遞減更快，使得算法不容易陷入局部最優(yōu)，在迭代后期遞減較慢，使得算法能夠細(xì)致地進(jìn)行局部搜索。因此，非線性自適應(yīng)參數(shù)可以更好地平衡算法的探索與開發(fā)能力，使算法更有可能獲得接近全局最優(yōu)值的近似解。

利用非線性自適應(yīng)參數(shù)替換GOA的線性自適應(yīng)參數(shù)，并將非線性自適應(yīng)參數(shù)作為當(dāng)前最佳位置的權(quán)重，構(gòu)建第一類新型蝗蟲優(yōu)化算法(NGOA1)，位置更新公式如下：

(13)

2.2 精英蝗蟲位置更新策略及NGOA2

GOA算法通過社會(huì)作用力函數(shù)表明，蝗蟲的位置更新與其他所有蝗蟲的位置均相關(guān)。但在實(shí)際應(yīng)用，位置不好的蝗蟲可能使得當(dāng)前解更新后變差，而且對(duì)于高維復(fù)雜函數(shù)來說，計(jì)算量過大，會(huì)導(dǎo)致算法尋優(yōu)速度極慢。鑒于此，本文提出精英蝗蟲位置更新策略，即僅由當(dāng)前最優(yōu)蝗蟲指導(dǎo)其他蝗蟲的位置更新，使所有蝗蟲均向最佳位置不斷靠攏，進(jìn)而加快了算法的收斂速度，也有利于提高算法的收斂精度。

將位置更新公式中其他蝗蟲位置替換為當(dāng)前最優(yōu)蝗蟲位置，提出基于非線性自適應(yīng)參數(shù)和精英蝗蟲位置更新策略的第二類新型蝗蟲優(yōu)化算法(NGOA2)，位置更新公式如下：

(14)

2.3 NGOA的實(shí)施步驟及流程圖

NGOA1和NGOA2的差異表現(xiàn)在位置更新公式的不同，因此同時(shí)給出兩類算法的實(shí)施步驟，相應(yīng)的流程如圖2所示。

圖2 NGOA的實(shí)施流程

1)設(shè)定種群規(guī)模N、最大迭代次數(shù)L、非線性自適應(yīng)參數(shù)c2的上界與下界；

3)開始迭代：計(jì)算當(dāng)代非線性自適應(yīng)參數(shù)c2，NGOA1根據(jù)式(13)進(jìn)行位置的更新，NGOA2根據(jù)式(14)進(jìn)行位置的更新，得到當(dāng)代的蝗蟲位置；

6)若達(dá)到最大迭代次數(shù)或全局最優(yōu)解，結(jié)束循環(huán)并返回最優(yōu)函數(shù)值；否則，轉(zhuǎn)入步驟3)。

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

為驗(yàn)證NGOA求解高維復(fù)雜函數(shù)的有效性，將CAGOA、NGOA1與GOA比較，探究圓弧自適應(yīng)參數(shù)、非線性自適應(yīng)參數(shù)的引入是否能改善GOA的尋優(yōu)性能；將NGOA1與CAGOA比較，觀察非線性自適應(yīng)參數(shù)的作用是否優(yōu)于圓弧自適應(yīng)參數(shù)；將NGOA2與NGOA1比較，分析精英蝗蟲位置更新策略能否提升算法的收斂精度。需要說明的是CAGOA的位置更新公式如下：

(15)

本文在Matlab R2018b的環(huán)境下進(jìn)行上述實(shí)驗(yàn)，并對(duì)比4種算法求解9個(gè)常用的標(biāo)準(zhǔn)測試函數(shù)[1-5，11]的結(jié)果。各函數(shù)的基本信息如表1所示，F(xiàn)1到F6為單模態(tài)測試函數(shù)，F(xiàn)7到F9為多模態(tài)測試函數(shù)。設(shè)置種群規(guī)模為30，最大迭代次數(shù)為500。

表1 測試函數(shù)的基本信息

為消除初始化種群帶來的影響，分別運(yùn)用GOA、CAGOA、NGOA1、NGOA2算法對(duì)9個(gè)測試函數(shù)求解30次，4種算法對(duì)應(yīng)的各函數(shù)最優(yōu)值的收斂情況如圖3所示。

圖3 GOA、CAGOA、NGOA1及NGOA2算法的收斂曲線

首先討論CAGOA的尋優(yōu)性能：對(duì)于F1～F3，F(xiàn)5，F(xiàn)7，F(xiàn)9來說，CAGOA的收斂精度和收斂速度略優(yōu)于GOA。對(duì)于F4，F(xiàn)6來說，CAGOA的收斂精度和收斂速度遜色于GOA。對(duì)于F8來說，CAGOA在迭代中期略優(yōu)于GOA，但是迭代后期陷入局部最優(yōu)值，最后得到高于GOA的近似值。整體來看，CAGOA中的圓弧自適應(yīng)參數(shù)沒有使得GOA的尋優(yōu)性能顯著提高。

其次分析NGOA1的尋優(yōu)性能：對(duì)于所有的9個(gè)函數(shù)來說，無論是單模態(tài)基準(zhǔn)函數(shù)，還是多模態(tài)基準(zhǔn)函數(shù)，NGOA1的收斂速度和收斂精度均遠(yuǎn)遠(yuǎn)高于CAGOA和GOA，具有較理想的尋優(yōu)性能，達(dá)到了改進(jìn)線性自適應(yīng)參數(shù)的目的。

最后探究NGOA2的尋優(yōu)性能：NGOA2求解函數(shù)F1～F9均能在迭代50次前達(dá)到較為滿意的收斂精度，表明其具有較快的收斂速度。與NGOA1相比，NGOA2的收斂速度更快，收斂精度更高，表明減少非當(dāng)前最佳蝗蟲位置對(duì)于各個(gè)蝗蟲位置更新的指導(dǎo)不僅不會(huì)造成算法收斂精度的降低，而且可以指導(dǎo)整個(gè)種群以更快的速度達(dá)到全局最優(yōu)值或全局最優(yōu)值的理想的近似解。

計(jì)算4種算法30次求解函數(shù)的最小值(最優(yōu)值)、最大值(最差值)、平均值以及標(biāo)準(zhǔn)差，利用SPSS 26.0對(duì)求解結(jié)果進(jìn)行Kruskal Wallis檢驗(yàn)，多重比較選擇Bonferroni方法，如表2、3所示。

表2 單模態(tài)基準(zhǔn)函數(shù)的尋優(yōu)結(jié)果

續(xù)表(表2)

表3 多模態(tài)基準(zhǔn)函數(shù)的尋優(yōu)結(jié)果

由表2、3可以看出：CAGOA和GOA求解不同的高維復(fù)雜函數(shù)得到的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差有優(yōu)有劣，2種算法的尋優(yōu)性能不分上下，進(jìn)一步證明了圓弧自適應(yīng)參數(shù)具有改善的空間。

NGOA1求解9個(gè)測試函數(shù)的結(jié)果均顯著優(yōu)于CAGOA和GOA，且具有極小的標(biāo)準(zhǔn)差，證明其具有較好的穩(wěn)健性，即尋優(yōu)性能好不是偶然情況。NGOA1對(duì)于單模態(tài)基準(zhǔn)函數(shù)的求解沒有達(dá)到全局最優(yōu)值的情況，但于多模態(tài)基準(zhǔn)函數(shù)F7和F8，卻可以達(dá)到全局最優(yōu)值。從最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差可以看出：在30次模擬中，每次均能達(dá)到全局最優(yōu)值，表明其具有較好的收斂精度，且能在某些高維復(fù)雜函數(shù)尋優(yōu)中跳出局部極值。NGOA2對(duì)于F1～F4、F7和F8均能達(dá)到全局最優(yōu)值，彰顯了求解高維復(fù)雜函數(shù)的優(yōu)越性。

4 結(jié)論

1)為提升蝗蟲優(yōu)化算法的收斂精度和收斂速度，通過構(gòu)造兩類新型蝗蟲優(yōu)化算法NGOA1和NGOA2。

2)證明了非線性自適應(yīng)參數(shù)對(duì)于蝗蟲優(yōu)化算法的適用性，及NGOA1對(duì)于求解高維復(fù)雜函數(shù)的有效性。

3)驗(yàn)證了減少非當(dāng)前最佳位置指導(dǎo)種群中其他蝗蟲位置更新是可行的。僅由當(dāng)前最佳蝗蟲位置決定其他蝗蟲位置更新，有利于提高算法的尋優(yōu)性能。

4)提出的基于非線性權(quán)重和最佳位置更新策略的蝗蟲優(yōu)化算法在多個(gè)單模態(tài)基準(zhǔn)函數(shù)和多模態(tài)基準(zhǔn)函數(shù)的30次求解中均能達(dá)到全局最優(yōu)值，具有良好的穩(wěn)健性，表明NGOA2具有較好的全局搜索能力，求解高維復(fù)雜函數(shù)能達(dá)到理想的收斂精度。