基因的gep的函數建模

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