濱江學(xué)院畢業(yè)論文題目非線性模型參數(shù)估計(jì)的大洪水算法院系大氣與遙感系專 業(yè) 測(cè)繪工程學(xué)生姓名 劉少東學(xué) 號(hào) 20092350012指導(dǎo)教師 王永弟職 稱 講師二0一三年五月二十日目錄TOC\o"1-5"\h\z\o"CurrentDocument"1引言 -1-\o"CurrentDocument"2非線性模型參數(shù)估計(jì) -1-\o"CurrentDocument"3基本大洪水算法 -2-\o"CurrentDocument"4大洪水算法改進(jìn) -3-5大洪水算法的應(yīng)用實(shí)例 -4-\o"CurrentDocument"6結(jié)束語(yǔ) -6-\o"CurrentDocument"參考文獻(xiàn) -7-\o"CurrentDocument"致謝 -8-\o"CurrentDocument"Abstract - 9-非線性模型參數(shù)估計(jì)的大洪水算法劉少東南京信息工程大學(xué)濱江學(xué)院測(cè)繪工程專業(yè)，南京210044摘要：經(jīng)過兩百多年的發(fā)展，線性模型參數(shù)估計(jì)理論已經(jīng)非常成熟，成果豐碩。但現(xiàn)實(shí)中的實(shí)際模型往往并非線性模型，而是非線性模型。用線性模型來解算非線性模型，常常會(huì)帶來很多問題，得出結(jié)論會(huì)與現(xiàn)實(shí)有較大差距。因此，現(xiàn)實(shí)中非線性模型該用非線性科學(xué)的方法解算。用大洪水直接搜索算法解算非線性模型，無(wú)需求導(dǎo)，適用范圍廣，具有較為理想的全局尋優(yōu)效果，以及較好的計(jì)算精度及較高的效率。關(guān)鍵字：非線性模型，參數(shù)估計(jì)，最小二乘法，大洪水算法1引言參數(shù)估計(jì)是數(shù)理統(tǒng)計(jì)中的一個(gè)名詞，其含義是根據(jù)含有誤差的觀測(cè)向量，依據(jù)一定的數(shù)學(xué)模型和準(zhǔn)則求解未知數(shù)，就是實(shí)際測(cè)量中的平差問題。通常情況下，包括測(cè)量工作中，非線性模型的出現(xiàn)要比線性模型頻繁得多，因而，非線性模型參數(shù)估計(jì)的使用也頻繁的多。1993年，GunterDueck最早提出了大洪水算法，那是一種受自然界啟發(fā)，通過模擬洪水上漲的過程來進(jìn)行全局優(yōu)化的算法。Dueck在對(duì)閾值接收算法(ThresholdAccepting)進(jìn)行研究的過程中，又發(fā)現(xiàn)了大洪水算法(GreatDelugeAlgorithm)和記錄更新法(Record-to-RecordTravel)這兩種行之有效的啟發(fā)式算法。大洪水算法與爬上算法(Thehill-climbingalgorithm)、模擬退火算法(Thesimulatedannealingalgorithm)頗為相似。用個(gè)形象的比喻來說，洪水不斷上漲，淹沒大地高山，某人不斷向上攀登，他能任意移動(dòng)。他必須不斷找到更高處以求躲避洪水生存下去，他最終會(huì)到達(dá)最高點(diǎn)，即得到最優(yōu)解。大洪水算法有著簡(jiǎn)單的結(jié)構(gòu)，較強(qiáng)的操作性，是一種新興的啟發(fā)性尋優(yōu)算法，非線性模型也在現(xiàn)實(shí)生產(chǎn)生活中被更加廣泛的應(yīng)用，文章將研究大洪水算法在解算非線性問題中，是否依舊適用高效。2非線性模型參數(shù)估計(jì)參數(shù)估計(jì)(ParameterEstimation)是一種基本的統(tǒng)計(jì)推斷形式，也是數(shù)理統(tǒng)計(jì)學(xué)的一個(gè)重要分支，更是測(cè)量數(shù)據(jù)處理(SurveyingDataProcessing)理論的重要組成部分。由于迄今為止，參數(shù)估計(jì)的一系列成果主要集中在線性模型(LineModel),線性模型參數(shù)估計(jì)理論是非線性模型(NonlinearModel)參數(shù)估計(jì)的基礎(chǔ)［1］。線性模型是數(shù)理統(tǒng)計(jì)學(xué)中發(fā)展比較早的分支之一［2］，關(guān)于它的參數(shù)估計(jì)問題，可以追溯到18世紀(jì)，發(fā)

展至今已十分完善。從二十世紀(jì)60年代，數(shù)理統(tǒng)計(jì)中對(duì)非線性參數(shù)估計(jì)的研究才開始進(jìn)行。但初期并沒有

-1-取得很好的研究成果。1980年，兩個(gè)加拿大的統(tǒng)計(jì)學(xué)家Bates和Watts在非線性模型中加入了曲率度量，這時(shí)，對(duì)于非線性模型的研究才取得了較大的進(jìn)步⑶。測(cè)量學(xué)上對(duì)非線性模型參數(shù)估計(jì)的深入研究始于上個(gè)世紀(jì)80年代后期。1985年之后，國(guó)際著名大地測(cè)量學(xué)家P.J.G.Teunissen在非線性模型參數(shù)估計(jì)領(lǐng)域做出了效果顯著的研究。他先后研究了非線性模型的最小二乘估計(jì)一、二階矩。闡明了關(guān)于度量非線性強(qiáng)度的指標(biāo)、非線性模型的識(shí)別以及非線性模型曲率的幾何意義等等。他又經(jīng)過反復(fù)試驗(yàn)，通過研究非線性模型展開式中舍去項(xiàng)造成的函數(shù)模型偏差，提出從舍去項(xiàng)中來發(fā)現(xiàn)了其對(duì)函數(shù)模型和參數(shù)的影響，然后又對(duì)參數(shù)估計(jì)的估值和函數(shù)模型進(jìn)行改良修正。之后，測(cè)量學(xué)花laha對(duì)非線性最小二乘的無(wú)迭代求解理論⑷進(jìn)行了較為系統(tǒng)地研究。學(xué)者Lohse系統(tǒng)地研究了非線性模型的參數(shù)估計(jì)理論。AthanasiosDermanis和FernandoSanso研究了可容許和不可容許的非線性估計(jì)原理，提出了非線性估計(jì)的貝葉斯方法m測(cè)繪領(lǐng)域也非常的重視非線性科學(xué)。1994年，在由國(guó)家自然科學(xué)基金委員會(huì)調(diào)整的關(guān)于自然科學(xué)學(xué)科發(fā)展戰(zhàn)略的調(diào)查報(bào)告《大地測(cè)量學(xué)》（國(guó)家自然科學(xué)基金委員會(huì)，1994）⑹中，明確提出：非線性模型參數(shù)估計(jì)理論是研究測(cè)量學(xué)的重要方法，是今后研究大地測(cè)量學(xué)科的重大基礎(chǔ)理論問題之一。這是由于學(xué)者在對(duì)非線性模型使用傳統(tǒng)的線性化解算方法中發(fā)現(xiàn)，很多理論在非線性模型中可用，但在非線性模型中并不適用；很多結(jié)論在線性模型中成立，但在非線性模型中卻不一定能成立；一些優(yōu)良的統(tǒng)計(jì)性質(zhì)在線性模型中存在，但在非線性模型中不一定存在。比如說，在求解線性模型參數(shù)估計(jì)問題中，隨機(jī)誤差滿足正態(tài)分布時(shí)，未知參數(shù)乂的最小二乘估計(jì)xis具有一致無(wú)偏性和方差最小性，但如果在求解非線性模型參數(shù)估計(jì)的問題中，即便是隨機(jī)誤差嚴(yán)格滿足了正太分布，未知參粼的非線性最小二乘估計(jì)xnls也是有偏的。其方差一般都不能達(dá)到CR下界。其實(shí)我們很難再現(xiàn)實(shí)生產(chǎn)生活中見到嚴(yán)格的線性模型，更多的是非線性模型。隨著近代統(tǒng)計(jì)學(xué)和科學(xué)技術(shù)飛速的發(fā)展，統(tǒng)計(jì)學(xué)家面前出現(xiàn)的是越來越多的，不能簡(jiǎn)單化為線性模型的非線性模型。很多非線性模型以及其他非線性統(tǒng)計(jì)的問題在生物、農(nóng)業(yè)、經(jīng)濟(jì)、工程技術(shù)等各個(gè)部門被提出來。在測(cè)量學(xué)上，大量的測(cè)量數(shù)據(jù)數(shù)學(xué)模型也是非線性模型。通常將其線性近似，在測(cè)量學(xué)上稱這種做法為線性化。在過去，觀測(cè)精度不高，對(duì)測(cè)量精度的要求也不高，模型誤差可以忽略不計(jì)，將非線性模型線性化是一種較為可行的方法。但如今觀測(cè)精度大幅提高，對(duì)測(cè)量精度的要求也隨之提高，傳統(tǒng)的線性化方法引起的模型誤差已不容忽視。常用的方法有兩大類：第一種需要對(duì)函數(shù)進(jìn)行求導(dǎo)計(jì)算，該方法在函數(shù)比較復(fù)雜時(shí)會(huì)很困難，遇到不可導(dǎo)函數(shù)時(shí)將不再使用。第二種是無(wú)需求導(dǎo)直接搜索算法，該方法無(wú)需求導(dǎo)，適用范圍廣，是近年來頗受關(guān)注的方法。大洪水算法即是一種直接搜索算法，本文將結(jié)合實(shí)例研究該算法在處理測(cè)量數(shù)據(jù)上是否具優(yōu)于其他算法。3基本大洪水算法1993年，Gunter最早提出大了洪水算法衛(wèi)。大洪水算法提出的靈感源于大自然，它進(jìn)行全局優(yōu)化的過程好比洪水上漲，淹沒高山尋找山脈的最高點(diǎn)。在結(jié)構(gòu)上，大洪水算法與另一種尋優(yōu)方法模擬退火法較為相似，區(qū)別在于迭代中候選解不一樣的接受規(guī)則。后來，Gunter成功地運(yùn)用大洪水算法解算出了經(jīng)典旅行商問題。隨后，受此啟發(fā)，國(guó)外一些學(xué)者相繼對(duì)大洪水算法進(jìn)行改進(jìn)優(yōu)化，廣泛地研究應(yīng)用，將其運(yùn)用于求解復(fù)雜系統(tǒng)可靠性優(yōu)化⑻,工件排序問題和課程時(shí)間表問題等NP-Hard類的問題等等，成果斐然。國(guó)內(nèi)的學(xué)者對(duì)大洪水算法的研究不多，但也取得了一些不錯(cuò)的成就。比如，魏欣和馬良成功地將大洪水算法運(yùn)用在了多目標(biāo)旅行商問題的求解上，盛虹平用其解算最小比率旅行商問題，也取得了較為不錯(cuò)的成果①。大洪水算法的遍歷過程與圣經(jīng)里諾亞洪水的傳說有著相似之處，其尋優(yōu)思想可以描述為：假想有一群高低不平的高山群，一個(gè)救生船藏在這其中某座高山的山頂，一個(gè)有著特殊能力的攀登者正在高山群中的某位置，他能任意從高山中一處去到另外一處。假如此刻大洪水爆發(fā)上漲，洪水迅速地奔涌而來淹沒山腳，向上蔓延。攀巖者必須不斷地向上尋找最高點(diǎn)以求脫險(xiǎn)。隨著洪水上漲逐漸逼近，攀巖者最終將會(huì)找這群藏在高山最高點(diǎn)的救生艇，脫離大洪水的威脅[10]0大洪水算法不但可以解算極大函數(shù)優(yōu)化問題，也能解算極小函數(shù)優(yōu)化問題。當(dāng)要對(duì)函數(shù)進(jìn)行極小優(yōu)化時(shí)，可將大洪水算法理解為大旱算法（greatdroughtalgorithm）。假設(shè)有一片海洋受到旱災(zāi)的侵襲，海水蒸發(fā)，海平面逐漸下降，某海洋生物不斷地向下，尋找能讓它繼續(xù)生存下去海水。下面為解算極小化函數(shù)優(yōu)化問題的基本大洪水算法，即大旱算法的步驟。（1）初始化count一迭代次數(shù)；it—（迭代因子）；up一海平面下降水位高度；產(chǎn)生0-1均勻分布的偽隨機(jī)數(shù)，映射至x0區(qū)間；WaterLevel—f（X0）（海平面高度）；（2） 對(duì)X0進(jìn)行領(lǐng)域搜索，得到一個(gè)新的解X；計(jì)算對(duì)應(yīng)的目標(biāo)函數(shù)f（X）；如果f（X）<WaterLevel,貝0Xo—XWaterLevel—WaterLevel-up（3） it—it+1;若it<count，轉(zhuǎn)（2）輸出X0和f（x0）；大洪水算法思想非常簡(jiǎn)單，因?yàn)槊枯喍贾辉试S從洪水水平面以上的點(diǎn)進(jìn)行選代（大旱算法從水平面以下的點(diǎn)進(jìn)行迭代），所以有著很高的解算效率。與模擬退火發(fā)等其他啟發(fā)式算法相比較，大洪水算法只依賴于唯一的一個(gè)參數(shù)up，操作簡(jiǎn)單。up值決定運(yùn)算速度，并且影響最終結(jié)算結(jié)果。若叩值取的過大，算法運(yùn)算速度會(huì)加快，但結(jié)算結(jié)果的精確性會(huì)降低；若up值取的過小，那么結(jié)算結(jié)果精度會(huì)較高，但需經(jīng)過較長(zhǎng)時(shí)間的解算。Gunter在大地測(cè)試中得出該參數(shù)還可以動(dòng)態(tài)賦值，即最好的up應(yīng)不超過目標(biāo)值f（X）和WaterLevel差值的1%[11]。4大洪水算法改進(jìn)大洪水算法是一種迭代算法，依賴于領(lǐng)域結(jié)構(gòu)。大洪水算法實(shí)施關(guān)鍵是怎樣設(shè)計(jì)尋找下一候選解的領(lǐng)域函數(shù)式。針對(duì)連續(xù)優(yōu)化問題，可以理解領(lǐng)域函數(shù)為在距離空間中通過附加擾動(dòng)構(gòu)造而成。下面給出對(duì)大洪水算法進(jìn)行改進(jìn)而成的三種不同構(gòu)造策略?！竀=x+r-cos0TOC\o"1-5"\h\z＜， .° (1)［J=J+r-sinU策略1：Logistic映射函數(shù)混沌拗動(dòng)構(gòu)造定義1：令T{t］,t2...}為L(zhǎng)ogistic映射函數(shù)產(chǎn)生的混沌序列，滿足：t=ut(1-1),i=1,2,…,u(e(2,4］ (2)當(dāng)u=4,0WtiW1時(shí)，混沌序列完全處于混沌狀態(tài)。此時(shí)，優(yōu)化變量X的取值范圍［a,b］與該混沌序列T的取值范圍［0,1］的映射公式分別為：t=(x—a)/(b—a),i=1,2… (3)iix=(b—a)/1+a,i=1,2… (4)策略2：圓周擾動(dòng)構(gòu)造定義2：對(duì)于二維連續(xù)優(yōu)化問題，當(dāng)前解(x，y)的領(lǐng)域函數(shù)為圓周擾動(dòng)構(gòu)造，則滿足。策略3邏輯自映射函數(shù)混沌擾動(dòng)構(gòu)造定義3令T{t1,t2...}為邏輯自映射函數(shù)產(chǎn)生的混沌序列，則滿足：TOC\o"1-5"\h\zt］=1—2x技，i=1,2,???，-1＜「＜1 (5)優(yōu)化變量X的取值范圍［a,b］與該混沌序列T的取值范圍［-1,1］的映射與逆映射公式分別為：t=2G—a)/(b—a)—1,i=1,2，… (6)x.=(b—a)G+1)/2+a,i=1,2,... (7)策略2與策略3中主要是基于混沌優(yōu)化思想的領(lǐng)域函數(shù)設(shè)計(jì)，也就是將優(yōu)化變量映射到混沌序列的取值范圍中，這樣得到的混沌序列與優(yōu)化變量有著相同的數(shù)目。然后選擇合適的混沌模型進(jìn)行迭代，迭代之后的混沌序列又逆向映射到優(yōu)化變量的取值范圍中。無(wú)論是策略1，策略2還是策略3,都要求預(yù)先知道優(yōu)化變量的取值范圍［a,b］［12］。5大洪水算法的應(yīng)用實(shí)例在處理解算測(cè)量數(shù)據(jù)的方法中，我們熟悉的線性觀測(cè)方程的一般形式為：TOC\o"1-5"\h\zL=bx+bx+???+bx+b+A(i=1,2,…，n) (8)i i11 i22 itt i0 i其矩陣形式為：L=BX+B+A (9)

式子中，￡=(Ly…”表示nX1的觀測(cè)向量；n為觀測(cè)值的個(gè)數(shù)；X表示tXI未知參數(shù)向量;(10)t為必要觀測(cè)的個(gè)數(shù)；B0=(B01B02…B”為nX1的常數(shù)向量；△二(氣A2…△〃)'為nx1的觀測(cè)誤差向量；B為nx(10)'bb…b、11121tbb…bB=<21:22:2t>:bb…?bn1n2nt比如水準(zhǔn)測(cè)量中，當(dāng)不設(shè)尺度比參數(shù)，且以待定高程為未知參數(shù)時(shí)，其觀測(cè)方程就是(9)式所示的線性形式。然而，測(cè)量中更多的觀測(cè)方程是非線性方程。一般的，用L表示nx1的觀測(cè)向量，用X表示tx1的未知參數(shù)向量，用A表示nx1的觀測(cè)誤差向量，則非線性觀測(cè)方程可寫為(11)L=f(x)+A(11)式中f(X)=(f(X)f(X)…fn(X))，是由n個(gè)X的非線性函數(shù)組成的nx1的向量，(11)式就是我們所要討論的一般非線性模型。 ..求(11)的最小二乘估計(jì)量，即求參數(shù)X的估值X，得：VV(X)=(f(X)—L)'(f(X)-L)(12)=f(X)f(X)-2f'(X)L+LL(12)=min由于L’L是一個(gè)常量，所以(12)等價(jià)于目標(biāo)函數(shù)R(X)=f(X)f(X)-2f(X)L=min非線性無(wú)約束最優(yōu)化問題。例：已知一個(gè)非線性模型L=xeix2。參數(shù)x，x的真值為X=(5.420136187 -0.25436189)，L有5i1 1 2 i個(gè)真值(用參數(shù)的真值X算得)和相應(yīng)的5個(gè)同精度獨(dú)立觀測(cè)值列于表1。表i L的真值和相應(yīng)的觀測(cè)值I12345真值4.2028343.2589242.5270061.9594691.519394觀測(cè)值4.23.252.521.951.51分別運(yùn)用單純形法，模擬退火法，大洪水算法對(duì)例題進(jìn)行求解得到計(jì)算結(jié)果列于蒞。計(jì)算方法X1X21X11真值5.420136187-0.254361890-單純形態(tài)法5.427324646-0.2558980000.0074模擬退火法5.423806309-0.2558710010.004大洪水算法5.422807188-0.2556782850.003表2計(jì)算結(jié)果由表2的計(jì)算結(jié)果可以看出，大洪水算法的||X||為三種算法中最小，即與真值的距離最小。由此說明在解算此非線性方程中，大洪水算法的結(jié)果最接近真值，是三種算法中效果最好的。對(duì)比解算精度與大洪水算法想近的模擬退火算法。模擬退火法需一個(gè)內(nèi)循環(huán)和一個(gè)外循環(huán)的控制，大洪水算法只有一個(gè)迭代次數(shù)t的循環(huán)控制，因而大洪水算法解算速度會(huì)快很多。理論上滿足模擬退火法退火三原則（即初始溫度做夠高、降溫速度足夠慢、終止溫度足夠低），即初始點(diǎn)足夠好、markov鏈足夠長(zhǎng)、計(jì)算時(shí)間足夠長(zhǎng)時(shí)，模擬退火法以概率1達(dá)到全局最優(yōu)解。而大洪水算法的精度只依賴參數(shù)up的值，up值足夠小，迭代次數(shù)t足夠多，解算精度就越接近最優(yōu)解。在對(duì)兩算法解算進(jìn)行嚴(yán)密控制時(shí)，兩者解算進(jìn)度相近。但模擬退火法需過長(zhǎng)的解算時(shí)間，在算法控制方面，markov鏈長(zhǎng)度無(wú)限，所以模擬退火法很難保證收斂到全局最優(yōu)解。由此可見，大洪水算法在解算效率上由于模擬退火法。6結(jié)束語(yǔ)大洪水算法解算無(wú)需進(jìn)行求導(dǎo)，結(jié)構(gòu)簡(jiǎn)單，且只依賴于一個(gè)參數(shù)，便于理解，易于執(zhí)行。具體解算過程中，可以通過人為比較選擇，或事先設(shè)定一個(gè)集合，記錄當(dāng)前已得非劣解，然后用新得到的解與之進(jìn)行比較，判斷是否已經(jīng)改進(jìn)非劣解，再?zèng)Q定是否停止運(yùn)算，輸出結(jié)果。本文以解算非線性模型參數(shù)估計(jì)問題為例，與模擬退火法以及單純形法想比較，體現(xiàn)了大洪水算法運(yùn)行效率和算法性能的優(yōu)越性?？梢姶蠛樗惴ㄔ诜蔷€性優(yōu)化領(lǐng)域是一種很好的求解手段。目前，人們對(duì)大洪水算法的研究還不多，研究文獻(xiàn)非常有限，所以將之改進(jìn)并運(yùn)用到更多領(lǐng)域，將有很大發(fā)展空間。參考文獻(xiàn)王新洲，《非線性模型參數(shù)估計(jì)理論與應(yīng)用》[M].武漢大學(xué)出版社，2002.6.28-29.成平，陳希孺，陳桂景，《參數(shù)估計(jì)》[M].上海科學(xué)技術(shù)出版社，1985.韋博成，《近代非線性回歸分析》[M].東南大學(xué)，1989.Blaha.G.Non-iterativeapproachtononlinearleast-squaresadjustment.ManuscriptGeodaetica.1994(19),pp.199-212.AthanasiosDermanisandFernandoSanso.Astudyofnon-linearestimation,IUGG交流論文，1995.國(guó)家自然科學(xué)基金委員會(huì).《大地測(cè)量學(xué)》[M].國(guó)防科技大學(xué)出版社，1994.GUNTERD.NewOptimizationHeuristics:TheGreatDelugeAlgorithmandtheRecord-to-recordtravel[J].JournalofComputationalPhysics,1993,104(1):86-92.RAVIV.OptimazationofComplexSystemReliabilitybyaModifiedGreatDelugeAlgorithm[J].Asia-PacificJournalofOperationalResearch,2004,21(4):487-497.王永弟.丁海永.非線性模型參數(shù)估計(jì)的大洪水算法[j].地理信息空間，2012,1672-4623(2012).盛虹平.馬良.混沌大洪水算法求解函數(shù)優(yōu)化問題[J].計(jì)算機(jī)應(yīng)用研究，2011,28(5):1626-1627.陳小蘭.熊立華.萬(wàn)民.宏觀進(jìn)化多目標(biāo)遺傳算法在梯級(jí)水庫(kù)調(diào)度中的應(yīng)用[J].水利發(fā)電學(xué)報(bào)，2009,28(3)：6-9,58.盛虹平，馬良.大洪水算法在平面選址問題中的應(yīng)用[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011,41(15).致謝隨著畢業(yè)論文落下最后一個(gè)句號(hào)，四年大學(xué)里的最后一個(gè)學(xué)習(xí)任務(wù)也就要完成了。閉上眼，靜靜回憶，回憶學(xué)年論文的寫作過往，選題、寫作、修改、初稿，定稿，再到畢業(yè)論文，寫作、初稿、定稿，在這半年時(shí)間里，給我?guī)椭畲螅钜兄x的人是我的導(dǎo)師王永弟老師。當(dāng)初，我嫩頭嫩腦地拿到論文題目時(shí)，一臉茫然，不知所措，無(wú)從下手，王永弟老師耐心的給我解釋什么是非線性，什么是大洪水算法，大洪水算法有什么用。我仿佛迷失于草木茂密的陌生叢林中，王老師給我指出了走出去的方向。選到這樣的論文題目，大概就是去學(xué)習(xí)一門新的學(xué)科，開始學(xué)習(xí)新的東西不是件容易的事情，那要把一個(gè)人從不會(huì)教到會(huì)，那人如果腦子不靈光，那就難上加難了。