解非線性方程組的擬牛頓混合遺傳算法

何俊紅，趙天緒

(寶雞文理學院 數學系,陜西 寶雞 721013)

?

·數理科學·

解非線性方程組的擬牛頓混合遺傳算法

何俊紅，趙天緒

(寶雞文理學院 數學系,陜西 寶雞 721013)

利用熵函數將非線性方程組轉化為一個極小值優化問題。結合擬牛頓法和遺傳算法的優缺點,提出了一種求解非線性方程組的擬牛頓混合遺傳優化算法。該方法不僅有效發揮了遺傳算法在進化初期的群搜索能力,而且利用了擬牛頓法的局部精搜索性能,克服了遺傳算法在后期易陷入局部收斂的缺陷,提高了算法整體尋優效率。計算機仿真表明，該算法對非線性方程組的求解具有較好的穩定性和較高的收斂精度。

非線性方程組;擬牛頓法;遺傳算法;熵函數

對計算機工程、網絡優化、航空航天交通流管理等領域的許多優化問題的解決可歸結為求解復雜非線性方程組。非線性方程組的解法長期以來是數值計算領域一個重要的研究內容，已經引起眾多學者的研究興趣,且在求解的理論和方法上已經得到了許多有效求解方法[1-4]。從現有的文獻可知,這些方法大體可分為兩類,一是純粹的經典優化算法,例如牛頓法、Newton流線法、區間牛頓法等；二是現代發展起來的一些智能進化計算法。對于經典優化算法而言，最典型的方法是牛頓法。牛頓法是一種線性逐步迭代計算方法，突出優點在于收斂速度較快，但有個明顯缺點,即每次迭代需知道函數導數值及迭代初始值的信息,而且初值選取的是否恰當會直接影響算法的收斂。近年來,由許多學者提出的求解非線性方程組的智能優化算法,有效避免了傳統優化算法在求解非線性方程組需求解目標函數的導數等解析性質,進而直接設計適應度函數進行群搜索。如文獻[5]利用差分思想設計了求解方程組的有效解法;文獻[6]利用模擬退火算法對非線性方程組進行了求解;文獻[7]結合遺傳進化設計了求解非線性方程組的有效方法；文獻[8]提出了一種求解非線性方程組的人工蜂群算法,這些方法在求解非線性方程組上取得了較好的效果。然而，智能進化計算法在進化初期具有較強的全局搜索能力,但在后期容易陷入局部最優,導致算法終止或只找到問題的局部最優解。針對這些缺陷,本文將非線性方程組轉化為一個極小值問題的極限形式,然后充分利用擬牛頓法的局部精搜索能力和遺傳算法的全局搜索性能,設計了求解非線性方程組的一種擬牛頓混合遺傳算法。最后通過3個經典實例對算法的性能進行了比較測試。結果表明，所給出算法對非線性方程組的求解是有效的。

1 相關概念及模型轉化

考慮下列的非線性方程組

(1)

這里x=(x1,x2,…，xn)T是n維實向量,x∈[L,U],fi(x)(i=1,2,…,n)是n個實非線性函數,且

[L,U]={x=(x1,x2,…，xn)T|li≤xi≤ui,i=1,2,…,n}

是問題解的搜索空間,li,ui分別是x的第i個分量xi的上下界。

若設‖·‖α表示向量值空間上的α-范數,當α→∞時,非線性方程組(1)可轉化為下列的極大極小優化問題

(2)

證 明 因為

2 算法設計

2.1 子空間高斯變異算子

在遺傳算法中,變異算子起著重要的角色,其能有效的增加種群的多樣性,促使種群向最優解逼近,設在第t代,設個體x0(t)被選擇參加變異,則變異的方法為

Δx～N(0,δ2),

ε為給定正常數,fmin為到目前為止種群找到的最優值。

2.2 保優策略

最好的個體不一定出現在最后一代,所以在進化開始時把最好的個體保留下來,如果在新種群中又發現更好的個體,則用它代替前面保留的個體。

2.3 擬牛頓法[10]

大家知道,Newton法[9]的突出優點是收斂速度快,可是,利用牛頓法需要計算目標函數的二階導數,且目標函數的Hessen矩陣可能非正定。而擬牛頓法正克服了Newton法需求目標函數的二階導數及Hessen矩陣求逆的缺點,其主要通過迭代中所得到解的梯度信息來構造近似矩陣列{Hk},從而用以近似牛頓法中的Hessen矩陣,然后沿方向dk=-Hkgk作一維搜索。其基本步驟為

步驟1 給出初始點x(1)∈[L,U]及允許誤差ε>0。

步驟2 計算‖gk‖=‖Ω(x(k),α)‖,若‖gk‖≤ε,停;否則,計算dk=-Hkgk。

步驟3 從x(k)出發,沿方向dk進行一維線性精搜索求出步長λk,使其滿足

且令x(k+1)=x(k)+λkdk。

步驟4 矯正Hk產生Hk+1,使得擬牛頓條件成立,令k=k+1,轉步驟2。

3 擬牛頓混合遺傳算法流程

對給定的非線性方程組,定義算法的適應度函數Ω(x,α),設定種群規模pop,雜交概率pc,變異概率pm,最優解的精度及遺傳算子中的參數值。

步驟1 隨機在搜索空間[L,U]產生初始種群pop(0),令t=0。

步驟2 對[L,U]中的個體以概率pc進行算術雜交產生雜交后代種群popc(t)。

步驟3 對popc(t)中的個體執行子空間高斯變異操作,變異后代與popc(t)中沒有參與變異個體共同組成新的變異后代種群popm(t)。

步驟4 對popm(t)中的每個個體執行擬牛頓精搜索,所得個體組成新搜索后代種群popn(t)。

步驟6 當終止條件滿足時,輸出方程組的最優解或滿足精度要求的次優解,否則,令t=t+1,轉步驟2。

4 數值模擬

為了有效驗證本文算法性能,記文中算法為NGEA,另從文獻選取3個具有代表性的非線性方程組,將其結果與本文算法所得結果進行數值比較,其比較結果如表1，2所示,其中G1,G3取自文獻[3]。G2選自文獻[11],3個非線性方程組具體形式為

其中,x=(x1,x2,x3),xi∈[-1.732,1.732](i=1～3),且理論解為x*=(1,1,1)T。

其中,x=(x1,x2),x1,x2∈[-2,2],且理論解x*=(0.290 9,0)T。

在計算仿真實驗中,群體規模pop=450,變異算子中隨機生成子空間個體數μ=200,雜交概率pc=0.80,變異概率pm=0.15,算法精度δ=10-12。對于上述每個方程,算法獨立運行30次,每次最大迭代次數為150,并將所求得解的平均值與文獻中的已有結果加以比較,其結果如表1，2所示。

從表1可以看出,算法NGEA所得方程G1的結果相比文獻[11]所得解的精度高,且每次運行中均能找到滿足精度要求的最優解,而且迭代的次數相比其他比較算法而言較少,即尋優成功率較高。相對于文獻[3],本文算法在找到問題的解的成功率與比較算法相同(其均為100%)。而所得解的3個分量的平均值均好于文獻中的結果,且每次運行中,本文算法最大迭代次數相比而言偏低。

表2的結果表明,文中算法NGEA對第2個測試函數G2所得結果比粒子群算法和文獻[3]中算法所得解的精度偏高,但每次搜索成功率相同(粒子群算法對G2的成功率沒有記錄)。對于第3個非線性方程G3,文中算法在所得最優解的各個分量上比粒子群算法及文獻[3]中的結果偏好。且獨立運行時,其每次迭代到最大次數不超過15次時算法基本終止,即這時已經找到問題的最優解或滿足精度要求的次優解,而粒子群算法和文獻[3]算法沒有給出詳細記錄,另外本文算法與比較的兩種算法對G2，G3均能在每次運行中找到滿足精度的最優解。

因此,從上述實驗仿真分析可以看出,本文所給算法對非線性方程組的求解具有良好的能力,其能利用較短的迭代次數獲得方程的最優解或滿足一定精度要求的次優解。

表1 文獻[11]、文獻[3]算法與NGEA對G1求得結果Tab.1 The results for the algorithms of reference [3],[11]and NGEA on G1

表2 粒子群算法、文獻[3]算法及文中算法NGEA對G2,G3求得結果Tab.2 The results for the algorithms of particle swarm, reference [3]and NGEA on G2,G3

5 結 語

在計算機工程、最優設計等領域的許多問題可歸結為求解非線性方程組。因此,如何高效求解非線性方程組是目前智能計算領域一個研究熱點問題。本文提出了一種解非線性方程組的擬牛頓混合遺傳算法,該方法利用熵函數法將問題轉化成了一個極小值化問題,并對轉化后的優化問題設計了求解的方法。最后的計算機仿真表明,所給方法對非線性方程組的求解非常有效。

[1] 付振岳,王順芳,丁海燕.并發遺傳煺火算法求解復雜非線性方程[J].云南大學學報(自然科學版),2012,34 (1):15-19.

[2] ABDOLLAHI M, LSAZADEH A, ABDOLLAHI D. Imperialist competitive algorithm for solving systems of nonlinear equations [J]. Computers and Mathematics with Applications, 2013,65：1894-1908.

[3] GROSAN C, ABRAHAM A. A new approach for solving nonlinear equations systems [J]. IEEE Transaction on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2008, 38(3), 698-714.

[4] DENIS J E. On Newton′s method and nonlinear simultaneous replacements [J]. SIAM J Numer Anal, 1967(4):103-108.

[5] 封全喜,劉三陽,唐國強,等.求解方程組的正交差分進化算法[J].計算機科學, 2012,39(5):187-189.

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

[7] KARRA C L, WECKB B L,FREEMAN M. Solutions to systems of nonlinear equations via a genetic algorithm[J].Engineering Applications of Artificial Intelligence, 1998，11：369-375.

[8] 張姣玲.求解非線性方程及方程組的人工蜂群算法[J].計算機工程與應用, 2012, 48(22)：45-47.

[9] 李興斯. 解非線性規劃的凝聚函數法[J]. 中國科學(A輯),1991,21(12): 1283-1288.

[10] 馬昌風. 最優化方法及其Matlab程序設計[M]. 北京：科學出版社,2010.

[11] 張安玲,劉雪英.求解非線性方程組的擬牛頓-粒子群混合算法[J].計算機工程與應用, 2008, 44(33)：41-43.

(編 輯亢小玉)

Quasi-Newton hybrid genetic algorithm for solving nonlinear system of equations

HE Jun-hong, ZHAO Tian-xu

(Department of Mathematics, Baoji University of Arts and Sciences, Baoji 721013， China)

First, the nonlinear system of equations was transformed into a minimum optimal problem by using an entropy function. And combining the Quasi-Newton method with the genetic algorithm, a Quasi-Newton hybrid genetic algorithm for solving the nonlinear system of equations is proposed. The proposed algorithm can not only utilize the swarm search ability of genetic algorithm in the initial evolution stage, but also take advantage of the local search property of the Quasi-Newton, and these have made the proposed algorithm overcome the local convergence of genetic algorithm in the later evolution stage and improved the overall search ability of the proposed algorithm. The computer simulations demonstrate the proposed algorithm has good stability and convergence precision in solving the nonlinear system of equations.

nonlinear system of equations; Quasi-Newton method; genetic algorithm; entropy function

2014-03-16

國家自然科學基金資助項目(11371291)；陜西省教育廳科研計劃基金資助項目(11JK0506)；寶雞文理學院校級重點科研計劃基金資助項目(ZK12044)

何俊紅， 女，陜西寶雞人，從事最優化、智能計算與系統模擬研究。

趙天緒，男，陜西寶雞人，寶雞文理學院教授，博士，從事最優化理論研究。

O224; TP301.6

：ADOI：10.16152/j.cnki.xdxbzr.2015-03-002