非線性方程組問題的粒子群-鄰近點(diǎn)混合算法

張琳

陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中 723001

非線性方程組問題的粒子群-鄰近點(diǎn)混合算法

張琳

陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中 723001

非線性方程組的求解問題是經(jīng)典數(shù)值分析中的一類基本問題。由于傳統(tǒng)算法涉及到函數(shù)的導(dǎo)數(shù)信息以及矩陣的求逆運(yùn)算，使得這些算法在實(shí)際應(yīng)用中有一定的局限性。

近年來，國內(nèi)外學(xué)者利用智能算法求解非線性方程組取得了良好的效果。智能算法有不需要初始點(diǎn)以及函數(shù)導(dǎo)數(shù)信息等優(yōu)點(diǎn)，因此得到很快的發(fā)展。張建科[1]用粒子群算法求解非線性方程與非線性方程組問題取得了良好效果；張安玲和劉雪英[2]給出了一種擬牛頓-粒子群混合算法；陳海霞[3]和趙曉穎等[4]把該問題轉(zhuǎn)化為光滑優(yōu)化問題，然后分別差分進(jìn)化和粒子群算法求解取得了良好效果。另外，像蜂群[5]、魚群等算法[6-9]也被用來求解非線性方程組問題。但這些算法大多都是依概率收斂的，并且往往需要較高的進(jìn)化代數(shù)，例如文獻(xiàn)[1，3，10]中最大進(jìn)化代數(shù)為1 000代。如何有效降低算法的進(jìn)化代數(shù)以提高計(jì)算速度，并且保證全局收斂或者以較高的概率收斂是一個(gè)很有意義的研究課題。

最近，周暢和張建科[11]利用粒子群和鄰近點(diǎn)混合算法求解極小極大問題，該混合算法不但有效降低了總體進(jìn)化代數(shù)，而且保證了較好的收斂性。

本文針對(duì)非線性方程組問題，在文獻(xiàn)[11]的研究基礎(chǔ)上進(jìn)一步發(fā)展，把粒子群算法作為內(nèi)層算法，外層算法采用距離函數(shù)構(gòu)造鄰近點(diǎn)算法。數(shù)值結(jié)果表明，該算法有效降低了進(jìn)化算法的進(jìn)化代數(shù)，收斂快、數(shù)值穩(wěn)定性較好，是求解非線性方程組問題的一種有效算法。

1 非線性方程組問題

考慮如下非線性方程組：

的最優(yōu)解，其中ai≤xi≤bi，cj(j=1,2,…,p)為加權(quán)系數(shù)。

單純使用智能算法可以求解一些簡單的非線性方程組問題，但往往所需進(jìn)化代數(shù)較高，由于智能算法是依概率收斂的隨機(jī)性算法，對(duì)一些較為復(fù)雜的此類問題，智能算法的收斂速度和收斂率都不太理想。

本文將把鄰近點(diǎn)算法和粒子群算法相混合，發(fā)揮各自的優(yōu)勢，給出一種快速有效的新算法。

2 基本PSO算法

粒子群算法源于對(duì)鳥群覓食行為的研究。假設(shè)在N維的搜索空間中，有m個(gè)個(gè)體粒子組成一個(gè)種群，其中第k個(gè)個(gè)體粒子可以表示為一個(gè)N維的向量，xk=(xk1,xk2,…,xkN),i=1,2,…,m，每個(gè)個(gè)體粒子的飛行位置就是搜索空間中的一個(gè)坐標(biāo)點(diǎn)，因而也是一個(gè)潛在的解。將xk代入需要求解的目標(biāo)函數(shù)就可以算出其適應(yīng)值，根據(jù)適應(yīng)值的大小以及需要優(yōu)化的目的（如：最大化問題還是最小化問題）可以衡量解的好壞。第k個(gè)個(gè)體粒子的飛行速度是N維向量V= (Vk1,Vk2,…,VkN)。如用Pkn=(Pk1,Pk2,…,PkN)表示第k個(gè)個(gè)體粒子迄今為止找到的最優(yōu)位置，用Pgn=(Pg1,Pg2,…,PgN)來表示整個(gè)群體迄今為止找到的最優(yōu)位置。

早期利用下列公式[12]對(duì)粒子個(gè)體進(jìn)行操作：

其中，k=[1,m],n=[1,N]；參數(shù)c1和c2通常稱為學(xué)習(xí)因子，都是非負(fù)常數(shù)；r1和r2為相互獨(dú)立的偽隨機(jī)數(shù)，都服從[0，1]上的均勻分布。vkn∈[-vmax,vmax],vmax為提前設(shè)定的常數(shù)。

從式（4）、式（5）可見，c1為調(diào)節(jié)粒子飛向自身最好位置方向的步長，c2為調(diào)節(jié)粒子飛向群體的全局最好位置方向的步長。為了使粒子不會(huì)離開搜索空間，通常把vkn限定在一個(gè)范圍中，即vkn∈[-vmax,vmax],vmax為最大速度，如果搜索空間在[-xmax,xmax]中，則可以設(shè)定vmax=kxmax,0.1≤k≤1.0，如果超出搜索范圍，則彈回搜索空間。

Shi和Eberhart又對(duì)式（4）作了重要改進(jìn)[13]：

在式（6）中ω＞0為慣性權(quán)重，控制前一速度對(duì)當(dāng)前速度的影響，當(dāng)ω較大時(shí)，前一速度影響較大，算法的全局搜索能力較強(qiáng)；當(dāng)ω較小時(shí)，前一速度影響較小，算法的局部搜索能力較強(qiáng)。算法通過自適應(yīng)調(diào)整ω大小來跳出局部最優(yōu)解。算法的終止條件根據(jù)具體問題取最大迭代代數(shù)或種群搜到的最優(yōu)位置滿足的預(yù)定最小閾值。

3 鄰近點(diǎn)算法

PPA（Proximal Point Algorithm）算法是由Martinet[14]在1970年提出的一種求解凸優(yōu)化問題的全局收斂算法，后來Rockafellar等人[15]對(duì)該算法作了進(jìn)一步的研究和發(fā)展。

對(duì)以下凸優(yōu)化問題：

這里f:Rn+m→(-∞,+∞]是一個(gè)閉正則凸函數(shù)。約束凸優(yōu)化問題包含于式（7）中，因?yàn)榭梢岳檬拘院瘮?shù)δC(?)把約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化問題。轉(zhuǎn)化方法如下：

如果f0(x,y):Rn+m→R為有約束優(yōu)化問題的目標(biāo)函數(shù)，該問題的可行域C={(x,y)|gi(x,y)≤0,i-1,…,p}為Rn+m中的閉凸集，每個(gè)約束函數(shù)gi(x,y)是可行域上的閉凸函數(shù)，則

因此，式（8）可化為式（7）。

采用PPA求解式（7），其迭代點(diǎn)列{(xk,yk)}計(jì)算如下：

其中D(·,·)是一個(gè)類似距離函數(shù)，早期的鄰近點(diǎn)算法采用經(jīng)典的歐幾里德距離函數(shù)來，很多滿足凸性的類似距離函數(shù)被提出來，例如：Bregman函數(shù)、類似熵函數(shù)等等。

PPA算法是一個(gè)經(jīng)典確定性算法，如果優(yōu)化問題是凸優(yōu)化問題，則由該算法產(chǎn)生的點(diǎn)列{(xk,yk)}收斂于全局最優(yōu)點(diǎn)，該結(jié)論在很多經(jīng)典文獻(xiàn)中都已證明過，可參見文獻(xiàn)[14-16]等文獻(xiàn)。

4 粒子群-鄰近點(diǎn)混合算法

以下結(jié)合鄰近點(diǎn)算法給出一種非線性方程組問題的改進(jìn)粒子群算法。

4.1 PSO-PPA算法步驟

步驟1調(diào)用PSO算法計(jì)算非線性方程組問題得到初始迭代點(diǎn)x0。

步驟2給定正數(shù)λk＞0，置k：=2。

步驟3調(diào)用PSO算法求解鄰近點(diǎn)迭代問題，得到xk+1。

步驟4檢驗(yàn)是否達(dá)到精度要求，若是，算法停止；否則，k：=k+1，轉(zhuǎn)步驟3。

4.2 內(nèi)層PSO算法

步驟1初始化一個(gè)規(guī)模為N的粒子群，隨機(jī)產(chǎn)生每一個(gè)粒子的初始位置和速度。

步驟2計(jì)算每個(gè)粒子的適應(yīng)值，對(duì)問題式（1），其適應(yīng)值函數(shù)為：，此處的距離函數(shù)也可以使用Bregman函數(shù)、類似熵函數(shù)等其他距離函數(shù)。

步驟3對(duì)每個(gè)粒子將其適應(yīng)值和其經(jīng)歷過的最好位置Pij的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的最好位置。

步驟4對(duì)每個(gè)粒子將其適應(yīng)值和全局經(jīng)歷過的最好位置Pgj的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的全局最好位置。

表1 計(jì)算結(jié)果比較

步驟5根據(jù)式（6），式（5）分別對(duì)粒子的速度和位置進(jìn)行更新。

步驟6如果滿足終止條件，則輸出解；否則返回步驟2。

4.3 必要的說明

（1）如果式（1）中的各個(gè)分量gi(x),i=1,2,…,p都是凸函數(shù)，則轉(zhuǎn)化后的優(yōu)化問題式（3）也是一個(gè)無約束凸優(yōu)化問題。因此，用鄰近點(diǎn)算法為外層算法可以保證迭代點(diǎn)列收斂到全局最優(yōu)解。

（2）對(duì)于比較復(fù)雜的非線性方程組問題，如果式（1）中的某個(gè)分量gi(x),i=1,2,…,p不是凸函數(shù)，則問題式（3）也是一個(gè)非凸優(yōu)化問題。盡管如此，本文中算法也可以求解，但此時(shí)的收斂性理論分析以及計(jì)算精度有待進(jìn)一步更深入研究。

5 數(shù)值結(jié)果

為驗(yàn)證本文算法的性能，取相關(guān)文獻(xiàn)中三個(gè)非線性方程組問題做測試，并和文獻(xiàn)中結(jié)果比較。

在此選取學(xué)習(xí)因子c1=c2=2,ω從1.0減小到0.4，群體規(guī)模數(shù)為20，內(nèi)循環(huán)最大進(jìn)化代數(shù)為100，λk=0.5，粒子的搜索范圍根據(jù)具體問題定。在硬件環(huán)境：CPU：Pentium4 2.93 GHz、內(nèi)存：512 MB等和軟件環(huán)境WindowsXP系統(tǒng)下用VC++6.0編程運(yùn)行。外循環(huán)迭代次數(shù)為5次，內(nèi)循環(huán)算法運(yùn)行PSO 20次，每次從中選取適應(yīng)值最差的粒子的位置作為下一次迭代的初始點(diǎn)。由于例2中fi(x)(i=1,2,3)都是非負(fù)的，因此直接最小化∑ifi(x)。計(jì)算結(jié)果見表1。

數(shù)據(jù)分析：本文列出了外層迭代5次，內(nèi)循環(huán)PSO的最大進(jìn)化代數(shù)100代，搜到的最差解和其他文獻(xiàn)中結(jié)果比較如表1所示。由于最大進(jìn)化代數(shù)和搜索成功率密切相關(guān)，因此在表1中列出了最大進(jìn)化代數(shù)，而沒有列出平均進(jìn)化代數(shù)。由表1可以看出，PSO-PPA算法對(duì)例1和例2需要較少的迭代步就可以達(dá)到10-9的精度，而且可保證對(duì)凸問題的100%全局收斂性。這是單純依靠概率收斂的進(jìn)化算法所達(dá)不到的。對(duì)例3的計(jì)算精度沒有HPSO高，但本文算法具有確定的收斂特性。可見，本文算法綜合了PPA和PSO的各自優(yōu)勢，即不需要初始點(diǎn)和函數(shù)可微性要求，對(duì)凸問題具有全局收斂性，是一種較好的混合算法。

但是，由于目前只證明了PPA算法對(duì)擬凸問題[16]具有全局收斂性。因此，混合算法對(duì)非擬凸問題，沒有全局收斂性理論結(jié)果，計(jì)算效果也不一定好。關(guān)于這一點(diǎn)，還需深入研究。

6 結(jié)論

本文針對(duì)非線性方程組問題，利用粒子群算法結(jié)合鄰近點(diǎn)算法給出了此類問題的一種新的混合有效算法，該算法無需使用導(dǎo)數(shù)信息。并能快速搜到問題的解。

該算法不但給非線性方程組問題提供了一種新方法，而且拓廣了粒子群算法的應(yīng)用范圍。數(shù)值結(jié)果表明，該算法收斂快、數(shù)值穩(wěn)定性好，是求解非線性方程組問題的一種有效算法。

[1]張建科，王曉智，劉三陽，等.求解非線性方程及方程組的粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（7）：56-58.

[2]張安玲，劉雪英.求解非線性方程組的擬牛頓-粒子群混合算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（33）：41-42.

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

[4]趙曉穎，劉國志，姜鳳利.求解一類不可微優(yōu)化問題極大熵微粒群混合算法[J].江西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，31（2）：193-196.

[5]張姣玲.求解非線性方程及方程組的人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（22）：45-47.

[6]劉大平，何平.區(qū)間-粒子群算法求解非線性方程組[J].內(nèi)江師范學(xué)院學(xué)報(bào)，2010（12）：21-23.

[7]陳海霞，楊鐵貴.基于凝聚函數(shù)法的非線性方程組求解[J].科學(xué)技術(shù)與工程，2010（6）：1494-1496.

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

[9]莫愿斌，陳德釗，胡上序.求解非線性方程組的混沌粒子群算法及應(yīng)用[J].計(jì)算力學(xué)學(xué)報(bào)，2007，24（4）：505-508.

[10]歐陽艾嘉，劉利斌，樂光學(xué)，等.求解非線性方程組的混合粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（9）：33-36.

[11]周暢，張建科.一類非線性極小極大問題的粒子群-鄰近點(diǎn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（36）：19-22.

[12]Kennedy J，Eberhart R.Particle Swarm Optimization[C]//Proc IEEE Int Conf Neural Networks.Piscataway：IEEE Press，1995：1942-1948.

[13]Shi Y，Eberhart R.A modified Particle Swarm Optimizer[C]// Proceedings of the IEEE International Conference on Evolutionary Computation.Piscataway，NJ：IEEE Press，1998：69-73.

[14]Martinet B.Regularisation d’inequations variationnelles par approximations successives[J].RIRO，1970，4：154-159.

[15]Rockafellar R T.Monotone operators and the proximal point algorithm[J].SIAMJournal on Control and Optimization，1976，14：877-898.

[16]Langenberg N，Tichatschke R.Interior proximal methods for quasiconvex optimization[J].Journal of Global Optimization，2012，52（3）：641-661.

ZHANG Lin

School of Mathematics and Computer Science,Shaanxi University of Technology,Hanzhong,Shaanxi 723001,China

The problems of nonlinear equations are a class of classical numerical calculation problems,and the simple evolutionary algorithm requires not only a high degree of evolution algebra,but also can not 100%guarantee to converge to the global optimal solution.To solve this problem,Particle Swarm Optimization and Proximal Point Algorithm are mixed,and the Proximal Point Algorithm is used as the outer layer algorithm,and the Particle Swarm Optimization is used as the inner layer algorithm to solve the problems of nonlinear equations.The algorithm has better effects of computation for convex problems,which is an effective algorithm of solving nonlinear equations.

Particle Swarm Optimization（PSO）;Proximal Point Algorithm（PPA）;systems of nonlinear equations

非線性方程組問題是一類經(jīng)典的數(shù)值計(jì)算問題，單純的進(jìn)化算法不但需要很高的進(jìn)化代數(shù)，而且也不能保證100%收斂到全局最優(yōu)解。為求解此問題，把粒子群算法和鄰近點(diǎn)算法相混合，利用鄰近點(diǎn)算法作為外層算法，粒子群算法作為內(nèi)層算法進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明該算法對(duì)凸問題有較好的計(jì)算效果，是求解非線性方程組問題的一種有效算法。

粒子群算法；鄰近點(diǎn)算法；非線性方程組問題

A

TP18

10.3778/j.issn.1002-8331.1306-0355

ZHANG Lin.Particle Swarm Optimization-Proximal Point Algorithm for systems of nonlinear equations.Computer Engineering and Applications,2013,49（24）：38-40.

陜西理工學(xué)院科研基金資助項(xiàng)目（No.SLGJX1025）。

張琳（1964—），男，副高，主要研究方向：應(yīng)用數(shù)學(xué)。

2013-07-01

2013-08-22

1002-8331（2013）24-0038-03

CNKI出版日期：2013-10-17http://www.cnki.net/kcms/detail/11.2127.TP.20131017.1529.013.html