王 倩，李風軍

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

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

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

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

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

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

Xi=Si+Gi+Ai

(1)

其中Si，Gi，Ai的表達式分別為：

(2)

(3)

(4)

(5)

(6)

dij=|xj-xi|

(7)

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

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

(8)

(9)

(10)

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

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

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

(11)

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

(12)

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

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

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

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

(13)

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

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

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

(14)

2.3 NGOA的實施步驟及流程圖

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

圖2 NGOA的實施流程

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

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

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

3 實驗結果與分析

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

(15)

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

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

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

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

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

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

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

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

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

續(xù)表(表2)

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

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

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

4 結論

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

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

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

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