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

何俊紅，趙天緒

(寶雞文理學(xué)院 數(shù)學(xué)系,陜西 寶雞 721013)

?

·數(shù)理科學(xué)·

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

何俊紅，趙天緒

(寶雞文理學(xué)院 數(shù)學(xué)系,陜西 寶雞 721013)

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

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

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

1 相關(guān)概念及模型轉(zhuǎn)化

考慮下列的非線性方程組

(1)

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

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

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

若設(shè)‖·‖α表示向量值空間上的α-范數(shù),當(dāng)α→∞時(shí),非線性方程組(1)可轉(zhuǎn)化為下列的極大極小優(yōu)化問題

(2)

證 明 因?yàn)?/p>

2 算法設(shè)計(jì)

2.1 子空間高斯變異算子

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

Δx～N(0,δ2),

ε為給定正常數(shù),fmin為到目前為止種群找到的最優(yōu)值。

2.2 保優(yōu)策略

最好的個(gè)體不一定出現(xiàn)在最后一代,所以在進(jìn)化開始時(shí)把最好的個(gè)體保留下來,如果在新種群中又發(fā)現(xiàn)更好的個(gè)體,則用它代替前面保留的個(gè)體。

2.3 擬牛頓法[10]

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

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

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

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

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

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

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

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

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

步驟2 對(duì)[L,U]中的個(gè)體以概率pc進(jìn)行算術(shù)雜交產(chǎn)生雜交后代種群popc(t)。

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

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

步驟6 當(dāng)終止條件滿足時(shí),輸出方程組的最優(yōu)解或滿足精度要求的次優(yōu)解,否則,令t=t+1,轉(zhuǎn)步驟2。

4 數(shù)值模擬

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

其中,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。

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

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

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

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

表1 文獻(xiàn)[11]、文獻(xiàn)[3]算法與NGEA對(duì)G1求得結(jié)果Tab.1 The results for the algorithms of reference [3],[11]and NGEA on G1

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

5 結(jié) 語

在計(jì)算機(jī)工程、最優(yōu)設(shè)計(jì)等領(lǐng)域的許多問題可歸結(jié)為求解非線性方程組。因此,如何高效求解非線性方程組是目前智能計(jì)算領(lǐng)域一個(gè)研究熱點(diǎn)問題。本文提出了一種解非線性方程組的擬牛頓混合遺傳算法,該方法利用熵函數(shù)法將問題轉(zhuǎn)化成了一個(gè)極小值化問題,并對(duì)轉(zhuǎn)化后的優(yōu)化問題設(shè)計(jì)了求解的方法。最后的計(jì)算機(jī)仿真表明,所給方法對(duì)非線性方程組的求解非常有效。

[1] 付振岳,王順芳,丁海燕.并發(fā)遺傳煺火算法求解復(fù)雜非線性方程[J].云南大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 封全喜,劉三陽,唐國強(qiáng),等.求解方程組的正交差分進(jìn)化算法[J].計(jì)算機(jī)科學(xué), 2012,39(5):187-189.

[6] 許小勇,張海芳,鐘太勇.求解非線性方程及方程組的模擬退火算法[J]. 航空計(jì)算技術(shù), 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].計(jì)算機(jī)工程與應(yīng)用, 2012, 48(22)：45-47.

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

[10] 馬昌風(fēng). 最優(yōu)化方法及其Matlab程序設(shè)計(jì)[M]. 北京：科學(xué)出版社,2010.

[11] 張安玲,劉雪英.求解非線性方程組的擬牛頓-粒子群混合算法[J].計(jì)算機(jī)工程與應(yīng)用, 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

國家自然科學(xué)基金資助項(xiàng)目(11371291)；陜西省教育廳科研計(jì)劃基金資助項(xiàng)目(11JK0506)；寶雞文理學(xué)院校級(jí)重點(diǎn)科研計(jì)劃基金資助項(xiàng)目(ZK12044)

何俊紅， 女，陜西寶雞人，從事最優(yōu)化、智能計(jì)算與系統(tǒng)模擬研究。

趙天緒，男，陜西寶雞人，寶雞文理學(xué)院教授，博士，從事最優(yōu)化理論研究。

O224; TP301.6

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