潘 學(xué)

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

0 引言

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

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

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

1 模型的建立

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

一般地，方程組(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)化算法，它模擬青蛙群體尋找食物時按子群分類進(jìn)行信息交換的過程，將全局搜索與子群內(nèi)部搜索相結(jié)合，使算法能朝全局最優(yōu)解方向進(jìn)化?；旌贤芴惴ǖ臄?shù)學(xué)模型如下:

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

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

2.2 BFGS 方法

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

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

其中，α =0.1，β =0.5。

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

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

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

3 實驗結(jié)果與分析

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

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

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

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

圖1 對第一個非線性方程組的計算誤差對比圖

圖2 對第二個非線性方程組的計算誤差對比圖

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

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

4 結(jié)束語

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

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

［2］陳海霞，楊鐵貴.基于極大熵差分進(jìn)化混合算法求解非線性方程組［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é)報:自然科學(xué)版，2012，34(1):15-19.

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

［6］高雷阜，齊微.改進(jìn)的粒子群理論及在非線性方程組中的應(yīng)用［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ī)應(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é)報，2011，39(11):2597-2603.

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

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

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

［14］唐煥文，秦學(xué)志.實用最優(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.