陳煥,范志紅,高瑞貞,張京軍

(河北工程大學信息與電氣工程學院,河北邯鄲056038)

遺傳算法是一類借鑒生物界自然選擇與遺傳機理的隨機化搜索算法,具有簡單,通用,魯棒性強等特點,在函數(shù)優(yōu)化、組合優(yōu)化、自動控制、人工生命等領域得到了廣泛的應用[1-4]。然而實踐表明遺傳算法仍然存在著一些不足,如局部尋優(yōu)能力較差,存在早熟收斂問題,沒有客觀的收斂判斷準則等[5-6]。經(jīng)過對編碼方式、控制參數(shù)的確定、選擇方式和交叉機理等進行深入探究,并引入動態(tài)策略和自適應策略,在一定程度上提高了局部搜索能力,抑制了早熟現(xiàn)象[7-10]。然而針對遺傳算法客觀的收斂準則設計卻并不多見,文獻[11, 12]將不動點理論和遺傳算法結合,嘗試將種群個體的承載單純形全部轉化為全標單純形作為收斂準則,分別采用K1剖分和J1剖分來求解函數(shù)優(yōu)化問題。K2(m)剖分是比K1剖分和J1剖分更為精細的一種剖分[13],本文利用同胚映射將 n維閉包腔函數(shù)優(yōu)化問題轉化為n維標準單純形不動點問題,對轉化后的解空間進行K2(m)剖分,并與遺傳算法結合,在客觀的收斂準則下獲得優(yōu)化問題更精確的近似最優(yōu)解。

1 不動點理論

不動點理論是最近幾十年發(fā)展起來的高度非線性問題數(shù)值解的一種有效的方法。純粹數(shù)學和應用數(shù)學的許多問題都可以歸結為單純形連續(xù)自映射的不動點問題。如優(yōu)化函數(shù) θ∶Cn→C是n維閉包腔Cn的一個連續(xù)自映射函數(shù),向量 x＊∈Cn使目標函數(shù)θ(x)達到極值的充要條件為▽θ (x＊)=0。令F∶Cn→Cn,構造函數(shù)F(x)=x-▽θ(x),則求解θ(x)的零點問題轉化為求解F (x)的不動點問題。然后通過對解空間進行適當?shù)膯渭兤史?對剖分頂點進行整數(shù)標號,利用標號信息從外部或邊界人為始點沿轉軸運算經(jīng)幾乎全標單純形序列收斂到附近的全標單純形,找到近似不動點。

本文利用同胚映射將求解n維閉包腔上函數(shù)F∶Cn→Cn的不動點問題轉化為求解n維標準單純形上函數(shù)f∶Sn→Sn的不動點問題,對轉化后的解空間進行K2(m)剖分來求得優(yōu)化問題的近似最優(yōu)解。

2 K2(m)剖分理論

2.1 同胚映射

利用同胚映射將n維閉包腔連續(xù)自映射的不動點計算問題都可以轉化成n維標準單純形連續(xù)自映射的不動點計算問題。

2.2 K2(m)剖分

2.3 整數(shù)標號

設f∶Sn→Sn是的自映射,G是對Sn進行K2(m)剖分后的的一個單純剖分,則對于每點 y∈G0,Sn的由f確定的整數(shù)標號函數(shù)為：l(y)=min {j∈N0|fj(y)≤yj＞0,fj+1(y)≥yj+1},其中令n+1=0。

2.4 剖分網(wǎng)徑

K2(m)剖分的剖分網(wǎng)徑為

由式(1)可知,meshK2(m)與m成反比,只要取m足夠大,就可以得到Sn的網(wǎng)徑小于任何預先指定的正實數(shù)的K2(m)單純剖分。

3 遺傳算法的改進

在剖分區(qū)域中從一組隨機初始點出發(fā)利用整數(shù)標號信息指導算法進行尋優(yōu),對種群進行反復的交叉、變異、選擇等遺傳操作,并對已走過的全標單純形設置標志,以使種群經(jīng)過有限代進化后達到包含全局最優(yōu)解的狀態(tài)。

3.1 編碼

采用實數(shù)編碼,形式如下：

其中,x=(x1,x2,1-x1-x2),x∈S2;f(x)—個體x的函數(shù)值,f(x)=Ax,f(x)∈S2,A為三階矩陣;yi—個體的承載單純形頂點;f(yi)—頂點yi的函數(shù)值;l(yi)—個體承載單純形頂點yi的整數(shù)標號。

3.2 生成初始群體

對自映射f∶S2→S2進行K2(m)剖分,隨機生成初始種群,計算種群中每個個體 x的函數(shù)值f (x),根據(jù)頂點標號函數(shù)l(y)計算每個頂點的整數(shù)標號l(yi),并將個體的適應度值定義為目標函數(shù)值3個分量的平方和。

3.3 交叉操作

交叉算子在遺傳算法中起關鍵作用,是產(chǎn)生新個體的最主要方法,它決定了遺傳算法的全局搜索能力。本文對父代種群施加交叉算子,操作如下：

(1)首先根據(jù)個體的承載單純形頂點的標號將個體分類。頂點標號全部相同的為第一類,頂點標號不全相同的為第二類,頂點標號全不相同的為第三類,對于第三類個體不進行交叉操作直接進入下一代。

若交叉后得到的個體的承載單純形的頂點標號屬于第一類,則比較子代個體和父代個體的適應度值大小。若子代的適應度值高于父代的適應度值,則將其和父代適應度值高的個體遺傳到下一代;若子代個體適應度值比父代都低,則將父代遺傳到下一代,淘汰子代個體。

若交叉后得到的個體的承載單純形的頂點標號屬于第二類,則將子代個體和父代個體承載單純形的頂點標號屬于第二類的遺傳到下一代,適應度值高的個體優(yōu)先。

3.4 變異操作

變異算子作為主要的搜索算子保持群體的多樣性。本算法對種群施加均勻變異,對非全標單純形中的個體優(yōu)先變異。

3.5 選擇操作

每一代中的全標單純形個體直接進入下一代種群,然后采用父子混合杰出者選擇策略,以確保優(yōu)秀基因繼續(xù)遺傳。

3.6 收斂判斷準則

當種群中的個體的承載單純形全部為全標單純形時終止計算,輸出全標單純形對應的近似不動點。

4 算例分析

設群體規(guī)模為100,求下列問題的極小值。

其中,1≥x1≥x2≥0

步驟1：將函數(shù)的優(yōu)化問題轉化為求解不動點問題

θ(x)在點(0.675 00,0.425 00)處達到極小值,對應的函數(shù)值為-0.321 20。

步驟2：將求解C2上的函數(shù)F(x)的不動點問題轉化為求解S2上的函數(shù)f(x)的不動點問題。

由于函數(shù)F∶C2→C2連續(xù),則得到復合映射h°F°g∶S2→S2。即

步驟3：應用VC++編寫程序,將轉化后的解空間進行K2(m)剖分,生成初始群,對個體按照頂點標號進行分類,根據(jù)算法描述對種群反復施加交叉、變異、選擇算子,直到滿足收斂判斷準則,并利用同胚映射將得到的不動點映射為優(yōu)化問題的全局最優(yōu)解。函數(shù)θ的全標單純形分布如圖1所示。

利用同胚映射g(x)=Px,x∈S2,將改進遺傳算法得到的不動點映射到C2中。種群的初始代分布見圖2-a,當m=4時,算法在6代收斂到全標單純形,對應的全局極小點為(0.679 33, 0.421 662),函數(shù)值是-0.321 232(圖2-b);當m=8時,算法在第4代收斂到全標單純形,對應的全局極小點為(0.675 596 01,0.425 002),函數(shù)值是-0.321 250 0(圖2-c),可以看出m值越大時,個體越集中。

5 結論

1)通過引入不動點算法和K2(m)剖分,可以使遺傳算法具有客觀的收斂準則,并獲得近似最優(yōu)解。

2)m值越大,剖分網(wǎng)徑越小,得到的最優(yōu)解越精確。

[1]陳琳,黃杰,龔正虎.一種求解最小診斷代價的小生境遺傳算法[J].計算機學報,2005,28(12)：2019-2026.

[2]劉習春,喻壽益.局部快速微調(diào)遺傳算法[J].計算機學報,2006,29(1)：100-105.

[3]周杰,王蘊恒,潘洪亮.基于遺傳算法的小波神經(jīng)網(wǎng)絡DTC轉速辨識[J].黑龍江科技學院學報,2009,19 (3)：240-243.

[4]張春玉,趙延林,陳勇.混合變量遺傳算法在預應力網(wǎng)架結構中的應用[J].黑龍江科技學院學報,2009, 19(4)：306-309.

[5]朱朝艷,王建設,王學志,等.改進遺傳算法的研究現(xiàn)狀分析[J].吉林水利,2010(7)：1-4.

[6]王莉.遺傳算法的收斂性統(tǒng)一判據(jù)[J].自動化技術與應用,2001,23(6)：16-19.

[7]王小平,曹立明.遺傳算法——理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社,2002.

[8]GOLDBER G D E.Genetic algorithms in search,optimization and machine learning,reading.[M].New York：Addision -Wesley Publishing Company,inc.,1989.

[9]張京釗,江濤.改進的自適應遺傳算法[J].計算機工程與應用,2010,46(11)：53-55.

[10]劉立民,潘偉,龐彥軍,等.多階段復合型遺傳算法的結構及性能研究[J].河北工程大學學報(自然科學版),2010,27(2)：107-112.

[11]DONG Y Z,ZHANG J J,GAO R Z,et al.An improved genetic algorithm based on hk1 Subdivision and fixed point theory[C]//WANG S Y,YU L A,WEN F H,et al.Proceedings the second International Conference on Business Intelligence and Financial Engineering.Beijing：IEEE Computer Society Press,2009：222-230.

[12]王紅霞,高瑞貞,張京軍.基于不動點理論的改進遺傳算法[J].河北工程大學學報(自然科學版),2010, 27(3)：100-103.

[13]王則柯.單純不動點算法基礎[M].長沙：國防科技大學出版社,1993.