呂昱呈，莫愿斌,2+

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

0 引 言

方程組的求解一直是難點(diǎn)問題，求解方程組有牛頓法、歐拉法以及錐模型信賴域算法[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)重改變天牛位置，加強(qiáng)全局尋優(yōu)能力；加入步長自適應(yīng)以精確提高天牛后期小范圍內(nèi)搜索的準(zhǔn)確性。通過標(biāo)準(zhǔn)測試函數(shù)對改進(jìn)的天牛須算法進(jìn)行性能測試，將其用于求解方程組和實(shí)際工程應(yīng)用問題，所得結(jié)果與其它算法對比表明該算法在方程組解的數(shù)量和質(zhì)量都具有優(yōu)勢，進(jìn)一步驗(yà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)天牛須算法來驗(yàn)證在求解方程組問題的有效性。

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次迭代時(shí)天牛質(zhì)心坐標(biāo)，d0為左右兩須之間的距離長度。式(7)是天牛位置的更新，其中，stept表示第t次迭代的步長因子，sign(·) 表示符號函數(shù)。

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

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

傳統(tǒng)BAS算法有較快尋優(yōu)能力，由于其初始位置隨機(jī)性，且在每一步移動過程中方向是隨機(jī)單一，導(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)插入兩點(diǎn)x1，x2， 并計(jì)算其函數(shù)值，此時(shí)區(qū)間被分成3段。通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。其原理如圖1所示。

圖1 黃金分割算法原理

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

(8)

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

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

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

(9)

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

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

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

(10)

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

圖2 步長變化對比

傳統(tǒng)BAS算法每次的步長變化均勻，天牛極易探索到某個(gè)范圍陷入局部最優(yōu)，導(dǎo)致求解錯(cuò)誤；引入步長自適應(yīng)機(jī)制后，GRBAS算法的步長在開始搜索時(shí)可以進(jìn)行大范圍空間搜索；迭代到中間次數(shù)時(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個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行測試。最后，將GRBAS算法運(yùn)用在求方程組的解。包括3個(gè)線性方程組和3個(gè)非線性方程組。

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

表1是標(biāo)準(zhǔn)測試函數(shù)相關(guān)參數(shù)設(shè)置，表2給出7種算法的實(shí)驗(yàn)結(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。每個(gè)函數(shù)均運(yùn)行20次，分別統(tǒng)計(jì)7種算法的平均值，最優(yōu)值以及最差值。圖4～圖13為每個(gè)函數(shù)迭代曲線。

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

表2 7種算法實(shí)驗(yàn)結(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的計(jì)算都收斂到最優(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)的天牛須算法計(jì)算精度和穩(wěn)定性都有較明顯提升。驗(yàn)證基于帶權(quán)重的改進(jìn)天牛須算法尋優(yōu)的有效性，表明GRBAS算法能夠在算法陷入局部最優(yōu)時(shí)有效跳出局部搜索范圍，同時(shí)在高維空間下，搜索解的能力較好，解值更接近與理論值。

4.3 方程組的求解

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

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

表3 線性方程組的實(shí)驗(yàn)結(jié)果

文中引入文獻(xiàn)[3]中的非線性方程組進(jìn)行仿真實(shí)驗(yà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個(gè)非線性方程組仿真測試結(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)勢，求解精度上更好；方程組②，牛頓法只能求出一個(gè)解，PSO算法和BAS算法的求解與理想值有一定的差距，HCS算法和GRBAS算法的求解精度相近，但GRBAS算法精度更高；方程組③雖然沒有求解到近似解值，但是比BAS、PSO算法求解結(jié)果更好，其解值與HCS結(jié)果相近，但是在求解精度上GRBAS算法更精確。通過實(shí)驗(yàn)結(jié)果分析，GRBAS算法具有較好的求解能力。

5 工程應(yīng)用

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

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

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

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

(11)

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

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

(12)

通過仿真測試，求得方程組(12)全部實(shí)數(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算法仿真運(yùn)行，運(yùn)行結(jié)果保留6位小數(shù)點(diǎn)，其結(jié)果與文獻(xiàn)結(jié)果對照見表7。

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

5.2 結(jié)果分析

用GRBAS算法對三角函數(shù)超越方程的仿真實(shí)驗(yàn)與算例1中文獻(xiàn)[15]的數(shù)據(jù)對比知，PSO算法沒有很好的求解到最優(yōu)值，每組解的誤差很大；文獻(xiàn)[15]使用牛頓法，其收斂性依賴于初值選取，造成求解結(jié)果數(shù)量受局限；本文算法比牛頓法求解的精度更高，同時(shí)算出3組文獻(xiàn)[15]中未求解出的解組。對3種算法的18組解進(jìn)行誤差比較知，GRBAS算法的誤差均勻。平均誤差比牛頓法求解略高一點(diǎn)，是由于在所給出的解集中有個(gè)別解組解值的精度較低影響整體平均誤差值。在其它解組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)用實(shí)例求解超越方程證明GRBAS算法在求解方程組的有效性和正確性。

6 結(jié)束語

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