喬亞茹,吳懷宇,陳志環(huán)+,陳 晨
(1.武漢科技大學(xué) 冶金自動(dòng)化與檢測(cè)技術(shù)教育部工程研究中心,湖北 武漢 430081; 2.武漢科技大學(xué) 機(jī)器人與智能系統(tǒng)研究院,湖北 武漢 430081; 3.水電水利規(guī)劃設(shè)計(jì)總院 規(guī)劃處,北京 100120)
在特定問(wèn)題的所有解中找到一個(gè)最優(yōu)解的過(guò)程為最優(yōu)化。隨著群智能優(yōu)化算法的興起[1,2],用于優(yōu)化問(wèn)題的算法也層出不窮[3,4]。
Shahrzad等[5]提出的蝗蟲優(yōu)化算法(grasshopper optimization algorithm,GOA)是一種新型群智能優(yōu)化算法,它通過(guò)模擬蝗蟲群在自然界的種群行為來(lái)解決優(yōu)化問(wèn)題。
其優(yōu)勢(shì)在于能夠較好地進(jìn)行局部開(kāi)發(fā)、參數(shù)少。但是,GOA也存在全局探索能力弱,易陷入局部最優(yōu)等缺點(diǎn)[6]。為解決這些問(wèn)題,Luo等[7]提出Levy飛行策略的GOA,提高了算法的搜索能力。Zhao等[8]提出隨機(jī)跳躍策略的GOA,隨機(jī)跳躍策略可以避免算法陷入局部最優(yōu)。Taher等[9]提出混合策略的GOA,通過(guò)變異更新、隨機(jī)突變擴(kuò)大搜索的區(qū)域來(lái)防止陷入局部最優(yōu)。然而,以上所引文獻(xiàn)的尋優(yōu)精度還有待提高,算法性能還存在著較大的提升空間。
另一方面,同步參數(shù)觀測(cè)器(SPO)因其控制器簡(jiǎn)單,易于實(shí)現(xiàn)等優(yōu)點(diǎn)被廣泛應(yīng)用于混沌系統(tǒng)參數(shù)辨識(shí)中。但是,SPO模型中參數(shù)通常根據(jù)經(jīng)驗(yàn)所得,選取不當(dāng)會(huì)大大降低模型的辨識(shí)精度。隨著群智能優(yōu)化算法的興起,越來(lái)越多算法被應(yīng)用在參數(shù)優(yōu)化中。因此,設(shè)計(jì)一種通用性強(qiáng)的算法來(lái)優(yōu)化SPO模型參數(shù)十分必要。
基于以上討論,本文針對(duì)GOA算法的不足,提出了SA-NGOA算法,并采用一類具有不同復(fù)雜特性的測(cè)試函數(shù)對(duì)該算法的優(yōu)化能力進(jìn)行評(píng)價(jià)。為了進(jìn)一步驗(yàn)證算法的有效性,還將SA-NGOA算法應(yīng)用到擴(kuò)展同步參數(shù)觀測(cè)器的參數(shù)優(yōu)化中,選擇最合適的參數(shù),提高辨識(shí)的精度。
GOA作為一種啟發(fā)式優(yōu)化算法,它主要是模擬蝗蟲的社會(huì)性活動(dòng)。在GOA中,將優(yōu)化問(wèn)題的候選解抽象成蝗蟲個(gè)體的位置?;认x在進(jìn)行社會(huì)性活動(dòng)的過(guò)程中,如繁殖、覓食、遷徙、聚集等,個(gè)體的位置主要受到蝗蟲間的社會(huì)作用力Si、 該蝗蟲受到的重力Gi和風(fēng)力Ai這3個(gè)因素的影響。用數(shù)學(xué)模型表述為
Xi=Si+Gi+Ai
(1)
式中:Si,Gi,Ai的表達(dá)式如下
(2)
s=fe-r/l-e-r
(3)
式中:f和l分別表示吸引強(qiáng)度參數(shù)和尺度參數(shù),本文l取值為1.5,f取值為0.5。
將Si,Gi,Ai代入式(1)中可得
(4)
然而,式(4)蝗蟲可以以很快的速度到達(dá)舒適區(qū),除此之外,它不會(huì)收斂到一個(gè)特定的值,為了解決這個(gè)問(wèn)題,通常利用參數(shù)來(lái)區(qū)分不同階段的尋優(yōu),此時(shí)位置更新公式如下
(5)
(6)
式中:cmax、cmin分別為c的最大值和最小值;t為算法的當(dāng)前迭代次數(shù);Tmax為算法的最大迭代次數(shù)。
在文獻(xiàn)[10]中,作者提出了一種同步參數(shù)觀測(cè)器(SPO)來(lái)辨識(shí)動(dòng)力系統(tǒng)中的未知參數(shù)。相比于其它參數(shù)觀測(cè)器,SPO結(jié)構(gòu)簡(jiǎn)單并且辨識(shí)精度更高。在本文中,我們基于SPO的設(shè)計(jì)原理將其進(jìn)一步擴(kuò)展(ESPO),具體設(shè)計(jì)原理如下:
考慮以下一組非線性微分方程描述的混沌系統(tǒng)
(7)
(8)
設(shè)系統(tǒng)(8)的第i個(gè)方程為
(9)
構(gòu)造擴(kuò)展同步參數(shù)觀測(cè)器如下
(10)
證明:從式(11)和式(12)可以得到如下誤差系統(tǒng)
(11)
(12)
對(duì)式(12)求導(dǎo),并將式(11)帶入式(12)可得
(13)
結(jié)合式(12)和式(13)由Lyapunov定理得到,該觀測(cè)器是穩(wěn)定的,可以識(shí)別出系統(tǒng)(9)所有的未知參數(shù)。
GOA作為近年來(lái)剛發(fā)展起來(lái)的一種群體智能優(yōu)化算法,該算法具有協(xié)調(diào)局部和全局的能力、模型參數(shù)少和局部開(kāi)發(fā)能力較好等優(yōu)點(diǎn)。同時(shí),與GA、PSO和DA[11]等傳統(tǒng)群智能優(yōu)化算法相比,GOA算法具有一定的競(jìng)爭(zhēng)性。然而,GOA也有易陷入局部最優(yōu),收斂精度不高等缺陷。本文針對(duì)GOA的這些缺陷對(duì)其進(jìn)行了一系列的改進(jìn)。
傳統(tǒng)蝗蟲優(yōu)化算法中參數(shù)c采用線性更新,這不利于算法在前期進(jìn)行全局探索和后期的開(kāi)發(fā),除此之外,在蝗蟲位置更新過(guò)程中,一些位置不好的蝗蟲也會(huì)參與并影響其它蝗蟲位置的更新,這降低了算法的尋優(yōu)效率以及尋優(yōu)精度。在本節(jié)中針對(duì)傳統(tǒng)GOA的不足,提出了一種非線性自適應(yīng)和模擬退火的蝗蟲優(yōu)化算法(SA-NGOA),改進(jìn)如下:
(1)改進(jìn)策略一:非線性自適應(yīng)蝗蟲優(yōu)化算法
式(5)中,括號(hào)外的參數(shù)c控制整個(gè)算法尋優(yōu)過(guò)程策略的轉(zhuǎn)變,即由全局搜索逐漸進(jìn)入局部勘探,這一點(diǎn)與粒子群算法中設(shè)置的慣性權(quán)重ω思想不謀而合,隨著迭代次數(shù)的增加,收縮蝗蟲搜尋與目標(biāo)值相鄰的區(qū)域,使其能夠逐漸收斂于目標(biāo)值;由于括號(hào)內(nèi)的c參數(shù)作用整個(gè)算法過(guò)程中,調(diào)節(jié)蝗蟲間的吸引域、舒適域等關(guān)鍵過(guò)程。對(duì)于參數(shù)c策略的使用好壞決定著整個(gè)算法的尋優(yōu)質(zhì)量,但是原算法中參數(shù)c更新策略為線性,因此在尋優(yōu)過(guò)程中存在全程搜索時(shí)間太短與局部收斂過(guò)程過(guò)長(zhǎng)的不足,導(dǎo)致算法的解陷入局部最優(yōu),無(wú)法收斂到目標(biāo)值[12-14]。針對(duì)上述問(wèn)題,為了更好地平衡算法的前期探索和后期的開(kāi)發(fā),本文提出利用非線性自適應(yīng)代替線性自適應(yīng)更新參數(shù)c的策略,合理分配勘探與開(kāi)采的占比,表達(dá)式如下
(14)
從式(14)可以明顯看出,參數(shù)c的更新公式仍然是遞減函數(shù),相較于改進(jìn)前的GOA線性自適應(yīng)的策略,本文提出非線性自適應(yīng)參數(shù)使得算法迭代中,參數(shù)c的數(shù)值更新曲線明顯優(yōu)異于初始算法,不僅有利于算法初期在全局探索過(guò)程的延長(zhǎng),還縮短了迭代后期的收斂過(guò)程所消耗的代價(jià)。
(2)改進(jìn)策略二:模擬退火蝗蟲優(yōu)化算法
在GOA中,蝗蟲的位置不僅與當(dāng)前蝗蟲位置有關(guān),還同時(shí)受到其它所有蝗蟲位置的干擾,而無(wú)法跟隨目標(biāo)蝗蟲的位置。雖然GOA的局部開(kāi)采能力較為優(yōu)異,與之而來(lái)產(chǎn)生的代價(jià)使得其它蝗蟲可能去跟隨更新后的當(dāng)前蝗蟲位置,即使更新后的蝗蟲位置沒(méi)有達(dá)到算法要求,從而使得GOA的收斂速度放緩,因此,限制每只蝗蟲的活動(dòng)范圍就顯得尤為重要,影響著整個(gè)蝗蟲算法的精度和收斂速度。因此,本文結(jié)合模擬退火算法,先對(duì)迭代更新的蝗蟲位置進(jìn)行取舍,剔除更差的更新個(gè)體位置,再進(jìn)行下一步驟。
模擬退火算法是由Metropolis等[15]提出的一種全局優(yōu)化算法,它是基于Monte-Carlo迭代求解策略的一種隨機(jī)算法,類比物理學(xué)中固體升溫使得粒子變的有序,從而達(dá)到更快冷卻的現(xiàn)象,將所得到的局部最優(yōu)解適當(dāng)“加溫”,從而達(dá)到跳出局部最優(yōu)的狀態(tài),該算法采用Metropolis準(zhǔn)則接收產(chǎn)生的最優(yōu)問(wèn)題解。Metropolis準(zhǔn)則表示如下
(15)
式中:Xn為后一時(shí)刻;X0為前一時(shí)刻;E(Xn)、E(X0) 分別為Xn時(shí)刻和X0時(shí)刻的內(nèi)能;KB為玻爾茲曼常數(shù)。
由于蝗蟲算法的全局搜索能力較弱,極易陷入局部最優(yōu),而模擬退火算法的Metropolis準(zhǔn)則可以幫助蝗蟲以一定概率跟隨其它蝗蟲位置,從而增大全局搜索的范圍,避免陷入局部最優(yōu),強(qiáng)化整個(gè)算法的全局勘探能力,從而提升算法性能。在模擬退火中蝗蟲的隨機(jī)位置公式如下
(16)
式中:xi是蝗蟲的當(dāng)前位置解;xi+1是蝗蟲的下一個(gè)位置解;r是0和1之間的隨機(jī)數(shù)。式(16)中,在算法后期,蝗蟲活動(dòng)的空間會(huì)隨著迭代次數(shù)的增加而受到限制,這樣能夠增強(qiáng)算法的開(kāi)發(fā)能力。SA-NGOA算法的運(yùn)行框架如算法1所示。
算法1:SA-NGOA算法迭代尋優(yōu)的執(zhí)行偽碼
(1)隨機(jī)初始化種群位置xi
(2)計(jì)算每個(gè)個(gè)體的適應(yīng)度值
(3)保存適應(yīng)度值最好的蝗蟲位置,即Pbest
(4)當(dāng)終止條件不滿足時(shí)(例如t 4.1 對(duì)每一個(gè)蝗蟲 根據(jù)式(14)更新參數(shù)c 由式(5)更新蝗蟲的位置,并計(jì)算適應(yīng)度 對(duì)蝗蟲進(jìn)行模擬退火操作 由式(16)選擇新的解,并計(jì)算適應(yīng)度 根據(jù)Metropolis準(zhǔn)則更新新解 結(jié)束當(dāng)前循環(huán) 4.2 計(jì)算所有蝗蟲的適應(yīng)度值 4.3 如果4.2中得到更好的適應(yīng)度值,則更新Pbest (5)如果滿足終止條件則結(jié)束循環(huán),否則跳到4.1 (6)輸出最佳位置和目標(biāo)函數(shù)值 從上文可以看出,ESPO具有較多的控制參數(shù),初始增益的設(shè)定會(huì)影響到模型的辨識(shí)精度。群智能算法在解決目標(biāo)優(yōu)化問(wèn)題中表現(xiàn)突出,為使ESPO實(shí)現(xiàn)最佳辨識(shí)效果,本文利用SA-NGOA算法對(duì)ESPO模型中增益組合進(jìn)行優(yōu)化,選擇最優(yōu)增益組合,提高辨識(shí)的精度,整個(gè)優(yōu)化流程如圖1所示。 圖1 SA-NGOA算法優(yōu)化ESPO參數(shù)的流程 SA-NGOA算法和非線性系統(tǒng)之間的橋梁是蝗蟲個(gè)體(即SPO增益集)和適應(yīng)度值。算法中每個(gè)個(gè)體位置代表一組ESPO模型中的增益組合,SA-NGOA算法優(yōu)化ESPO模型參數(shù)基本步驟如下: (1)初始化種群位置,賦值給ESPO增益組合; (2)定義非線性系統(tǒng)的仿真時(shí)長(zhǎng)、采樣步長(zhǎng)、狀態(tài)變量的初始值; (3)用龍格-庫(kù)塔法求解微分方程,在有限時(shí)間內(nèi)輸出對(duì)應(yīng)的狀態(tài)變量; (4)通過(guò)輸出的未知參數(shù)的真實(shí)值和觀測(cè)值,可以求出參數(shù)估計(jì)誤差; (5)計(jì)算適應(yīng)度值,適應(yīng)度函數(shù)用于評(píng)估每個(gè)蝗蟲性能的好壞,因此適應(yīng)度函數(shù)的選取是ESPO參數(shù)優(yōu)化中最關(guān)鍵的問(wèn)題。本文選取的適應(yīng)度函數(shù)如下 (17) 式中:m是待辨識(shí)的未知參數(shù)個(gè)數(shù),n是模擬時(shí)間,ω是權(quán)重系數(shù),在本文中取ω=4×10-4。 (6)將適應(yīng)度向量集傳輸?shù)絊A-NGOA中作為該蝗蟲的適應(yīng)值,促使算法搜索過(guò)程向前推進(jìn); (7)更新參數(shù)c,更新蝗蟲位置; (8)進(jìn)行模擬退火操作,在蝗蟲鄰域內(nèi)選擇新解,并根據(jù)Metropolis準(zhǔn)則更新新解; (9)迭代次數(shù)隨著每一代蝗蟲群的更新而不斷增加,當(dāng)它等于預(yù)先設(shè)定的最大迭代次數(shù)時(shí),整個(gè)迭代過(guò)程停止,得到最優(yōu)增益組合。 為了對(duì)本文提出的非線性自適應(yīng)和模擬退火算法(SA-NGOA)的性能進(jìn)行測(cè)試分析,選取6個(gè)具有一定代表性的基準(zhǔn)函數(shù),其中,F(xiàn)1~F3為單模態(tài)的基準(zhǔn)測(cè)試函數(shù),F(xiàn)4~F6為多模態(tài)的基準(zhǔn)測(cè)試函數(shù),選擇的基準(zhǔn)函數(shù)具有一定的代表性。其函數(shù)表達(dá)式和定義域見(jiàn)表1,它們的尋優(yōu)目標(biāo)都是求解函數(shù)的最小值,所選函數(shù)的理想最優(yōu)值均為0。 在這部分中,本文利用表1中的6個(gè)基準(zhǔn)函數(shù)分別對(duì)DA[11]、GA[16]、GOA、SA-NGOA的求解性能進(jìn)行了仿真測(cè)試。為了保證測(cè)試結(jié)果的準(zhǔn)確性,相同參數(shù)設(shè)置為:種群規(guī)模N=30,最大迭代次數(shù)Tmax=500。而具體參數(shù)因不同的算法而改變:對(duì)于GOA,cmax=1,cmin=10-4;對(duì)于SA,初始溫度T0=100,結(jié)束溫度T=1,KB=10;DA、GA算法的參數(shù)設(shè)置與文獻(xiàn)[11]和文獻(xiàn)[16]保持一致;其它改進(jìn)GOA與基本GOA設(shè)置一樣。為減少算法的隨機(jī)性誤差,對(duì)4種算法在6個(gè)函數(shù)下獨(dú)立運(yùn)20次,記錄并比較各個(gè)算法適應(yīng)度的最小值、最大值、平均值和標(biāo)準(zhǔn)差,測(cè)試結(jié)果見(jiàn)表2。 從表2可知,除函數(shù)F5之外,GOA算法在整體上都要好于DA算法和GA算法,但SA-NGOA算法的尋優(yōu)結(jié)果最好。對(duì)于函數(shù)F1和F3,從平均值與標(biāo)準(zhǔn)值的數(shù)量級(jí)差別可知,DA尋優(yōu)能力較差,GA和GOA次之,SA-NGOA最好。對(duì)于函數(shù)F2,DA、GA和GOA尋優(yōu)結(jié)果相近,但GOA標(biāo)準(zhǔn)差最小,可知GOA尋優(yōu)結(jié)果較穩(wěn)定,而SA-NGOA不論是尋優(yōu)精度還是穩(wěn)定性上都更有優(yōu)勢(shì)。對(duì)于多模態(tài)的基準(zhǔn)函數(shù)F4和F6存在多個(gè)極值點(diǎn),DA早熟陷入局部最優(yōu),SA-NGOA相比于GA和GOA具有更高的收斂精度。主要由兩個(gè)因素導(dǎo)致這樣的結(jié)果。在算法初期,依據(jù)SA的Metropolis準(zhǔn)則可以幫助蝗蟲以一定概率跟隨其它蝗蟲位置,從而增大全局搜索的范圍,避免陷入局部最優(yōu),強(qiáng)化整個(gè)算法的全局勘探能力;在算法后期,模擬退火算法對(duì)每個(gè)蝗蟲的活動(dòng)領(lǐng)域進(jìn)行限制,可有效改善收斂時(shí)間長(zhǎng)、最優(yōu)解精度低等不足。 表1 基準(zhǔn)測(cè)試函數(shù) 表2 不同算法尋優(yōu)結(jié)果對(duì)比 為了進(jìn)一步驗(yàn)證不同改進(jìn)策略的有效性,將SA-NGOA與只含有改進(jìn)策略一的非線性自適應(yīng)蝗蟲優(yōu)化算法(NGOA)、只含有改進(jìn)策略二的結(jié)合模擬退火蝗蟲優(yōu)化算法(SA-GOA)以及GOA進(jìn)行對(duì)比。為了保證算法之間比較的一致性,參數(shù)的設(shè)置與上文一致。不同改進(jìn)策略算法的平均收斂曲線如圖2所示。從圖2可以看出,在兩種改進(jìn)策略的算法中,結(jié)合模擬退火的SA-GOA的改進(jìn)效果更好。因?yàn)椴呗远啾扔诓呗砸唬瑢?duì)后期蝗蟲的隨機(jī)域進(jìn)行收縮限制,使其僅在最優(yōu)解小范圍內(nèi)迭代,不僅提升了算法的收斂精度,還節(jié)省了大量的開(kāi)采時(shí)間。 圖2 不同策略算法的平均收斂曲線 NGOA的改進(jìn)效果并不突出,但其尋優(yōu)精度也高于GOA的尋優(yōu)精度。該策略采用非線性更新參數(shù)c的方法,使全局探索和局部開(kāi)發(fā)的能力達(dá)到平衡。結(jié)合兩種改進(jìn)的策略,將兩種改進(jìn)策略各自的優(yōu)點(diǎn)充分融合,使得SA-NGOA相對(duì)于兩種改進(jìn)策略算法在收斂速度和尋優(yōu)精度上都具有顯著的優(yōu)越性。 為驗(yàn)證SA-NGOA算法的有效性,本文將該算法用于ESPO參數(shù)優(yōu)化??紤]如下Chen系統(tǒng)[17] (18) 式中:a、b、c表示系統(tǒng)參數(shù)。當(dāng)a=35,b=3,c=28時(shí),系統(tǒng)(18)呈現(xiàn)混沌特性,即出現(xiàn)混沌吸引子,如圖3所示。 圖3 Chen系統(tǒng)的吸引子 若參數(shù)a、b、c全部未知的情況下,根據(jù)式(10)設(shè)計(jì)觀測(cè)器如下 (19) 為了分析算法性能,將SA-NGOA算法與SA、GOA算法進(jìn)行比較,在數(shù)值仿真中,整個(gè)迭代過(guò)程如圖1所示。為了公平起見(jiàn),種群數(shù)量為30,最大迭代次數(shù)為50,每個(gè)算法獨(dú)立運(yùn)行20次,其它參數(shù)不做改變。 對(duì)于Chen系統(tǒng),在仿真中,采用4階龍格-庫(kù)塔法求解微分方程(18),步長(zhǎng)為0.01 s,仿真時(shí)間為5 s。系統(tǒng)的相關(guān)參數(shù)見(jiàn)表3。系統(tǒng)中增益參數(shù)k=[k1,k2,k3,k4,k5,k6] 取值范圍為[0,20]。 圖4是ESPO參數(shù)優(yōu)化過(guò)程中適應(yīng)度函數(shù)平均收斂曲線。從圖4中可以看出,SA-NGOA相比SA、GOA收斂速度更快,尋優(yōu)精度更高。圖5~圖7為Chen系統(tǒng)文獻(xiàn)[10]中經(jīng)典SPO、SA-NGOA算法優(yōu)化后ESPO分別對(duì)未知參數(shù)a、b、c的辨識(shí)曲線。其中,在SA-NGOA算法優(yōu)化ESPO參數(shù)中,算法找到的最佳值作為ESPO的增益值。從圖中可以看出,文獻(xiàn)[10]中經(jīng)典SPO和SA-NGOA算法優(yōu)化后ESPO都可以準(zhǔn)確辨識(shí)出未知參數(shù)。但是,SA-NGOA算法優(yōu)化下的ESPO擁有更高的辨識(shí)效率和滿意的辨識(shí)精度。 表3 Chen系統(tǒng)的初始狀態(tài) 第3部分結(jié)果分析中,為分析SA-NGOA算法的有效性,選用不同算法對(duì)6個(gè)基準(zhǔn)函數(shù)進(jìn)行對(duì)照實(shí)驗(yàn),從尋優(yōu)速度、收斂精度上來(lái)看,SA-NGOA均優(yōu)異于改進(jìn)前的算法,還從側(cè)面驗(yàn)證了改進(jìn)策略的合理性和有效性。同時(shí),將SA-NGOA算法用于ESPO參數(shù)優(yōu)化,結(jié)果顯示優(yōu)化后的ESPO有更高的辨識(shí)精度和辨識(shí)速度??傊?,以上實(shí)驗(yàn)都驗(yàn)證了改進(jìn)算法的有效性。 圖4 3種算法的平均收斂曲線 圖5 參數(shù)a的辨識(shí)曲線 圖6 參數(shù)b的辨識(shí)曲線 圖7 參數(shù)c的辨識(shí)曲線 為改善GOA算法的性能,本文提出了一種非線性自適應(yīng)模擬退火的蝗蟲優(yōu)化算法(SA-NGOA),該算法利用非線性自適應(yīng)更新參數(shù)c,更好地平衡了全局探索與局部開(kāi)發(fā),并在此基礎(chǔ)上混合了模擬退火算法,避免算法陷入局部最優(yōu),結(jié)果表明,SA-NGOA算法有效提高了蝗蟲優(yōu)化算法的收斂速度與全局尋優(yōu)性能。為了更好地發(fā)揮SA-NGOA算法求解復(fù)雜優(yōu)化問(wèn)題的優(yōu)勢(shì),將SA-NGOA算法用于ESPO參數(shù)優(yōu)化,實(shí)驗(yàn)結(jié)果表明,SA-NGOA算法有效實(shí)現(xiàn)了ESPO增益組合的優(yōu)化,與經(jīng)典SPO相比具有更快的辨識(shí)速度和更高的辨識(shí)精度。2.2 優(yōu)化策略
3 實(shí)驗(yàn)與結(jié)果分析
3.1 基準(zhǔn)函數(shù)測(cè)試
3.2 基于SA-NGOA的ESPO參數(shù)優(yōu)化
4 結(jié)束語(yǔ)