3.2　基于遺傳程序設(shè)計(jì)的降水徑流回歸模型

3.2.1　遺傳程序設(shè)計(jì)

遺傳程序設(shè)計(jì)(Genetic Programming,簡(jiǎn)稱GP),是一種從生物演化過(guò)程得到靈感的自動(dòng)化生成和選擇計(jì)算機(jī)程序來(lái)完成用戶定義的任務(wù)的技術(shù)。從理論上講,人類用遺傳編程只需要告訴計(jì)算機(jī)“需要完成什么”,而不用告訴它“如何去完成”,最終可能實(shí)現(xiàn)真正意義上的人工智能。遺傳編程是一種特殊的利用進(jìn)化算法的機(jī)器學(xué)習(xí)技術(shù),它開(kāi)始于一群由隨機(jī)生成的千百萬(wàn)個(gè)計(jì)算機(jī)程序組成的“人群”,然后根據(jù)一個(gè)程序完成給定任務(wù)的能力來(lái)確定某個(gè)程序的適合度,應(yīng)用達(dá)爾文的自然選擇(適者生存)確定勝出的程序,計(jì)算機(jī)程序間也模擬兩性組合、變異、基因復(fù)制、基因刪除等代代進(jìn)化,直到達(dá)到預(yù)先確定的某個(gè)中止條件為止。遺傳編程的首批試驗(yàn)由斯蒂芬·史密斯(1980年)和Nichael·克拉姆(1985年)發(fā)表,約翰·Koza(1992年)也寫(xiě)了一本著名的書(shū),《遺傳編程:用自然選擇讓計(jì)算機(jī)編程》,來(lái)介紹遺傳編程。使用遺傳編程的計(jì)算機(jī)程序可以用很多種編程語(yǔ)言來(lái)寫(xiě)成,早期(或者說(shuō)傳統(tǒng))的GP實(shí)現(xiàn)中,程序的指令和數(shù)據(jù)的值使用樹(shù)狀結(jié)構(gòu)的組織方式,所以那些本來(lái)就提供樹(shù)狀組織形式的編程語(yǔ)言最適合于GP,例如Koza使用的Lisp語(yǔ)言。其他形式的遺傳程序也被提倡和實(shí)現(xiàn),例如相對(duì)簡(jiǎn)單的適合傳統(tǒng)編程語(yǔ)言(例如Fortran、BASIC和C語(yǔ)言)的線性遺傳編程。有商業(yè)化的GP軟件把線性遺傳編程和匯編語(yǔ)言結(jié)合來(lái)獲得更好的性能,也有的實(shí)現(xiàn)方法直接生成匯編程序。遺傳編程所需的計(jì)算量非常之大(處理大量候選的計(jì)算機(jī)程序),以至于在20世紀(jì)90年代的時(shí)候它只能用來(lái)解決一些簡(jiǎn)單的問(wèn)題。近年來(lái),隨著遺傳編程技術(shù)自身的發(fā)展和中央處理器計(jì)算能力的指數(shù)級(jí)提升,GP開(kāi)始產(chǎn)生了一大批顯著的成果。該方法通過(guò)對(duì)運(yùn)算符及基本函數(shù)進(jìn)行編碼并存儲(chǔ)于節(jié)點(diǎn)之中,表達(dá)式由各節(jié)點(diǎn)聯(lián)結(jié)而成的樹(shù)結(jié)構(gòu)存儲(chǔ),每棵樹(shù)即為一條染色體,利用遺傳算法的思想,經(jīng)過(guò)初始染色體群的生成,交叉操作、變異操作,根據(jù)“優(yōu)勝劣汰”的原則進(jìn)行搜索和優(yōu)化,自動(dòng)生成最優(yōu)的結(jié)構(gòu)表達(dá)式,是一種自動(dòng)化編程技術(shù)、一種智能算法,擅長(zhǎng)于進(jìn)行模型結(jié)構(gòu)的自動(dòng)搜索。

遺傳算法的優(yōu)化機(jī)理:在遺傳算法里優(yōu)化問(wèn)題的解被稱為個(gè)體,它表示為一個(gè)變量序列,叫做染色體或者基因串。染色體一般被表達(dá)為簡(jiǎn)單的字符串或數(shù)字串,不過(guò)也有其他的依賴于特殊問(wèn)題的表示方法適用,這一過(guò)程稱為編碼。首先,算法隨機(jī)生成一定數(shù)量的個(gè)體,有時(shí)候操作者也可以對(duì)這個(gè)隨機(jī)產(chǎn)生過(guò)程進(jìn)行干預(yù),以提高初始種群的質(zhì)量。在每一代中,每一個(gè)個(gè)體都被評(píng)價(jià),并通過(guò)計(jì)算適應(yīng)度函數(shù)得到一個(gè)適應(yīng)度數(shù)值。種群中的個(gè)體被按照適應(yīng)度排序,適應(yīng)度高的在前面。這里的“高”是相對(duì)于初始的種群的低適應(yīng)度來(lái)說(shuō)的。下一步是產(chǎn)生下一代個(gè)體并組成種群。這個(gè)過(guò)程是通過(guò)選擇和繁殖完成的,其中繁殖包括交配(crossover,在算法研究領(lǐng)域中我們稱之為交叉操作)和突變(mutation)。選擇則是根據(jù)新個(gè)體的適應(yīng)度進(jìn)行的,但同時(shí)并不意味著完全的以適應(yīng)度高低作為導(dǎo)向,因?yàn)閱渭冞x擇適應(yīng)度高的個(gè)體將可能導(dǎo)致算法快速收斂到局部最優(yōu)解而非全局最優(yōu)解,我們稱之為早熟。作為折中,遺傳算法依據(jù)原則:適應(yīng)度越高,被選擇的機(jī)會(huì)越高,而適應(yīng)度低的,被選擇的機(jī)會(huì)就低。初始的數(shù)據(jù)可以通過(guò)這樣的選擇過(guò)程組成一個(gè)相對(duì)優(yōu)化的群體。之后,被選擇的個(gè)體進(jìn)入交配過(guò)程。一般的遺傳算法都有一個(gè)交配概率(又稱為交叉概率),一般是0.6～1,這個(gè)交配概率反映兩個(gè)被選中的個(gè)體進(jìn)行交配的概率。例如,交配概率為0.8,則80%的“夫妻”會(huì)生育后代。每?jī)蓚€(gè)個(gè)體通過(guò)交配產(chǎn)生兩個(gè)新個(gè)體,代替原來(lái)的“老”個(gè)體,而不交配的個(gè)體則保持不變。交配父母的染色體相互交換,從而產(chǎn)生兩個(gè)新的染色體,第一個(gè)個(gè)體前半段是父親的染色體,后半段是母親的,第二個(gè)個(gè)體則正好相反。不過(guò)這里的半段并不是真正的一半,這個(gè)位置叫做交配點(diǎn),也是隨機(jī)產(chǎn)生的,可以是染色體的任意位置。再下一步是突變,通過(guò)突變產(chǎn)生新的“子”個(gè)體。一般遺傳算法都有一個(gè)固定的突變常數(shù)(又稱為變異概率),通常是0.1或者更小,這代表變異發(fā)生的概率。根據(jù)這個(gè)概率,新個(gè)體的染色體隨機(jī)的突變,通常就是改變?nèi)旧w的一個(gè)字節(jié)(0變到1,或者1變到0)。經(jīng)過(guò)這一系列的過(guò)程(選擇、交配和突變),產(chǎn)生的新一代個(gè)體不同于初始的一代,并一代一代向增加整體適應(yīng)度的方向發(fā)展,因?yàn)樽詈玫膫€(gè)體總是更多地被選擇去產(chǎn)生下一代,而適應(yīng)度低的個(gè)體逐漸被淘汰掉。這樣的過(guò)程不斷重復(fù):每個(gè)個(gè)體被評(píng)價(jià),計(jì)算出適應(yīng)度,兩個(gè)個(gè)體交配,然后突變,產(chǎn)生第三代。周而復(fù)始,直到終止條件滿足為止。一般終止條件有以下幾種:①進(jìn)化次數(shù)限制;②計(jì)算耗費(fèi)的資源限制(例如計(jì)算時(shí)間、計(jì)算占用的內(nèi)存等);③一個(gè)個(gè)體已經(jīng)滿足最優(yōu)值的條件,即最優(yōu)值已經(jīng)找到;④適應(yīng)度已經(jīng)達(dá)到飽和,繼續(xù)進(jìn)化不會(huì)產(chǎn)生適應(yīng)度更好的個(gè)體;⑤人為干預(yù);⑥以及以上兩種或更多種的組合。

遺傳算法在解決優(yōu)化問(wèn)題過(guò)程中有如下特點(diǎn):①遺傳算法在適應(yīng)度函數(shù)選擇不當(dāng)?shù)那闆r下有可能收斂于局部最優(yōu),而不能達(dá)到全局最優(yōu)。②初始種群的數(shù)量很重要,如果初始種群數(shù)量過(guò)多,算法會(huì)占用大量系統(tǒng)資源,如果初始種群數(shù)量過(guò)少,算法很可能忽略掉最優(yōu)解。③對(duì)于每個(gè)解,一般根據(jù)實(shí)際情況進(jìn)行編碼,這樣有利于編寫(xiě)變異函數(shù)和適應(yīng)度函數(shù)(Fitness Function)。④在編碼過(guò)的遺傳算法中,每次變異的編碼長(zhǎng)度也影響到遺傳算法的效率,如果變異代碼長(zhǎng)度過(guò)長(zhǎng),變異的多樣性會(huì)受到限制,如果變異代碼過(guò)短,變異的效率會(huì)非常低下,選擇適當(dāng)?shù)淖儺愰L(zhǎng)度是提高效率的關(guān)鍵。⑤變異率也是一個(gè)重要的參數(shù)。⑥對(duì)于動(dòng)態(tài)數(shù)據(jù),用遺傳算法求最優(yōu)解比較困難,因?yàn)槿旧w種群很可能過(guò)早地收斂,而對(duì)以后變化了的數(shù)據(jù)不再產(chǎn)生變化,對(duì)于這個(gè)問(wèn)題,研究者提出了一些方法增加基因的多樣性,從而防止過(guò)早的收斂。其中一種是所謂觸發(fā)式超級(jí)變異,就是當(dāng)染色體群體的質(zhì)量下降(彼此的區(qū)別減少)時(shí)增加變異概率,另一種叫隨機(jī)外來(lái)染色體,是偶爾加入一些全新的隨機(jī)生成的染色體個(gè)體,從而增加染色體多樣性。⑦選擇過(guò)程很重要,但交叉和變異的重要性存在爭(zhēng)議,一種觀點(diǎn)認(rèn)為交叉比變異更重要,因?yàn)樽儺悆H僅是保證不丟失某些可能的解,而另一種觀點(diǎn)則認(rèn)為交叉過(guò)程的作用只不過(guò)是在種群中推廣變異過(guò)程所造成的更新,對(duì)于初期的種群來(lái)說(shuō),交叉幾乎等效于一個(gè)非常大的變異率,而這么大的變異很可能影響進(jìn)化過(guò)程。⑧遺傳算法很快就能找到良好的解,即使是在很復(fù)雜的解空間中。⑨遺傳算法并不一定總是最好的優(yōu)化策略,優(yōu)化問(wèn)題要具體情況具體分析,所以在使用遺傳算法的同時(shí),也可以嘗試其他算法,互相補(bǔ)充,甚至根本不用遺傳算法。⑩遺傳算法不能解決那些“大海撈針”的問(wèn)題,所謂“大海撈針”問(wèn)題就是沒(méi)有一個(gè)確切的適應(yīng)度函數(shù)表征個(gè)體好壞的問(wèn)題,使得算法的進(jìn)化失去導(dǎo)向。??????對(duì)于任何一個(gè)具體的優(yōu)化問(wèn)題,調(diào)節(jié)遺傳算法的參數(shù)可能會(huì)有利于更好的更快的收斂,這些參數(shù)包括個(gè)體數(shù)目、交叉率和變異率,例如太大的變異率會(huì)導(dǎo)致丟失最優(yōu)解,而過(guò)小的變異率會(huì)導(dǎo)致算法過(guò)早的收斂于局部最優(yōu)點(diǎn),對(duì)于這些參數(shù)的選擇,現(xiàn)在還沒(méi)有實(shí)用的上下限。

本章將這種方法用到降水徑流回歸模型上,與傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)模型、線性回歸模型等進(jìn)行擬合精度比較,獲得了滿意的效果。

3.2.2　遺傳程序設(shè)計(jì)的步驟

遺傳程序設(shè)計(jì)的具體步驟如下。

步驟1 明確目標(biāo)函數(shù)。假設(shè)X={(x11,x12,…,x1m),(x21,x22,…,x2m),…,(xn1,xn2,…,xnm)}為輸入樣本系列,X'={x'1,x'2,…,x'n}為輸出樣本系列。遺傳程序計(jì)算的目的就是最終尋找最佳函數(shù)表達(dá)式G(c,x1,…,xm),使誤差極小化

式中c——實(shí)常數(shù)。

步驟2 表達(dá)式編碼。將變量x、常數(shù)c、運(yùn)算符和基本函數(shù)進(jìn)行編碼,并形成集合D,其可細(xì)分為終端集T和函數(shù)集F。終端集T的元素為變量x、常數(shù)c,函數(shù)集F的元素為運(yùn)算符以及基本函數(shù)關(guān)系,這里為算術(shù)運(yùn)算{+,-,×,÷}和初等函數(shù){sin,cos,arctan,arccot}。表3.1為本書(shū)的編碼方案,即如果出現(xiàn)編碼值為0則在區(qū)間[-1,1]上隨機(jī)的選取一個(gè)數(shù);如果出現(xiàn)編碼值為1,那么程序隨機(jī)選擇xi(i=1,2,…,m)。稱函數(shù)G(c,x1,…,xm)為遺傳程序設(shè)計(jì)問(wèn)題的染色體,可以使用二叉樹(shù)的形式進(jìn)行表示,如圖3.1所示。

步驟3 初始化染色體。通過(guò)選擇集合D、T、F元素產(chǎn)生初始染色群體,即二叉樹(shù),樹(shù)的根節(jié)點(diǎn)我們從函數(shù)集F所對(duì)應(yīng)的編碼值中隨機(jī)進(jìn)行選取,其中間結(jié)點(diǎn)則在集合D對(duì)應(yīng)的編碼值中隨機(jī)進(jìn)行選擇,而葉節(jié)點(diǎn)就在終端集T所對(duì)應(yīng)的編碼值中隨機(jī)進(jìn)行選擇。假設(shè)染色體群體規(guī)模是N,則將生成N棵二叉樹(shù),取這些樹(shù)的最大深度(即層數(shù))在4～6之間,其目的是方便對(duì)表達(dá)式進(jìn)行分析解釋。

步驟4 評(píng)價(jià)父代群體。將初始父代染色群體解碼后,代入式(3.1),計(jì)算出各染色體所對(duì)應(yīng)的目標(biāo)函數(shù)值f(i),i=1,2,…,N,根據(jù)f(i)的大小判斷染色體的優(yōu)劣,函數(shù)值小的個(gè)體為較優(yōu)秀個(gè)體,根據(jù)優(yōu)劣情況對(duì)染色體群進(jìn)行排序,優(yōu)良染色體排在前面,則定義第i個(gè)父代染色體的適應(yīng)度函數(shù)值F(i)為

步驟5 遺傳運(yùn)算。對(duì)父代染色體進(jìn)行選擇、交叉、變異的遺傳運(yùn)算。其中選擇操作按比例從父代中選取染色體,父代個(gè)體i被選擇的概率按下式計(jì)算:

設(shè):p(0)=0,p(i)=s(1)+s(2)+…+s(N)。利用計(jì)算機(jī)生成均勻分布隨機(jī)數(shù)u∈[0,1],如果u屬于區(qū)間[p(i-1),p(i)]中,則第i個(gè)染色體被選取。此外,為提高全局搜索的能力,本書(shū)直接選取最優(yōu)秀的5個(gè)父代染色體復(fù)制到子代中。

交叉操作是要隨機(jī)的在兩棵父代二叉樹(shù)選取交叉點(diǎn),而后把以交叉點(diǎn)為根節(jié)點(diǎn)的子樹(shù)進(jìn)行相互交換。

變異操作是在選取的染色體中隨機(jī)產(chǎn)生一個(gè)變異點(diǎn),以變異點(diǎn)為根節(jié)點(diǎn),將其以下的子樹(shù)(包括變異點(diǎn))按照步驟3的方式隨機(jī)產(chǎn)生一棵子樹(shù)來(lái)代替。

各種遺傳操作都依據(jù)相應(yīng)的操作概率執(zhí)行:假設(shè)選擇操作概率為ps,交叉操作概率為pc,那么變異操作概率就是pm=1-ps-pc。利用計(jì)算機(jī)生成均勻分布隨機(jī)數(shù)u∈[0,1],如果u≤ps,則進(jìn)行遺傳運(yùn)算進(jìn)行選擇操作,如果ps<u≤(ps+pc),則遺傳運(yùn)算進(jìn)行交叉操作,如果u>(ps+pc)則進(jìn)行變異操作。進(jìn)行N-5次操作,就完成1次進(jìn)化迭代過(guò)程,生產(chǎn)出新的染色體群。

步驟6 尋優(yōu)最佳染色體。每次迭代中保留最佳染色體,并且產(chǎn)生新的子代染色體群,然后依據(jù)步驟4,進(jìn)行反復(fù)演化,一直到其進(jìn)化迭代次數(shù)大于之前的預(yù)設(shè)值,或目標(biāo)函數(shù)值優(yōu)于預(yù)設(shè)值,這時(shí)結(jié)束程序運(yùn)行,計(jì)算過(guò)程完成。此時(shí)的最佳染色體即為尋優(yōu)結(jié)果。

3.2.3　基于遺傳程序設(shè)計(jì)的產(chǎn)流預(yù)報(bào)模型

由于難以全面掌握流域各項(xiàng)物理參數(shù),根據(jù)降水徑流關(guān)系進(jìn)行產(chǎn)流計(jì)算是常用方法。影響降雨徑流關(guān)系的主要因素有前期影響雨量Pa,降雨歷時(shí),降雨強(qiáng)度,暴雨中心位置等,可以通過(guò)流域中分布的各個(gè)雨量站測(cè)得的雨情分析流域平均面雨量,并根據(jù)歷史數(shù)據(jù),利用遺傳程序設(shè)計(jì)建立面雨量、前期影響雨量與徑流深R的關(guān)系,即P—Pa—R模型,逐時(shí)段計(jì)算變化的前期影響雨量Pa的值,逐時(shí)段計(jì)算出凈雨,即徑流深R,得出凈雨過(guò)程。具體模型如下。

(1)計(jì)算流域時(shí)段t平均面雨量。

式中 Pt——流域t時(shí)段平均面雨量,mm;

Pi,t——流域t時(shí)段第i個(gè)雨量站實(shí)測(cè)雨量,mm;

wi——第i個(gè)雨量站的權(quán)重。

(2)計(jì)算流域前期影響雨量。如果流域內(nèi)前后兩天無(wú)雨,則前期影響雨量由式(3.5)計(jì)算:

式中 Pa,t——流域t時(shí)段前期影響雨量,mm;

K——土壤含水量的消退系數(shù)。

若第t-1時(shí)段內(nèi)有降水Pt-1,但未形成徑流,則:

若第t-1時(shí)段內(nèi)有降水Pt-1,并形成徑流Rt-1,則:

(3)基于遺傳程序建立回歸模型。

式中 f(·)——遺傳程序形成的降水徑流關(guān)系函數(shù)。