張琳

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

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

張琳

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

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

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

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

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

1 非線性方程組問題

考慮如下非線性方程組：

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

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

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

2 基本PSO算法

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

早期利用下列公式[12]對粒子個體進行操作：

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

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

Shi和Eberhart又對式（4）作了重要改進[13]：

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

3 鄰近點算法

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

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

這里f:Rn+m→(-∞,+∞]是一個閉正則凸函數(shù)。約束凸優(yōu)化問題包含于式（7）中，因為可以利用示性函數(shù)δC(?)把約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化問題。轉(zhuǎn)化方法如下：

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

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

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

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

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

4 粒子群-鄰近點混合算法

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

4.1 PSO-PPA算法步驟

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

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

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

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

4.2 內(nèi)層PSO算法

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

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

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

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

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

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

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

4.3 必要的說明

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

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

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

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

在此選取學習因子c1=c2=2,ω從1.0減小到0.4，群體規(guī)模數(shù)為20，內(nèi)循環(huá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編程運行。外循環(huán)迭代次數(shù)為5次，內(nèi)循環(huán)算法運行PSO 20次，每次從中選取適應(yīng)值最差的粒子的位置作為下一次迭代的初始點。由于例2中fi(x)(i=1,2,3)都是非負的，因此直接最小化∑ifi(x)。計算結(jié)果見表1。

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

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

6 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

[11]周暢，張建科.一類非線性極小極大問題的粒子群-鄰近點算法[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ù)值計算問題，單純的進化算法不但需要很高的進化代數(shù)，而且也不能保證100%收斂到全局最優(yōu)解。為求解此問題，把粒子群算法和鄰近點算法相混合，利用鄰近點算法作為外層算法，粒子群算法作為內(nèi)層算法進行求解。實驗結(jié)果表明該算法對凸問題有較好的計算效果，是求解非線性方程組問題的一種有效算法。

粒子群算法；鄰近點算法；非線性方程組問題

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.

陜西理工學院科研基金資助項目（No.SLGJX1025）。

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

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