融合粗糙集和擴散二元螢火蟲算法的屬性約簡方法

程美英， 倪志偉， 朱旭輝

(1. 合肥工業(yè)大學(xué)管理學(xué)院， 安徽 合肥 230009； 2. 過程優(yōu)化與智能決策教育部重點實驗室， 安徽 合肥 230009； 3. 新加坡南洋理工大學(xué)計算機科學(xué)與工程學(xué)院計算智能中心實驗室， 新加坡 639798)

?

融合粗糙集和擴散二元螢火蟲算法的屬性約簡方法

程美英1,2,3， 倪志偉1,2， 朱旭輝1,2

(1. 合肥工業(yè)大學(xué)管理學(xué)院， 安徽 合肥 230009； 2. 過程優(yōu)化與智能決策教育部重點實驗室， 安徽 合肥 230009； 3. 新加坡南洋理工大學(xué)計算機科學(xué)與工程學(xué)院計算智能中心實驗室， 新加坡 639798)

從一維細胞自動機模型入手，將自然界中種群的擴散行為引入二元螢火蟲算法(binary glowworm swarm optimization, BGSO)中，提出了一種擴散二元螢火蟲算法 (spread binary glowworm swarm optimization, SBGSO)。該算法對螢火蟲個體設(shè)置營養(yǎng)值及營養(yǎng)閾值的上下限，然后執(zhí)行擴散操作，以正態(tài)分布方式產(chǎn)生新的個體，并淘汰一些持續(xù)表現(xiàn)很差的個體，釋放資源給其他個體，以保持種群的動態(tài)多樣性。然后將SBGSO作為搜索策略，粗糙集 (rough set, RS) 作為評價準則，應(yīng)用于大數(shù)據(jù)預(yù)處理的屬性約簡問題。為驗證本文算法的可行性，采用5個UCI數(shù)據(jù)集進行實驗，并結(jié)合10-fold和支持向量機(support vector machine,SVM)算法對預(yù)測結(jié)果分類準確率進行分析，通過與其他算法對比,表明本文算法具有較好的約簡效果。

二元螢火蟲算法； 擴散機制； 一維細胞自動機； 粗糙集； 屬性約簡

0　引　言

螢火蟲算法是一種模擬自然界中螢火蟲成蟲聚集發(fā)光行為的仿生智能算法。目前螢火蟲算法主要有兩個版本：一種稱為GSO(glowworm swarm optimization)[1],另一種稱為FA(firefly algorithm)[2]。FA在仿生原理上與GSO大致相似，但具體實現(xiàn)時有一定的差異。螢火蟲算法自提出以來，在連續(xù)域優(yōu)化及離散域優(yōu)化問題[3-6](如：彈道導(dǎo)彈突防、車輛路徑規(guī)劃、多目標優(yōu)化、函數(shù)優(yōu)化等)中得到較好的應(yīng)用?！疤剿骱屠谩钡臎_突以及算法初始時刻運行時間過長是螢火蟲算法固有的缺陷，為克服其缺點，目前對螢火蟲算法的改進策略主要分為以下幾個主要方面：①與混沌策略相結(jié)合的螢火蟲算法。如：文獻[7]利用切比雪夫混沌映射初始化螢火蟲種群，從而提高初始解的質(zhì)量；文獻[8]對種群中適應(yīng)值較低的個體進行混沌擾動，從而保持種群的動態(tài)多樣性；文獻[9]采用混沌方法優(yōu)化局部最優(yōu)解,從而加快算法的快速收斂。②與調(diào)節(jié)步長機制相結(jié)合的螢火蟲算法。如：文獻[10-11]將算法中的步長設(shè)置成與算法迭代次數(shù)相關(guān)的函數(shù),并隨著迭代次數(shù)的增加逐步遞減,從而保持全局及局部探索能力的平衡；文獻[12]引入個體搜索“成功”或“失敗”的概念，當螢火蟲個體搜索成功時加大步長，反之縮減步長；文獻[13]中算法的步長與鄰域內(nèi)螢火蟲個體分布密度相關(guān), 當鄰域內(nèi)螢火蟲個體分布稀疏時使用較大步長,反之選擇較小的步長以提高解的精度。③與其他群智能算法相結(jié)合的螢火蟲算法。如與人工魚群算法[14]、遺傳算法[15]、蜂群算法[16-17]、蛙跳算法[18]、雜草算法[19]等結(jié)合，實現(xiàn)優(yōu)勢互補。

為拓寬螢火蟲算法的應(yīng)用范圍，使其在二元離散優(yōu)化問題(即一個維數(shù)為L的0、1序列表示問題的一個解)中得到較好的應(yīng)用，本文將二進制編碼引入螢火蟲算法中，提出了一種新穎的二元螢火蟲算法(binary glowworm swarm optimization, BGSO)。 “探索和利用”的沖突是螢火蟲算法固有的缺陷，將自然界中種群的擴散行為引入BGSO中，提出了一種基于擴散行為的二元螢火蟲算法(spread binary glowworm swarm optimization, SBGSO)。然后將SBGSO與粗糙集(rough set, RS)相結(jié)合，應(yīng)用于大數(shù)據(jù)預(yù)處理中典型二元離散優(yōu)化問題——屬性約簡問題。

本文首先簡要介紹基本GSO的原理及求解步驟，在此基礎(chǔ)上，將模糊函數(shù)映射機制引入到GSO中，提出BGSO，并采用一維二值細胞自動機對問題的求解過程進行描述；其次針對BGSO中“早熟”的缺陷，對種群中的螢火蟲個體設(shè)置營養(yǎng)值及營養(yǎng)閾值，執(zhí)行擴散及淘汰操作，提出SBGSO，并對該算法的收斂性、復(fù)雜度(包括時間復(fù)雜度和空間復(fù)雜度)進行理論分析；然后將SBGSO作為搜索策略，RS作為子集評估度量準則，應(yīng)用于求解二元離散優(yōu)化問題——屬性約簡問題中；最后對算法進行了仿真實驗與對比分析。

1　BGSO

1.1基本GSO

在基本GSO中，初始時刻種群中的螢火蟲個體攜帶等量的熒光素，隨機分布在整個搜索空間中。隨后螢火蟲個體通過追隨各自視覺范圍內(nèi)比自身亮的螢火蟲進行位置進化，群體更新，最終收斂在最優(yōu)目標值上?；静襟E如下：

步驟 1根據(jù)式(1)將螢火蟲i在第t次迭代的位置xi(t)對應(yīng)的目標函數(shù)值J(xi(t))轉(zhuǎn)換成熒光素值li(t)：

(1)

步驟 3按式(2)計算螢火蟲i在其動態(tài)決策域半徑內(nèi)向螢火蟲δ移動的概率Piδ(t)：

(2)

步驟 4螢火蟲i移動后，按式(3)更新自身的位置：

(3)

步驟 5按式(4)更新螢火蟲i的動態(tài)決策域半徑：

(4)

循環(huán)步驟1～步驟5，螢火蟲個體最終收斂在全局最優(yōu)解上。其中，ρ為熒光素揮發(fā)系數(shù)；μ為熒光素更新率；Ni(t)為螢火蟲i決策域內(nèi)的螢火蟲個數(shù)；η為動態(tài)決策域更新率；nt為領(lǐng)域集內(nèi)所含螢火蟲數(shù)目的閾值；s為移動步長；rs為螢火蟲個體的感知半徑[1]。

1.2BGSO一維細胞自動機模型

為更好地將螢火蟲算法應(yīng)用于二元離散優(yōu)化問題，引入二進制編碼，并采用一維二值細胞自動機模型對問題的復(fù)雜求解過程進行描述，如圖1所示。

圖1　一維二值螢火蟲算法細胞自動機模型Fig.1　One-dimensional two values glowworm swarm optimization cellular automata model

(5)

任意時刻t，螢火蟲從初始細胞出發(fā)遍歷圖1，按式(5)隨機從細胞狀態(tài)集合中選擇0或1。一次遍歷結(jié)束后所得的0/1序列即對應(yīng)問題的一個解。在上述離散化機制中，模糊函數(shù)將連續(xù)空間內(nèi)移動的螢火蟲個體位置離散化，從而達到求解具有0/1特性的二元離散型優(yōu)化問題的目的。

2　SBGSO

算法的“早熟收斂”是螢火蟲算法固有的缺陷。在BGSO的運行初期，種群中的超級個體因具有較強的亮度而吸引其他個體迅速向其周圍靠攏，種群多樣性喪失，算法早熟收斂。因而提高種群的多樣性，使得種群在求解問題中保持持續(xù)優(yōu)化能力是改進BGSO的有效途徑。

在生物的進化過程中，由于生存環(huán)境的壓力(如食物的匱乏、種群外部競爭等)、種群自身密度的制約以及生境的斑塊化都會導(dǎo)致生物個體從一個生境轉(zhuǎn)移到另一個生境中， 這不僅可以維持生態(tài)系統(tǒng)的平衡穩(wěn)定，還可以進一步防止物種的滅絕[20]。受此啟發(fā)，在本節(jié)中，將自然界中種群擴散行為引入BGSO中，提出了SBGSO。

2.1SBGSO主要思想

2.1.1種群初始化

令初始種群規(guī)模為gsonum，[Xmin,Xmax]為搜索空間范圍。初始時刻，按式(6)隨機產(chǎn)生螢火蟲個體的初始位置xij(0)(xij(0)∈[Xmin,Xmax])，其中rand()為隨機數(shù)。

xij(0)=(rand()/Rand_Max+1.0))×

(6)

2.1.2種群擴散

(7)

(8)

新個體的位置設(shè)置如文獻[21]所示，以父代為軸線，將子代按正態(tài)分布方式擴散在L維空間中，設(shè)最大、最小方差分別為τ0和τf，當前迭代次數(shù)為Iter，最大迭代次數(shù)為Maxiter。因正切函數(shù)tan()的值隨著自變量的減小而逐步遞減，根據(jù)正切函數(shù)的特點，得到：

(9)

則由父代個體i產(chǎn)生的子代位置為

(10)

由式(9)和式(10)可以看出：開始時，τ值較大，子代螢火蟲個體距離父代較遠，而后期τ值隨著迭代次數(shù)Iter的增加而逐步遞減，子代螢火蟲個體分布在離父代個體較近的位置。這就使得子代個體能比較均勻地分布在父代周圍，拓寬了螢火蟲個體的搜索范圍。

2.1.3種群淘汰

經(jīng)過擴散操作之后，種群的規(guī)模擴大，達爾文曾指出：沒有一個自然種群能無限制地增長。種群在增長過程中會遇到來自方方面面的環(huán)境阻力，如種群規(guī)模制約、食物濃度制約和競爭強度制約。

2.2SBGSO主要步驟

本文SBGSO的主要步驟如下：

步驟 1初始化螢火蟲個體熒光素值、位置、決策域半徑、營養(yǎng)值、個體自身最優(yōu)值、全局最優(yōu)值及全局最差值等；

步驟 2螢火蟲個體遍歷圖1一維二值細胞自動機模型，按式(5)隨機選擇0或1；

步驟 3每次迭代之后，計算每只螢火蟲個體所對應(yīng)0/1序列的適應(yīng)值，并與自身最優(yōu)值進行對比，按式(7)對自身營養(yǎng)值進行更新；

步驟 4將螢火蟲個體自身營養(yǎng)值與Nup及Ndown進行對比，進行淘汰或擴散操作；

步驟 5擴散操作，根據(jù)式(8)確定產(chǎn)生的子代數(shù)目，按式(9)和式(10)確定子代位置，并計算子代適應(yīng)值；

步驟 6綜合比較父代和子代個體的適應(yīng)值，得到全局最優(yōu)值和全局最差值；

步驟 7螢火蟲個體按式(1)～式(4)進行移動，并對熒光素、位置及個體決策域半徑進行更新；

步驟 8循環(huán)步驟3～步驟7，若滿足循環(huán)結(jié)束條件，轉(zhuǎn)至步驟9，不滿足繼續(xù)；

步驟 9輸出全局最優(yōu)結(jié)果。

2.3SBGSO收斂性證明

本小節(jié)先通過建立BGSO對應(yīng)的吸收態(tài)Markov過程模型，進而證明本文提出的SBGSO以概率1收斂。

證畢

證明由全概率式可得，對于?t=1,2,…，有

則有

證畢

定理 1當t→∞時，SBGSO以概率1收斂到全局最優(yōu)解。

證明假設(shè)搜索解空間Ω被劃分為n×m個小區(qū)間，則Ω=Z1∪Z2∪…∪Zn，且Zb=z1∪z2∪…∪zm(b=1,2,…，n)。設(shè)定n,m值時，令n,m足夠大，從而確保每個小區(qū)間中只有唯一局部最優(yōu)解。

(2) 淘汰操作。當螢火蟲個體自身營養(yǎng)值低于Ndown時，則淘汰該螢火蟲，表明該區(qū)域相對于上一次迭代，沒有出現(xiàn)更優(yōu)的解。

綜上分析：當t→∞時，螢火蟲個體通過擴散及淘汰操作，可以遍歷整個搜索解空間，故本文提出的SBGSO算法能以概率1收斂到全局最優(yōu)解。

證畢

2.4SBGSO時間復(fù)雜度分析

假設(shè)初始時刻，子種群的規(guī)模為gsonum，L為細胞陣列長度。由第2.2節(jié)算法主要步驟可逐步得出SBGSO算法的時間復(fù)雜度。

因種群規(guī)模為gsonum，步驟1中初始化每只螢火蟲個體的熒光素值、決策域半徑、初始營養(yǎng)值及自身最優(yōu)解的時間復(fù)雜度均為O(gsonum)，初始化螢火蟲個體實數(shù)位置所需時間為gsonum·L，時間復(fù)雜度為O(gsonum·L)，其他參數(shù)初始化時間復(fù)雜度為O(1)；步驟2中g(shù)sonum只螢火蟲個體遍歷圖1隨機選擇0或1，時間復(fù)雜度為O(gsonum·L)；步驟3將每次迭代之后的實數(shù)位置轉(zhuǎn)換成0/1序列，時間復(fù)雜度為O(gsonum·L)，求解種群中所有螢火蟲個體的適應(yīng)值，時間復(fù)雜度為O(gsonum·L)，比較個體適應(yīng)值與自身最優(yōu)適應(yīng)值時間復(fù)雜度為O(gsonum)，更新自身營養(yǎng)值時間復(fù)雜度為O(gsonum)；步驟4中將每只螢火蟲個體自身的營養(yǎng)值與營養(yǎng)閾值的上限Nup和下限Ndown進行對比,時間復(fù)雜度為O(gsonum)；步驟5中假設(shè)每次迭代時，有α個父代需要進行擴散操作，γ只螢火蟲執(zhí)行淘汰操作，且α個父代每次產(chǎn)生的所有子代個數(shù)總和為Nω，當進行擴散操作時，初始化子代個體營養(yǎng)值時間復(fù)雜度為O(Nω)，產(chǎn)生子代個體實數(shù)位置的時間復(fù)雜度為O(Nω·L)，將子代實數(shù)位置轉(zhuǎn)換成0/1序列時間復(fù)雜度為O(Nω·L),計算子代個體適應(yīng)值時間復(fù)雜度為O(gsonum·L)，γ只螢火蟲執(zhí)行淘汰操作時間復(fù)雜度為O(γ·L)；步驟6中綜合比較父代和子代的適應(yīng)值，得到全局最優(yōu)解及全局最差解的時間復(fù)雜為O((gsonum+Nω-γ)·L)；步驟7中螢火蟲熒光素更新時間復(fù)雜度為O(gsonum+Nω-γ)，位置更新時間復(fù)雜度為O((gsonum+Nω-γ)·L)，個體決策域半徑更新時間復(fù)雜度O((gsonum+Nω-γ)·(gsonum+Nω-γ))；步驟8對gsonum+Nω-γ只螢火蟲個體判斷是否滿足結(jié)束條件，需要的時間復(fù)雜度為O(gsonum+Nω-γ)；步驟9輸出全局最優(yōu)解的時間復(fù)雜度為O(1)。

因本文算法經(jīng)過擴散或淘汰操作之后，種群中螢火蟲數(shù)目時刻都在變化。假設(shè)處于飽和狀態(tài)時，種群規(guī)模為gsonum+Nω-γ，則算法經(jīng)過Maxiter次迭代后，SBGSO算法時間復(fù)雜度為

T=O(Maxiter·(gsonum+Nω-γ)·L)

(11)

2.5SBGSO空間復(fù)雜度分析

存儲每只螢火蟲個體的熒光素值及決策域半徑所需空間均為gsonum；存儲長度為L的實數(shù)位置所需空間為gsonum·L；存儲每只螢火蟲個體的0/1序列所需空間為gsonum·L；記錄螢火蟲個體自身最優(yōu)解所需空間為gsonum；記錄螢火蟲個體自身最優(yōu)解所對應(yīng)的0/1序列所需空間為gsonum·L；記錄種群最優(yōu)個體及最差個體所對應(yīng)的0/1序列所需空間均為L；記錄Nω只新螢火蟲執(zhí)行擴散操作所需的存儲空間為Nω+Nω+Nω·L，γ只螢火蟲執(zhí)行淘汰操作會釋放出γ+γ+γ·L個空間；存儲其他參數(shù)所需空間為常數(shù)；則經(jīng)過上述分析，整個計算過程所需的存儲空間為

(12)

3　SBGSO融合RS求屬性約簡問題

3.1屬性約簡優(yōu)化目標

定義 4設(shè)S=為一決策表信息系統(tǒng)，U為論域，C為條件屬性集合，D為決策屬性集合；V=Ur∈AVr為屬性值集合，Vr表示屬性r∈A值域，f:U×A→V為信息函數(shù)[23]。

定義 5給定S=(U,A),U為論域，若B?A,且B≠?,B上的不可分辨關(guān)系IND(B)指B中所有等價關(guān)系的交集∩B也是一個等價關(guān)系[23]。

定義 6給定S=，對于不可分辨關(guān)系B?A及任一子集X?U，B-(X)=:{x|(x∈U∧[x]B∩X≠?)}和B-(X)={x|(x∈U∧[x]B?X)}分別表示X的上、下近似集,集合BNB(X)=B-(X)-B-(X)稱為X的B邊界，[X]B表示U中所有與x的不可分辨關(guān)系IND(B)[23]。

定義 7設(shè)近似空間P為k=(U,R)，Q∈R稱知識Q以依賴度k(0≤k≤1)依賴于知識P，即P?Q,當且僅當

(13)

式中，card表示集合的基數(shù)；posP(Q)為Q的P正域。

假設(shè)L為原始數(shù)據(jù)集中的屬性個數(shù)，ν為約簡后的屬性個數(shù)，本文的目標為：①約簡后所得的屬性必須滿足分類質(zhì)量；②約簡后的屬性個數(shù)必須盡量少，即

(14)

式中，k(0≤k≤1)表示決策屬性對條件屬性的依賴度。

3.2基于ASDM屬性依賴度求解算法

為求解屬性的依賴度，采用文獻[24]提出的屬性集合依賴度算法(attribute sets dependability method, ASDM),其求解步驟如下：

步驟 1將條件屬性集P作等價類劃分，得等價類γ；

步驟 2將決策屬性集作等價類劃分,得等價類Ψ；

步驟 3求γ∩Ψ的元素數(shù)，即card()；

步驟 4k=rP(Q)={card()|{γ∩Ψ}}/{對象個數(shù)}。

3.3SBGSO融合RS求解屬性約簡主要步驟

本小節(jié)將第2節(jié)提出的SBGSO結(jié)合RS,求解屬性約簡問題。令原始數(shù)據(jù)集屬性個數(shù)為L，則圖1的一維細胞自動機長度為L。細胞狀態(tài)Q={0,1},螢火蟲從起始細胞出發(fā),從左向右遍歷一維細胞自動機,隨機選擇0或1,1表示該屬性被選擇核屬性,0表示該屬性不是核屬性,如0/1序列 (1,0,0,1,0,0,0,1) 表示原始屬性集中第1,4,8屬性為核屬性。然后利用ASDM算法計算每只螢火蟲個體所對應(yīng)0/1序列的屬性依賴度，進而得出螢火蟲個體的適應(yīng)值。

步驟 1初始化螢火蟲位置、熒光素值、決策域半徑、個體營養(yǎng)值及營養(yǎng)閾值上下限等參數(shù)；

步驟 2設(shè)條件屬性個數(shù)為L，則細胞自動機長度設(shè)為L，細胞狀態(tài)Q={0,1},螢火蟲個體遍歷圖1一維二值細胞自動機模型，隨機選擇0或1，1表示該屬性為核屬性，反之0不是；

步驟 3每次迭代之后，利用ASDM算法計算核屬性的屬性依賴度，計算每只螢火蟲個體所對應(yīng)0/1序列的適應(yīng)值，并將該適應(yīng)值與自身最優(yōu)值進行比較，更新自身營養(yǎng)值；

步驟 4將每只螢火蟲個體自身營養(yǎng)值與營養(yǎng)閾值的上限Nup和下限Ndown進行對比，進行淘汰或擴散操作；

步驟 5擴散操作，確定擴散操作后產(chǎn)生的子代數(shù)目，確定子代位置，并給子代個體賦予營養(yǎng)值初始值，最后計算子代個體適應(yīng)值；

步驟 6綜合比較父代和子代適應(yīng)值，得到全局最優(yōu)值和全局最差值；

步驟 7螢火蟲熒光素、位置及個體決策域半徑更新；

步驟 8循環(huán)步驟3～步驟7，若滿足循環(huán)結(jié)束條件，轉(zhuǎn)至步驟9，不滿足繼續(xù)；

步驟 9輸出全局最優(yōu)值。

4　仿真實驗

4.1實驗設(shè)置

4.1.1實驗環(huán)境設(shè)置

本文所涉及的所有實驗均采用VC6.0編寫，編譯運行的PC機參數(shù)為32位Windows 7操作系統(tǒng)Intel(R) Core(TM) i5-3470 CPU, 3.20 GHz。

4.1.2參數(shù)設(shè)置說明

算法中各參數(shù)設(shè)置如下：Xmax=5，Xmin=-5，li(0)=5.0，μ=0.6，ρ=0.4，s=0.03，η=0.08，nt=5，τ0=3，τf=0.5，初始決策域半徑為1.0，最大決策域半徑為3.0。種群規(guī)模gsonum及運行代數(shù)的設(shè)置一般與問題的規(guī)模成正比。營養(yǎng)閾值的上限Nup和下限Ndown的設(shè)置根據(jù)具體問題進行自適應(yīng)調(diào)整(如在求解Breast Cancer數(shù)據(jù)集時，Nup=10，Ndown=1)。

4.2測試數(shù)據(jù)

為了驗證本文算法的可行性和有效性，選用UCI中的5個數(shù)據(jù)集進行實驗(見表1)。在利用本文算法時，不考慮類別數(shù)。在UCI數(shù)據(jù)集中，Breast Cancer的實例數(shù)總共有699個，但因其中16個實例缺失屬性值，在實驗中將該16個實例剔除，剩余683個；剩余數(shù)據(jù)集Bupa, Wine, Iris, Contraceptive均無屬性值缺失。

表1　測試數(shù)據(jù)集

4.3實驗結(jié)果分析

4.3.1屬性約簡率及對比實驗

運用本文SBGSO結(jié)合RS，屬性約簡結(jié)果見表2。其中，屬性約簡率為((L-ν)/L)×100%。對比分析文獻[22,25]，如表3所示：本文算法除Wine數(shù)據(jù)集在約簡率上稍微低于文獻[25]，其他數(shù)據(jù)集的約簡率均等于或大于文獻[22,25]。同樣對比分析文獻[26-27]，如表4所示：本文算法在數(shù)據(jù)集Wine和Iris上的屬性約簡率大大高于樂觀多粒度模糊粗糙集約簡算法、悲觀多粒度模糊粗糙集約簡及一致性準則屬性約簡算法。

表2　本文方法屬性約簡結(jié)果

表3　多種方法屬性約簡結(jié)果對比分析(1)

表4　多種方法屬性約簡結(jié)果對比分析(2)

4.3.2分類準確率及對比實驗

在采用SBGSO結(jié)合RS進行屬性約簡后，繼續(xù)采用中國臺灣學(xué)者Chih-Jen Lin提供的LIB-SVM (www.csie.ntu.edu.tw/～cjlin/libsvm)算法結(jié)合10-fold交叉驗證分析屬性約簡前后的分類準確率，選擇徑向基核函數(shù)(radial basis function,RBF)為支持向量機(support vector machine,SVM)的核函數(shù)，最優(yōu)參數(shù)c∈[2-5,215]，g∈[2-15,23]的值利用網(wǎng)格搜索法選取，實驗結(jié)果如表5所示。

表5　屬性約簡分類準確率分析

運用本文方法，Bupa屬性子集的最優(yōu)分類準確率和平均分類準確率均有所提高，分別上升了2.462 1%和0.692 4%；Wine和Iris屬性子集的最優(yōu)分類準確率與原始數(shù)據(jù)集基本保持一致，而平均分類準確率分別上升了6.816 4%和1.867 1%；Breast Cancer和Contraceptive的最優(yōu)分類準確率和平均分類準確率有輕微下降。

在現(xiàn)有文獻中，將群智能算法與相應(yīng)子集評估度量準則相結(jié)合來求解屬性約簡的方法較多。如文獻[22]結(jié)合基于生命周期的二元蟻群算法和分形維數(shù)應(yīng)用于屬性約簡，文獻[25]結(jié)合改進的離散型螢火蟲算法和分形理論求解屬性約簡問題，而本文以SBGSO作為搜索策略、RS作為子集評估度量準則。表6將本文實驗結(jié)果與文獻[22,25]進行對比，進一步體現(xiàn)了本文算法的優(yōu)越性。

表6　文獻[22,25]方法與本文方法對比結(jié)果

由表6可知，針對數(shù)據(jù)集Wine和Iris，本文算法具有更好的最優(yōu)分類準確率和平均分類準確率；而數(shù)據(jù)集Bupa和Contraceptive屬性子集的最優(yōu)分類準確率及平均分類準確率均高于文獻[22]，但均略低于文獻[25]；數(shù)據(jù)集Breast Cancer的最優(yōu)分類準確率與文獻[22,25]一致，但平均分類準確率略低于文獻[22,25]。

5　結(jié)束語

本文主要工作如下：①從一維細胞自動機模型入手，將BGSO歸結(jié)到一維二值細胞自動機這一框架之下，不僅很好地解決了帶0/1特性的二元離散優(yōu)化問題，而且體現(xiàn)了計算的本質(zhì)；②將自然界中種群擴散行為引入BGSO中，提出了SBGSO，保持了種群的動態(tài)多樣性，平衡了算法“探索和利用”的沖突；③屬性約簡在大數(shù)據(jù)預(yù)處理中起著十分重要的作用，本文將SBGSO與RS相結(jié)合，為大數(shù)據(jù)的預(yù)處理提供了一種新穎的方法。因生物擴散在自然生態(tài)系統(tǒng)中隨處可見，下一步的工作將繼續(xù)研究生態(tài)系統(tǒng)中種群的擴散動力學(xué)，并將其引入到其他群智能算法中，以彌補算法的“早熟”缺陷。

[1] Krishnanand K N, Ghose D. Glowworm swarm optimisation:a new method for optimising multimodal functions [J].InternationalJournalofComputationalIntelligenceStudies, 2009, 1(1):93-119.

[2] Yang X S.Nature-inspiredetaheutisticalgorithms[M]. London: Luniver Press, 2008.

[3] Jayakumar D N, Venkatesh P. Glowworm swarm optimization algorithm with topsis for solving multiple objective environmental economic dispatch problem [J].AppliedSoftComputing, 2014, 23(10):375-386.

[4] Wu B, Qian C H, Ni W H, et al. The improvement of glowworm optimization for continuous optimization problem [J].ExpertSystemwithApplications, 2013, 39(7): 6335-6342.

[5] Du P Z, Tang Z M, Lu J F, et al. Global path planning for ALV based on improved glowworm swarm optimization under uncer-tain enviroment [J].ActaElectronicaSinica, 2014,42(3):616-624.(杜鵬楨,唐振民, 陸建峰,等.不確定環(huán)境下基于改進螢火蟲算法的地面自主車輛全局路徑規(guī)劃方法[J]. 電子學(xué)報, 2014,42(3):616-624.)

[6] Fan Y S, Wang M L, Wen M M, et al. Analysis of ballistic missile penetration effectiveness based on FA-AHP [J].SystemsEngineeringandElectronics,2015, 37(4): 845-850. (范陽壽,汪民樂,文苗苗,等.基于螢火蟲算法層次分析法的彈道導(dǎo)彈突防效能分析[J]. 系統(tǒng)工程與電子技術(shù), 2015,37(4): 845-850.)

[7] Yu S H, Su S B. Research and application of chaotic glowworm swarm optimization algorithm[J].JournalofFrontiersofComputerScienceandTechnology,2014,8(3):352-357.(郁書好, 蘇守寶. 混沌螢火蟲優(yōu)化算法的研究及應(yīng)用[J]. 計算機科學(xué)與探索, 2014,8(3):352-357.)

[8] Xu H L, Su S B, Yan R R, et al. A firefly algorithm with chaotic diversity control [J].JournalofUniversityofScienceandTechnologyofChina, 2014,44(7):612-617. (徐華麗,蘇守寶, 嚴仍榮, 等. 一種混沌多樣性控制的螢火蟲優(yōu)化算法[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報, 2014，44(7):612-617.)

[9] Zhang J L, Zhou G, Zhou Y Q. A new artificial glowwarm optimization algorithm based on chaos method [J].AdvancesinIntelligentandSoftComputing, 2010, 82: 683-693.

[10] Yu S H, Yang S L, Su S B. A improve glowworm swarm optimization with adaptive step[J].Mini-microSystems, 2014，35(6): 1396-1400. (郁書好, 楊善林, 蘇守寶. 一種改進的變步長螢火蟲優(yōu)化算法[J]. 小型微型計算機系統(tǒng), 2014，35(6): 1396-1400.)

[11] He L F, Tong X, Huang S W. Glowwarm swarm optimization algorithm based on hierarchical multi-subgroups[J].JournalofInformation&ComputationScience, 2013,10 (4): 1245-1251.

[12] Huang Z X, Zhou Y Q. Adaptive glowwarm swarm optimization algorithm with changing step for optimizing multimodal functions [J].ComputerEngineeringandApplication, 2012, 48(8):43-47. (黃正新, 周永權(quán). 一種變步長自適應(yīng)螢火蟲群多模態(tài)函數(shù)優(yōu)化算法[J]. 計算機工程與應(yīng)用,2012,48(8):43-47.)

[13] Huang Z X, Zhou Y Q. Self-adaptive step glowworm swarm optimization algorithm for optimizing multimodal function[J].ComputerScience, 2011, 38(7): 220-224. (黃正新,周永權(quán).自適應(yīng)步長螢火蟲群多模態(tài)函數(shù)優(yōu)化算法[J].計算機科學(xué),2011, 38(7):220-224.)

[14] Li Y M, Zhou Y Q, Yao X G. Improved glowwrom swarm optimization based on the behavior of follow[J].ComputerScience, 2011,38(3): 248-251. (李詠梅,周永權(quán),姚祥光. 基于追尾行為的改進型人工螢火蟲群算法[J],計算機科學(xué),2011, 38(3): 248-251.)

[15] Du X X, Zhang J F, Sun M. Artificial glowworm swarm optimization algorithm based on adaptive distribution mixed mutation[J].JournalofComputerApplications, 2013, 33(7): 1922-1925, 1972.(杜曉昕,張劍飛,孫明.基于自適應(yīng)t分布混合變異的人工螢火蟲算法[J].計算機應(yīng)用，2013,33(7)：1922-1925,1972.)

[16] Wu B, Cui Z Y, Ni W H. Hybrid swarm intelligence behavior [J].ComputerScience, 2012, 39(5):198-200. (吳斌,崔志勇,倪衛(wèi)紅.具有混合群智能行為的螢火蟲群優(yōu)化算法研究[J].計算機科學(xué),2012, 39(5):198-200.)

[17] Wu Bin, Qian C H, Ni W H. Glowworm swarm optimization for cross dock scheduling problem[J].ComputerEngineeringandApplication, 2013, 49(6): 39-42,51. (吳斌,錢存華,倪衛(wèi)紅.螢火蟲群優(yōu)化算法在越庫調(diào)度問題中的應(yīng)用[J].計算機工程與應(yīng)用,2013, 49(6): 39-42,51.)

[18] Li Y. Leapfrog firefly algorithm and application in dispatch of power system containing wind farm [D]. Shanghai: East China University of Science, 2013. (李洋.蛙跳螢火蟲算法及其在含風電場的電力系統(tǒng)調(diào)度中的應(yīng)用[D].上海：華東理工大學(xué)，2013.)

[19] Wang Y J. Hybrid artificial fireflies swarm optimization algorithm and its application [D]. Guangxi：Guangxi University of Nationalities, 2012.(王迎菊.混合型人工螢火蟲群優(yōu)化算法及應(yīng)用研究[D]. 南寧：廣西民族大學(xué)，2012.)

[20] Zhang L. The study of dispersal population dynamics [D]. Xinjiang： Xinjiang University, 2007. (張龍. 擴散種群的動力學(xué)模型研究[D].烏魯木齊: 新疆大學(xué), 2007.)

[21] Sang H Y, Pan Q K. A discrete invasive weed optimization algorithm for the integrated lot-streaming flow shop scheduling problem [J].ControlTheory&Applications，2015, 32 (2): 246-250. (桑紅燕,潘全科.求解流水車間批量流集成調(diào)度的離散入侵雜草優(yōu)化算法[J].控制理論與應(yīng)用,2015, 32(2): 246-250.)

[22] Cheng M Y, Ni Z W, Zhu X H. Lifecycle-based binary ant colony algorithm [J].PatternRecognitionandArtificialIntelligence, 2014, 27(11): 1005-1014. (程美英,倪志偉,朱旭輝.基于生命周期的二元蟻群優(yōu)化算法[J].模式識別與人工智能,2014, 27(11): 1005-1014.)

[23] Xu X S, Chen R Y. Attribute decision reduction method based on hybrid rough sets and niche immune optimization[J].ActaElectronicaSinica,2014,42(8):1545-1550.(徐雪松,陳榮元.融合粗糙集與小生境免疫優(yōu)化的屬性約簡方法[J].電子學(xué)報, 2014, 42(8):1545-1550.)

[24] Meng Q Q, Mei C H. Research on a new dependability of attribute sets [J].ComputerApplication, 2007, 27(7):1748-1750. (孟慶全,梅燦華.一種新的屬性集依賴度[J].計算機應(yīng)用,2007, 27(7):1748-1750.)

[25] Ni Z W, Xiao H W, Wu Z J, et al. Attribute selection method based on improved discrete glowworm swarm optimization and fractal dimension [J].PatternRecognitionandArtificialIntelligence, 2013, 26(12): 1169-1178. (倪志偉，肖宏旺，伍章俊，等. 基于改進離散型螢火蟲群優(yōu)化算法和分形維數(shù)的屬性選擇方法[J]. 模式識別與人工智能, 2013, 26(12): 1169-1178.)

[26] Cui Y J. Multi-granularity rough set in incomplete information systems theory and reduction research [D]. Nanjing: Nanjing University of Science & Technology, 2014. (翟永健.不完備信息系統(tǒng)中多粒度粗糙集理論與約簡研究[D]. 南京：南京理工大學(xué)，2014.)

[27] Yang M. A novel algorithm for attribute reduction based on consistency criterion [J].ChineseJournalofComputers, 2010, 33(2): 231-239. (楊明.一種基于一致性準則的屬性約簡算法[J].計算機學(xué)報,2010, 33(2): 231-239.)

Attribute reduction method combined with spread binary glowworm swarm optimization and rough set

CHENG Mei-ying1,2,3, NI Zhi-wei1,2, ZHU Xu-hui1,2

(1. School of Management，Hefei University of Technology， Hefei 230009, China; 2.Key Laboratory ofProcessOptimizationandIntelligentDecision-Making，MinistryofEducation，Hefei230009,China;3.ComputationalIntelligenceLab,SchoolofComputerScienceandEngineering,NanyangTechnologicalUniversity,Singapore639798)

Starting from the one-dimensional cellular automata model, the spread mechanism is introduced to binary glowworm swarm optimization (BGSO), and a spread binary glowworm swarm optimization (SBGSO) is proposed. In SBGSO, nutrition value and nutrition threshold is involved to each glowworm, then the spread operation is performed to produce offspring by using the method of normal distribution. Additionally, the individuals who continue to perform poorly are eliminated. The aforementioned operations can largely keep the diversity of the whole populations. After that, SBGSO is combined with rough set (RS) to handle the attribute reduction problem. When dealing with the attribute reduction problem, SBGSO is taken as a kind of search strategy and RS is taken as the evaluation criteria for attribute subsets. To analyze the feasibility and effectiveness of the proposed method, five UCI datasets are used to conduct experiments. Moreover, the 10-fold and SVM are involved to analyze the classification accuracy, experimental results show that the method has relatively higher reduction rate compared with other methods.

binary glowworm swarm optimization (BGSO); spread mechanism; one-dimensional cellular automata; rough set (RS); attribute reduction

2015-10-09；

2016-06-20；網(wǎng)絡(luò)優(yōu)先出版日期：2016-07-20。

TP 301.6

A

10.3969/j.issn.1001-506X.2016.10.32

程美英(1983-)，女，博士研究生，主要研究方向為計算智能、數(shù)據(jù)挖掘。

E-mail:qyc12117@126.com

倪志偉(1963-)，男，教授，博士研究生導(dǎo)師，主要研究方向為數(shù)據(jù)挖掘、機器學(xué)習、人工智能。

E-mail:zhwnelson@163.com

朱旭輝(1991-)，男，博士研究生，主要研究方向為進化計算、數(shù)據(jù)挖掘。

E-mail:943177204@qq.com

網(wǎng)絡(luò)優(yōu)先出版地址：http:∥www.cnki.net/kcms/detail/11.2422.TN.20160720.1114.004.html