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

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

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