夏綠玉

(銅陵職業(yè)技術(shù)學(xué)院，安徽 銅陵 244000)

?

超越方程的全局優(yōu)化解法

夏綠玉

(銅陵職業(yè)技術(shù)學(xué)院，安徽 銅陵 244000)

現(xiàn)有的粒子群算法在求解超越方程時具有局部搜索能力差、后期收斂速度較慢的缺陷，導(dǎo)致了粒子群算法無法得到較為精確的超越方程的根。在粒子群算法的基礎(chǔ)上，加入局部搜索能力較好、后期收斂速度較快的擬牛頓算法，依照算法的進(jìn)程自動甄選粒子群算法和擬牛頓算法，充分發(fā)揮粒子群算法的全局搜索性能和擬牛頓法的局部搜索性能，進(jìn)而將超越方程轉(zhuǎn)化為了純粹的函數(shù)優(yōu)化問題，并基于此方法進(jìn)行求解實驗，結(jié)果表明該方法具有極高的收斂速度和求解精度。

粒子群算法；全局優(yōu)化；擬牛頓法；超越方程

超越方程是數(shù)學(xué)、工程實踐中廣泛存在的棘手問題，但五次及以上方程并沒有根式解，只能使用數(shù)值解法進(jìn)行求解。傳統(tǒng)的數(shù)值方法種類繁雜：對分法、單形調(diào)優(yōu)法、復(fù)形調(diào)優(yōu)法、弦截法等[1-2]。但這些方法受方程本身特性的影響較為嚴(yán)重，不同的初值會得到不同結(jié)果，通用性較差、精度較低。需要科研人員根據(jù)以往的經(jīng)驗針對具體的問題選擇適用的方法，其主觀性較強(qiáng)，不適合工程實際中的大范圍推廣與應(yīng)用。

20世紀(jì)90年代，Kennedy等[3]提出了粒子群(Particle Swarm Optimization，簡稱PSO)算法，該算法在求解超越方程時可以很好地探尋超越方程的根。Particle Swarm Optimization的通用性較好、迭代格式較為簡單，對于連續(xù)性、非連續(xù)性問題具有很好的適用性，也是一種方便掌握的數(shù)學(xué)工具[4]，但是，Particle Swarm Optimization在后期收斂之時耗時較多，且收斂效果較差，不能夠很好地收斂至較小的范圍[5-6]。擬牛頓法(Quasi-Newton Methods)是一種迭代算法，是求解非線性優(yōu)化問題最有效的方法之一，于20世紀(jì)50年代由美國Argonne國家實驗室的物理學(xué)家W.C.Davidon提出。

本文糅合了Quasi-Newton Methods和Particle Swarm Optimization的優(yōu)點，提出全局優(yōu)化解法(Global Optimization Solution)，充分發(fā)揮粒子群算法的全局搜索性能和擬牛頓法的局部搜索性能，進(jìn)而將超越方程轉(zhuǎn)化為了純粹的函數(shù)優(yōu)化問題，并利用C++開發(fā)計算程序，與傳統(tǒng)的計算方法相比較，驗證Global Optimization Solution的全局搜索能力與局部搜索能力。

1　問題描述

有一超越方程

f(x)=0,

(1)

全部的實數(shù)根位于(a,b)中，可以將式(1)轉(zhuǎn)化為

g(x)=f(x)2，

(2)

式(2)在[a,b]區(qū)間內(nèi)的極小值點便是式(1)在(a,b)區(qū)間內(nèi)的根，當(dāng)g(x)的最小值為0時，所對應(yīng)的x就是式(1)的根。

2　全局優(yōu)化算法描述

擬牛頓法是一種收斂性很強(qiáng)的算法，具體做法如下：取X=(x0,y0,R)，假設(shè)(x0,y0,R)第i次迭代的值為

(3)

則第i+1次迭代的值為

X(i+1)=(x0,y0,R)(i)-(f0(X(i))+f1(X(i))+f2(X(i)))TF(X(i))-1。

(4)

其中

(5)

令δ(i)=F(X(i))-1(f0(X(i))+f1(X(i))+f2(X(i)))T，

(6)

δ(i)=(δ(i)(x0),δ(i)(y0),δ(i)(R))T，

則有

(7)

由此，我們給定一個精度和初值

(8)

一直迭代，當(dāng)

|max(f0(X(i))+f1(X(i))+f2(X(i)))T|<ε，

(9)

時便得結(jié)果

(10)

此后，將擬牛頓法嵌入粒子群算法中，具體做法如下：

1)初始化粒子群，假設(shè)粒子群的種群規(guī)模為N，定義隨機(jī)位置，取k=0；

2)對粒子群中的每一個粒子計算其適應(yīng)度的值pi；

3)將當(dāng)下計算的粒子適應(yīng)度的值pi與粒子歷史上適應(yīng)度最好的位置pbi進(jìn)行比較，如果pi比pbi更好，則將其作為當(dāng)前的最好位置；

4)將當(dāng)下計算的粒子適應(yīng)度的值pi與粒子全局適應(yīng)度最好的位置pgi進(jìn)行比較，如果pi比pgi更好，則將其作為全局的最好位置；

5)對粒子速度和位置進(jìn)行更新，更新方法如下：

(11)

其中，1≤i≤N并且1≤d≤D；

6)當(dāng)達(dá)到最大的代數(shù)M，找出當(dāng)前全局最優(yōu)個體pg，進(jìn)行下一步，如果未達(dá)到最大的代數(shù)M，令k=k+1，重新進(jìn)入步驟2)；

7)進(jìn)行式(3)和式(10)的計算；

8)輸出結(jié)果。

3　數(shù)值計算

利用上述思想，編制GlobalOptimizationSolution的C+ +程序GOS，利用GOS進(jìn)行計算。

3.1全局搜索

算例1：求解x44+x+1=0的根，見表1。

表1　x44+x+1=0的根

根據(jù)基礎(chǔ)的數(shù)學(xué)知識可知，x44+x+1=0共有44個根，通過表1可知，GlobalOptimizationSolution搜索出了44個根，說明GlobalOptimizationSolution的全局搜索能力較佳。

算例2：求解27-18x+2x2=cosx的根。

根據(jù)數(shù)學(xué)知識，27-18x+2x2=cosx有2個根(如圖1所示)，GlobalOptimizationSolution搜索出了2個根：x1=1.936 571 998 300 551 6;x2=7.158 983 280 758 961。

通過圖1可知，GlobalOptimizationSolution搜索出了2個根，說明GlobalOptimizationSolution的全局搜索能力較佳。

圖1　27-27-18x+2x2=cosx的圖像

3.2局部搜索

將GlobalOptimizationSolution搜索出的局部根同文獻(xiàn)[7]中FAC算法搜索出的局部根進(jìn)行比較。

算例3：求解(x-1)2sin2x+(x-1)3cos3x+5(x2-1)=0在區(qū)間[-5,5]內(nèi)的根。

通過表2可以看出，結(jié)果保留小數(shù)點后6位，GlobalOptimizationSolution搜索出的局部根與精確解相等，而FAC方法最大絕對誤差為0.000 120，最大相對誤差為0.000 120。GlobalOptimizationSolution比FAC方法要精確。

表2　本文方法和FAC法的對比

算例4：求解cos(x-1)-sin2x=0在區(qū)間[-3,3]內(nèi)的根。

通過表3可以看出，結(jié)果保留小數(shù)點后6位，GlobalOptimizationSolution搜索出的局部根與精確解相比，最大絕對誤差為0.000 001，最大相對誤差為0.000 002，而FAC方法最大絕對誤差為0.000 100，最大相對誤差為0.000 046。GlobalOptimi-zationSolution比FAC方法要精確。

3.3計算時間

算例5：分別求解

在區(qū)間[-3,3]內(nèi)的根。

表3　本文方法和FAC法的對比

利用文獻(xiàn)7中FAC算法、SPSO算法進(jìn)行計算，與Global Optimization Solution搜索出局部根所花時間進(jìn)行對比，結(jié)果見表4。

表4　本文方法和FAC法、SPSO法的對比

由表4可以看出，Global Optimization Solution的最大耗時為55 ms，F(xiàn)AC法、SPSO法最大耗時分別為398 ms、452 ms。Global Optimization Solution耗時僅為FAC法、SPSO法的13.8%、12.2%；Global Optimization Solution的平均最大耗時為29 ms，F(xiàn)AC法、SPSO法最大耗時分別為224 ms、275.6 ms。Global Optimization Solution的平均耗時僅為FAC法、SPSO法的12.9%、10.5%；Global Optimization Solution的計算成功率為100%，F(xiàn)AC法的計算成功率為100%，但SPSO法的計算成功率在47%～75%。說明Global Optimization Solution是一種計算成功率高，耗時極短的計算方法。

5　結(jié)語

Global Optimization Solution充分發(fā)揮粒子群算法的全局搜索性能和擬牛頓法的局部搜索性能，進(jìn)而將超越方程轉(zhuǎn)化為了純粹的函數(shù)優(yōu)化問題，優(yōu)點可總結(jié)如下：1)Global Optimization Solution全局搜索能力強(qiáng)；2)Global Optimization Solution局部搜索能力強(qiáng)，計算精度高；3)Global Optimization Solution計算耗時短。

[1] Bianchini M,Fanelli S,Gori M.Optimal Algorithms for Well-Conditioned Nonlinear Systems of Equations[J].IEEE Transactions on Computers,2001,50(7):689-698.

[2] 陳子儀,康立山,胡欣.遺傳算法在方程求根中的應(yīng)用[J].Wuhan University Journal of Natural Sciences,1998(5):577-580.

[3] Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]// Micro Machine and Human Science,1995.MHS '95.,Proceedings of the Sixth International Symposium on.IEEE,1995:39-43.

[4] 劉華鎣.粒子群優(yōu)化算法的改進(jìn)研究及在石油工程中的應(yīng)用[D].大慶：東北石油大學(xué),2012.

[5] 田明俊,周晶.巖土工程參數(shù)反演的一種新方法[J].巖石力學(xué)與工程學(xué)報,2005,24(9):1492-1496.

[6] Jing K E,Qian J X,Qiao Y Z.A modified particle swarm optimization algorithm[J].Journal of Circuits & Systems,2003,26(2):151-155.

[7] 郭改文,黃卡瑪.森林競爭算法及在超越方程求解中的應(yīng)用[J].四川大學(xué)學(xué)報:工程科學(xué)版,2008(6)：127-132.

The Global Optimization Method to Transcendental Equation

XIA Lyu-yu

(TonglingPolytechnic，TonglingAnhui244000，China)

The existing PSO (particle swarm optimization) algorithm has many problems in solving the transcendental equation，such as poor local search ability，post-convergence slower，which causes that PSO algorithm can not get more precise transcendental equation roots.In this article，based on particle swarm optimization algorithm，and adding quasi-Newton algorithm with better local search ability and faster post-convergence，the particle swarm algorithm and quasi-Newton method have been automatically selected and given full performance in local search ability abut this two algorithms.Thus the transcendental equation has been transformed into purely function optimization problem.Based on this method，a solution experiment has been made，and the results show that this method has the very high convergence speed and solution accuracy.

particle swarm optimization；global optimization；quasi-Newton method；transcendental equation

10.3969/j.issn.1009-8984.2016.03.028

2016-05-23

夏綠玉(1983-)，女(漢)，安徽銅陵，碩士，講師

主要研究概率論與數(shù)理統(tǒng)計。

O241.7

A

1009-8984(2016)03-0125-04