基于AF-PSO求解緩和曲線非線性方程組

基于AF-PSO求解緩和曲線非線性方程組

劉斌1,岳建平1,李永泉2

(1.河海大學(xué) 地球科學(xué)與工程學(xué)院，江蘇 南京 210098;2.南京市測繪勘察設(shè)計(jì)研究院有限公司，江蘇 南京 210005)

摘要：在線路測設(shè)工程中，根據(jù)緩和曲線內(nèi)外側(cè)地面點(diǎn)的實(shí)測坐標(biāo)，推導(dǎo)出曲線非線性方程，解算出對(duì)應(yīng)的曲線長具有一定的實(shí)際意義。針對(duì)傳統(tǒng)牛頓迭代解法計(jì)算量大，對(duì)形式復(fù)雜方程不適用等問題，提出一種基于人工魚群和粒子群的協(xié)同優(yōu)化算法，該算法綜合利用人工魚群算法的良好全局收斂性和粒子群算法的局部快速收斂性、易實(shí)現(xiàn)性等優(yōu)點(diǎn),發(fā)揮兩者的優(yōu)越性。實(shí)例表明，人工魚群和粒子群協(xié)同優(yōu)化算法可以很好地應(yīng)用到緩和曲線非線性方程組的求解中，且收斂速度快，求解精度高。

關(guān)鍵詞：人工魚群算法；粒子群算法；混合算法；緩和曲線；非線性方程

中圖分類號(hào)：U412.34

收稿日期：2014-07-28

作者簡介：劉斌(1991-),男，碩士研究生.

Hybrid optimization algorithm based on artificial fish swarm and particle swarm algorithm

LIU Bin1,YUE Jian-ping1,LI Yong-quan2

(1.School of Earth Sciences and Engineering Hohai University,Nanjing 210098,China;2.Nanjing Institute of Surverying,Mapping & Geotechnical Investigation Co.,Ltd.,Nanjing 210005,China)

Abstract：During the works of line surverying,it’s of great significance to derive the nonlinear equations and solve the length of curvve according to the measured coordinate of ground point of the relaxation curve.But the traditional Newton solution has a large amount of calculation and can’t be used to solve the complex equations.The hybrid optimization algorithm based on artificial fish swarm and particle swarm algorithm is better than the traditional Newton solution, which makes full use of the fast convergence of AFSA and the global convergence of PSO.It combines the advantages of both. The examples show it can be used to solve the nonlinear equations of transition curve.

Key words：AFSO；PSO；hybrid optimization algorithm；transition curve；nonlinear equation

在公路、鐵路、地鐵隧道、輕軌等線路工程中,線路前進(jìn)的方向由于受到地形、地物、地質(zhì)及其它因素的限制，經(jīng)常需要改變，所以需在轉(zhuǎn)向處設(shè)置曲線將兩直線連接起來。在一般情況下，為了提高車輛運(yùn)行的安全性與平順性，都要在直線和圓曲線之間設(shè)置緩和曲線。其曲率半徑R在與直線段分界處為無窮大,與圓曲線相交處與圓曲線半徑相等。緩和曲線上任一點(diǎn)的坐標(biāo),可以根據(jù)緩和曲線的參數(shù)方程計(jì)算得到。緩和曲線兩側(cè)的點(diǎn),若已知與緩和曲線之間的距離,根據(jù)緩和曲線上對(duì)應(yīng)點(diǎn)的坐標(biāo)和過該點(diǎn)的法線斜率,也可以計(jì)算出坐標(biāo)[1]。

文獻(xiàn)[2]提出利用緩和曲線上任一點(diǎn)處切線與法線斜率積為常數(shù)這一特性,推導(dǎo)出了關(guān)于曲線長的一元非線性方程[3-7],利用牛頓割線迭代法進(jìn)行方程的快速解算。

而牛頓迭代法計(jì)算量大，需進(jìn)行多次迭代，誤差較大。本文提出一種人工魚群和粒子群協(xié)同優(yōu)化算法(AF-PSO)。利用人工魚群算法的全局收斂性和粒子群算法的易實(shí)現(xiàn)性、局部快速收斂性，協(xié)同搜索，提高算法的全局收斂速度[8-11]。并將實(shí)例結(jié)果與牛頓迭代法和人工魚群算法求解結(jié)果做比較，表明AF-PSO算法對(duì)緩和曲線非線性方程的求解更為快速有效。

1緩和曲線非線性方程

在圖1所示的緩和曲線直角坐標(biāo)系中，R為圓曲線半徑，L0為緩和曲線長，由全站儀測量得到PH的坐標(biāo)(xH,yH)。過PH點(diǎn)作緩和曲線的法線與緩和曲線交于點(diǎn)Pl，坐標(biāo)為(xl,yl)。

圖1　緩和曲線直角坐標(biāo)系

(1)

其中，yl和xl可由緩和曲線參數(shù)方程式得到。

(2)

文獻(xiàn)[2]對(duì)xl和yl取l的幾次方項(xiàng)作了詳細(xì)分析，如式(2)所示，在不同曲率半徑下，xl的5次方項(xiàng)的絕對(duì)值最大值都在厘米級(jí)以上，9次方項(xiàng)及以后各項(xiàng)絕對(duì)值的最大值都小于0.2 mm，因此xl取到5次方項(xiàng)。同樣，在不同曲率半徑下，yl的7次方項(xiàng)的絕對(duì)值最大值在毫米級(jí)，11次方項(xiàng)及以后各項(xiàng)的絕對(duì)值的最大值遠(yuǎn)小于0.1 mm，所以yl取到7次方項(xiàng)。把xl和yl代入式(1)得

(3)

式(3)即為緩和曲線非線性方程的最終形式，R為與緩和曲線相連接的圓曲線的半徑，L0為緩和曲線長度。

2算法基本原理

2.1　人工魚群算法

2.2　粒子群算法

(4)

(5)

其中：r1和r2是在[0,1]之間均勻分布的隨機(jī)數(shù)，w代表慣性權(quán)重系數(shù)參數(shù)，C1和C2是正常數(shù)，稱之為學(xué)習(xí)因子或者加速因子。粒子群的每個(gè)個(gè)體從初始的位置和速度開始按式(1)、式(2)進(jìn)行迭代計(jì)算，直到符合算法終止條件。

3人工魚群和粒子群混合優(yōu)化算法

將人工魚群算法和粒子群算法結(jié)合起來，利用粒子群算法的快速局部收斂和人工魚群的全局收斂性，使新的人工魚群和粒子群協(xié)同優(yōu)化算法克服了人工魚群算法收斂速度慢、粒子群算法易陷入局部最優(yōu)的缺點(diǎn)，不僅具有快速的局部收斂速度，而且保證具有全局收斂性能，是一種性能較優(yōu)的優(yōu)化算法。

同時(shí)，引入邊界條件和跳躍概率P，初始化兩個(gè)種群個(gè)體后，判斷每個(gè)個(gè)體適應(yīng)度值是否滿足邊界條件，不滿足的重新生成數(shù)值，直至所有個(gè)體都滿足邊界條件。

邊界條件設(shè)定為所有個(gè)體適應(yīng)度值必須滿足式(6)。

(6)

(7)

人工魚群和粒子群中個(gè)體每進(jìn)行一次迭代后，從兩個(gè)種群中選取適應(yīng)度最差的10%的個(gè)體，按式(7)進(jìn)行跳躍。

(8)

式中：randn()產(chǎn)生[0,1]之間的隨機(jī)數(shù)，P設(shè)置種群個(gè)體跳躍的范圍，一般P的取值范圍是(0,0.3),則種群個(gè)體的跳躍區(qū)間為[(1-P)·Best,(1+P)·Best],Best為公告板最優(yōu)值。

人工魚群和粒子群協(xié)同優(yōu)化算法的操作步驟如下：

1)隨機(jī)初始化人工魚群POP1和粒子群POP2，在變量可行域內(nèi)隨機(jī)生成N個(gè)個(gè)體，設(shè)定人工魚的可視域Visual，人工魚的移動(dòng)步長Step，擁擠度因子σ及跳躍概率P。

2)初始化粒子群POP2，在變量可行域內(nèi)隨機(jī)生成N個(gè)個(gè)體，設(shè)定粒子群的加速度參數(shù)c1和c2，以及慣性權(quán)重系數(shù)w。

3)POP1按人工魚群算法的適應(yīng)度函數(shù)計(jì)算出每個(gè)個(gè)體的適應(yīng)度值，POP2按粒子群算法的適應(yīng)度函數(shù)算出每個(gè)個(gè)體的適應(yīng)度函數(shù)值。判斷兩個(gè)種群個(gè)體適應(yīng)度值是否都滿足邊界條件，不滿足的重新生成數(shù)值，直至所有個(gè)體滿足邊界條件。

4)將POP1執(zhí)行人工魚群算法，得到新的種群POP1′。

5)將POP2執(zhí)行粒子群算法，得到新的種群POP2′。

6)將兩個(gè)群體中適應(yīng)度值最小的個(gè)體數(shù)值作為最優(yōu)解賦給公告板Best。

7)從POP1′和POP2′中選取適應(yīng)度最差的10%的個(gè)體，以跳躍概率p進(jìn)行跳躍，更新其數(shù)值。

8)循環(huán)判斷公告板上的最優(yōu)解Best是否小于設(shè)定的誤差限。若是，輸出最優(yōu)解，否則，將新種群POP1′和POP2′執(zhí)行各自對(duì)應(yīng)算法，直到Best小于誤差限為止。

算法流程如圖2所示。

圖2　人工魚群和粒子群協(xié)同優(yōu)化算法流程圖

4仿真實(shí)驗(yàn)

4.1　函數(shù)測試

為了驗(yàn)證人工魚群和粒子群協(xié)同優(yōu)化算法的性能，選取2個(gè)典型的測試函數(shù)對(duì)算法做仿真實(shí)驗(yàn)。

1)Rastrigin函數(shù)

(9)

Rastrigin函數(shù)是一個(gè)多峰函數(shù)，在xi=0(i=1,2,…,D)的時(shí)候函數(shù)達(dá)到全局最小值f(xi)=0。

2)F1(X)=f1(X)h2(X)

h1(X)=[30+(2x1-2x2)2(18-32x1+

(10)

在此實(shí)驗(yàn)中，人工魚群和粒子群個(gè)體數(shù)都為N=50，人工魚視野范圍Visual=2，移動(dòng)步長Step=0.8，擁擠度因子δ=0.618，粒子群的加速度因子C1和C2都取為1.2，跳躍概率p=0.3，連續(xù)運(yùn)行50次后，取函數(shù)平均值和迭代時(shí)間作為AFSA和本文算法(AF-PSO)的評(píng)價(jià)指標(biāo)，測試結(jié)果如表1所示。

表1　AFSA和AF-PSO測試結(jié)果比較

由表1可以看出，本文算法AF-PSO的優(yōu)化結(jié)果明顯優(yōu)于基本的人工魚群算法，且精度高，速度快。

4.2　實(shí)例測試

采用文獻(xiàn)[2]中所用算例，以某大跨徑預(yù)應(yīng)力混凝上連續(xù)剛構(gòu)橋?yàn)槔４髽蚰硺蚨找粋?cè)位于直線上，另一側(cè)位于緩和曲線上。與緩和曲線相接的圓曲線半徑R為800 m，緩和曲線l長度為120 m。曲線長l由式(1)解得，從而求得實(shí)際施工梁段向中點(diǎn)到線路中心的距離，通過與設(shè)計(jì)值進(jìn)行比較，則可知道梁段相對(duì)于線路中心線是否偏離。

算法在matlab下編程實(shí)現(xiàn)，參數(shù)設(shè)置如下：人工魚群和粒子群個(gè)體數(shù)都為N=50，人工魚視野范圍Visual=10，移動(dòng)步長Step=2，擁擠度因子δ=0.618，粒子群的加速度因子C1和C2都取為1.2，跳躍概率p=0.2，連續(xù)運(yùn)行20次計(jì)算平均值，以誤差值和迭代時(shí)間作為評(píng)價(jià)指標(biāo)。本文算法與基本人工魚群算法求解結(jié)果如表2所示。

表2　AFSA與AF-PSO實(shí)例求解結(jié)果比較

從表2可以看出，AF-PSO求解緩和曲線非線性方程解的精度明顯優(yōu)于基本人工魚群算法，且耗時(shí)更短。文獻(xiàn)[2]中利用牛頓分割迭代法的求解結(jié)果為l=31.046。誤差值為2.44×10-5，可以看出，本文算法的求解精度和速度有所提高。

5結(jié)束語

利用人工魚群算法的全局收斂性和粒子群算法的局部收斂性，加入跳躍因子和邊界搜索條件，提出了一種人工魚群和粒子群協(xié)同優(yōu)化算法，實(shí)例計(jì)算表明，AF-PSO比基本人工魚群算法、牛頓迭代法等求解速度更快、精度更高，不管方程是否可微或形式復(fù)雜，都不影響其求解，為緩和曲線非線性方程的求解提供了一種新方法。

參考文獻(xiàn)：

[1]侯曉真,于瑞鵬.道路勘測階段控制測量方法的研究[J].測繪工程,2012,21(4):70-73.

[2]高淑照,史東晏.緩和曲線非線性方程的快速解算[J].測繪通報(bào),2006(3):28-30.

[3]郭曉梅.非線性方程數(shù)值解法探究[J].棗莊學(xué)院學(xué)報(bào),2010,27(2):23-25.

[4]黃娜,馬昌鳳.求解非線性方程組的一個(gè)新的三階迭代算法[J].福建師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,29(1):25-30.

[5]張姣玲,林桂友,許國良,等.求解非線性方程的混合人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用,2014(10):48-51.

[6]胡菊英,陳文貴,朱良文,等.非完整緩和曲線點(diǎn)的既有坐標(biāo)計(jì)算方法探討[J].礦山測量,2013(6):70-72.

[7]王祖華.鐵路緩和曲線代數(shù)式方程的通用設(shè)計(jì)方法[J].石家莊鐵道大學(xué)學(xué)報(bào),2011,24(2):46-48.

[8]張英杰,李志武,奉中華,等.一種基于動(dòng)態(tài)參數(shù)調(diào)整的改進(jìn)人工魚群算法[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版,2012,39(5):77-82.

[9]羅德相,周永權(quán),黃華娟,等.粒子群和人工魚群混合優(yōu)化算法[J].計(jì)算機(jī)與應(yīng)用化學(xué),2009,26(10):1257-1261.

[10]黃光球,劉嘉飛,姚玉霞,等.人工魚群算法的全局收斂性證明[J].計(jì)算機(jī)工程,2012,38(2):204-206.

[11]謝錚桂,鐘少丹,韋玉科,等.改進(jìn)的粒子群算法及收斂性分析[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(1):46-49.曉真,于瑞鵬.道路勘測階段控制測量方法的研究[J].測繪工程,2012,21(4):70-73.

[2]高淑照,史東晏.緩和曲線非線性方程的快速解算[J].測繪通報(bào),2006(3):28-30.

[3]郭曉梅.非線性方程數(shù)值解法探究[J].棗莊學(xué)院學(xué)報(bào),2010,27(2):23-25.

[4]黃娜,馬昌鳳.求解非線性方程組的一個(gè)新的三階迭代算法[J].福建師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,29(1):25-30.

[5]張姣玲,林桂友,許國良,等.求解非線性方程的混合人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用,2014(10):48-51.

[6]胡菊英,陳文貴,朱良文,等.非完整緩和曲線點(diǎn)的既有坐標(biāo)計(jì)算方法探討[J].礦山測量,2013(6):70-72.

[7]王祖華.鐵路緩和曲線代數(shù)式方程的通用設(shè)計(jì)方法[J].石家莊鐵道大學(xué)學(xué)報(bào),2011,24(2):46-48.

[8]張英杰,李志武,奉中華,等.一種基于動(dòng)態(tài)參數(shù)調(diào)整的改進(jìn)人工魚群算法[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版,2012,39(5):77-82.

[9]羅德相,周永權(quán),黃華娟,等.粒子群和人工魚群混合優(yōu)化算法[J].計(jì)算機(jī)與應(yīng)用化學(xué),2009,26(10):1257-1261.

[10]黃光球,劉嘉飛,姚玉霞,等.人工魚群算法的全局收斂性證明[J].計(jì)算機(jī)工程,2012,38(2):204-206.

[11]謝錚桂,鐘少丹,韋玉科,等.改進(jìn)的粒子群算法及收斂性分析[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(1):46-49.

[責(zé)任編輯：劉文霞]