基于不動點算法和K2(m)剖分的遺傳算法的改進

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

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

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

1 不動點理論

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

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

2 K2(m)剖分理論

2.1 同胚映射

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

2.2 K2(m)剖分

2.3 整數標號

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

2.4 剖分網徑

K2(m)剖分的剖分網徑為

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

3 遺傳算法的改進

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

3.1 編碼

采用實數編碼,形式如下：

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

3.2 生成初始群體

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

3.3 交叉操作

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

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

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

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

3.4 變異操作

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

3.5 選擇操作

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

3.6 收斂判斷準則

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

4 算例分析

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

其中,1≥x1≥x2≥0

步驟1：將函數的優化問題轉化為求解不動點問題

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

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

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

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

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

5 結論

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

2)m值越大,剖分網徑越小,得到的最優解越精確。

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

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

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

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

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

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

[7]王小平,曹立明.遺傳算法——理論、應用與軟件實現[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.