可拓聚類適應(yīng)度共享小生境遺傳算法研究

李中華， 張?zhí)┥?/p>

(中南大學(xué) 信息科學(xué)與工程學(xué)院, 410083 長沙)

?

可拓聚類適應(yīng)度共享小生境遺傳算法研究

李中華， 張?zhí)┥?/p>

(中南大學(xué) 信息科學(xué)與工程學(xué)院, 410083 長沙)

摘要:針對遺傳算法易陷入早熟收斂和全局搜索能力差等缺點(diǎn)，提出一種基于可拓理論的小生境遺傳算法. 算法首先構(gòu)造了遺傳編碼物元和可拓遺傳算子，然后通過可拓聚類方法實(shí)現(xiàn)小生境群體的劃分，結(jié)合適應(yīng)度共享技術(shù)和聚類代表個(gè)體保存策略，維持穩(wěn)定多樣的小生境. 仿真實(shí)驗(yàn)表明，該算法能可靠、快速地收斂到全局最優(yōu)解，有效避免早熟收斂，其收斂速度和求解精度均優(yōu)于簡單遺傳算法和常規(guī)小生境算法.

關(guān)鍵詞:遺傳算法；小生境；可拓聚類；適應(yīng)度共享；代表個(gè)體；早熟收斂

基本遺傳算法(SGA)是一類模擬生物進(jìn)化的智能優(yōu)化算法，已廣泛應(yīng)用于工程領(lǐng)域的優(yōu)化求解. 但大量實(shí)踐和研究表明，基本遺傳算法存在全局搜索能力差和早熟收斂等問題，被稱為基因漂移[1]. 針對這一問題, 學(xué)者提出了各種小生境遺傳算法(NGA)，但這些經(jīng)典的小生境技術(shù)均存在參數(shù)設(shè)置問題[2-5]. 這些參數(shù)的預(yù)設(shè)與優(yōu)化需要一定的先驗(yàn)知識(shí)，處置不當(dāng)將難以維持穩(wěn)定的小生境，從而限制了算法的有效運(yùn)用.

本文基于可拓理論[6]和全局性優(yōu)化考慮，提出可拓聚類適應(yīng)度共享小生境遺傳算法(ECNGA). 算法基本原理為：構(gòu)造可拓遺傳算法模型，提出遺傳信息物元編碼和可拓遺傳算子；利用可拓聚類方法對每代種群劃分形成小生境群體；根據(jù)適應(yīng)度共享機(jī)制調(diào)整個(gè)體適應(yīng)度，再種群進(jìn)化，并結(jié)合聚類小生境的代表個(gè)體保存策略，維持小生境的穩(wěn)定性和多樣性，從而有效地防止算法早熟收斂,增強(qiáng)全局搜索能力.

1可拓聚類分析

定義1設(shè)聚類Hp={R1,R2,…,Rnp}，類內(nèi)樣本個(gè)體的物元模型[6]為

對i=1,2,…,m，各物元特征Ci的屬性值分別為v1iv2i…vnpi. 令

稱類Hp各特征屬性取值區(qū)間為Vpi(Cpi)=[api,bpi].

定義Rp為類Hp的中心物元，記為

若np=1時(shí)，令Vpi(Cpi)=[ai,bi]，即各特征屬性取值為節(jié)域區(qū)間，同時(shí)令中心物元為Rp=R1.

定義2關(guān)聯(lián)度計(jì)算準(zhǔn)則[6-8]:

1)已知類Hp={R1,R2,…,Rnp}，取待聚類樣本Rx=[N,C,V]，樣本的m維特征觀測值為V=(x1,x2,…,xm)T.

2)對類Hp，計(jì)算Rx各特征屬性xi的基本關(guān)聯(lián)函數(shù)為

3)計(jì)算綜合關(guān)聯(lián)度Kx(Hp).若規(guī)定各項(xiàng)聚類特征的權(quán)重系數(shù)為λp=[λp1,λp2,…,λpm]，則

權(quán)重系數(shù)表示各項(xiàng)特征在聚類評價(jià)體系中的相對重要程度，可采用專家評價(jià)法、層次分析法或比重權(quán)數(shù)法確定[7].

關(guān)聯(lián)度Kx(Hp)表示樣本Rx與類Hp={R1,R2,…,Rnp}的關(guān)聯(lián)程度，其取值大小是判定樣本是否歸屬該類的直接依據(jù).

可拓聚類方法的基本流程如下:

Step 1按照聚類樣本的指標(biāo)或維數(shù)建立物元模型為

Step 2初始化聚類. 將待聚類物元按某種規(guī)則排序(例如遺傳優(yōu)化的適應(yīng)度排序)，并產(chǎn)生一隨機(jī)數(shù)k(1

Step 3依次取剩余樣本Rx，計(jì)算Rx對類Hp(p=1,2,…,k)的關(guān)聯(lián)度Kx(H1),Kx(H2),…,Kx(Hk).

Step 4判定待聚類樣本Rx的類屬. 令Kx(Hq)=max{Kx(H1),Kx(H2),…,Kx(Hk)}. 若Kx(Hq)>0，則Rx屬于類Hq；Kx(Hq)=0，可認(rèn)為Rx屬于或不屬于類Hq；Kx(Hq)<0，Rx不屬于已知類，需增加新的聚類，即設(shè)樣本Rx為新類別，聚類數(shù)目k=k+1.

Step 5調(diào)整新增樣本的類Hq或新增類的屬性取值區(qū)間、中心物元，并求平均關(guān)聯(lián)度. Hq類內(nèi)平均關(guān)聯(lián)度記為

式中，nq是Hq類內(nèi)樣本數(shù)目，Ki(Hq)是類內(nèi)第i個(gè)樣本的關(guān)聯(lián)度.

Step 7跳轉(zhuǎn)Step3，處理所有待聚類的n-k個(gè)樣本物元.

Step 8聚類檢驗(yàn).

1)對類Hp(p=1,2,…,k),計(jì)算并固定中心物元Rp；

2)計(jì)算所有物元Rx對所有類的關(guān)聯(lián)Kx(Hp)(x=1,2,…,n,p=1,2,…,k)；

3)令Kx(Hq)=max{Kx(H1),…,Kx(Hk)}，聚類樣本Rx歸屬至類Hq；

4)循環(huán)以上3步，直至所有樣本個(gè)體的聚類歸屬不變.

Step 9輸出聚類結(jié)果，包括聚類數(shù)目k，每一個(gè)聚類Hp下的樣本數(shù)np，及類內(nèi)樣本關(guān)于該聚類的關(guān)聯(lián)度Kx(Hp).

熵是反映集合內(nèi)樣本聚類多樣性程度的重要指標(biāo).

2可拓聚類適應(yīng)度共享小生境遺傳算法

2.1DNA編碼物元

定義4設(shè)遺傳信息為物元的集合，記為Ri=[N,C,V]. 基因特征屬性Cj(j=1,2,…,m)的量值為vij，其定義域Vj=[aj,bj].

將屬性量值用遺傳算法編碼(l1,l2,…,lt)表示，則每項(xiàng)特征所對應(yīng)的編碼為

式中,X1,X2,….Xt為在[-,+]的t個(gè)區(qū)間.

經(jīng)過量值編碼后，將遺傳信息物元擴(kuò)展定義為DNA編碼物元[7]，記為

2.2可拓遺傳算子

定義5設(shè)DNA編碼物元R0∈R，將R0改變?yōu)榱硪粋€(gè)同類DNA編碼物元或多個(gè)同類編碼物元的可拓變換，稱為R0的可拓遺傳算子，記作

可拓遺傳算子可用事元[6]的形式化語言表示為

式中，OT是動(dòng)作的名稱，表示實(shí)施遺傳操作的類型，即

OT∈{復(fù)制，交叉，變異，置換，增刪，擴(kuò)縮，…}.

可拓遺傳可解析為：vt4對vt1實(shí)施變換OT，變換量為vt2，變換結(jié)果為vt3. 結(jié)合物元可拓變換的多種形式, 可得一些常用或特有的可拓遺傳算子.

1)復(fù)制算子(或稱選擇算子)T{R}={R}，即

常用的復(fù)制選擇方法有適應(yīng)度比例選擇法、錦標(biāo)賽選擇法和排序選擇法.

式中，(i,j)表示交叉的基因座位置.

若為實(shí)數(shù)編碼的算術(shù)交叉算子，取隨機(jī)數(shù)α∈(0,1)，則有

2.3小生境構(gòu)造及適應(yīng)度共享

基于可拓聚類方法構(gòu)造小生境，對個(gè)體適應(yīng)度共享. 其基本過程為：

1)對每代種群X(t)進(jìn)行可拓聚類. 聚類數(shù)目k，每一個(gè)類Hp下的樣本數(shù)np，類內(nèi)樣本關(guān)聯(lián)度Kx(Hp).

2)定義每個(gè)聚類中個(gè)體的小生境數(shù)[8-9]為

式中，mi為個(gè)體i的小生境數(shù)，其值越大，表示其相似個(gè)體越多，反之越稀疏.

3)適應(yīng)度共享，調(diào)整小生境中個(gè)體的適應(yīng)度為

式中fi、fi′分別為共享前、后的適應(yīng)度.

ECNGA算法對種群聚類，并選出每類的代表個(gè)體[10]保存至下一代種群. 代表個(gè)體保存策略如下：

Step 2遺傳生成種群X(t+1)，并可拓聚類；

Step 3取ai(t)(i=1,2,…,k)，判斷其聚類歸屬Hp(p∈[1,2,…,k′])；

Step 4以代表個(gè)體替換聚類Hp中適應(yīng)度最低的個(gè)體；

Step 5比較代表個(gè)體ai(t)與目前聚類中適應(yīng)度最高個(gè)體的bp(t+1)，若f(ai(t))

采用適應(yīng)度共享機(jī)制和代表個(gè)體保存策略進(jìn)行遺傳操作，可使種群維持穩(wěn)定且多樣的小生境，提高算法的全局搜索能力.

2.4交叉概率Pc和變異概率Pm

為促進(jìn)種群的多樣性，Pc、Pm應(yīng)與小生境熵Et呈負(fù)相關(guān)關(guān)系. 另外，對適應(yīng)度高的個(gè)體，可增大Pc以加快其進(jìn)化速度，減小Pm以避免破壞其結(jié)構(gòu)模式. 因此，設(shè)計(jì)自適應(yīng)調(diào)整Pc和Pm為

2.5ECNGA可拓小生境遺傳算法流程

Step 2計(jì)算種群X(t)中個(gè)體適應(yīng)度fi，按適應(yīng)度降序排列.

Step 4代表個(gè)體保存并更新標(biāo)記.

Step 5計(jì)算種群中所有個(gè)體的共享適應(yīng)度fi′.

Step 6種群進(jìn)化，即可拓遺傳形成種群X(t+1).

1)可拓選擇從父代X(t)中運(yùn)用選擇算子選擇出n/2 對個(gè)體.

2)可拓交叉n/2對個(gè)體依概率Pc進(jìn)行交叉，形成n個(gè)中間個(gè)體.

3)可拓變異依概率Pm對n個(gè)中間個(gè)體變異，形成子代X(t+1).

Step 7終止檢驗(yàn). 若不滿足終止準(zhǔn)則，置t←t+1并跳轉(zhuǎn)step2；滿足時(shí)則輸出種群X(t+1)中最優(yōu)解.

2.6算法收斂性分析

引理1[10-11]基本遺傳算法SGA收斂到全局最優(yōu)解的概率小于1.

引理2[10-11]保留最優(yōu)個(gè)體的GA算法以概率1收斂到全局最優(yōu)解.

定理1采用代表個(gè)體保存策略的ECNGA算法以概率1收斂到全局最優(yōu)解.

證明標(biāo)記代表個(gè)體{a1(t),a2(t),…,ak(t)}∈X(t)，令

即ap(t)為X(t)的最優(yōu)個(gè)體.

1)設(shè)p=q，若ap(t)>bq(t+1)，則最優(yōu)個(gè)體ap(t)被保存；反之即存在超過ap(t)的最優(yōu)個(gè)體bq(t+1)，且bq(t+1)被保存.

2)設(shè)p≠q，ap(t)>bq(t+1)，則ap(t)>bp(t+1)，最優(yōu)個(gè)體ap(t)在類Hp中保存；ap(t)

綜上，采用代表個(gè)體保存策略的ECNGA算法在每代選擇操作前保留最優(yōu)個(gè)體，依據(jù)引理2，ECNGA算法以概率1收斂到全局最優(yōu)解.

3仿真實(shí)驗(yàn)及分析

實(shí)驗(yàn)1經(jīng)典多峰Shubert函數(shù)尋優(yōu).

Shubert函數(shù)有760個(gè)局部最優(yōu)點(diǎn)和18個(gè)全局最優(yōu)點(diǎn)，全局最優(yōu)目標(biāo)函數(shù)值-186.730 9. 取適應(yīng)度函數(shù)為

同時(shí)比較SGA、模糊聚類FCNGA[4]及ECNGA三種算法. 參考文獻(xiàn)[4]設(shè)置算法參數(shù)：每次隨機(jī)產(chǎn)生初始種群，規(guī)模n=100，進(jìn)化代數(shù)Gmax=500，交叉算子ηc=0.6，變異算子ηm=0.01，終止條件為目標(biāo)函數(shù)值與當(dāng)前最優(yōu)解差0.1%時(shí)或進(jìn)化代數(shù)達(dá)Gmax,優(yōu)化重復(fù)次數(shù)50. 仿真結(jié)果如表1所示，進(jìn)化曲線圖1所示.

表1　多峰函數(shù)尋優(yōu)仿真結(jié)果對比

圖1　種群平均值進(jìn)化曲線

從表1數(shù)據(jù)及圖1進(jìn)化曲線可知，ECNGA算法明顯優(yōu)于其他兩種算法，搜索能力較強(qiáng)，有更高的求解質(zhì)量和更快的收斂速度，并避免了出現(xiàn)早熟而陷入局部極值的情形.

實(shí)驗(yàn)2自調(diào)整模糊控制器優(yōu)化設(shè)計(jì).

圖2所示為基于可拓遺傳優(yōu)化的自調(diào)整模糊控制系統(tǒng)結(jié)構(gòu)圖. 圖2中各物理量分別為系統(tǒng)給定值r(k)、輸出響應(yīng)y(k)、誤差e(k)、誤差變化率ec(k)及控制輸出量u(k).

模糊控制規(guī)則解析式為

式中:E、EC為誤差、誤差變化率量化取整，U為控制量量化取整，修正因子α∈[αL,αH] 且0<αL≤αH<1.

圖2　可拓遺傳優(yōu)化的自調(diào)整模糊控制系統(tǒng)結(jié)構(gòu)圖

圖2中可拓遺傳優(yōu)化機(jī)構(gòu)的作用是根據(jù)所選取的尋優(yōu)目標(biāo)函數(shù)，搜索修正因子α、量化因子Ke、Kec及比例因子Ku等復(fù)雜多維參數(shù)的全局最優(yōu)解，構(gòu)成最優(yōu)模糊控制器.

選取ITAE作為尋優(yōu)目標(biāo)函數(shù)，即

式中，T為采樣周期，n為決定ITAE指標(biāo)的總時(shí)間.

在MATLAB/SIMULINK中構(gòu)建尋優(yōu)模糊控制系統(tǒng). 設(shè)對象為多數(shù)工控過程的二階慣性加延遲的模型:

設(shè)置尋優(yōu)約束條件[12]為

式中:δ為控制要求的穩(wěn)態(tài)誤差，取δ=0.01；umax為被控對象允許輸入的最大值，仿真模塊內(nèi)取umax=12 V.

ECNGA算法尋優(yōu)后獲得最優(yōu)控制參數(shù)為(Ke,Kec,Ku,αL,αH)=(12.7,36.1,1.57,0.23,0.84),同等條件下，SGA算法優(yōu)化參數(shù)為(Ke,Kec,Ku,αL,αH)=(13.6,41.4,1.69,0.26,0.78).

將兩組優(yōu)化參數(shù)分別代入自調(diào)整模糊控制仿真模塊，即可得控制結(jié)果曲線,如圖3、4所示. 采樣周期T=0.1 s.

圖3　正弦信號(hào)跟蹤

圖4　階躍信號(hào)跟蹤

1)正弦信號(hào)跟蹤實(shí)驗(yàn). 如圖3曲線所示，點(diǎn)形虛線為給定信號(hào)r(t)=sint，取ITAE控制指標(biāo)總時(shí)間為50. 線段虛線為SGA優(yōu)化的模糊控制正弦響應(yīng)曲線，其ITAE=273.1，實(shí)線為ECNGA優(yōu)化后的模糊控制正弦響應(yīng)曲線，其ITAE=211.5.

2)階躍信號(hào)跟蹤實(shí)驗(yàn). 如圖4所示，給定階躍信號(hào)r(t)=ε(t)，10 s前為模糊控制階躍響應(yīng)上升階段. 曲線①為SGA優(yōu)化參數(shù)，ITAE=11.2，穩(wěn)態(tài)e()=0.004 7；曲線②為ECNGA優(yōu)化參數(shù)，ITAE=5.9，穩(wěn)態(tài)e()=-0.001 4. 在30 s處施加負(fù)載擾動(dòng)時(shí)，可觀察優(yōu)化模糊控制器能更快恢復(fù)穩(wěn)定.

對比兩組優(yōu)化參數(shù)可知，ECNGA優(yōu)化方法可獲得全局最優(yōu)解，其模糊控制器在信號(hào)跟蹤的動(dòng)靜態(tài)性能方面優(yōu)于SGA優(yōu)化模糊控制，其響應(yīng)曲線雖然稍有超調(diào), 但調(diào)節(jié)時(shí)間大大縮短，控制精度和穩(wěn)態(tài)性能也有了比較明顯的改進(jìn)，而且對擾動(dòng)的魯棒穩(wěn)定性更好.

4結(jié)論

1)使用可拓聚類分析對種群劃分小生境,按照共享機(jī)制對個(gè)體的適應(yīng)度進(jìn)行調(diào)整,可以增大種群多樣性和有效防止早熟收斂;結(jié)合聚類代表個(gè)體保存策略,維持穩(wěn)定的小生境,以增強(qiáng)全局搜索能力．

2)引入度量種群多樣性的小生境熵自動(dòng)調(diào)整進(jìn)化參數(shù),可有效平衡算法快速性和多樣性的矛盾．

3)該算法優(yōu)于標(biāo)準(zhǔn)遺傳算法和常規(guī)小生境遺傳算法,具有全局尋優(yōu)能力和較高的搜索效率,是一種適用于復(fù)雜尋優(yōu)問題的有效優(yōu)化算法．

參考文獻(xiàn)

[1] 玄光男,程潤偉. 遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2004:21-30.

[2] CHEN C H, LIU T K, CHOU Y H. A novel crowding genetic algorithm and its applications to manufacturing robots[J]. IEEE Transactions on Industrial Informatics, 2014, 10(3): 1705-1706.

[3] KIM Hyoungjin, LIOU Mengsing. New fitness sharing approach for multi-objective genetic algorthm[J]. Journal of Global Optimization,2013,55(3):579-595.

[4] 譚艷艷,許峰.自適應(yīng)模糊聚類小生境遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用, 2009,45(4): 52-55.

[5] 陸青,梁昌勇, 楊善林,等.面向多模態(tài)函數(shù)優(yōu)化的自適應(yīng)小生境遺傳算法[J].模式識(shí)別與人工智能, 2009,22(1):91-99.

[6] 楊春燕,蔡文.可拓學(xué)[M]. 北京:科學(xué)出版社,2014: 18-96.

[7] 王科俊,徐晶, 王磊,等. 基于可拓遺傳算法的機(jī)器人路徑規(guī)劃[J] 哈爾濱工業(yè)大學(xué)學(xué)報(bào),2006,38(7):1135-1138.

[8] 趙 敏,林道榮, 瞿波,等.一種新的基于小生境模擬退火的遺傳算法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào), 2013,32(3):367-372.

[9] SANTRA A K., CHRISTY C. J, NAGARAJAN B. Cluster based hybrid niche mimetic and genetic algorithm for text document categorization[J]. International Journal of Computer Science Issues, 2011, 8(2): 450-456.

[10]何琳,王科俊, 李國斌,等.最優(yōu)保留遺傳算法及其收斂性分析[J].控制與決策, 2000,15(1): 63-66.

[11]LI Junhua,LI Ming. An analysis on convergence and convergence rate estimate of elitist genetic algorithms in noisy environments[J]. Optik, 2013,124(24):6780-6785.

[12]葛平淑,郭烈.參數(shù)自調(diào)整的月球車路徑跟蹤模糊控制器設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用, 2012,48(11): 55-59.

(編輯王小唯苗秀芝)

Research of fitness sharing niche genetic algorithms based on extension clustering

LI Zhonghua, ZHANG Taishan

(School of Information Science and Engineering, Central South University, 410083 Changsha, China)

Abstract:To solve the problems of premature convergence and weak ability in global search of the genetic algorithm, a fitness sharing niche genetic algorithm based on extenics is proposed.The algorithm build the matter-element code and extension genetic operator, create niche groups by extension clustering, and preserve the stability of niche groups by combining fitness sharing mechanism and elitist retention strategy. Experiments show that the algorithm can solve the optimal performance with global search ability and fast convergence rate. It is proved to be more effective and accurate than standard geneic algorithm and normal niche genetic algorithm.

Keywords:genetic algorithm; niche; extension clustering; fitness sharing; elitist retention; premature convergence

中圖分類號(hào):TP319.4

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):0367-6234(2016)05-0178-06

通信作者:李中華，chinali@csu.edu.cn.

作者簡介:李中華(1968—), 男, 博士, 副教授;

收稿日期:2015-03-05.

doi：10.11918/j.issn.0367-6234.2016.05.029

張?zhí)┥?1940—), 男, 教授, 博士生導(dǎo)師.