張春濤 向瑞銀 任友俊

（1.重慶三峽學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，重慶萬州 404100）

（2.曲靖師范學(xué)院計算機(jī)科學(xué)與工程學(xué)院，云南曲靖 655011）

遺傳算法(Genetic Algorithm，簡稱GA)是一種更為宏觀意義下的仿生算法，它模仿的機(jī)制是一切生命與智能的產(chǎn)生與進(jìn)化過程.它通過模擬達(dá)爾文“優(yōu)勝劣汰、適者生存”的原理激勵好的結(jié)構(gòu)；通過模擬孟德爾遺傳變異理論在迭代過程中保持己有的結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu).它是近年來開始得到廣泛關(guān)注的一種新型非數(shù)值優(yōu)化算法，具有智能性搜索、并行式計算和全局優(yōu)化等優(yōu)點，沒有傳統(tǒng)的建立在梯度計算基礎(chǔ)上優(yōu)化算法的缺點，特別適合于求解目標(biāo)函數(shù)的多極值點問題.[3]

1 遺傳算法在最佳一致逼近中的應(yīng)用

求解函數(shù)的最佳一致逼近多項式，關(guān)鍵是確定n次多項式p ( x )的系數(shù)，即求p(x) = a0+a1x +…+anxn中的系數(shù)a0,a1,…,an.我們可以直接對這些系數(shù)編碼，進(jìn)行遺傳操作.但當(dāng)系數(shù)較多，即逼近多項式的次數(shù)較高，且原函數(shù)的值較大，則使得系數(shù)的取值范圍增大，為了達(dá)到理想的精度，則使遺傳算法中的個體長度積聚增加，這十分不利于算法的操作.但是我們利用最佳一致逼近的特點：逼近函數(shù)與被逼近函數(shù)有不同的交點（交點個數(shù)與逼近函數(shù)的次數(shù)有關(guān)）.因此，我們改為尋找交點，然后用這些交點的插值函數(shù)無限地逼近被逼近函數(shù).顯然把決策變量改為交點組時的個體長度遠(yuǎn)遠(yuǎn)小于決策變量是系數(shù)時個體的長度，因為區(qū)間是固定的，還可通過縮放區(qū)間來減小個體編碼長度，并且我們可以用插值函數(shù)來進(jìn)行誤差分析.

1.1 算法描述

1.1.1 編碼：由問題的描述，我們采用二進(jìn)制編碼方法，即每個系數(shù) ai或每個插值節(jié)點 xi(i = 0,1,2,…,n)用固定的k（要經(jīng)過具體函數(shù)在定義區(qū)間中的值來決定）位二進(jìn)制位來表示，因此一個個體要(n+1)*k位二進(jìn)制位表示，即個體的編碼長度l = (n+1)*k.

1.1.2 初始群體的確定.設(shè)群體規(guī)模N = 100，初始群體中的個體用隨機(jī)的方法產(chǎn)生.

1.1.3 確定適應(yīng)值函數(shù) G (x).我們直接計算fabs (f(a) - p(a))的值，其中a是f(x) - p(x)在定義區(qū)間中的最大值點，此時 p(x)是由給定的個體解碼得到對應(yīng)的系數(shù)或個體解碼得到插值節(jié)點而定.

1.1.4 選擇算子.我們采用比例選擇算子，即個體在下一代群體中的個數(shù)由該個體的適應(yīng)值在種群總的適應(yīng)值中的比例來決定.

1.1.5 交叉算子.我們采用兩點交叉算子，交叉概率pc為0.7 ＜ pc＜ 0.95.

1.1.6 變異算子.我們采用基本位變異算子，變異概率pm為0.001 ＜ pm＜ 0.1.

1.1.7 終止條件.取最大迭代次數(shù)T ＜ 100或插值誤差充分小.

1.2 仿真實驗

例1.求函數(shù)f(x)=ex在 [-1,1] 上的二次多項式逼近.

顯然最佳逼近多項式 p(x) 具有如下形式：p(x) = a0+a1x+a2x2，我們分別用雷米茲方法、遺傳算法和切比雪夫節(jié)點插值法對其求解，結(jié)果如表1所示：

表1 ex的二次最佳一致逼近

例2.求函數(shù)f(x) = ex在[-1,1]上的三次多項式逼近 p(x) = a0+a1x+a2x2+a3x3.

此時，在用遺傳算法求解時，不直接求其系數(shù)，改為求交點，然后用拉格朗日進(jìn)行節(jié)點插值.則

我們分別用雷米茲方法、遺傳算法和切比雪夫節(jié)點插值法對其求解，結(jié)果如表2所示：

表2 ex的三次最佳一致逼近

例3.求函數(shù)f(x) = e(x/2)*sin(x)*cos(x/5)在[-1,1]上的三次多項式逼近.

此時的逼近函數(shù) p (x) 有如下形式：

仍采用上面的三種算法進(jìn)行求解，結(jié)果見表3：

表3 f(x)的三次多項式逼近

我們畫出逼近函數(shù)和被逼近函數(shù)的圖形，如圖1所示：（其中*是f(x)的圖形，虛線是p(x)的圖形）

圖1 函數(shù)和逼近多項式的圖象

從上面的三個示例可以看出用雷米茲方法求解函數(shù)的最佳一致逼近多項式有很快的收斂速度和很高的精度，但對初始點組有依賴性，計算較復(fù)雜，而用遺傳算法求解收斂也較快，精度也較高，而且當(dāng)逼近函數(shù)的階較高時，逼近函數(shù)能很好地表示被逼近函數(shù).

2 遺傳算法在最佳平方逼近中的應(yīng)用

前面介紹的最佳一致逼近考慮的是整個區(qū)間上絕對誤差的最大值，計算量一般較大.同時，對于那些僅有個別小區(qū)段上有較大誤差的函數(shù)，反而不能很好地反映其真實情況，因為它過于遷就原函數(shù)的某一峰值，造成逼近函數(shù)整體上偏離被逼近函數(shù)（原函數(shù)）.

求解最佳平方逼近函數(shù)的傳統(tǒng)算法很多，下面我們用遺傳算法來求解.

2.1 算法描述

2.2 仿真實驗

例4.求f (x) = ex,x∈[0,1]的最佳二次平方逼近多項式.計算結(jié)果如表4.

表4 平方逼近和一乘逼近

3 遺傳算法在最小一乘逼近中的應(yīng)用

當(dāng)原函數(shù)的峰值較多且較突時，由最佳平方逼近的計算可知，它放大了逼近函數(shù)和被逼近函數(shù)的誤差，使逼近函數(shù)遷就被逼近函數(shù)的某些峰值而偏離被逼近函數(shù).下面我們用另一近似標(biāo)準(zhǔn)，即1-范數(shù)的最小一乘逼近.

定義2.f (x)∈C [a, b]，則f(x)的1-范數(shù)定義為：

在C [a,b]中定義了1-范數(shù)后，C [a,b]就成為一種線性賦范空間.最小一乘逼近問題可描述為：

由于1-范數(shù)的不可微性，使得求解最小一乘逼近函數(shù)較難，因為傳統(tǒng)的優(yōu)化算法一般要基于梯度的信息.遺傳算法不需要梯度信息，只要目標(biāo)函數(shù)可計算就行，因此我們可以用遺傳算法來計算最小一乘逼近函數(shù).

3.1 算法描述

3.2 仿真實驗

例5.求f(x) = ex，x∈[0,1]的最小一乘逼近二次多項式.計算結(jié)果如表4所示.

例6.求f(x) = sin(x) + 6xex，χ∈[0,1]的最小一乘和最佳平方逼近二次多項式.結(jié)果如表5所示.

表5 最小一乘和最佳平方逼近多項式

從表4和表5可以看出使用遺傳算法能較方便的求解出函數(shù)的最佳平方和最小一乘逼近多項式。

4 結(jié)論

本文討論了遺傳算法在最佳一致逼近、最佳平方逼近和最小一乘逼近中的應(yīng)用，根據(jù)遺傳算法基本與問題的復(fù)雜程度無關(guān)和不需目標(biāo)函數(shù)可導(dǎo)等一些輔助信息的特性，找到了求解1-范數(shù)的最小一乘逼近問題的有效算法.我們用遺傳算法求解了基于三種范數(shù)的逼近函數(shù)，效果較明顯，最重要的是可以將該求解方法推廣到基于任何范數(shù)的逼近函數(shù)和任意范數(shù)的數(shù)據(jù)擬合上去，當(dāng)然操作策略可以改進(jìn)，從而不必為每種范數(shù)逼近問題設(shè)計各自不相關(guān)的算法.

[1]馬振華.現(xiàn)代應(yīng)用數(shù)學(xué)手冊 計算方法分冊[M].北京：北京出版社，1990.

[2]楊大地，涂光裕.數(shù)值分析[M].重慶：重慶大學(xué)出版社，1998.

[3]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1999.

[4]張春濤.遺傳算法在信息論中的應(yīng)用[J].重慶三峽學(xué)院學(xué)報，2008（3）.