改進的蝗蟲優化算法及其應用

喬亞茹，吳懷宇，陳志環+，陳 晨

(1.武漢科技大學 冶金自動化與檢測技術教育部工程研究中心，湖北 武漢 430081； 2.武漢科技大學 機器人與智能系統研究院，湖北 武漢 430081； 3.水電水利規劃設計總院 規劃處，北京 100120)

0 引 言

在特定問題的所有解中找到一個最優解的過程為最優化。隨著群智能優化算法的興起[1，2]，用于優化問題的算法也層出不窮[3，4]。

Shahrzad等[5]提出的蝗蟲優化算法(grasshopper optimization algorithm，GOA)是一種新型群智能優化算法，它通過模擬蝗蟲群在自然界的種群行為來解決優化問題。

其優勢在于能夠較好地進行局部開發、參數少。但是，GOA也存在全局探索能力弱，易陷入局部最優等缺點[6]。為解決這些問題，Luo等[7]提出Levy飛行策略的GOA，提高了算法的搜索能力。Zhao等[8]提出隨機跳躍策略的GOA，隨機跳躍策略可以避免算法陷入局部最優。Taher等[9]提出混合策略的GOA，通過變異更新、隨機突變擴大搜索的區域來防止陷入局部最優。然而，以上所引文獻的尋優精度還有待提高，算法性能還存在著較大的提升空間。

另一方面，同步參數觀測器(SPO)因其控制器簡單，易于實現等優點被廣泛應用于混沌系統參數辨識中。但是，SPO模型中參數通常根據經驗所得，選取不當會大大降低模型的辨識精度。隨著群智能優化算法的興起，越來越多算法被應用在參數優化中。因此，設計一種通用性強的算法來優化SPO模型參數十分必要。

基于以上討論，本文針對GOA算法的不足，提出了SA-NGOA算法，并采用一類具有不同復雜特性的測試函數對該算法的優化能力進行評價。為了進一步驗證算法的有效性，還將SA-NGOA算法應用到擴展同步參數觀測器的參數優化中，選擇最合適的參數，提高辨識的精度。

1 蝗蟲優化算法和擴展SPO

1.1 蝗蟲優化算法

GOA作為一種啟發式優化算法，它主要是模擬蝗蟲的社會性活動。在GOA中，將優化問題的候選解抽象成蝗蟲個體的位置。蝗蟲在進行社會性活動的過程中，如繁殖、覓食、遷徙、聚集等，個體的位置主要受到蝗蟲間的社會作用力Si、 該蝗蟲受到的重力Gi和風力Ai這3個因素的影響。用數學模型表述為

Xi=Si+Gi+Ai

(1)

式中：Si，Gi，Ai的表達式如下

(2)

s=fe-r/l-e-r

(3)

式中：f和l分別表示吸引強度參數和尺度參數，本文l取值為1.5，f取值為0.5。

將Si，Gi，Ai代入式(1)中可得

(4)

然而，式(4)蝗蟲可以以很快的速度到達舒適區，除此之外，它不會收斂到一個特定的值，為了解決這個問題，通常利用參數來區分不同階段的尋優，此時位置更新公式如下

(5)

(6)

式中：cmax、cmin分別為c的最大值和最小值；t為算法的當前迭代次數；Tmax為算法的最大迭代次數。

1.2 擴展SPO

在文獻[10]中，作者提出了一種同步參數觀測器(SPO)來辨識動力系統中的未知參數。相比于其它參數觀測器，SPO結構簡單并且辨識精度更高。在本文中，我們基于SPO的設計原理將其進一步擴展(ESPO)，具體設計原理如下：

考慮以下一組非線性微分方程描述的混沌系統

(7)

(8)

設系統(8)的第i個方程為

(9)

構造擴展同步參數觀測器如下

(10)

證明：從式(11)和式(12)可以得到如下誤差系統

(11)

(12)

對式(12)求導，并將式(11)帶入式(12)可得

(13)

結合式(12)和式(13)由Lyapunov定理得到，該觀測器是穩定的，可以識別出系統(9)所有的未知參數。

2 SA-NGOA算法和優化策略

GOA作為近年來剛發展起來的一種群體智能優化算法，該算法具有協調局部和全局的能力、模型參數少和局部開發能力較好等優點。同時，與GA、PSO和DA[11]等傳統群智能優化算法相比，GOA算法具有一定的競爭性。然而，GOA也有易陷入局部最優，收斂精度不高等缺陷。本文針對GOA的這些缺陷對其進行了一系列的改進。

2.1 SA-NGOA

傳統蝗蟲優化算法中參數c采用線性更新，這不利于算法在前期進行全局探索和后期的開發，除此之外，在蝗蟲位置更新過程中，一些位置不好的蝗蟲也會參與并影響其它蝗蟲位置的更新，這降低了算法的尋優效率以及尋優精度。在本節中針對傳統GOA的不足，提出了一種非線性自適應和模擬退火的蝗蟲優化算法(SA-NGOA)，改進如下：

(1)改進策略一：非線性自適應蝗蟲優化算法

式(5)中，括號外的參數c控制整個算法尋優過程策略的轉變，即由全局搜索逐漸進入局部勘探，這一點與粒子群算法中設置的慣性權重ω思想不謀而合，隨著迭代次數的增加，收縮蝗蟲搜尋與目標值相鄰的區域，使其能夠逐漸收斂于目標值；由于括號內的c參數作用整個算法過程中，調節蝗蟲間的吸引域、舒適域等關鍵過程。對于參數c策略的使用好壞決定著整個算法的尋優質量，但是原算法中參數c更新策略為線性，因此在尋優過程中存在全程搜索時間太短與局部收斂過程過長的不足，導致算法的解陷入局部最優，無法收斂到目標值[12-14]。針對上述問題，為了更好地平衡算法的前期探索和后期的開發，本文提出利用非線性自適應代替線性自適應更新參數c的策略，合理分配勘探與開采的占比，表達式如下

(14)

從式(14)可以明顯看出，參數c的更新公式仍然是遞減函數，相較于改進前的GOA線性自適應的策略，本文提出非線性自適應參數使得算法迭代中，參數c的數值更新曲線明顯優異于初始算法，不僅有利于算法初期在全局探索過程的延長，還縮短了迭代后期的收斂過程所消耗的代價。

(2)改進策略二：模擬退火蝗蟲優化算法

在GOA中，蝗蟲的位置不僅與當前蝗蟲位置有關，還同時受到其它所有蝗蟲位置的干擾，而無法跟隨目標蝗蟲的位置。雖然GOA的局部開采能力較為優異，與之而來產生的代價使得其它蝗蟲可能去跟隨更新后的當前蝗蟲位置，即使更新后的蝗蟲位置沒有達到算法要求，從而使得GOA的收斂速度放緩，因此，限制每只蝗蟲的活動范圍就顯得尤為重要，影響著整個蝗蟲算法的精度和收斂速度。因此，本文結合模擬退火算法，先對迭代更新的蝗蟲位置進行取舍，剔除更差的更新個體位置，再進行下一步驟。

模擬退火算法是由Metropolis等[15]提出的一種全局優化算法，它是基于Monte-Carlo迭代求解策略的一種隨機算法，類比物理學中固體升溫使得粒子變的有序，從而達到更快冷卻的現象，將所得到的局部最優解適當“加溫”，從而達到跳出局部最優的狀態，該算法采用Metropolis準則接收產生的最優問題解。Metropolis準則表示如下

(15)

式中：Xn為后一時刻；X0為前一時刻；E(Xn)、E(X0) 分別為Xn時刻和X0時刻的內能；KB為玻爾茲曼常數。

由于蝗蟲算法的全局搜索能力較弱，極易陷入局部最優，而模擬退火算法的Metropolis準則可以幫助蝗蟲以一定概率跟隨其它蝗蟲位置，從而增大全局搜索的范圍，避免陷入局部最優，強化整個算法的全局勘探能力，從而提升算法性能。在模擬退火中蝗蟲的隨機位置公式如下

(16)

式中：xi是蝗蟲的當前位置解；xi+1是蝗蟲的下一個位置解；r是0和1之間的隨機數。式(16)中，在算法后期，蝗蟲活動的空間會隨著迭代次數的增加而受到限制，這樣能夠增強算法的開發能力。SA-NGOA算法的運行框架如算法1所示。

算法1：SA-NGOA算法迭代尋優的執行偽碼

(1)隨機初始化種群位置xi

(2)計算每個個體的適應度值

(3)保存適應度值最好的蝗蟲位置，即Pbest

(4)當終止條件不滿足時(例如t

4.1 對每一個蝗蟲

根據式(14)更新參數c

由式(5)更新蝗蟲的位置，并計算適應度

對蝗蟲進行模擬退火操作

由式(16)選擇新的解，并計算適應度

根據Metropolis準則更新新解

結束當前循環

4.2 計算所有蝗蟲的適應度值

4.3 如果4.2中得到更好的適應度值，則更新Pbest

(5)如果滿足終止條件則結束循環，否則跳到4.1

(6)輸出最佳位置和目標函數值

2.2 優化策略

從上文可以看出，ESPO具有較多的控制參數，初始增益的設定會影響到模型的辨識精度。群智能算法在解決目標優化問題中表現突出，為使ESPO實現最佳辨識效果，本文利用SA-NGOA算法對ESPO模型中增益組合進行優化，選擇最優增益組合，提高辨識的精度，整個優化流程如圖1所示。

圖1 SA-NGOA算法優化ESPO參數的流程

SA-NGOA算法和非線性系統之間的橋梁是蝗蟲個體(即SPO增益集)和適應度值。算法中每個個體位置代表一組ESPO模型中的增益組合，SA-NGOA算法優化ESPO模型參數基本步驟如下：

(1)初始化種群位置，賦值給ESPO增益組合；

(2)定義非線性系統的仿真時長、采樣步長、狀態變量的初始值；

(3)用龍格-庫塔法求解微分方程，在有限時間內輸出對應的狀態變量；

(4)通過輸出的未知參數的真實值和觀測值，可以求出參數估計誤差；

(5)計算適應度值，適應度函數用于評估每個蝗蟲性能的好壞，因此適應度函數的選取是ESPO參數優化中最關鍵的問題。本文選取的適應度函數如下

(17)

式中：m是待辨識的未知參數個數，n是模擬時間，ω是權重系數，在本文中取ω=4×10-4。

(6)將適應度向量集傳輸到SA-NGOA中作為該蝗蟲的適應值，促使算法搜索過程向前推進；

(7)更新參數c，更新蝗蟲位置；

(8)進行模擬退火操作，在蝗蟲鄰域內選擇新解，并根據Metropolis準則更新新解；

(9)迭代次數隨著每一代蝗蟲群的更新而不斷增加，當它等于預先設定的最大迭代次數時，整個迭代過程停止，得到最優增益組合。

3 實驗與結果分析

3.1 基準函數測試

為了對本文提出的非線性自適應和模擬退火算法(SA-NGOA)的性能進行測試分析，選取6個具有一定代表性的基準函數，其中，F1～F3為單模態的基準測試函數，F4～F6為多模態的基準測試函數，選擇的基準函數具有一定的代表性。其函數表達式和定義域見表1，它們的尋優目標都是求解函數的最小值，所選函數的理想最優值均為0。

在這部分中，本文利用表1中的6個基準函數分別對DA[11]、GA[16]、GOA、SA-NGOA的求解性能進行了仿真測試。為了保證測試結果的準確性，相同參數設置為：種群規模N=30，最大迭代次數Tmax=500。而具體參數因不同的算法而改變：對于GOA，cmax=1，cmin=10-4；對于SA，初始溫度T0=100，結束溫度T=1，KB=10；DA、GA算法的參數設置與文獻[11]和文獻[16]保持一致；其它改進GOA與基本GOA設置一樣。為減少算法的隨機性誤差，對4種算法在6個函數下獨立運20次，記錄并比較各個算法適應度的最小值、最大值、平均值和標準差，測試結果見表2。

從表2可知，除函數F5之外，GOA算法在整體上都要好于DA算法和GA算法，但SA-NGOA算法的尋優結果最好。對于函數F1和F3，從平均值與標準值的數量級差別可知，DA尋優能力較差，GA和GOA次之，SA-NGOA最好。對于函數F2，DA、GA和GOA尋優結果相近，但GOA標準差最小，可知GOA尋優結果較穩定，而SA-NGOA不論是尋優精度還是穩定性上都更有優勢。對于多模態的基準函數F4和F6存在多個極值點，DA早熟陷入局部最優，SA-NGOA相比于GA和GOA具有更高的收斂精度。主要由兩個因素導致這樣的結果。在算法初期，依據SA的Metropolis準則可以幫助蝗蟲以一定概率跟隨其它蝗蟲位置，從而增大全局搜索的范圍，避免陷入局部最優，強化整個算法的全局勘探能力；在算法后期，模擬退火算法對每個蝗蟲的活動領域進行限制，可有效改善收斂時間長、最優解精度低等不足。

表1 基準測試函數

表2 不同算法尋優結果對比

為了進一步驗證不同改進策略的有效性，將SA-NGOA與只含有改進策略一的非線性自適應蝗蟲優化算法(NGOA)、只含有改進策略二的結合模擬退火蝗蟲優化算法(SA-GOA)以及GOA進行對比。為了保證算法之間比較的一致性，參數的設置與上文一致。不同改進策略算法的平均收斂曲線如圖2所示。從圖2可以看出，在兩種改進策略的算法中，結合模擬退火的SA-GOA的改進效果更好。因為策略二相比于策略一，對后期蝗蟲的隨機域進行收縮限制，使其僅在最優解小范圍內迭代，不僅提升了算法的收斂精度，還節省了大量的開采時間。

圖2 不同策略算法的平均收斂曲線

NGOA的改進效果并不突出，但其尋優精度也高于GOA的尋優精度。該策略采用非線性更新參數c的方法，使全局探索和局部開發的能力達到平衡。結合兩種改進的策略，將兩種改進策略各自的優點充分融合，使得SA-NGOA相對于兩種改進策略算法在收斂速度和尋優精度上都具有顯著的優越性。

3.2 基于SA-NGOA的ESPO參數優化

為驗證SA-NGOA算法的有效性，本文將該算法用于ESPO參數優化。考慮如下Chen系統[17]

(18)

式中：a、b、c表示系統參數。當a=35，b=3，c=28時，系統(18)呈現混沌特性，即出現混沌吸引子，如圖3所示。

圖3 Chen系統的吸引子

若參數a、b、c全部未知的情況下，根據式(10)設計觀測器如下

(19)

為了分析算法性能，將SA-NGOA算法與SA、GOA算法進行比較，在數值仿真中，整個迭代過程如圖1所示。為了公平起見，種群數量為30，最大迭代次數為50，每個算法獨立運行20次，其它參數不做改變。

對于Chen系統，在仿真中，采用4階龍格-庫塔法求解微分方程(18)，步長為0.01 s，仿真時間為5 s。系統的相關參數見表3。系統中增益參數k=[k1，k2，k3，k4，k5，k6] 取值范圍為[0，20]。

圖4是ESPO參數優化過程中適應度函數平均收斂曲線。從圖4中可以看出，SA-NGOA相比SA、GOA收斂速度更快，尋優精度更高。圖5～圖7為Chen系統文獻[10]中經典SPO、SA-NGOA算法優化后ESPO分別對未知參數a、b、c的辨識曲線。其中，在SA-NGOA算法優化ESPO參數中，算法找到的最佳值作為ESPO的增益值。從圖中可以看出，文獻[10]中經典SPO和SA-NGOA算法優化后ESPO都可以準確辨識出未知參數。但是，SA-NGOA算法優化下的ESPO擁有更高的辨識效率和滿意的辨識精度。

表3 Chen系統的初始狀態

第3部分結果分析中，為分析SA-NGOA算法的有效性，選用不同算法對6個基準函數進行對照實驗，從尋優速度、收斂精度上來看，SA-NGOA均優異于改進前的算法，還從側面驗證了改進策略的合理性和有效性。同時，將SA-NGOA算法用于ESPO參數優化，結果顯示優化后的ESPO有更高的辨識精度和辨識速度。總之，以上實驗都驗證了改進算法的有效性。

圖4 3種算法的平均收斂曲線

圖5 參數a的辨識曲線

圖6 參數b的辨識曲線

圖7 參數c的辨識曲線

4 結束語

為改善GOA算法的性能，本文提出了一種非線性自適應模擬退火的蝗蟲優化算法(SA-NGOA)，該算法利用非線性自適應更新參數c，更好地平衡了全局探索與局部開發，并在此基礎上混合了模擬退火算法，避免算法陷入局部最優，結果表明，SA-NGOA算法有效提高了蝗蟲優化算法的收斂速度與全局尋優性能。為了更好地發揮SA-NGOA算法求解復雜優化問題的優勢，將SA-NGOA算法用于ESPO參數優化，實驗結果表明，SA-NGOA算法有效實現了ESPO增益組合的優化，與經典SPO相比具有更快的辨識速度和更高的辨識精度。