求解非線性方程組的蛙跳和BFGS混合算法

潘 學(xué)

(廣西民族大學(xué)教務(wù)處，廣西 南寧 530006)

0 引言

在工程計(jì)算中，非線性方程組的求解問題是最常見的問題之一，如在數(shù)值天氣預(yù)報(bào)、石油地質(zhì)勘探、計(jì)算生物化學(xué)、控制領(lǐng)域和軌道設(shè)計(jì)等方面均有應(yīng)用。因此，尋找高效可靠的非線性方程組的求解方法是非常有必要的［1-2］。目前，求解非線性方程組主要有兩種途徑:一種是采用傳統(tǒng)的數(shù)值求解方法，比如牛頓迭代法、梯度下降法、BFGS方法和它們的改進(jìn)算法等［3］。這些方法具有較高的求解精度和較快的收斂速度，但對初始值非常敏感，如果選取的初始值不在這些傳統(tǒng)方法的收斂域內(nèi)，這些方法將失效［4］。另一種是采用群智能優(yōu)化算法，如遺傳算法、模擬退火算法、差分進(jìn)化算法和人工魚群算法［5-6］等。這些算法的優(yōu)點(diǎn)是對函數(shù)本身沒有要求，對初始值不敏感，但容易陷入局部最優(yōu)，導(dǎo)致求解精度不高。

2003 年，美國學(xué)者 Eusuff和 Lansey［7］借鑒粒子群優(yōu)化算法的思想，將種群的個(gè)體看作青蛙，通過模擬青蛙在覓食過程中共享最優(yōu)信息的行為，提出了一種新的群智能優(yōu)化算法—混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)。SFLA是一種受自然生物啟示而產(chǎn)生的基于群體協(xié)同搜索的優(yōu)化方法，具有概念簡單、參數(shù)少、計(jì)算速度快、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。目前，SFLA已被成功運(yùn)用到解決貼片機(jī)貼裝順序優(yōu)化問題、組合優(yōu)化和數(shù)值優(yōu)化等領(lǐng)域［8-9］。隨著研究的深入，學(xué)者們發(fā)現(xiàn)，與其他群智能優(yōu)化算法一樣，蛙跳算法也存在早熟收斂和求解精度不夠高的缺點(diǎn)［10］。為了提高蛙跳算法的優(yōu)化性能，學(xué)者們提出了很多的改進(jìn)算法。比如，趙鵬軍等人［11］在子群內(nèi)部搜索中結(jié)合吸引排斥機(jī)制，有效避免了算法早熟收斂的問題;何兵等人［12］將蛙跳算法和差分進(jìn)化算法進(jìn)行融合，提出了一種蛙跳和差分進(jìn)化混合算法，提高了算法的性能;葛宇等人［13］將Logistic混沌序列引入到蛙跳算法中，提出了自適應(yīng)混沌變異蛙跳算法，并用實(shí)驗(yàn)證明了該算法的有效性，等等。這些改進(jìn)算法在一定程度上提高了蛙跳算法的性能，但是仍然有各自的不足。

基于以上的分析，本文在利用蛙跳算法求解非線性方程組時(shí)，引入具有強(qiáng)局部收斂能力的BFGS算法，以提高蛙跳算法的局部細(xì)化搜索能力，進(jìn)而提高算法的求解精度。仿真實(shí)驗(yàn)結(jié)果表明，本文提出的蛙跳和BFGS混合算法在解決非線性方程組方面效果顯著，其求解精度比已有的一些求解方法的求解精度高，是求解非線性方程組的有效方法。

1 模型的建立

實(shí)函數(shù)非線性方程組的一般形式(假設(shè)有n個(gè)變量 x1，x2，...，xn和 n 個(gè)方程，且有解)為:

一般地，方程組(1)式可以轉(zhuǎn)化為如下的最優(yōu)化問題形式:

則構(gòu)造適應(yīng)度函數(shù)可以設(shè)置為:

則求解非線性方程組(1)的問題就轉(zhuǎn)化為求適應(yīng)度函數(shù)Y最小值的優(yōu)化問題。

2 蛙跳和BFGS混合算法

2.1 混合蛙跳算法的基本理論

混合蛙跳算法是一種群體智能進(jìn)化算法，它模擬青蛙群體尋找食物時(shí)按子群分類進(jìn)行信息交換的過程，將全局搜索與子群內(nèi)部搜索相結(jié)合，使算法能朝全局最優(yōu)解方向進(jìn)化。混合蛙跳算法的數(shù)學(xué)模型如下:

設(shè)青蛙群體規(guī)模為F，其中第i個(gè)個(gè)體在D維空間中的坐標(biāo)為xi=(xi1，xi2，…，xiD)，計(jì)算個(gè)體的適應(yīng)度f(xi)，根據(jù)適應(yīng)度將其按升序順序排列存儲(chǔ)于集合{(xi，fi)，i=1，2，…，F(xiàn)}中，然后按照特定的劃分原則將整個(gè)青蛙群體分為S個(gè)子群{Y1，Y2，…，Ys}，每個(gè)子群中包含N個(gè)個(gè)體，即滿足關(guān)系F=SN。族群劃分規(guī)則為:

在每一個(gè)子群中，適應(yīng)度最優(yōu)的解記為 xb=(xb1，xb2，…，xbD)，適應(yīng)度最差的解記為 xw=(xw1，xw2，…，xwD);群體中適應(yīng)度最優(yōu)的解記為xg=(xg1，xg2，…，xgD)。則在每次進(jìn)化中，對xw進(jìn)行更新操作，其搜索策略為:

其中，r為［0，1］內(nèi)的均勻隨機(jī)數(shù)，j=1，2，…，S，Dmax為最大移動(dòng)步長。如果f(xw')優(yōu)于f(xw)，則用xw'代替xw;若沒有改進(jìn)，則用xg替換xb，重復(fù)執(zhí)行式(5)和式(6);如若仍沒有改進(jìn)，則從搜索空間中隨機(jī)產(chǎn)生一個(gè)新的解代替原來的xw，并在指定迭代次數(shù)內(nèi)繼續(xù)執(zhí)行以上操作。隨后對所有族群的青蛙重新混合并排序，更新群體最佳青蛙位置xb，然后重新劃分族群，如果循環(huán)直到滿足終止條件，從而完成了蛙跳算法的進(jìn)化過程。

2.2 BFGS 方法

BFGS 方法［14］是由 Broyden、Fletcher、Goldfarb 和Shanno等人在1970年提出的。它是一個(gè)擬牛頓方法，具有二次終止性、整體收斂性和超線性收斂性，且算法所產(chǎn)生的搜索方向是共軛的。BFGS方法是一個(gè)有效的局部算法，用來求解優(yōu)化問題的主要步驟如下:

其中，Step5中不精確一維搜索方法使用的是Wolfe不精確一維搜索方法，即要求λk滿足:

其中，α =0.1，β =0.5。

2.3 蛙跳和BFGS混合算法的過程

混合蛙跳算法具有良好的全局搜索能力，并具有對初始值、參數(shù)選擇不敏感、魯棒性強(qiáng)和容易實(shí)現(xiàn)等優(yōu)點(diǎn)，是一種較好的全局優(yōu)化方法。但在優(yōu)化后期混合蛙跳算法的收斂速度有所變慢，而且求解精度不高，這是因?yàn)榛旌贤芴惴ㄈ狈α己玫木植考?xì)化搜索能力，導(dǎo)致搜索結(jié)果僅獲得滿意解域而不是最優(yōu)解。為了克服這些缺點(diǎn)，本文在混合蛙跳算法的進(jìn)化后期階段引入BFGS方法，利用BFGS強(qiáng)的局部搜索能力和超收斂性來加快收斂速度，提高算法整體的局部搜索能力，進(jìn)而提高求解精度。由于BFGS是局部搜索算法，其優(yōu)化結(jié)果的好壞在很大程度上取決于初始值的選取，為此可以利用具有全局有所能力較強(qiáng)的混合蛙跳算法提供給BFGS方法良好的初始值。

設(shè)群體中解的個(gè)數(shù)為M、子群數(shù)為S、最大子群內(nèi)部進(jìn)化代數(shù)為P以及最大全局進(jìn)化代數(shù)為G，適應(yīng)度函數(shù)為f(x)。針對最小值函數(shù)優(yōu)化問題，本文提出的蛙跳和BFGS混合算法的偽代碼如下:

3 實(shí)驗(yàn)結(jié)果與分析

為了測試本文算法求解非線性方程組的性能，采用蛙跳和BFGS混合算法對3個(gè)非線性方程組［15］進(jìn)行測試，測試結(jié)果和幾種傳統(tǒng)的數(shù)值方法以及混合蛙跳算法的結(jié)果進(jìn)行比較。所有實(shí)驗(yàn)均在Intel(R)Core(TM)2 Duo CPU E4500、2G 內(nèi)存和 MATLAB 7.11.0的環(huán)境中運(yùn)行。算法中涉及的參數(shù)設(shè)置如下:種群中解個(gè)數(shù)M=300，子群數(shù)S=30，子群內(nèi)解個(gè)數(shù)N=10，子群內(nèi)部進(jìn)化代數(shù)P=25，BFGS的最大迭代次數(shù)K=10，ε=1E－7。為了減小誤差，本文算法的最后結(jié)果是算法獨(dú)立運(yùn)行20次的平均值。實(shí)驗(yàn)結(jié)果如表1～表3所示，圖1和圖2分別是基本混合蛙跳算法和本文算法對第一個(gè)非線性方程組和第二個(gè)非線性方程組的計(jì)算誤差的對比圖。

表1 第一個(gè)非線性方程組的求解結(jié)果

表2 第二個(gè)非線性方程組的求解結(jié)果

表3 第三個(gè)非線性方程組的求解結(jié)果

圖1 對第一個(gè)非線性方程組的計(jì)算誤差對比圖

圖2 對第二個(gè)非線性方程組的計(jì)算誤差對比圖

從表1可以看出，對于第一個(gè)非線性方程組，前面4種傳統(tǒng)算法的計(jì)算結(jié)果相差不大，誤差基本上是1E－4。而基本混合蛙跳算法的計(jì)算結(jié)果比傳統(tǒng)算法的結(jié)果要好，誤差降到了1E－10，而本文算法的計(jì)算誤差達(dá)到1E－32，比基本混合蛙跳算法的誤差降低了3倍。這表明，對于第一個(gè)非線性方程組，本文的計(jì)算精度比其它算法提高了很多。圖1是基本混合蛙跳算法和本文算法對第一個(gè)非線性方程組的計(jì)算誤差對比圖，從圖中可以看出，本文算法的收斂速度比基本混合蛙跳算法的收斂速度快。對于第二個(gè)非線性方程組，表2的實(shí)驗(yàn)結(jié)果表明，本文算法的誤差結(jié)果達(dá)到了0，這說明本文算法獲得了精確解，而其它算法卻沒有達(dá)到這個(gè)精度。圖2是第二個(gè)非線性方程組的計(jì)算誤差圖，從圖2也可以看出，本文算法的收斂速度比基本混合蛙跳算法的收斂速度快。第三個(gè)方程組包含10個(gè)方程，從表3可以看出，相對于傳統(tǒng)算法，混合蛙跳算法和本文算法的計(jì)算誤差要小很多，特別本文算法，誤差比基本混合蛙跳算法降低了1倍。

3個(gè)經(jīng)典的非線性方程組的實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)算法和基本混合蛙跳算法相比，本文算法能用更少的迭代次數(shù)找到更精確的解，計(jì)算精度有所提高。

4 結(jié)束語

為提高蛙跳算法的局部細(xì)化能力，進(jìn)而提高其計(jì)算精度，引入局部搜索能力強(qiáng)的BFGS算法，提出一種蛙跳算法和BFGS的混合算法。該混合算法較好地利用了蛙跳算法強(qiáng)的全局搜索能力和BFGS強(qiáng)的局部細(xì)化能力，不但可以加快算法的收斂速度，而且有效地提高了搜索精度，具有很強(qiáng)的魯棒性。3個(gè)非線性方程組的實(shí)驗(yàn)結(jié)果表明，該方法是一種較好的求解非線性方程組的算法，能獲得比傳統(tǒng)算法和基本蛙跳算法更好的求解精度和收斂速度。

［1］王冬冬，周永權(quán).人工魚群算法在求解非線性方程組中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2007，24(6):242-244.

［2］陳海霞，楊鐵貴.基于極大熵差分進(jìn)化混合算法求解非線性方程組［J］.計(jì)算機(jī)應(yīng)用研究，2010，27(6):2028-2030.

［3］Li D H，F(xiàn)ukushima M.A modified BFGS method and its global convergence in nonconvex minimization［J］.Journal of Computational and Applied Mathematics，2001，129(1-2):15-35.

［4］付振岳，王順芳，丁海燕，等.并發(fā)遺傳退火算法求解復(fù)雜非線性方程組［J］.云南大學(xué)學(xué)報(bào):自然科學(xué)版，2012，34(1):15-19.

［5］劉利斌，歐陽艾嘉，許衛(wèi)明，等.求解非線性方程組的BFGS差分進(jìn)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(33):55-58.

［6］高雷阜，齊微.改進(jìn)的粒子群理論及在非線性方程組中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(35):48-50，76.

［7］Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled forg leaping algorithm［J］.Journal of Water Resources Planning and Management，2003，129(3):210-225.

［8］萬博，盧昱，陳立云，等.求解CVRP的改進(jìn)混合蛙跳算法研究［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(12):4503-4506.

［9］陳鐵梅，羅家祥，胡躍明.基于蟻群-混合蛙跳算法的貼片機(jī)貼裝順序優(yōu)化［J］.控制理論與應(yīng)用，2011，28(12):1813-1820.

［10］丁衛(wèi)平，王建東，管致錦.基于量子蛙跳協(xié)同進(jìn)化的粗糙屬性快速約簡［J］.電子學(xué)報(bào)，2011，39(11):2597-2603.

［11］趙鵬軍.基于差分?jǐn)_動(dòng)的混合蛙跳算法［J］.計(jì)算機(jī)應(yīng)用，2010，30(10):2575-2577.

［12］何兵，車林仙，劉初升.一種蛙跳和差分進(jìn)化混合算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(18):4-8.

［13］葛宇，王學(xué)平，梁靜.自適應(yīng)混沌變異蛙跳算法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(3):945-947.

［14］唐煥文，秦學(xué)志.實(shí)用最優(yōu)化方法［M］.大連:大連理工大學(xué)出版社，2006.

［15］Grosan C，Abraham A.A new approach for solving nonlinear equations systems［J］.IEEE Transactions on Systems，Man and Cybernetics-Part A，2008，38(3):698-714.