帶權(quán)重的改進(jìn)天牛須算法解方程組及工程應(yīng)用

呂昱呈，莫愿斌,2+

(1.廣西民族大學(xué) 人工智能學(xué)院，廣西 南寧 530006；2.廣西民族大學(xué) 廣西混雜計算與集成電路設(shè)計分析重點實驗室，廣西 南寧 530006)

0 引 言

方程組的求解一直是難點問題，求解方程組有牛頓法、歐拉法以及錐模型信賴域算法[1]等。傳統(tǒng)數(shù)值算法求解對初始值設(shè)定要求較高，使算法存在局限性。目前優(yōu)化算法被用在方程組求解中，將方程組轉(zhuǎn)化為目標(biāo)尋優(yōu)問題，提供一種解決方案。曾等[2]提出蝴蝶算法融合改進(jìn)的反向?qū)W習(xí)和二次插值；黎等[3]提出布谷鳥算法結(jié)合差分進(jìn)化和二次插值求方程組較多解問題。優(yōu)化算法求解方程組仍有很多問題值得研究，Zhang等[4]所提出改進(jìn)的布谷鳥算法對非線性方程組的求解只注重單值解值；Ariyaratne等[5]對方程組求解值的精度較低。

為此，提出一種求解方程組的方法，將黃金分割法調(diào)整搜索區(qū)間的優(yōu)勢融入天牛須算法(BAS)[6]中；添加位置權(quán)重改變天牛位置，加強全局尋優(yōu)能力；加入步長自適應(yīng)以精確提高天牛后期小范圍內(nèi)搜索的準(zhǔn)確性。通過標(biāo)準(zhǔn)測試函數(shù)對改進(jìn)的天牛須算法進(jìn)行性能測試，將其用于求解方程組和實際工程應(yīng)用問題，所得結(jié)果與其它算法對比表明該算法在方程組解的數(shù)量和質(zhì)量都具有優(yōu)勢，進(jìn)一步驗證了改進(jìn)算法的尋優(yōu)能力與求解方程組性能。

1 方程組的優(yōu)化模型轉(zhuǎn)換

線性方程組，是方程關(guān)于未知量均為一次的方程組。非線性方程，是因變量與自變量之間不是線性關(guān)系。求解此類方程往往很難得到精確解，需要求近似解問題。相應(yīng)的求近似解的方法也逐漸得到重視。方程組[2]如下

(1)

(2)

方程組的解對應(yīng)F(x1,x2,…,xn) 最小值為0的解，所以方程組求解問題可轉(zhuǎn)為求下式的最優(yōu)解

(3)

因此選擇尋優(yōu)性能好的算法是解方程組問題的關(guān)鍵，對此本文提出基于黃金分割的帶位置權(quán)重和自適應(yīng)天牛須算法來驗證在求解方程組問題的有效性。

2 天牛須優(yōu)化算法

天牛須算法是根據(jù)天牛覓食為仿生原理的智能優(yōu)化算法。BAS算法當(dāng)前在圖像處理[7]、路徑規(guī)劃[8]、電力調(diào)度[9]等問題得到初步應(yīng)用。天牛覓食的過程就是天牛須算法的尋優(yōu)過程。其步驟如下

(4)

stept+1=eta*stept

(5)

(6)

(7)

式(4)是天牛方向向量，n為空間維度。式(5)是天牛步長更新公式，遞減因子eta在[0,1]之間，本文取0.95；式(6)中，xl、xr分別表示天牛左右兩須位置，xt表示在第t次迭代時天牛質(zhì)心坐標(biāo)，d0為左右兩須之間的距離長度。式(7)是天牛位置的更新，其中，stept表示第t次迭代的步長因子，sign(·) 表示符號函數(shù)。

天牛須算法依靠兩條須能夠?qū)崿F(xiàn)快速尋優(yōu)，但同時也會因為位置更新的方向單一，導(dǎo)致天牛陷入局部最優(yōu)，由于天牛沒有跳出局部最優(yōu)的能力，降低BAS算法的搜索精度[10]；混合教與學(xué)算法的天牛須搜索[11]在一定程度上提高了搜索精度，但仍未求解到最優(yōu)值，且迭代次數(shù)很大也未尋到最優(yōu)解?；诖颂岢霰疚牡母倪M(jìn)方法，當(dāng)天牛在搜索過程中陷入局部某個極值時能夠跳出限制，同時改變天牛的位置方向使算法在快速迭代收斂的同時有更優(yōu)的尋優(yōu)效果。

3 改進(jìn)的天牛須算法

傳統(tǒng)BAS算法有較快尋優(yōu)能力，由于其初始位置隨機性，且在每一步移動過程中方向是隨機單一，導(dǎo)致算法在尋優(yōu)過程中極易陷入局部最優(yōu)。為解決此問題，本文引入基于黃金分割的帶位置權(quán)重和自適應(yīng)的算法，對傳統(tǒng)BAS算法進(jìn)行改進(jìn)。

3.1 引入黃金分割法

黃金分割法是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法，每次可以將區(qū)間按照一定比率壓縮，修正原來的求解范圍。即在搜索區(qū)間 [a,b] 內(nèi)插入兩點x1，x2， 并計算其函數(shù)值，此時區(qū)間被分成3段。通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。其原理如圖1所示。

圖1 黃金分割算法原理

文中的GRBAS算法是在天牛走完當(dāng)前這一步時，獲取其左右兩須的位置值，作為黃金分割法的搜索區(qū)間，構(gòu)成與目標(biāo)函數(shù)值相近的低次多項式，利用黃金分割算子式在搜索區(qū)間搜索極值點的方法，每次迭代取試探點

(8)

式中：αk+1和βk+1表示在搜索區(qū)間內(nèi)通過黃金分割法選取的試探點位置。在求解方程組過程中引入黃金分割，把多項式的最優(yōu)解與原函數(shù)的最優(yōu)解之間的距離逐步減小，是一個收斂速度極快的搜索方法。提升了天牛須搜索算法的局部搜索能力，提高天牛跳出局部最優(yōu)的能力以及搜索精度的能力。

3.2 帶位置權(quán)重的天牛

天牛更新位置時，因蓄力等因素做微弱方向位置調(diào)整飛到下一個目的地。本文引入“位置權(quán)重”因子w，改變天牛位置，增強天牛全局尋優(yōu)能力，引入位置權(quán)重的天牛位置更新方程如式(9)所示

(9)

由式(9)可知，較大的w能加強BAS全局搜索能力，反之，較小的w能加強局部搜索能力。BAS算法本身存在易陷入局部最優(yōu)的缺陷，要提升全局搜索能力，因此選擇較大的w，實驗結(jié)果表明，w在[0.95,0.96]之間BAS有更快的收斂速度，算法求解精度也得到很大的提高，提高了BAS算法的性能。

3.3 天牛步長自適應(yīng)

根據(jù)式(7)可知，步長step越大，天牛全局搜索能力越強，反之，局部搜索能力越強。本文提出步長自適應(yīng)機制，算法前期，讓天牛在求解空間擴(kuò)大搜索范圍快速尋優(yōu)，采用大步長因子，算法后期，采用小步長因子?；谏鲜雒枋觯ㄟ^測試驗算，本文采用如下天牛步長自適應(yīng)機制

(10)

式中：stept是第t次迭代時的步長，stepmax表示初始步長長度。原始步長和自適應(yīng)步長遞減情況對比如圖2所示。

圖2 步長變化對比

傳統(tǒng)BAS算法每次的步長變化均勻，天牛極易探索到某個范圍陷入局部最優(yōu)，導(dǎo)致求解錯誤；引入步長自適應(yīng)機制后，GRBAS算法的步長在開始搜索時可以進(jìn)行大范圍空間搜索；迭代到中間次數(shù)時，步長縮短變快，促使搜索范圍的收縮；迭代后期，步長縮短減弱，使算法查找尋優(yōu)更精確，豐富全局搜索能力，提升搜索精度。

3.4 算法流程

基于黃金分割的帶位置權(quán)重和自適應(yīng)的天牛須算法的流程如圖3所示。

圖3 算法流程

改進(jìn)天牛須算法(GRBAS)偽代碼如下所示：

Algorithm GRBAS.

Input： set direction vectordir; distance between the two beetles’ antennaesd; step lengthstep; max iterationn; spatial dimensionk；

Output：Best valuefbest.

(1)Set the initial position of beetlex=rands(k,1);

(3)fori=1 ton

(4)Initilization beetle direction vectordir=rands(k,1);

(5)Calculate the position of two beetles’antennaes;

(6) Initilization beetle antennae coordinatexleft、xright;

(7) Calculate the fitness of thexleftandxright；

(8)Change range through golden ratio:x0=xright*w+0.382*(xleft-xright)andx1=xright*w+0.618*(xleft-xright);

(9) Calculate the fitness of thex0 andx1;

(10)Update the range of two antennaes of beetle;

(11)end

(12)Adaptive step size;

(13)Update the position of beetle through w:x=x*w-step*dor*sign(fleft-fright);

(14)fbest_store=the fitness of the best value;

(15)returnfbest_store;

4 測試與結(jié)果分析

為測試GRBAS算法的尋優(yōu)能力和精確度，對10個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行測試。最后，將GRBAS算法運用在求方程組的解。包括3個線性方程組和3個非線性方程組。

4.1 標(biāo)準(zhǔn)測試函數(shù)的測試

表1是標(biāo)準(zhǔn)測試函數(shù)相關(guān)參數(shù)設(shè)置，表2給出7種算法的實驗結(jié)果。算法最大迭代次數(shù)均為900，粒子群算法(PSO)、人工魚群算法(AFSA)和改進(jìn)的海鷗算法(MSOA)種群數(shù)目為200，學(xué)習(xí)因子為2，慣性因子0.8，人工魚最大步長0.1，感知距離為1。MSOA螺旋系數(shù)u和v初始為0.1。BAS和GRBAS算法初始步長設(shè)為1。蟻獅算法(ALO)和烏燕鷗算法(STOA)的尋找群體數(shù)目為40。每個函數(shù)均運行20次，分別統(tǒng)計7種算法的平均值，最優(yōu)值以及最差值。圖4～圖13為每個函數(shù)迭代曲線。

表1 標(biāo)準(zhǔn)測試函數(shù)的相關(guān)參數(shù)

表2 7種算法實驗結(jié)果

表2(續(xù))

表2(續(xù))

圖4 函數(shù)f1的迭代曲線

圖5 函數(shù)f2的迭代曲線

圖6 函數(shù)f3的迭代曲線

圖7 函數(shù)f4的迭代曲線

圖8 函數(shù)f5的迭代曲線

圖9 函數(shù)f6的迭代曲線

圖10 函數(shù)f7的迭代曲線

圖11 函數(shù)f8的迭代曲線

圖12 函數(shù)f9的迭代曲線

圖13 函數(shù)f10的迭代曲線

4.2 結(jié)果分析

通過7種算法對比，GRBAS算法對測試函數(shù)f1、f2、f3、f4、f5、f7、f8、f9、f10的計算都收斂到最優(yōu)值，比其它算法在求解精度和準(zhǔn)確率都高。對于函數(shù)f6，GRBAS有求解到最優(yōu)解的情況，MSOA、STOA算法求解陷入局部最優(yōu)，原始BAS算法的解值范圍極不穩(wěn)定，而GRBAS算法的解值穩(wěn)定。

對比圖4～圖13可知，函數(shù)f1、f3、f4、f8，GRBAS算法在迭代次數(shù)約720次就求得最優(yōu)解停止迭代，其它算法在設(shè)定的900次迭代后仍未收斂到最優(yōu)；函數(shù)、f5、f7、f10，GRBAS算法在迭代初期就能尋優(yōu)求到最優(yōu)值，其它函數(shù)均有不同程度的陷入局部最優(yōu)或在最大收斂次數(shù)后仍未求解出最優(yōu)解的情況；函數(shù)f2、f9算法GRBAS在迭代約250次求得最優(yōu)解，而其它算法在900次迭代后仍未停止求解；函數(shù)f6，GRBAS算法的收斂效果較其它算法更平穩(wěn)。

由此知改進(jìn)的天牛須算法計算精度和穩(wěn)定性都有較明顯提升。驗證基于帶權(quán)重的改進(jìn)天牛須算法尋優(yōu)的有效性，表明GRBAS算法能夠在算法陷入局部最優(yōu)時有效跳出局部搜索范圍，同時在高維空間下，搜索解的能力較好，解值更接近與理論值。

4.3 方程組的求解

為了測試該算法求解方程組的性能，選取3組線性方程組[12]和3組非線性方程組進(jìn)行測試，每個方程均獨立運行10次，將結(jié)果取平均值，實驗結(jié)果如表3所示。線性方程組如下

理論值： (1,2.5,3,6.5,7)

表3 線性方程組的實驗結(jié)果

文中引入文獻(xiàn)[3]中的非線性方程組進(jìn)行仿真實驗，非線性方程組如下

理論值： (-0.707 106 78,1.5)(0,1)(-1,2)

理論值：(1.546 342,1.391 174)(1.067 412,0.139 460)

近似理論值：x1=-0.451 123，x2=0.445 178

對3個非線性方程組仿真測試結(jié)果見表4。

結(jié)果分析：從表3知，經(jīng)典牛頓方法能夠求出理想值，方程組(1)和方程組(2)，PSO、BAS以及GRBAS算法求出的值都接近理想值，GRBAS的求解精度更好；方程組(3)PSO算法的求解值偏離理想值，BAS和GRBAS算法的求解值較理想值接近，但是GRBAS的求解精度更好。

從表4知，對于方程組①，文獻(xiàn)[13]和HCS能夠找出方程組的全部解且其值接近于理論值，BAS算法雖能求得全部解但求解精度不高，而GRBAS算法更具有優(yōu)勢，求解精度上更好；方程組②，牛頓法只能求出一個解，PSO算法和BAS算法的求解與理想值有一定的差距，HCS算法和GRBAS算法的求解精度相近，但GRBAS算法精度更高；方程組③雖然沒有求解到近似解值，但是比BAS、PSO算法求解結(jié)果更好，其解值與HCS結(jié)果相近，但是在求解精度上GRBAS算法更精確。通過實驗結(jié)果分析，GRBAS算法具有較好的求解能力。

5 工程應(yīng)用

工程中許多問題要用方程組求解，如三電平逆變器問題[14]，為逆變器SHEPWM的非線性方程組求解對調(diào)制技術(shù)提供新方案，使開關(guān)角度更易于收斂；供電網(wǎng)絡(luò)系統(tǒng)各節(jié)點電壓的求解；懸索橋鞍處主纜長度的計算要對二元非線性方程組進(jìn)行求解。

5.1 工程領(lǐng)域中方程組

在建筑工程的相關(guān)實際操作中，如鋼筋混凝土結(jié)構(gòu)的研究問題通常會歸結(jié)到三角函數(shù)超越方程求解結(jié)果的實零點。求解三角函數(shù)超越方程組常用牛頓迭代法和梯度下降法，使用這兩種算法在初值選取時有較高的要求。求解三角函數(shù)超越方程其極值的位置是很困難的。該類超越方程經(jīng)過恒等變形、代換和消元，可歸結(jié)為含有一個變量的方程組

F(x)=(F1(x),F(x),…,F(x))T=0

(11)

表4 非線性方程組①-③的實驗結(jié)果

其中，x=(x1,x2,…,xn)T為n個變量。由于三角函數(shù)在區(qū)間上是一個周期函數(shù)，在區(qū)間內(nèi)方程組的實零點不唯一，針對這一特點，使用改進(jìn)天牛須算法進(jìn)行求其全部實零點。為了測試GRBAS算法在求三角函數(shù)超越方程組的性能，文中引入了文獻(xiàn)[15]中的超越方程組作為算例1進(jìn)行仿真實驗

(12)

通過仿真測試，求得方程組(12)全部實數(shù)解表5所示以及誤差值對比見表6。

表5 GRBAS算法求解結(jié)果

表6 誤差分析

本文引用文獻(xiàn)[16]中的超越方程作為算例2。其超越方程式(13)如下

(x-1)2sin2x+(x-1)3cos3x+5(x2-1)=0

(13)

求解該超越方程在區(qū)間[-5,5]內(nèi)的根。通過GRBAS算法仿真運行，運行結(jié)果保留6位小數(shù)點，其結(jié)果與文獻(xiàn)結(jié)果對照見表7。

表7 GRBAS算法與文獻(xiàn)結(jié)果對比

5.2 結(jié)果分析

用GRBAS算法對三角函數(shù)超越方程的仿真實驗與算例1中文獻(xiàn)[15]的數(shù)據(jù)對比知，PSO算法沒有很好的求解到最優(yōu)值，每組解的誤差很大；文獻(xiàn)[15]使用牛頓法，其收斂性依賴于初值選取，造成求解結(jié)果數(shù)量受局限；本文算法比牛頓法求解的精度更高，同時算出3組文獻(xiàn)[15]中未求解出的解組。對3種算法的18組解進(jìn)行誤差比較知，GRBAS算法的誤差均勻。平均誤差比牛頓法求解略高一點，是由于在所給出的解集中有個別解組解值的精度較低影響整體平均誤差值。在其它解組GRBAS算法在解值的精度上更好。算例2中GRBAS算法的仿真結(jié)果與文獻(xiàn)[16]中結(jié)果對比知，GRBAS算法能很好搜索求解到精確值。文獻(xiàn)[16]的方法最大相對誤差為0.000 120，GRBAS算法最大相對誤差為0.000 003。表明改進(jìn)天牛須算法有效解決了在建筑工程領(lǐng)域里，鋼筋混凝土相關(guān)問題中常見的非線性方程組多解問題。工程應(yīng)用實例求解超越方程證明GRBAS算法在求解方程組的有效性和正確性。

6 結(jié)束語

本文針對基本天牛須算法存在易陷入局部最優(yōu)、求解精度低的不足，提出一種帶位置權(quán)重的黃金分割自適應(yīng)天牛須算法(GRBAS)。將黃金分割法引入天牛須算法中，把天牛左右兩須的位置作為黃金分割的區(qū)間邊界；引入“位置權(quán)重”影響當(dāng)前天牛位置，利于改變天牛受局部范圍的困擾，再對天牛采用自適應(yīng)改變每一次迭代的步長，使算法在前期搜索范圍更廣，后期收斂更精確。通過標(biāo)準(zhǔn)函數(shù)測試、線性和非線性方程組的求解，以及用于求解工程實際中三角函數(shù)超越方程組，均獲得滿意效果。表明了GRBAS算法的有效性和可行性，其在跳出局部最優(yōu)能力、求解精度方面均優(yōu)于基本的BAS算法。