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

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

?

可拓聚類適應度共享小生境遺傳算法研究

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

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

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

關鍵詞:遺傳算法；小生境；可拓聚類；適應度共享；代表個體；早熟收斂

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

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

1可拓聚類分析

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

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

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

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

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

定義2關聯(lián)度計算準則[6-8]:

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

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

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

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

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

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

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

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

Step 3依次取剩余樣本Rx，計算Rx對類Hp(p=1,2,…,k)的關聯(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，可認為Rx屬于或不屬于類Hq；Kx(Hq)<0，Rx不屬于已知類，需增加新的聚類，即設樣本Rx為新類別，聚類數(shù)目k=k+1.

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

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

Step 7跳轉Step3，處理所有待聚類的n-k個樣本物元.

Step 8聚類檢驗.

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

2)計算所有物元Rx對所有類的關聯(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步，直至所有樣本個體的聚類歸屬不變.

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

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

2可拓聚類適應度共享小生境遺傳算法

2.1DNA編碼物元

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

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

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

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

2.2可拓遺傳算子

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

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

式中，OT是動作的名稱，表示實施遺傳操作的類型，即

OT∈{復制，交叉，變異，置換，增刪，擴縮，…}.

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

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

常用的復制選擇方法有適應度比例選擇法、錦標賽選擇法和排序選擇法.

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

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

2.3小生境構造及適應度共享

基于可拓聚類方法構造小生境，對個體適應度共享. 其基本過程為：

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

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

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

3)適應度共享，調整小生境中個體的適應度為

式中fi、fi′分別為共享前、后的適應度.

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

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

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

Step 4以代表個體替換聚類Hp中適應度最低的個體；

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

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

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

為促進種群的多樣性，Pc、Pm應與小生境熵Et呈負相關關系. 另外，對適應度高的個體，可增大Pc以加快其進化速度，減小Pm以避免破壞其結構模式. 因此，設計自適應調整Pc和Pm為

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

Step 2計算種群X(t)中個體適應度fi，按適應度降序排列.

Step 4代表個體保存并更新標記.

Step 5計算種群中所有個體的共享適應度fi′.

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

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

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

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

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

2.6算法收斂性分析

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

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

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

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

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

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

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

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

3仿真實驗及分析

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

Shubert函數(shù)有760個局部最優(yōu)點和18個全局最優(yōu)點，全局最優(yōu)目標函數(shù)值-186.730 9. 取適應度函數(shù)為

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

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

圖1　種群平均值進化曲線

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

實驗2自調整模糊控制器優(yōu)化設計.

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

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

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

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

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

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

式中，T為采樣周期，n為決定ITAE指標的總時間.

在MATLAB/SIMULINK中構建尋優(yōu)模糊控制系統(tǒng). 設對象為多數(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ù)分別代入自調整模糊控制仿真模塊，即可得控制結果曲線,如圖3、4所示. 采樣周期T=0.1 s.

圖3　正弦信號跟蹤

圖4　階躍信號跟蹤

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

2)階躍信號跟蹤實驗. 如圖4所示，給定階躍信號r(t)=ε(t)，10 s前為模糊控制階躍響應上升階段. 曲線①為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處施加負載擾動時，可觀察優(yōu)化模糊控制器能更快恢復穩(wěn)定.

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

4結論

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

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

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

參考文獻

[1] 玄光男,程潤偉. 遺傳算法與工程優(yōu)化[M].北京:清華大學出版社,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] 譚艷艷,許峰.自適應模糊聚類小生境遺傳算法[J].計算機工程與應用, 2009,45(4): 52-55.

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

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

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

[8] 趙 敏,林道榮, 瞿波,等.一種新的基于小生境模擬退火的遺傳算法[J].遼寧工程技術大學學報, 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ù)自調整的月球車路徑跟蹤模糊控制器設計[J].計算機工程與應用, 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

中圖分類號:TP319.4

文獻標志碼:A

文章編號: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—), 男, 教授, 博士生導師.