帶權重的改進天牛須算法解方程組及工程應用

呂昱呈，莫愿斌,2+

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

0 引 言

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

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

1 方程組的優化模型轉換

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

(1)

(2)

方程組的解對應F(x1,x2,…,xn) 最小值為0的解，所以方程組求解問題可轉為求下式的最優解

(3)

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

2 天牛須優化算法

天牛須算法是根據天牛覓食為仿生原理的智能優化算法。BAS算法當前在圖像處理[7]、路徑規劃[8]、電力調度[9]等問題得到初步應用。天牛覓食的過程就是天牛須算法的尋優過程。其步驟如下

(4)

stept+1=eta*stept

(5)

(6)

(7)

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

天牛須算法依靠兩條須能夠實現快速尋優，但同時也會因為位置更新的方向單一，導致天牛陷入局部最優，由于天牛沒有跳出局部最優的能力，降低BAS算法的搜索精度[10]；混合教與學算法的天牛須搜索[11]在一定程度上提高了搜索精度，但仍未求解到最優值，且迭代次數很大也未尋到最優解。基于此提出本文的改進方法，當天牛在搜索過程中陷入局部某個極值時能夠跳出限制，同時改變天牛的位置方向使算法在快速迭代收斂的同時有更優的尋優效果。

3 改進的天牛須算法

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

3.1 引入黃金分割法

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

圖1 黃金分割算法原理

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

(8)

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

3.2 帶位置權重的天牛

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

(9)

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

3.3 天牛步長自適應

根據式(7)可知，步長step越大，天牛全局搜索能力越強，反之，局部搜索能力越強。本文提出步長自適應機制，算法前期，讓天牛在求解空間擴大搜索范圍快速尋優，采用大步長因子，算法后期，采用小步長因子。基于上述描述，通過測試驗算，本文采用如下天牛步長自適應機制

(10)

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

圖2 步長變化對比

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

3.4 算法流程

基于黃金分割的帶位置權重和自適應的天牛須算法的流程如圖3所示。

圖3 算法流程

改進天牛須算法(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 測試與結果分析

為測試GRBAS算法的尋優能力和精確度，對10個標準測試函數進行測試。最后，將GRBAS算法運用在求方程組的解。包括3個線性方程組和3個非線性方程組。

4.1 標準測試函數的測試

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

表1 標準測試函數的相關參數

表2 7種算法實驗結果

表2(續)

表2(續)

圖4 函數f1的迭代曲線

圖5 函數f2的迭代曲線

圖6 函數f3的迭代曲線

圖7 函數f4的迭代曲線

圖8 函數f5的迭代曲線

圖9 函數f6的迭代曲線

圖10 函數f7的迭代曲線

圖11 函數f8的迭代曲線

圖12 函數f9的迭代曲線

圖13 函數f10的迭代曲線

4.2 結果分析

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

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

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

4.3 方程組的求解

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

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

表3 線性方程組的實驗結果

文中引入文獻[3]中的非線性方程組進行仿真實驗，非線性方程組如下

理論值： (-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個非線性方程組仿真測試結果見表4。

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

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

5 工程應用

工程中許多問題要用方程組求解，如三電平逆變器問題[14]，為逆變器SHEPWM的非線性方程組求解對調制技術提供新方案，使開關角度更易于收斂；供電網絡系統各節點電壓的求解；懸索橋鞍處主纜長度的計算要對二元非線性方程組進行求解。

5.1 工程領域中方程組

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

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

(11)

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

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

(12)

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

表5 GRBAS算法求解結果

表6 誤差分析

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

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

(13)

求解該超越方程在區間[-5,5]內的根。通過GRBAS算法仿真運行，運行結果保留6位小數點，其結果與文獻結果對照見表7。

表7 GRBAS算法與文獻結果對比

5.2 結果分析

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

6 結束語

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