基于煙花算法與差分進(jìn)化算法的模糊分類系統(tǒng)設(shè)計(jì)

朱曉東，劉 沖，郭雅默

(鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州450001)

0 引言

模糊分類系統(tǒng)能夠融合專家經(jīng)驗(yàn)，通過易于理解的模糊規(guī)則來闡述實(shí)際問題的內(nèi)部機(jī)理，因而在模式識(shí)別、數(shù)據(jù)挖掘等領(lǐng)域得到了廣泛的應(yīng)用．為了提高模糊系統(tǒng)的性能，學(xué)者們做了大量的研究:利用聚類算法建立模糊模型［1］，采用遺傳算法［2-3］或神經(jīng)網(wǎng)絡(luò)［4-5］學(xué)習(xí)模糊規(guī)則及隸屬函數(shù)的特征參數(shù)等． 然而，這些算法在追求模型高精確度的同時(shí)，采用了較多的模糊規(guī)則和模糊集合，使得模型結(jié)構(gòu)復(fù)雜、難以理解．為了建立結(jié)構(gòu)簡(jiǎn)單易懂、精確度高的模糊模型，文獻(xiàn)［6］采用分層模糊的概念來構(gòu)造模糊系統(tǒng)，降低了系統(tǒng)維度，簡(jiǎn)化了系統(tǒng)的結(jié)構(gòu)． 文獻(xiàn)［7］采用基于類空間模糊度的計(jì)算幾何分類器權(quán)重分配方法來構(gòu)建分類器，這種方法使得模型的精確性和解釋性都得到了進(jìn)一步的提高．

煙花算法［8］是受煙花在夜空中的爆炸現(xiàn)象啟發(fā)而提出的一種新的群智能算法，和粒子群算法等其他方法相比具有較好的搜索性能． 在煙花算法中，性能較好的煙花在較小的搜索范圍內(nèi)產(chǎn)生數(shù)量較多的子代火花，進(jìn)而加快了收斂速度;而性能較差的煙花則在較大的搜索范圍內(nèi)產(chǎn)生數(shù)量較少的子代火花，因而擴(kuò)大了搜索范圍，提高了種群的多樣性．但是，煙花算法忽略了不同煙花個(gè)體之間的相互聯(lián)系和學(xué)習(xí)，這樣容易使算法過早成熟．為了解決這個(gè)問題，將差分算法與煙花算法相結(jié)合，進(jìn)一步增加種群的多樣性，擴(kuò)大搜索區(qū)域，增強(qiáng)個(gè)體間的相互聯(lián)系，防止算法過早陷入局部最優(yōu)［9］．筆者將煙花算法和差分進(jìn)化算法用于模糊模型優(yōu)化，能夠使種群以較快的收斂速度、較好的搜索性能尋找全局最優(yōu)個(gè)體，建立結(jié)構(gòu)簡(jiǎn)單、精確度高的模糊模型．

1 預(yù)備知識(shí)

1．1 模糊分類系統(tǒng)

對(duì)于n 維m 類的分類問題，其中x = (x1，x2，…，xn)為輸入變量，{g1，g2，…，gn}為輸出類的標(biāo)值號(hào)，則經(jīng)典的模糊分類系統(tǒng)的規(guī)則可表示為［10］

Ri:if x1is μi1and x2is μi2and … and xnis μin，

then the pattern (x1，…，xn)belongs to gi． (1)其中，μi1，…，μin為模糊集合．其高斯型隸屬函數(shù)為

式中:νij，σij分別表示函數(shù)的中心和方差． 對(duì)于樣本xk，模糊系統(tǒng)所對(duì)應(yīng)的輸出類別為激勵(lì)強(qiáng)度最大的規(guī)則的后件類別號(hào)．

1．2 煙花算法

煙花算法是Tan 通過模擬煙花的爆炸過程而提出的一種群體智能算法［8］． 該算法在每一代都選擇出性能較好的煙花作為父代，來產(chǎn)生子代火花用以搜索最優(yōu)解．對(duì)于煙花xi，產(chǎn)生子代火花的數(shù)量si以及爆炸的范圍Ai分別定義如下:

式中:si和A^是控制參數(shù);L 為種群大小;fmax和fmin分別表示目標(biāo)函數(shù)的最大值和最小值;ε 是一個(gè)極小的常量以避免除數(shù)為零．

為了避免性能優(yōu)秀的煙花對(duì)子代的影響過大，以至于喪失種群多樣性，需對(duì)si的大小范圍進(jìn)行限制:

對(duì)于一個(gè)D 維的問題，隨機(jī)選擇煙花xi的z(z＜D)個(gè)位置，對(duì)每一個(gè)位置加上一個(gè)位移構(gòu)成(1 ≤j ≤si，1 ≤k ≤z)．生成火花的方法有兩種．大部分火花是通過對(duì)加上一個(gè)位移hk= Ai·rand(-1，1)而得到的，即

對(duì)于上述兩種方法，如果產(chǎn)生的新的位置超出了搜索區(qū)間，需要將其映射到搜索區(qū)間內(nèi)，方法如下:

在每一次迭代中，所有的個(gè)體(包括煙花和火花)中的最優(yōu)個(gè)體，總是被選為煙花進(jìn)入下一代，并根據(jù)距離概率［9］選擇其他L-1 個(gè)個(gè)體作為下一代的父體煙花．

1．3 差分進(jìn)化算法

僅僅采用煙花算法對(duì)初始模糊模型進(jìn)行優(yōu)化，容易過早成熟收斂，陷入局部最優(yōu)解［9］． 為了提高種群的多樣性，擴(kuò)大搜索范圍，在每一次迭代過程中，采用煙花算法產(chǎn)生新的子代火花，并選擇出較好的個(gè)體作為下一代煙花，然后執(zhí)行差分算法對(duì)被選擇出的煙花進(jìn)一步優(yōu)化． 差分算法的步驟為:

(1)變異操作．對(duì)于個(gè)體xi，在種群中隨機(jī)選擇3 個(gè)個(gè)體xr1，xr2和xr3，其中的一個(gè)個(gè)體加上另外兩個(gè)個(gè)體的差值與權(quán)值系數(shù)的乘積，生成變異個(gè)體vi，即

vi= xr1+ γ(xr2- xr3)． (9)

式中:r1，r2，r3∈［1，L］;γ 是變異尺度因子，用來控制攝動(dòng)幅度．

(2)交叉操作．在原始個(gè)體和變異個(gè)體之間進(jìn)行比較，挑選出試驗(yàn)個(gè)體uji．采用二項(xiàng)式交叉，即

式中:cr是交叉概率;r(i)是(0，2 ×c ×n］之間的隨機(jī)數(shù)．

(3)選擇操作． 將原始個(gè)體和試驗(yàn)個(gè)體進(jìn)行比較，比較優(yōu)秀者被選擇進(jìn)入下一代種群．這個(gè)操作過程表示為

2 利用煙花算法和差分算法建立模糊分類系統(tǒng)

采用模糊C - 均值(FCM)聚類算法構(gòu)造初始模糊系統(tǒng)，但初始模糊模型在分類精度以及可解釋性方面的效果都比較差． 采用煙花算法和差分進(jìn)化算法對(duì)模型的結(jié)構(gòu)和參數(shù)進(jìn)行學(xué)習(xí)和優(yōu)化，并在進(jìn)化算法中采用相似相融原理［10］對(duì)模型進(jìn)行約簡(jiǎn)［11］，在保證系統(tǒng)精確度的前提下，簡(jiǎn)化系統(tǒng)結(jié)構(gòu)，使得系統(tǒng)更好理解、透明性更高．

2．1 模糊分類系統(tǒng)的初始化

為了避免“維數(shù)災(zāi)”問題，首先進(jìn)行特征變量的選擇［11］，以降低系統(tǒng)的維度．并采用模糊C-均值(FCM)聚類算法辨識(shí)初始模糊模型［12］，其中初始聚類數(shù)為c，即初始的模糊模型規(guī)則數(shù)，取c = 3Nc(Nc為實(shí)際分類數(shù))．

規(guī)則Ri的后件所對(duì)應(yīng)的類標(biāo)號(hào)值［11］為

其中，uik是數(shù)據(jù)xk對(duì)ith聚類中心的隸屬度，且滿足:

2．2 染色體編碼

設(shè)定種群的個(gè)體數(shù)為L(zhǎng)，染色體表示為Hp，p =1，2，…，L，第一條染色體根據(jù)初始模型的參數(shù)來構(gòu)造，其中隸屬函數(shù)的中心vij和方差σij為編碼參數(shù)，則第一條染色體的編碼為

H1= (v11，…，vcn，σ11，…，σcn)． (17)

搜索區(qū)域?yàn)椋跦min，Hmax］:

2．3 適應(yīng)度函數(shù)

建立模型的主要目的是能夠準(zhǔn)確地模擬實(shí)際問題，為此，精確性是模糊分類系統(tǒng)的一個(gè)重要性能指標(biāo)，可用分類誤差來衡量模糊分類系統(tǒng)的精確性:

系統(tǒng)的解釋性是指，人們?nèi)菀淄ㄟ^該系統(tǒng)理解并學(xué)習(xí)實(shí)際問題的內(nèi)部機(jī)理．一般情況下，模型的結(jié)構(gòu)越復(fù)雜，所包含的模糊規(guī)則和模糊集合數(shù)量越多，人們學(xué)習(xí)該模型就越困難，模型的解釋性就越差［11，13］． 若要使模型易于理解，應(yīng)在滿足精確性的前提下，采用盡可能少的規(guī)則和集合;而且，模糊規(guī)則必須滿足一致性和完備性，輸入變量的兩個(gè)相鄰的模糊集合應(yīng)滿足可區(qū)分性，并在恰當(dāng)?shù)碾`屬函數(shù)值處交叉．

精確性和解釋性是模糊系統(tǒng)的兩個(gè)重要指標(biāo)，利用加權(quán)求和法的思想，將這兩個(gè)指標(biāo)綜合，構(gòu)成為如下適應(yīng)度函數(shù):

F = ω1JERR+ ω2NR+ ω3NS． (22)

式中:JERR為衡量模型精確性的指標(biāo)，為類別被劃分錯(cuò)誤的樣本數(shù)目;NR，NS分別為模糊規(guī)則和模糊集合的數(shù)目，用來度量模型的解釋性;ω1，ω2和ω3為預(yù)先設(shè)置的權(quán)值參數(shù)，其值的大小一般是根據(jù)具體問題需要和經(jīng)驗(yàn)進(jìn)行選?。?/p>

2．4 模糊分類器的設(shè)計(jì)步驟

基于煙花算法和差分進(jìn)化算法的模糊分類器設(shè)計(jì)的詳細(xì)步驟如下．

步驟1:初始化．首先，對(duì)系統(tǒng)的特征變量進(jìn)行選擇，降低模糊系統(tǒng)的維度;其次，利用FCM 聚類算法構(gòu)建初始模糊模型，并對(duì)初始種群P 進(jìn)行染色體編碼．

步驟2:計(jì)算模糊規(guī)則和模糊集合之間的相似度，并約簡(jiǎn)模糊模型結(jié)構(gòu)．

步驟3:根據(jù)公式(3)、(5)計(jì)算每一個(gè)煙花所產(chǎn)生子代火花的數(shù)量，由公式(4)得出子代火花范圍．

步驟4:根據(jù)公式(6)、(8)產(chǎn)生普通子代，根據(jù)公式(7)、(8)得到少量由高斯位移產(chǎn)生的子代．

步驟5:根據(jù)適應(yīng)度函數(shù)值，選擇最優(yōu)個(gè)體，并在適應(yīng)度排在前2L 的個(gè)體中隨機(jī)選擇L -1 個(gè)個(gè)體組成種群P'．選擇概率為

步驟6:對(duì)由煙花算法得到的種群P'，采用差分算法，經(jīng)過變異、交叉、選擇操作得到種群P．

步驟7:判斷是否滿足步長(zhǎng)終止條件，如果滿足，返回步驟2;否則，算法執(zhí)行結(jié)束．

2．5 算法流程圖

模糊分類器設(shè)計(jì)步驟的算法流程如圖1 所示．

圖1 模糊分類器設(shè)計(jì)算法流程圖Fig．1 Flowchart of the fuzzy classifier generation

3 試驗(yàn)與分析

采用Iris 數(shù)據(jù)樣本作為實(shí)驗(yàn)數(shù)據(jù)．Iris 數(shù)據(jù)是由4 維數(shù)據(jù)［x1:Sepal length;x2:Sepal width;x3:Petal length;x4:Petal width］的150 個(gè)樣本組成．對(duì)實(shí)驗(yàn)數(shù)據(jù)的特征進(jìn)行篩選，選擇x3和x4為輸入變量［3］;采用FCM 聚類對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)建一個(gè)由9 個(gè)模糊規(guī)則和18 個(gè)模糊集合所組成的初始模型．該模型的結(jié)構(gòu)復(fù)雜，且錯(cuò)誤分類樣本數(shù)目為10，分類精確度為93．3%，分類效果差．

采用煙花算法和差分進(jìn)化算法對(duì)模型的結(jié)構(gòu)和參數(shù)進(jìn)行優(yōu)化，并利用相似度原理對(duì)規(guī)則和集合進(jìn)行約簡(jiǎn)．關(guān)于實(shí)驗(yàn)中一些常量參數(shù)的設(shè)定，筆者是在參考相關(guān)文獻(xiàn)資料的基礎(chǔ)上經(jīng)過反復(fù)試驗(yàn)而獲取的．選取不同的常量參數(shù)所得到的模糊模型，其性能有一定的差別． 經(jīng)過多次實(shí)驗(yàn)和分析后，最終設(shè)定種群的大小L=40，進(jìn)化代數(shù)為100，模糊集合和規(guī)則的相似性融合的閾值分別為0．4和0． 9，適應(yīng)度函數(shù)參數(shù)ω1= 1，ω2= 0． 5，ω3=0．2．

經(jīng)過優(yōu)化后的模型精確性提高了很多，錯(cuò)誤劃分樣本數(shù)目降為4，精確性度高達(dá)97．3%，模糊集合數(shù)減少到5，其隸屬函數(shù)如圖2 所示，模糊規(guī)則數(shù)降為3，模型的結(jié)構(gòu)簡(jiǎn)單了許多，解釋性得到了提高．

圖2 優(yōu)化后模糊模型的隸屬函數(shù)圖Fig．2 Membership function of the optimized fuzzy model

表1 列舉了本文方法與其他文獻(xiàn)方法的對(duì)比結(jié)果．可以看出，基于煙花算法和差分進(jìn)化算法所建立的模糊分類系統(tǒng)分類精度高、結(jié)構(gòu)簡(jiǎn)單、易于理解．文獻(xiàn)［14 -15］中的分類系統(tǒng)的分類效果雖然比本文方法的精確度稍好一些，但系統(tǒng)所包含的模糊集合數(shù)目較多、結(jié)構(gòu)復(fù)雜、解釋性差．文獻(xiàn)［16］中的分類系統(tǒng)與本文所建立的系統(tǒng)相比，結(jié)構(gòu)更為簡(jiǎn)單，解釋性稍好，但其分類準(zhǔn)確度較差．總體來說，筆者所建立的模糊分類系統(tǒng)在精確性與解釋性這兩個(gè)相互矛盾的方面獲得了較好的折衷，模型更為合理．

表1 Iris 分類問題不同建模方法的性能比較Tab.1 Comparison of different modeling methods on the Iris classification problem

4 結(jié)論

為了建立能夠準(zhǔn)確模擬實(shí)際問題并且易于被人們所理解的模糊模型，采用煙花算法和差分進(jìn)化算法來建立模糊模型是一種很好的選擇． 這是首次將煙花算法應(yīng)用到模糊建模領(lǐng)域，利用煙花算法和差分算法對(duì)模型結(jié)構(gòu)和參數(shù)進(jìn)行優(yōu)化． 在煙花算法中，性能較好的煙花在較小的范圍內(nèi)產(chǎn)生較多的子代個(gè)體，加快了收斂速度;另一方面，性能較差的個(gè)體在較大的范圍內(nèi)產(chǎn)生較少的子代個(gè)體，從而增大了搜索范圍．而采用差分算法對(duì)子代火花進(jìn)一步優(yōu)化，能夠提高種群的多樣性，很好地解決了煙花算法容易過早地陷入局部最優(yōu)的問題，并最終以較少的模糊規(guī)則和模糊集合數(shù)取得了精確性良好的模糊分類系統(tǒng)．

筆者采用的是加權(quán)求和法的方法構(gòu)建適應(yīng)度函數(shù)，將多目標(biāo)轉(zhuǎn)化為一個(gè)目標(biāo)函數(shù)．但是，目前還沒有確定某種算法能較好地確定權(quán)值大小，在這里僅是根據(jù)經(jīng)驗(yàn)來設(shè)定權(quán)值大小，可見，這種方法具有一定的局限性．下一步，筆者將嘗試并研究采用Pareto 最優(yōu)解的理論來處理多個(gè)目標(biāo)的問題．

［1］ 生龍，張洪斌． 二型模糊系統(tǒng)在音頻信號(hào)分類中的應(yīng)用［J］． 電子科技大學(xué)學(xué)報(bào)，2013，42(3):436 -441．

［2］ 郭亦文，李軍，耿林霄． 基于遺傳算法獲取模糊規(guī)則［J］． 計(jì)算機(jī)應(yīng)用，2014，34(10):2899 -2903．

［3］ 張永，吳曉蓓，向崢嶸，等． 基于決策樹和遺傳算法的模糊分類系統(tǒng)設(shè)計(jì)［J］． 東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2006，36(1):23 -36．

［4］ 馮冬青，張希平． 基于神經(jīng)網(wǎng)絡(luò)的自學(xué)習(xí)模糊控制［J］． 鄭州大學(xué)學(xué)報(bào)(工學(xué)版)，2003，24(4):6-10．

［5］ 張景元． 基于神經(jīng)網(wǎng)絡(luò)的自適應(yīng)模糊控制系統(tǒng)［J］． 計(jì)算機(jī)工程與設(shè)計(jì)，2014，35(10):3613-3616．

［6］ 王杰，周賀松． 增一型分層模糊系統(tǒng)結(jié)構(gòu)的PCA優(yōu)化方法［J］． 鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2013，45(2):59 -63．

［7］ 張濤，洪文學(xué)． 基于模糊度的計(jì)算幾何分類器權(quán)重分配［J］．控制與決策，2013，28(4):569 -573．

［8］ ZHENG Shaoqiu，JANECEK A，TAN Ying． Enhanced fireworks algorithm［C］//2013 IEEE Congress on Evolutionary Computation． Cancun，México:IEEE Press，2013:2069 -2077．

［9］ ZHENG Yujun，XU Xinli，LING Haifeng，et al． A hybrid fireworks optimization method with differential evolution operators［J］． Neurocomputing，2012，148:75 -82．

［10］SETNES M，BABUSKA R，KAYMAK U，et al． Similarity measures in fuzzy rule base simplification［J］．IEEE Transactions on Systems，Man and Cybernetics，1998，28(3):376 -386．

［11］張永，吳曉蓓，向崢嶸，等． 基于多目標(biāo)進(jìn)化算法的高維模糊分類系統(tǒng)的設(shè)計(jì)［J］． 系統(tǒng)仿真學(xué)報(bào)，2007，19(1):210 -215．

［12］文傳軍，汪慶淼，詹永照． 均衡模糊C 均值聚類算法［J］． 計(jì)算機(jī)科學(xué)，2014，41(8):250 -253．

［13］WANG Hanli，KWONG S，JIN Yaochu，et al． Multi-objective hierarchical genetic algorithm for interpretable fuzzy rule-based knowledge extraction［J］． Fuzzy Sets and Systems，2005，149(1):149 -186．

［14］ISHIBUCHI H，NAKASHIMA T，MURATA T． Threeobjective genetics-based machine learning for linguistic rule extraction［J］． Information Sciences，2001，136(1):109 -133．

［15］WANG J S，LEE C S G． Self adaptive neuro-fuzzy inference systems for classification applications［J］．IEEE Transactions on Fuzzy System，2002，10(6):790 -802．

［16］ZHANG Yong，WU Xiaobei，XING Zongyi，et al． On generating interpretable and precise fuzzy systems based on Pareto multi-objective cooperative coevolutionary algorithm［J］． Applied Soft Computing，2011，11(1):1284 -1294．