基于極大熵差分進化混合算法求解非線性方程組

摘 要:針對非線性方程組，給出了一種新的算法——極大熵差分進化混合算法。首先把非線性方程組轉(zhuǎn)換為一個不可微優(yōu)化問題;然后用一個稱之為凝聚函數(shù)的光滑函數(shù)直接代替不可微的極大值函數(shù)，從而可把非線性方程組的求解轉(zhuǎn)換為無約束優(yōu)化問題，利用差分進化算法對其進行求解。計算結(jié)果表明，該算法在求解的準確性和有效性均優(yōu)于其他算法。

關(guān)鍵詞:差分進化算法; 非線性方程組; 極大熵方法

中圖分類號:TP18文獻標志碼:A

文章編號:1001-3695(2010)06-2028-03

doi:10.3969/j.issn.1001-3695.2010.06.008

Solving nonlinear equations based on maximum-entropy differential evolution hybrid algorithm

CHEN Hai-xia， YANG Tie-gui

(Dept. of Basic Education， Zhengzhou Occupation Technology College， Zhengzhou 450121， China)

Abstract:To solve nonlinear equations， this paper presented a new method， referred to as maximum-entropy differential evolution hybrid algorithm. First， transformed nonlinear equations problems into non-differentiable optimization， and used the smooth aggregate function to instead of maximum function in non-differentiable optimization problem. Thereupon， the primal problem could be transformed into unconstrained optimization， then used the differential evolution algorithm to solve this problem. Numerical results show that the proposed method is more accurate and effective.

Key words:differential evolution algorithm; nonlinear equations; maximum entropy method

0 引言

求解非線性方程組是科學技術(shù)和工程應用中的常見問題。非線性方程組的解法長期以來是數(shù)學和工程應用中的一個重要的研究內(nèi)容。很多實際問題的數(shù)學模型最終都歸結(jié)為求解形如F(x)=0的非線性方程組，求解非線性方程組的常用方法是牛頓法。牛頓法的收斂性和性能在很大程度上依賴于初始點，在適當?shù)臈l件下，該方法具有二階收斂速度。牛頓法對迭代初始值的要求相當苛刻，如果初始值不在牛頓迭代的收斂域內(nèi)，該方法失效。但是對于很多非線性方程組，選擇好的初始點是一件非常困難的事情。鑒于牛頓法的缺點，文獻[1]結(jié)合遺傳算法和經(jīng)典算法的優(yōu)點，提出了一種用于求解非線性方程組的混合遺傳算法。該混合算法充分發(fā)揮了遺傳算法的群體搜索和全局收斂性，有效地克服了經(jīng)典算法初始點敏感的問題;同時在遺傳算法中引入經(jīng)典算法(Powell法、擬牛頓迭代法)作局部搜索，克服了遺傳算法收斂速度慢和精度差的缺點。文獻[2]探討了用模擬退火算法求解非線性方程及方程組的方法，該方法把方程組求解問題轉(zhuǎn)換為函數(shù)優(yōu)化問題;文獻[3]提出了一種求解線性和非線性方程組的通用算法——蒙特卡羅算法;文獻[4]提出了一種求解線性和非線性方程組的微粒群算法。關(guān)于各種求解非線性方程組的智能算法正在不斷的發(fā)展當中，隨著計算機技術(shù)的發(fā)展，相信會有更多智能算法出現(xiàn)。

近年來，一些不依賴于初始點和梯度信息的智能優(yōu)化算法得到了迅速發(fā)展。Storn等人[5]和Lampinen[6]于1995年提出的差分進化(differential evolution，DE)算法是一種隨機的并行直接搜索算法，它可對非線性不可微連續(xù)空間函數(shù)進行最小化，以其易用性、穩(wěn)健性和強大的全局尋優(yōu)能力在多個領(lǐng)域取得成功。在1996年舉行的第一屆國際IEEE進化優(yōu)化競賽上，對提出的各種方法進行了現(xiàn)場驗證，DE算法被證明是最快的進化算法。目前，DE算法已經(jīng)在許多領(lǐng)域得到了應用[7，8]。本文通過把非線性方程組優(yōu)化問題都轉(zhuǎn)換成等價的不可微優(yōu)化問題， 采用極大熵函數(shù)對不可微優(yōu)化問題進行處理， 引入適當?shù)哪繕撕瘮?shù)， 進而把原問題轉(zhuǎn)換為無約束優(yōu)化， 然后利用差分進化算法對其進行求解。數(shù)值實驗結(jié)果表明了該方法的正確性和有效性。

1 問題的轉(zhuǎn)換

考慮非線性方程組F(x)=0，x∈DRn。其中F(x)=(f1(x)，f2(x)，…， fm(x))T， fj∶Rn→R是連續(xù)可微的實值函數(shù)。若用‖#8226;‖p表示向量空間p-范數(shù)，于是非線性方程組可以轉(zhuǎn)換為求解

minx∈Rn‖F(xiàn)(x)‖p

取p=2，即為一個非線性最小二乘問題min∑mi=1f 2i(x)。關(guān)于該問題的求解，方法已經(jīng)很多，讀者可以參考相關(guān)文獻。本文取p=∞，則上述問題轉(zhuǎn)換為

minx∈Rnmax1≤i≤m{|fi(x)|}

記f(x)=max1≤i≤m{|fi(x)|}，因此原非線性方程組問題就轉(zhuǎn)換為求解優(yōu)化問題minx∈Rn f(x)。一般情況下，函數(shù)f(x)是不可微的，這給一些數(shù)值計算上帶來了困難。下面引進極大熵函數(shù)Fp(x)=1pln∑mi=1exp[p|fi(x)|]。其中p>0為控制參數(shù)。關(guān)于極大熵函數(shù)的導出讀者可以參考文獻[9，10]，熵函數(shù)也稱凝聚函數(shù)。該函數(shù)從數(shù)學上是以原來函數(shù)fi(x)絕對值的指數(shù)函數(shù)構(gòu)成向量函數(shù)Lp范數(shù)的自然對數(shù)。先頭的指數(shù)變換使向量的各分量為正，后面的對數(shù)變換使函數(shù)值復原。

下面證明，當p趨于無窮大時，F(xiàn)p(x)在整個空間上一致逼近f(x)。

命題1 f(x)≤Fp(x)≤f(x)+1pln m。

證明 把Fp(x)改寫成等價形式Fp(x)=f(x)+1pln∑mi=1exp{p[|fi(x)|-f(x)]}，很顯然，|fi(x)|-f(x)≤0，1≤i≤m，且其中至少有一個等于零。因此有1≤∑mi=1exp{p[|fi(x)|-f(x)]}≤m，從而有0≤Fp(x)-f(x)≤1pln m，即f(x)≤Fp(x)≤f(x)+1pln m。

命題2 Fp(x)的值隨參數(shù)p的增加而單調(diào)下降，且當p趨于無窮大時Fp(x)以f(x)為極限。

證明 設(shè)向量函數(shù)ψ(x)，它的分量分別為|fi(x)|的指數(shù)函數(shù)，即ψi(x)=exp[|fi(x)|]，i=1，2，…，m。因其分量皆為正值，故它的Lp范數(shù)可直接定義為‖ψ(x)‖p=∑mi=1exp[ψi(x)]p1/p=∑mi=1exp[p|fi(x)|]1/p。其中p≥1。

對上式兩邊取對數(shù)，即可得到ln‖ψ(x)‖p=1p{∑mi=1exp[p|fi(x)|]}，等式的右端就是凝聚函數(shù)，因此有Fp(x)=ln‖ψ(x)‖p。由Jensen不等式[10]，若q≥p≥1，即有‖ψ(x)‖p≥‖ψ(x)‖q，兩邊取自然對數(shù)，立刻得到Fp(x)≥Fq(x)，這就完成了單調(diào)性的證明。

向量值函數(shù)ψ(x)的L∞范數(shù)‖ψ(x)‖∞=limp→∞‖ψ(x)‖p=maxi ψi(x)，從而有l(wèi)imp→∞Fp(x)=limp→∞ ln‖ψ(x)‖p=ln[max1≤i≤mψi(x)]=max1≤i≤mln[ψi(x)]=max1≤i≤m{|fi(x)|}=f(x)。

注:該命題說明凝聚函數(shù)Fp(x)隨著p的增大從上方逼近f(x)=max1≤i≤m{|fi(x)|}。

因此在實際計算時，可將p取得足夠大，然后用可微函數(shù)Fp(x)代替不可微函數(shù)f(x)，從而將不可微優(yōu)化問題minx∈Rn f(x)的求解變換成一個易于求解的可微優(yōu)化問題minx∈RnFp(x)。利用上述凝聚函數(shù)的性質(zhì)，非線性方程組問題就可以轉(zhuǎn)換為無約束優(yōu)化問題minx∈RnFp(x)，下面考慮用差分進化算法(DE)求解該無約束優(yōu)化問題。

2 差分進化算法

DE算法同其他進化算法一樣，也是對候選解的種群進行操作，DE算法的自參考種群繁殖方案與其他進化算法不同，它通過把種群中兩個成員之間的加權(quán)差向量加到第三個成員上來產(chǎn)生新參數(shù)向量，該操作稱為變異;然后將變異向量的參數(shù)與另外預先確定的目標向量參數(shù)按一定規(guī)則混合來產(chǎn)生實驗向量，該操作稱為交叉。若實驗向量的代價函數(shù)比目標向量的代價函數(shù)低，實驗向量就在下一代中代替目標向量。最后的操作稱為選擇，種群中所有成員必須被作為目標向量這樣操作一次，以便在下一代中出現(xiàn)相同競爭者。在進化過程中對每一代都評價最佳參數(shù)向量，以記錄最小化過程，這樣利用隨機偏差擾動產(chǎn)生新個體的方式可以獲得一個有非常好的收斂性結(jié)果。

差分進化算法整體結(jié)構(gòu)類似于遺傳算法，與遺傳算法的主要區(qū)別體現(xiàn)在以下四個方面:a)遺傳算法可以采用實值編碼和二進制編碼，而差異演化算法只采用實值編碼方式;b)遺傳算法的交叉操作會產(chǎn)生新個體，而差異演化算法的交叉操作則不會產(chǎn)生新個體，其作用主要是增加群體的多樣性;c)差異演化算法的變異操作是把兩個個體向量的差異化信息加到第三個個體向量上，這是不同于遺傳算法的最大區(qū)別;d)差異演化算法的選擇操作直接將目標函數(shù)值作為適應度值，然后比較適應度值，適應度值小的個體保存到下一代(目標函數(shù)值為最小值)，而不像遺傳算法有各種復雜的選擇策略。與遺傳算法相比，差異演化算法操作簡單、控制參數(shù)少、易編程實現(xiàn)，它尤其擅長求解多變量、非凸、多峰以及非線性的函數(shù)優(yōu)化問題，所以很受研究者的青睞。

2.1 標準差分進化算法

DE是一種基于群體進化算法，具有記憶個體最優(yōu)解和種群內(nèi)信息共享的特點，即通過種群內(nèi)個體間的合作與競爭來實現(xiàn)對優(yōu)化問題的求解，其本質(zhì)是一種基于實數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法[6]。算法首先在問題的可行解空間隨機初始化種群X0=[x01，x02，…，x0NP]， NP為種群規(guī)模;個體x0i=[x0i，1，x0i，2，…，x0i，D]用于表征問題解，D為優(yōu)化問題的維數(shù)。算法的基本思想是:對當前種群進行變異和交叉操作，產(chǎn)生另一個新種群;然后利用基于貪婪思想的選擇操作對這兩個種群進行一對一的選擇，從而產(chǎn)生最終的新一代種群。具體而言，首先通過式(1)對每一個在t時刻的個體xti實施變異操作，得到與其相對應的變異個體vt+1i，即

vt+1i=xtr1+K(xtr2-xtr3)(1)

其中:r1，r2，r3∈{1，2，…，NP}互不相同且與i不同;xtr1為父代基向量;(xtr2-xtr3)稱做父代差分向量;K為縮放比例因子。然后利用式(2)對xti和由式(1)生成的變異個體vt+1i實施交叉操作，生成實驗個體，即

ut+1i，j=vt+1i，j if(rand(j)≤CR) or j=rnbr(i)xti，j else(2)

其中:rand(j)為[0，1]的均勻分布隨機數(shù);CR為范圍在[0，1]的交叉概率;rnbr(i)為{1，2，…，D}間的隨機量。利用式(3)對實驗個體ut+1i和xti的目標函數(shù)進行比較，對于最小化問題，則選擇目標函數(shù)值低的個體作為新種群的個體xt+1i，即

xt+1i=ut+1iif f(ut+1i)

xtielse(3)

其中:f為目標函數(shù)。上述過程是標準版本的DE，表示為DE/rand/1/bin。文獻[5]中提供了其余有關(guān)DE的變種。DE算法的搜索性能取決于算法全局探索和局部開發(fā)能力的平衡，而這在很大程度上依賴于算法的控制參數(shù)的選取，包括種群規(guī)模、縮放比例因子和交叉概率等。相對其他進化算法而言，DE所需調(diào)節(jié)的參數(shù)較少，合理的參數(shù)選擇指導參見文獻[5，8]。歸納起來，DE算法具有如下優(yōu)點:

a)算法通用，不依賴于問題信息;

b)算法原理簡單，容易實現(xiàn);

c)群體搜索，具有記憶個體最優(yōu)解的能力;

d)協(xié)同搜索，具有利用個體局部信息和群體全局信息指導算法進一步搜索的能力;

e)易于與其他算法混合，構(gòu)造出具有更優(yōu)性能的算法。

2.2 差分進化算法流程

a)確定DE算法控制參數(shù)和所采用的具體策略。DE算法控制參數(shù)包括種群數(shù)量、變異算子、交叉算子、最大進化代數(shù)、終止條件等。

b)隨機產(chǎn)生初始種群，進化代數(shù)k=l。

c)對初始種群進行評價，即計算初始種群中每個個體的目標函數(shù)值。

d)判斷是否達到終止條件或進化代數(shù)達到最大。若是，則進化終止，將此時的最佳個體作為解輸出;若否則繼續(xù)。

e)進行變異和交叉操作，對邊界條件進行處理得到臨時種群。

f)對臨時種群進行評價，計算臨時種群中每個個體的目標函數(shù)值。

g)進行選擇操作，得到新種群。

h)進化代數(shù)k=k+1，轉(zhuǎn)d)。

3 極大熵差分進化混合算法求解非線性方程組

對給定的非線性方程組，構(gòu)造相應的適應度函數(shù)minx∈RnFp(x)，應用DE算法來求解該無約束優(yōu)化問題。

求解整數(shù)非線性方程組問題的差分進化算法步驟如下:

a)由給定的非線性方程組問題，構(gòu)造相應的適應度函數(shù)minx∈RnFp(x)，k=0，給定一個精度ε;

b)給定p是一個充分大的常數(shù);

c)用差分進化算法求解minx∈RnFp(x)，得到xk;

d)若滿足要求，則停止，得到近似最優(yōu)解x*=xk;否則修正p的值，并令k=k+1，返回c)。

4 數(shù)值實驗

為了測試本文算法的求解性能，下面取文獻[11，12]中的問題作測試并進行比較。

算例1[11]f1(x)=(x1-5x2)2=0f2(x)=(x2-2x3)2=0f3(x)=(3x1+x3)2=0

其中:-1≤x1，x2，x3≤1。

算例2[12] f1(x1，x2)=x21-x2-1=0

f2(x1，x2)=x1-cos(0.5πx2)=0

其中:x∈[-2，2]，精確解為x*=(-1/2，1.5)T，x*=(0.1)T。

采用上述方法進行求解，取參數(shù)p=1×106。 差分進化算法的參數(shù)選取如下:群體規(guī)模NP=60，初始交叉CR=0.3，初始縮放因子K=0.1，算法終止的最大進化代數(shù)為500。用MATLAB 6.5編程，算法運行50次，取平均值， 其結(jié)果如表1 所示。

表1 極大熵差分進化算法解非線性方程組的數(shù)值結(jié)果

算例搜到解次數(shù)成功率計算得到的x(取平均值)

1501(-0.000004; -0.000002; -0.000001)

2501(-0.707736; 1.500679) 搜到26次(0.000117; 0.999835)搜到24次

從表1的計算結(jié)果可以看出，利用本文提出的極大熵差分進化算法進行計算，在計算的成功率和準確性方面明顯優(yōu)于文獻[3]和[11]中的算法。已有文獻中只得到了該問題的一個解，主要是因為確定性算法是用給定初始點進行搜索的，無法同時搜到原問題的所有可能解，而本文算法中的初始點是隨機的，通過50次搜索就有可能獲得原問題盡可能多的最優(yōu)解。

5 結(jié)束語

本文通過把非線性方程組問題都轉(zhuǎn)換成不可微問題，結(jié)合極大熵函數(shù)法，給出了此類問題的一種新的有效算法——極大熵差分進化混合算法。利用本文提出的算法進行計算，在計算的成功率和準確性方面明顯優(yōu)于已有文獻中的算法，并且當參數(shù)p適當大時，可以得到與理論值一致的結(jié)果。可見，利用極大熵差分進化算法求解非線性方程組，可使算法簡單直觀，容易計算，且計算的準確性、成功率高。

參考文獻:

[1]田巧玉，古鐘璧，周新志.基于混合遺傳算法求解非線性方程組[J]. 計算機技術(shù)與發(fā)展，2007，17(3):10-12.

[2]許小勇，張海芳，鐘太勇.求解非線性方程及方程組的模擬退火算法[J]. 航空計算技術(shù)，2007，37(1):44-46.

[3]程錦榮，丁振鋒，汪志，等.求解線性和非線性方程組的一種通用算法[J]. 安徽大學學報，2008，32(2):48-51.

[4]KENNEDY J， EBERHART R. Particle swarm optimization[C]// Proc of IEEE International Conference on Neural Networks.Piscata-way:IEEE Press，1995:1942-1948.

[5]STORN R， PRICE K. Differential evolution:a simple and efficient adaptive scheme for global optimization over continuous spaces [R]. Berkeley: University of California， 2006.

[6]LAMPINEN J. A bibliography of differential evolution algorithm[EB/OL]. (2002-10-14). http://www.lut.fi/~jlampine/debiblio.htm.

[7]LIN Y C， HWANG K S， WANG Feng-sheng， et al. Co-evolutionary hybrid differential evolution for mixed-integer optimization problems[J]. Engineering Optimization，2001，33(6):663-682.

[8]吳亮紅，王耀南，陳正龍.求解混合整數(shù)非線性規(guī)劃問題的改進差分進化算法[J].小型微型計算機系統(tǒng)，2007，28(4):666-669.

[9]李興斯.解非線性規(guī)劃的凝聚函數(shù)法[J]. 中國科學(A輯)，1991，34(12):1283-1288.

[10]李興斯. 解非線性規(guī)劃問題的一個可微“準”精確懲罰函數(shù)方法[J].科學通報，1991，36(19):1451-1453.

[11]張建科，王曉智，劉三陽.求解非線性方程及方程組的微粒群算法[J]. 計算機工程與應用，2006，42(7):56-58.

[12]施妙根，顧麗珍.科學和工程計算基礎(chǔ)[M].北京: 清華大學出版社，1999.