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

程美英， 倪志偉， 朱旭輝

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

?

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

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

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

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

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

0　引　言

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

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

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

1　BGSO

1.1基本GSO

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

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

(1)

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

(2)

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

(3)

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

(4)

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

1.2BGSO一維細胞自動機模型

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

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

(5)

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

2　SBGSO

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

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

2.1SBGSO主要思想

2.1.1種群初始化

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

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

(6)

2.1.2種群擴散

(7)

(8)

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

(9)

則由父代個體i產生的子代位置為

(10)

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

2.1.3種群淘汰

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

2.2SBGSO主要步驟

本文SBGSO的主要步驟如下：

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

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

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

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

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

步驟 6綜合比較父代和子代個體的適應值，得到全局最優值和全局最差值；

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

步驟 8循環步驟3～步驟7，若滿足循環結束條件，轉至步驟9，不滿足繼續；

步驟 9輸出全局最優結果。

2.3SBGSO收斂性證明

本小節先通過建立BGSO對應的吸收態Markov過程模型，進而證明本文提出的SBGSO以概率1收斂。

證畢

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

則有

證畢

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

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

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

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

證畢

2.4SBGSO時間復雜度分析

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

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

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

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

(11)

2.5SBGSO空間復雜度分析

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

(12)

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

3.1屬性約簡優化目標

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

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

定義 6給定S=，對于不可分辨關系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的不可分辨關系IND(B)[23]。

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

(13)

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

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

(14)

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟 5擴散操作，確定擴散操作后產生的子代數目，確定子代位置，并給子代個體賦予營養值初始值，最后計算子代個體適應值；

步驟 6綜合比較父代和子代適應值，得到全局最優值和全局最差值；

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

步驟 8循環步驟3～步驟7，若滿足循環結束條件，轉至步驟9，不滿足繼續；

步驟 9輸出全局最優值。

4　仿真實驗

4.1實驗設置

4.1.1實驗環境設置

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

4.1.2參數設置說明

算法中各參數設置如下：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。種群規模gsonum及運行代數的設置一般與問題的規模成正比。營養閾值的上限Nup和下限Ndown的設置根據具體問題進行自適應調整(如在求解Breast Cancer數據集時，Nup=10，Ndown=1)。

4.2測試數據

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

表1　測試數據集

4.3實驗結果分析

4.3.1屬性約簡率及對比實驗

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

表2　本文方法屬性約簡結果

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

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

4.3.2分類準確率及對比實驗

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

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

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

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

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

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

5　結束語

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

[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.(杜鵬楨,唐振民, 陸建峰,等.不確定環境下基于改進螢火蟲算法的地面自主車輛全局路徑規劃方法[J]. 電子學報, 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. (范陽壽,汪民樂,文苗苗,等.基于螢火蟲算法層次分析法的彈道導彈突防效能分析[J]. 系統工程與電子技術, 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.(郁書好, 蘇守寶. 混沌螢火蟲優化算法的研究及應用[J]. 計算機科學與探索, 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. (徐華麗,蘇守寶, 嚴仍榮, 等. 一種混沌多樣性控制的螢火蟲優化算法[J]. 中國科學技術大學學報, 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. (郁書好, 楊善林, 蘇守寶. 一種改進的變步長螢火蟲優化算法[J]. 小型微型計算機系統, 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. (黃正新, 周永權. 一種變步長自適應螢火蟲群多模態函數優化算法[J]. 計算機工程與應用,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. (黃正新,周永權.自適應步長螢火蟲群多模態函數優化算法[J].計算機科學,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. (李詠梅,周永權,姚祥光. 基于追尾行為的改進型人工螢火蟲群算法[J],計算機科學,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.(杜曉昕,張劍飛,孫明.基于自適應t分布混合變異的人工螢火蟲算法[J].計算機應用，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. (吳斌,崔志勇,倪衛紅.具有混合群智能行為的螢火蟲群優化算法研究[J].計算機科學,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. (吳斌,錢存華,倪衛紅.螢火蟲群優化算法在越庫調度問題中的應用[J].計算機工程與應用,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. (李洋.蛙跳螢火蟲算法及其在含風電場的電力系統調度中的應用[D].上海：華東理工大學，2013.)

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

[20] Zhang L. The study of dispersal population dynamics [D]. Xinjiang： Xinjiang University, 2007. (張龍. 擴散種群的動力學模型研究[D].烏魯木齊: 新疆大學, 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. (桑紅燕,潘全科.求解流水車間批量流集成調度的離散入侵雜草優化算法[J].控制理論與應用,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. (程美英,倪志偉,朱旭輝.基于生命周期的二元蟻群優化算法[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.(徐雪松,陳榮元.融合粗糙集與小生境免疫優化的屬性約簡方法[J].電子學報, 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].計算機應用,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. (倪志偉，肖宏旺，伍章俊，等. 基于改進離散型螢火蟲群優化算法和分形維數的屬性選擇方法[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. (翟永健.不完備信息系統中多粒度粗糙集理論與約簡研究[D]. 南京：南京理工大學，2014.)

[27] Yang M. A novel algorithm for attribute reduction based on consistency criterion [J].ChineseJournalofComputers, 2010, 33(2): 231-239. (楊明.一種基于一致性準則的屬性約簡算法[J].計算機學報,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；網絡優先出版日期：2016-07-20。

TP 301.6

A

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

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

E-mail:qyc12117@126.com

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

E-mail:zhwnelson@163.com

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

E-mail:943177204@qq.com

網絡優先出版地址：http:∥www.cnki.net/kcms/detail/11.2422.TN.20160720.1114.004.html