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

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

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

1 不動(dòng)點(diǎn)理論

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

本文利用同胚映射將求解n維閉包腔上函數(shù)F∶Cn→Cn的不動(dòng)點(diǎn)問(wèn)題轉(zhuǎn)化為求解n維標(biāo)準(zhǔn)單純形上函數(shù)f∶Sn→Sn的不動(dòng)點(diǎn)問(wèn)題,對(duì)轉(zhuǎn)化后的解空間進(jìn)行K2(m)剖分來(lái)求得優(yōu)化問(wèn)題的近似最優(yōu)解。

2 K2(m)剖分理論

2.1 同胚映射

利用同胚映射將n維閉包腔連續(xù)自映射的不動(dòng)點(diǎn)計(jì)算問(wèn)題都可以轉(zhuǎn)化成n維標(biāo)準(zhǔn)單純形連續(xù)自映射的不動(dòng)點(diǎn)計(jì)算問(wèn)題。

2.2 K2(m)剖分

2.3 整數(shù)標(biāo)號(hào)

設(shè)f∶Sn→Sn是的自映射,G是對(duì)Sn進(jìn)行K2(m)剖分后的的一個(gè)單純剖分,則對(duì)于每點(diǎn) y∈G0,Sn的由f確定的整數(shù)標(biāo)號(hào)函數(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)徑小于任何預(yù)先指定的正實(shí)數(shù)的K2(m)單純剖分。

3 遺傳算法的改進(jìn)

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

3.1 編碼

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

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

3.2 生成初始群體

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

3.3 交叉操作

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

(1)首先根據(jù)個(gè)體的承載單純形頂點(diǎn)的標(biāo)號(hào)將個(gè)體分類(lèi)。頂點(diǎn)標(biāo)號(hào)全部相同的為第一類(lèi),頂點(diǎn)標(biāo)號(hào)不全相同的為第二類(lèi),頂點(diǎn)標(biāo)號(hào)全不相同的為第三類(lèi),對(duì)于第三類(lèi)個(gè)體不進(jìn)行交叉操作直接進(jìn)入下一代。

若交叉后得到的個(gè)體的承載單純形的頂點(diǎn)標(biāo)號(hào)屬于第一類(lèi),則比較子代個(gè)體和父代個(gè)體的適應(yīng)度值大小。若子代的適應(yīng)度值高于父代的適應(yīng)度值,則將其和父代適應(yīng)度值高的個(gè)體遺傳到下一代;若子代個(gè)體適應(yīng)度值比父代都低,則將父代遺傳到下一代,淘汰子代個(gè)體。

若交叉后得到的個(gè)體的承載單純形的頂點(diǎn)標(biāo)號(hào)屬于第二類(lèi),則將子代個(gè)體和父代個(gè)體承載單純形的頂點(diǎn)標(biāo)號(hào)屬于第二類(lèi)的遺傳到下一代,適應(yīng)度值高的個(gè)體優(yōu)先。

3.4 變異操作

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

3.5 選擇操作

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

3.6 收斂判斷準(zhǔn)則

當(dāng)種群中的個(gè)體的承載單純形全部為全標(biāo)單純形時(shí)終止計(jì)算,輸出全標(biāo)單純形對(duì)應(yīng)的近似不動(dòng)點(diǎn)。

4 算例分析

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

其中,1≥x1≥x2≥0

步驟1：將函數(shù)的優(yōu)化問(wèn)題轉(zhuǎn)化為求解不動(dòng)點(diǎn)問(wèn)題

θ(x)在點(diǎn)(0.675 00,0.425 00)處達(dá)到極小值,對(duì)應(yīng)的函數(shù)值為-0.321 20。

步驟2：將求解C2上的函數(shù)F(x)的不動(dòng)點(diǎn)問(wèn)題轉(zhuǎn)化為求解S2上的函數(shù)f(x)的不動(dòng)點(diǎn)問(wèn)題。

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

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

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

5 結(jié)論

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

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

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

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

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

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

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

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

[7]王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社,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ìn)的自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(11)：53-55.

[10]劉立民,潘偉,龐彥軍,等.多階段復(fù)合型遺傳算法的結(jié)構(gòu)及性能研究[J].河北工程大學(xué)學(xué)報(bào)(自然科學(xué)版),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]王紅霞,高瑞貞,張京軍.基于不動(dòng)點(diǎn)理論的改進(jìn)遺傳算法[J].河北工程大學(xué)學(xué)報(bào)(自然科學(xué)版),2010, 27(3)：100-103.

[13]王則柯.單純不動(dòng)點(diǎn)算法基礎(chǔ)[M].長(zhǎng)沙：國(guó)防科技大學(xué)出版社,1993.