基因的gep的函數(shù)建模

基因的gep的函數(shù)建模

基于遺傳程序設(shè)計的復(fù)雜模型在科學(xué)領(lǐng)域，人們通常需要分析和結(jié)論其內(nèi)部規(guī)律，即函數(shù)建模。函數(shù)建模問題可以描述為：對于給定的數(shù)據(jù)(xi,yi)；i=1,2，…，m)，要求在某個函數(shù)類的集合中尋找一個函數(shù)Φ(x)，使得Φ(xi)盡量逼近yi。求解建模問題的傳統(tǒng)方法有數(shù)據(jù)擬合、回歸分析和逼近論等。這些方法需要先選擇一個模型f(x,w)，然后再去確定模型中的參數(shù)w，從而擬合、逼近已知數(shù)據(jù)。顯然，模型的選擇是至關(guān)重要的，而這需要用到特定領(lǐng)域的專門知識。而且當(dāng)模型結(jié)構(gòu)很復(fù)雜時，即使掌握了問題的背景知識，選擇一個合適的模型以及進行參數(shù)估計也是很困難的。針對傳統(tǒng)方法在處理建模問題時的局限性，遺傳程序設(shè)計（GeneticProgramming,GP）提供了一種可行的自動建模方法。它采用樹結(jié)構(gòu)來表示函數(shù)，通過雜交、變異等遺傳操作去改變這些樹結(jié)構(gòu)，并一代代地演化下去直到獲得合適的解。這種方法不需要了解特定領(lǐng)域的專業(yè)知識，利用遺傳算法的自適應(yīng)性和自學(xué)習(xí)性進行搜索，在函數(shù)自動建模方面取得較好的效果。但是，遺傳程序設(shè)計采用樹結(jié)構(gòu)作為編碼，這種不定長的復(fù)雜編碼需要龐大的存儲空間，遺傳操作也復(fù)雜，而且容易產(chǎn)生無效的語法樹?；虮磉_式程序設(shè)計（GeneExpressionProgramming,GEP）是葡萄牙學(xué)者CandidaFerreira于2000年首次提出的，它是一種新穎的遺傳算法，采用等長線性符號作為遺傳編碼，易于遺傳操作，而個體表現(xiàn)型則對應(yīng)于樹結(jié)構(gòu)，因此具有用簡單的編碼解決復(fù)雜問題的優(yōu)點。GEP在函數(shù)自動建模方面體現(xiàn)了優(yōu)越的性能。1gep的基本原則1.1函數(shù)符號的生成GEP的遺傳編碼是等長的線性符號串，稱為GEP染色體。一個染色體可以由多個基因組成。每個GEP基因由頭部和尾部組成，頭部可以包含終結(jié)符和函數(shù)符號，而尾部只能包含終結(jié)符。終結(jié)符是指程序中的輸入，常量以及沒有參數(shù)的函數(shù)。函數(shù)符號可以是相關(guān)問題領(lǐng)域中的運算符號（如+，-，*，\，sin,cos,ln等），也可以是程序設(shè)計中的一個程序構(gòu)件。頭部的長度h通常依具體問題而定，而尾部的長度t則由以下公式得到：是一個合法的GEP基因，其中黑體表示尾部。要把GEP基因解碼為表達式樹，應(yīng)按照從左到右的順序逐一讀取基因中的字符，然后根據(jù)語法規(guī)則按照層次順序排放即可。公式（2）表示如下的表達式樹。在這個例子中，尾部的最后一個字符b并沒有出現(xiàn)在表達式樹中，即有效的基因片段只有12個字符，則稱該基因的有效長度為12。如果上述基因的頭部第4位發(fā)生變異，“S”變成了“+”，則變成如下的基因：其對應(yīng)的表達式樹則變成：在這種情況下，基因中所有的符號都出現(xiàn)在表達式樹中，則該基因的有效長度為13。1.2gep中的評價能否成功求出問題的解在很大程度上取決于適應(yīng)度函數(shù)的設(shè)計，適應(yīng)度函數(shù)將指導(dǎo)程序演化的方向。對于函數(shù)建模問題，程序的最后解答是一個表達式，對該表達式的評價就是指利用該表達式計算得到的數(shù)據(jù)與訓(xùn)練數(shù)據(jù)的吻合程度。在GEP中，通常采用殘差平方和作為評價標(biāo)準(zhǔn)，或者采用均方差作為評價標(biāo)準(zhǔn)。設(shè)有m個樣本值（Xi,Yi），Φ(x)表示某個個體（染色體），則殘差平方和Q為：均方差為個體Φ(x)的適應(yīng)度函數(shù)為：或者顯然，適應(yīng)值越小，表示誤差越小，該個體就越優(yōu)。算法停機條件是：群體中最優(yōu)個體的適應(yīng)值達到預(yù)期的誤差范圍或者程序的演化代數(shù)達到預(yù)定的演化代數(shù)。2提高算法2.1計算有效長度GEP的編碼形式是等長線性符號，表現(xiàn)型是表達式樹。根據(jù)表達式樹，可以計算出基因表達式的值。文獻介紹了構(gòu)造表達式樹的層次法，然而建立樹的過程是復(fù)雜和繁瑣的。文獻提出了一種新的計算方法——基因閱讀運算器（GRCM）。這種方法不需要構(gòu)造樹，直接閱讀有效長度內(nèi)的基因片段就能計算出該基因所表示的函數(shù)的值。但是文獻并沒有給出有效長度的計算方法，若用構(gòu)造樹的方法來確定有效長度，則GRCM的高效性就大打折扣。GEP基因由頭部和尾部兩部分組成，但并非基因中所有的字符都有用。如公式（2）表示的基因的有效長度為12，而公式（3）表示的基因的有效長度為13。本文給出了計算有效長度的偽代碼，用簡單的方法計算出基因的有效長度，而不需要把基因解碼為表達式樹。然后結(jié)合GRCM方法，快速計算出染色體的適應(yīng)值。其有效長度的計算過程如圖3所示：剛開始，e和p都指向基因第一位“+”，因為p指向雙目運算符，則e向后移兩位；然后p后移一位，指向單目運算符“S”，則e相應(yīng)后移一位；p再后移一位，指向終結(jié)符“a”，則e保持不邊；p再后移，指向雙目運算符“*”，則e后移兩位。p再后移，超出了基因頭部長度，算法結(jié)束。此時e即為該基因的有效長度，也即e指向有效基因片段的最后一個基因位。算出有效基因長度后，再結(jié)合GRCM方法，可以快速計算出基因的適應(yīng)值。首先從有效基因長度內(nèi)的最后一個運算符“*”開始，讀取有效基因片段的最后兩個基因位結(jié)合該運算符進行運算，把計算結(jié)果取代該運算符，并將該位標(biāo)志為終結(jié)符，然后基因有效長度減2。依次類推，直到有效長度為1，則基因的第1位中存放的即是該基因的適應(yīng)值。改進后的算法從計算基因有效長度到最后算出基因的適應(yīng)值，都不需要轉(zhuǎn)換為表達式樹，非常簡單。2.2通過函數(shù)函數(shù)進行優(yōu)化在函數(shù)建模中，常量參數(shù)的處理是一個重要的部分。Ferreira在文獻中提出一種常量處理方法：事先給每個基因指定一個常量集合，保存在數(shù)組中，集合中的常量在演化過程中通過其他遺傳操作發(fā)生變化；在染色體末尾增加一段與基因尾部長度相同的整數(shù)編碼，稱為常數(shù)域，用于指向常數(shù)集合中的第幾個常數(shù)；在基因的終結(jié)符集合中增加“？”，表示對常數(shù)域的引用。假設(shè)有如下基因，其頭部長度為6。其對應(yīng)的表達式樹為從常數(shù)域中從左到右取出相應(yīng)的整數(shù),按照從上到下，從左到右的順序分別代替表達式樹中的“？”，則表達式樹變?yōu)閳D6。假設(shè)指定的常數(shù)集合為：把常數(shù)集合中相應(yīng)的常數(shù)代入其中，得到圖7:這種方法需要額外的遺傳操作對常量集合進行優(yōu)化，實現(xiàn)起來比較復(fù)雜。文獻提出了一種簡化的常量處理方法：MC方法。MC方法也是事先指定一個數(shù)值常量集合，所不同的是該常量集合在演化過程中保持不變。不必在基因尾部增加常數(shù)域，而是直接把常量集合中的每個元素作為終結(jié)符，利用GEP本身進行優(yōu)化。其中常量集合C定義為：其中δ是一個常量。集合Hn定義為則對任意的di∈Hn，都2能用C上的不超過n個函數(shù)組成的表達式表示。假設(shè)n=3，則有c1=δ,c2=3δ,c3=9δ,終結(jié)符D={a,1,2,3}。假設(shè)有以下基因其對應(yīng)的表達式樹為：然后再把樹中的1,2,3分別替換為c1,c2,c3的值即可得到最終表達式樹。文獻也對文獻的常數(shù)處理方法進行了改進：在終結(jié)符中引入符號“？”表示引用隨機常數(shù)，用一個數(shù)組保存隨機常數(shù)，譯碼時按順序用數(shù)組中的元素替換基因中的“？”。數(shù)組中常量通過專門的雜交，變異操作進行改變。這種方法不需要在基因尾部增加常數(shù)域，不需要進行二次索引。以上三種方法都是在演化過程種一邊搜索函數(shù)結(jié)構(gòu)，一邊進行參數(shù)的優(yōu)化。這就可能導(dǎo)致一些結(jié)構(gòu)良好的模型因為其中的參數(shù)不夠優(yōu)化而被淘汰掉。本文采用文獻中的常數(shù)處理方法，另外又在建模算法中加入了參數(shù)估計模塊，選擇當(dāng)前較優(yōu)的一些染色體進行參數(shù)優(yōu)化。例如演化中得到較好的個體是：則利用參數(shù)估計模塊，對其中的“？”在一定數(shù)值范圍內(nèi)進行搜索，保存得到最優(yōu)適應(yīng)值的那一組參數(shù)。2.3整個算法流程詳細的算法流程如圖9所示。3測試實驗中的公共參數(shù)設(shè)置：每個染色體由3個基因組成，每個基因的頭部長度為4，群體規(guī)模為20，最大演化代數(shù)為2000。3.1x與y關(guān)系式某公司為評估對推銷員進行培訓(xùn)的天數(shù)x與他們所獲得的業(yè)績y的數(shù)據(jù)如表1，試找出x與y的關(guān)系式。函數(shù)集O={+,-,*,/}，終結(jié)符集D={x,?}。計算得到較好的函數(shù)模型為：殘差平方和為：91.167，這比用最小二乘法得到的模型y=31.71*(1.363)x的精度要好很多。3.2模型求解結(jié)果在某個化學(xué)反映里，測得生成物得濃度y與時間t的數(shù)據(jù)表如表2，試找出t與y的關(guān)系式。試驗的函數(shù)集O={+,-,*,/,sin,cos,ln}，終結(jié)符集D={t,?}。計算得到較好函數(shù)模型為：殘差平方和為：0.0467017，均方差為0.216106與文獻中的結(jié)果進行比較見表3。文獻中還給出了另一個模型：均方差為0.129740。（我們把數(shù)據(jù)代入模型中得到的實際均方差為32.8390826。）文獻得到的模型為：4頻繁函數(shù)集文章介紹了GEP在函數(shù)建模中的應(yīng)用，給出計算有效基因的偽代碼，結(jié)合GRCM方法閱讀基因，不需要轉(zhuǎn)換為樹結(jié)構(gòu)就能快速計算出染色體的適應(yīng)值。關(guān)于常數(shù)的處理，增加了參數(shù)估計模塊，對較好模型進行參數(shù)優(yōu)化，試驗顯示這種方法是有效的。對于難以用單個函數(shù)來描述的復(fù)雜數(shù)據(jù)集，文獻提出了頻繁函數(shù)集概念，即通過函數(shù)集合來描述數(shù)據(jù)集。在未來的研究中，我們將把本文算法應(yīng)用到這樣的更復(fù)雜的數(shù)據(jù)集中。其中n表示所使用的函數(shù)集中需要變量最多的函數(shù)的參數(shù)個數(shù)。例如符號集O={+，-，