基于二叉樹編碼的數(shù)據(jù)擬合

基于二叉樹編碼的數(shù)據(jù)擬合

1.基于二叉樹編碼的數(shù)據(jù)擬合在科學研究和科學研究中，通常需要分析收集的數(shù)據(jù)，并從它們中獲得自變量x、x、。。。xn和y型資源向量分析方案，即數(shù)據(jù)調(diào)整，是傳統(tǒng)的算法。特別是對于高階多項式和多自變量（即多維空間）的情況，計算過程復(fù)雜，操作最大，得到的結(jié)果精度不高。鑒于上述考慮,我們嘗試采用二叉樹編碼的遺傳算法來進行數(shù)據(jù)擬合.充分利用遺傳算法廣搜索空間和只關(guān)注目標函數(shù)信息,而不需要推導(dǎo)過程及其它信息的特性,同時利用了二叉樹的結(jié)構(gòu)特點,極大地降低了問題的復(fù)雜性和運算量,并得到了較高的精度值.2.算法的概念和實現(xiàn)2.1算法的框架設(shè)計利用二叉樹依據(jù)特定的遍歷方式與函數(shù)表達式一一對應(yīng)的特性,將滿足一定條件的隨機二叉樹作為問題的一個解.同時利用二叉樹的結(jié)構(gòu)特點——任何結(jié)點的左、右子樹仍是二叉樹——構(gòu)造特定的選擇算子、雜交算子、變異算子.首先產(chǎn)生一定數(shù)目的二叉樹群體作為問題的初始解空間,然后對二叉樹群體演化n代,每一次演化都經(jīng)過評價、選擇、雜交、變異過程,找到當前最好的二叉樹個性,并將之對應(yīng)的函數(shù)表達式作為最優(yōu)解.同時,在演化過程中,為了保持個體的多樣性,每演化一定代數(shù)m(稱之為演化周期)就新增加若干新個體(稱之為外族個體)替代原有群體中其適應(yīng)值處于整個建群體的中間部分的若干個體,以增加群體的多樣性.參數(shù)的設(shè)置仍采用人工設(shè)置方式.算法的一般框架結(jié)構(gòu)如下:2.2基本步驟(1)操作符操作數(shù)產(chǎn)生一定數(shù)目的棵隨機二叉樹(一般取100棵以上),放入二叉樹組a中.每棵二叉樹滿足下列要求:每一結(jié)點由操作數(shù)和操作符組成.操作符操作數(shù)說明:在實際當中變量的個數(shù)n需要根據(jù)具體情況而定;分支結(jié)點必須為操作符,葉子結(jié)點必須為操作數(shù);二叉樹的層數(shù)不能超過layer層(layer一般取8);每棵二叉樹的適應(yīng)值存在(采用最小二乘誤差),且要求其適應(yīng)值不超過1E+8.適應(yīng)值求法(適應(yīng)值越小,則該二叉樹越好):∑(f(x1,x2,x3,…,xn)-y)2其中f為與二叉樹對應(yīng)的函數(shù),y為真實值.(2)累積概率法Ⅰ.求出每棵二叉樹的適應(yīng)值,并將二叉樹數(shù)組a中的元素按適應(yīng)值從小到大的順序排列;Ⅱ.保留二叉樹群體中最好的bs棵和最壞的bs棵(bs的值一般取群體規(guī)模的百分之五,我們稱之為保留數(shù)),求出中間二叉樹的選擇概率、累積概率,然后根據(jù)累積概率確定中間的二叉樹.方法如下;為每一棵中間二叉樹產(chǎn)生一隨機小數(shù)r,若acc[i-1]<i<acc[i](acc為存放累積概率的數(shù)組,i為當前二叉樹在數(shù)組中的位置),則將第i棵二叉樹保留下來,經(jīng)過這樣的選擇之后,產(chǎn)生的新群體中可能含有相同的二叉樹,從而體現(xiàn)了優(yōu)質(zhì)個體在演化過程中看作有較強的生存能力.選擇概率的求法:求出所有的中間二叉樹的適應(yīng)值的倒數(shù)總和sum,則二叉樹a[i]的選擇概率select[i]為:(1/s[i])sum(s[i]為第i棵二叉樹的適應(yīng)值);累積概率的求法:accu[i]=∑select[j]:(k<=j<=i,k為二叉樹數(shù)組中第一棵中間二叉樹的位置)(3)生成相應(yīng)的群體適應(yīng)值的隨機二叉樹.判斷當前演化的代數(shù)是否為演化周期的整數(shù)倍.若是,則產(chǎn)生一定數(shù)目的滿足條件的隨機二叉樹(也即外族個體,一般為群體規(guī)模的五分之一)代替原來群體當中適應(yīng)值處于中間部分的個體.(4)兩叉樹雜交后的狀態(tài)I.雜交樹的選取:給每棵二叉樹產(chǎn)生-0～1之間的隨機小數(shù),若該隨機小數(shù)小于雜交率,則選中該棵二叉樹,然后對選中的二叉樹序列按照選中的先后次序每相鄰兩棵進行雜交.若最后剩余一棵,則丟掉.Ⅱ.兩棵二叉樹的雜交過程:為兩棵二叉樹隨機選擇雜交點(可以為二叉樹中的任意結(jié)點).將以兩雜交點為根結(jié)點的二叉樹相互交換;若雜交后的二叉樹超過layer層,則截斷,并且第layer層的二叉樹結(jié)點由產(chǎn)生的隨機操作數(shù)代替;若經(jīng)過上述過程后,二叉樹的適應(yīng)值不存在或大于1E+8,則丟掉該棵二叉樹,并產(chǎn)生一棵符合要求的隨機二叉樹代替(見初始化二叉樹部分說明).(5)隨機選擇的變異點為模擬中心的點Ⅰ.變異樹的選取:給每棵二叉樹產(chǎn)生一隨機小數(shù),若該隨機小數(shù)小于變異率,則選中該棵二叉樹,并對其進行變異操作;Ⅱ.變異過程:隨機選擇變異點(可以為二叉樹中中的任意結(jié)點);變異點的處理:i.若隨機選擇的變異點為葉子結(jié)點,則從下面兩種處理方式中隨機選擇一種;葉子結(jié)點ii.若隨機選擇的變異點為分枝結(jié)點,則根據(jù)其類型從該燈型的處理方式中隨機選擇一種進行處理.分枝結(jié)點為一元運算符:以不同于原來值的隨機一元運算符代替.分枝結(jié)點為二元運算符若結(jié)過變異后的二叉樹的適應(yīng)值不存在,或其適應(yīng)值大于1E+8,則丟掉該棵二叉樹,并產(chǎn)生一棵適應(yīng)值滿足條件的隨機二叉樹代替(見初始化二叉樹部分說明).Ⅲ.將二叉樹群體按照適應(yīng)值從小到大的順序進行排序,并保留群體演化至此適應(yīng)值最小的二叉樹個體.然后對演化代數(shù)進行判斷,若演化代數(shù)不少于n,則轉(zhuǎn)(6),否則轉(zhuǎn)(2).(6)報告的結(jié)果將演化n代后的當前二叉樹群體當中適應(yīng)值最小的二叉樹作為最優(yōu)解,顯示該二叉樹對應(yīng)的函數(shù)表達式、演化代數(shù)、參數(shù)設(shè)置及適應(yīng)值的大小.2.3叉樹最大深度、10.4%、10.7e-326e-熱價值的計算為了驗證算法的可行性,我們用C語言將該算法編寫成程序,并對以下三維空間上20組實驗點進行了測試.實驗點(X,Y,Z):(-0.8,-0.4,0.447)(-0.4,-0.4,0.825)(0.0,0.8,0.600)(0.6,-0.8,0.000)(-0.8,-0.2,0.566)(-0.4,-0.6,0.693)(0.0,1.0,0.000)(0.6,-0.6,0.529)(-0.8,0.0,0.600)(-0.4,-0.8,0.477)(0.2,-0.8,0.566)(0.6,-0.4,0.693)(-0.8,-0.2,0.566)(-0.4,-0.8,0.566)(0.2,-0.6,0.775)(0.6,-0.2,0.775)(-0.8,-0.4,0.447)(-0.2,-0.6,0.775)(0.2,-0.4,0.894)(0.6,0.0,0.800)在取參數(shù)(群體規(guī)模=500,二叉樹最大深度=8,二叉樹的允許的最大適應(yīng)值1E+8,外族群體=20,演化周期=3,保留數(shù)=5,雜交概率=0.6,變異概率=0.2)運行程序,演化第20代得到結(jié)果,其數(shù)學表達式為:0.62816+x2*y其適應(yīng)值為:7.90436E-01.3.動態(tài)參數(shù)方法與用數(shù)值分析的方法進行數(shù)據(jù)擬合相比,采用基于二叉樹編碼的遺傳算法極大的降低了問題的復(fù)雜度和運算量.同時,外族個體的引進及最優(yōu)解的保留增加了群體的多樣性,擴大了解空間,并保留了群體