采用云量子PSO的屬性約簡方法

常紅偉，夏克文 ，2，白建川 ，2，牛文佳 ，武盼盼

1.河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津 300401

2.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401

粗糙集（RS）理論是一種有效分析和處理不準(zhǔn)確、不完整信息的數(shù)學(xué)工具。其中，屬性約簡是粗糙集理論的核心內(nèi)容之一，是在保持原有判斷能力不改變的條件下，剔除其中不相關(guān)或不重要的屬性，然后探索最優(yōu)的屬性組合，從而降低知識(shí)的復(fù)雜度，減小系統(tǒng)規(guī)模，進(jìn)而發(fā)現(xiàn)隱含的知識(shí)，挖掘出潛在的規(guī)律[1-2]。屬性約簡的計(jì)算問題是一個(gè)NP-hard問題[3]。針對(duì)該問題，不少學(xué)者提出了很多高效的啟發(fā)式搜索算法，其中，有很多關(guān)于粒子群優(yōu)化算法（PSO）與屬性約簡相結(jié)合的方法。在文獻(xiàn)[4]中，提出了一種基于GA-PSO的粗糙集約簡方法，對(duì)不滿足適應(yīng)度條件的粒子進(jìn)行交叉變異，加強(qiáng)局部收斂能力同時(shí)保持了全局搜索能力；在文獻(xiàn)[5]中，提出一種粗糙集和遺傳粒子群算法相結(jié)合的方法進(jìn)行屬性約簡，在數(shù)據(jù)量大、屬性維度高的問題上，具有高效的處理能力；在文獻(xiàn)[6]中，提出一種基于PSO算法的屬性約簡方法，應(yīng)用于有監(jiān)督的特征選擇中，同時(shí)利用標(biāo)準(zhǔn)醫(yī)療數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了所提方法增強(qiáng)現(xiàn)有的特征技術(shù)的效率；在文獻(xiàn)[7]中，提出一種量子粒子群算法和蝙蝠算法相混合的方法，避免早熟的同時(shí)改變量子粒子群中的因子，并將其應(yīng)用于求解模具車間調(diào)度問題。

而在粒子群優(yōu)化算法中，種群根據(jù)自身所處的位置選擇不同搜索方式存在模糊性、不確定性，不能準(zhǔn)確地找到全局搜索和局部搜索的平衡點(diǎn)，進(jìn)而容易造成局部最優(yōu)和早熟等問題[8]。為此，Sun等人提出了量子粒子群優(yōu)化算法（QPSO），使粒子能夠出現(xiàn)在可行區(qū)域的任意位置，擴(kuò)大了搜索區(qū)間，與標(biāo)準(zhǔn)PSO相比，尋優(yōu)性能有所增強(qiáng)[9]。盡管如此，依然存在陷入局部最優(yōu)的可能。而云模型[10]是由中國工程院院士李德毅等人提出的一種描述定性與定量之間的不確定關(guān)系模型，其特征可以通過期望值、熵值和超熵值來表示，構(gòu)造不同的算法來生成云滴及確定度，進(jìn)而為不確定的、模糊的定性定量關(guān)系提供搜索方法依據(jù)。

為此，本文擬引入云模型到量子粒子群算法中，提出了一種結(jié)合云模型改進(jìn)的量子粒子群算法，同時(shí)利用屬性依賴度構(gòu)造屬性約簡數(shù)學(xué)模型，然后使用改進(jìn)的算法求解該數(shù)學(xué)模型，并對(duì)UCI數(shù)據(jù)庫中的4個(gè)典型數(shù)據(jù)集進(jìn)行仿真對(duì)比與分析。

1 改進(jìn)量子粒子群算法

1.1 量子PSO概述

量子粒子群優(yōu)化算法（QPSO）是在2004年Sun等人研究了Clcrc教授的關(guān)于PSO粒子收斂行為的研究成果后提出的一種新穎智能算法模型。該模型基于δ勢(shì)阱建立的，因此粒子具有量子的行為。由于處于量子束縛態(tài)的粒子能夠以特定的幾率出現(xiàn)在量子空間中任意位置，同時(shí)滿足聚集態(tài)的性質(zhì)，進(jìn)而能夠搜索整個(gè)區(qū)間，因此QPSO算法的全局搜索能力強(qiáng)于PSO優(yōu)化算法。由于量子空間中的粒子無法同時(shí)確定速度和位置，因此粒子的狀態(tài)只能通過波函數(shù)來表示，同時(shí)利用求解Schrodinger方程獲得空間中粒子在某點(diǎn)顯現(xiàn)的概率密度函數(shù)。為了得到粒子的位置，將量子狀態(tài)塌縮到經(jīng)典狀態(tài)，進(jìn)一步利用逆變換方法獲得粒子的位置公式：

在文獻(xiàn)[11]中L被定義為：

粒子的位置計(jì)算公式表示如下：

其中，μ,rand表示[0，1]之間的隨機(jī)數(shù)；β表示收縮擴(kuò)張因子；M表示種群的個(gè)數(shù)；D表示粒子的維度；Pi表示第i個(gè)粒子的Pbest；X(t)表示前一時(shí)刻粒子的位置。

而收縮擴(kuò)張因子β對(duì)傳統(tǒng)的量子PSO算法收斂性有很大的影響。如果選取不當(dāng)，就會(huì)陷入局部最優(yōu)和早熟。下面將對(duì)算法提出改進(jìn)。

1.2 算法改進(jìn)

本文將云模型與量子粒子群算法結(jié)合，形成云量子粒子群算法（CQPSO），為了平衡收縮擴(kuò)張因子對(duì)QPSO算法收斂性的影響，改進(jìn)的算法利用黃金分割理論，把粒子分成3個(gè)子群，根據(jù)不同粒子群的搜索狀態(tài)調(diào)整收縮擴(kuò)張因子β的值，調(diào)整策略如下：

（1）設(shè)粒子群的個(gè)數(shù)為n，在第k次迭代中xi的適應(yīng)度為 fi(k)，同時(shí)根據(jù)適應(yīng)度的大小，對(duì)種群進(jìn)行從小到大的排序，則粒子群的黃金適應(yīng)度為：

優(yōu)于 fgold(k)的粒子群個(gè)數(shù)為n1，則其黃金適應(yīng)度為：

次于 fgold(k)的粒子群個(gè)數(shù)為n2，則其黃金適應(yīng)度為：

本文根據(jù)粒子適應(yīng)度的不同來確定不同的收縮因子，進(jìn)而將粒子群劃分為3個(gè)子群。

（2）如果當(dāng)前粒子的適應(yīng)度 fi(k)優(yōu)于 fgold1(k)，表明該部分粒子接近最優(yōu)值，不需要再進(jìn)行全局搜索，應(yīng)加快局部收斂速度，所以收斂因子β取0.4。

（3）若粒子適應(yīng)度 fi(k)優(yōu)于 fgold2(k)而次于 fgold1(k)，采用云模型對(duì)其改進(jìn)：先設(shè)定粒子的數(shù)學(xué)期望值為EX=fbest(k),b1=b2=2，粒子的熵為：En=(fgold1(k)-fbest(k))/b1，設(shè)粒子的超熵與熵的關(guān)系值為He=En/b2,則在此區(qū)間內(nèi)的粒子β的取值為：

式（10）中 En′=normrnd(En,He)。

（4）若粒子適應(yīng)度 fi(k)次于 fgold2(k)，則該部分粒子適應(yīng)度較差，表明距離群體的最優(yōu)解較遠(yuǎn)，應(yīng)擴(kuò)大全局收斂能力，所以收斂因子β取0.9。

1.3 測(cè)試函數(shù)仿真對(duì)比

為了驗(yàn)證新算法的有效性，本文采用4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)[12]進(jìn)行仿真對(duì)比。

（1）Sphere經(jīng)典函數(shù)是單峰函數(shù)，數(shù)學(xué)表示如下：

該函數(shù)在x=[0,0,…,0]處有全局最小值0。仿真尋優(yōu)迭代曲線如圖1所示。

圖1 Sphere函數(shù)尋優(yōu)迭代曲線

由圖1可知，在相同的初始值和初始速度條件下，CQPSO下降速度最快，同時(shí)CQPSO算法到達(dá)最大迭代次數(shù)200次后達(dá)到無限接近全局最優(yōu)[0,0,…,0]處，比QPSO算法迭代尋優(yōu)結(jié)果精確7個(gè)數(shù)量級(jí),同時(shí)比PSO算法迭代尋優(yōu)結(jié)果精確16個(gè)數(shù)量級(jí)。

（2）Schwefel經(jīng)典函數(shù)也是一個(gè)單峰函數(shù)，數(shù)學(xué)表示如下：

該函數(shù)在x=[0,0,…,0]處有全局最小值0。仿真尋優(yōu)迭代曲線如圖2所示。

圖2 Schwefel函數(shù)尋優(yōu)迭代曲線

由圖2可知，CQPSO算法和QPSO算法到達(dá)最大迭代次數(shù)50次后，取得的最小值無限接近于全局最優(yōu)[0,0,…,0]處，比PSO算法迭代結(jié)果精確1個(gè)數(shù)量級(jí)。

（3）Rastrigin經(jīng)典函數(shù)是多峰函數(shù)，數(shù)學(xué)表示如下：

該函數(shù)在x=[0,0,…,0]處有全局最小值0。仿真尋優(yōu)迭代曲線如圖3所示。

圖3 Rastrigin函數(shù)尋優(yōu)迭代曲線

由圖3可知，在相同的初始值和初始速度條件下，CQPSO下降速度最快，CQPSO算法迭代170次時(shí)達(dá)到全局最優(yōu)[0,0,…,0]處，傳統(tǒng)QPSO算法迭代173次達(dá)全局最優(yōu)，傳統(tǒng)PSO算法迭代185次達(dá)全局最優(yōu)。

（4）Ackley函數(shù)為連續(xù)、旋轉(zhuǎn)、不可分離的多峰函數(shù)。主要通過一個(gè)余弦波形來調(diào)整指數(shù)函數(shù)，維數(shù)可調(diào)。它的拓?fù)浣Y(jié)構(gòu)的特征是：外部區(qū)域幾乎平坦（由于主導(dǎo)函數(shù)是指數(shù)函數(shù)），中間出現(xiàn)一個(gè)孔或者峰（由于余弦波形的調(diào)整），從而變得不平滑。此多峰函數(shù)具有大量局部優(yōu)點(diǎn)，但是全局最優(yōu)值在[0,0,…,0]處。數(shù)學(xué)表示如下：

該函數(shù)在x=[0,0,…,0]處有全局最小值0。仿真尋優(yōu)迭代曲線如圖4所示。

圖4 Schwefel函數(shù)尋優(yōu)迭代曲線

由圖4可知，CQPSO算法到達(dá)最大迭代次數(shù)100次后達(dá)到無限接近全局最優(yōu)[0,0,…,0]處，比QPSO算法迭代尋優(yōu)結(jié)果精確2個(gè)數(shù)量級(jí)，同時(shí)比PSO算法迭代尋優(yōu)結(jié)果精確4個(gè)數(shù)量級(jí)。

由于仿真函數(shù)的最小值均為0，所以仿真結(jié)果的最小值與誤差相等。上述測(cè)試函數(shù)仿真結(jié)果即誤差如表1所示。

表1 測(cè)試函數(shù)仿真結(jié)果對(duì)比表

通過上述經(jīng)典函數(shù)仿真測(cè)試，提出的CQPSO算法可行。下面將進(jìn)一步應(yīng)用此改進(jìn)的算法進(jìn)行屬性約簡。

2 基于CQPSO算法的粗糙集屬性約簡

2.1 屬性約簡描述

粗糙集理論是一種有效分析和處理不準(zhǔn)確、不完整信息的有效工具[13]。屬性約簡的目的是在保持原有判斷能力不改變的條件下，保證屬性約簡個(gè)數(shù)最少。粗糙集和屬性約簡相關(guān)基本知識(shí)如下：

定義1設(shè) P?Q,Y∈U,[x]p={y∈U|x ind(P)y},集合Y的下邊界（正域）定義為：PY=posp(Y)={x∈U|[x]p∈Y}。

定義2設(shè)一個(gè)知識(shí)庫K=(U,R),R表示一個(gè)等價(jià)關(guān)系P,Q∈R，依賴性γp(Q)=card(posp(Q))/card(U)，其中card(X)表示集合X中所包含元素的個(gè)數(shù)。

定義3條件屬性C中所有不可缺少的屬性的集合。

定理1若R?P,γp(Q)=γR(Q)，則稱R是P的一個(gè)相對(duì)約簡。

由定理1可知，約簡前后劃分Q的依賴性是不變的。

2.2 粒子編碼與適應(yīng)值函數(shù)

（1）粒子編碼

對(duì)于PSO中的粒子編碼問題，通過一定的轉(zhuǎn)換，先將屬性轉(zhuǎn)成能夠直接處理的粒子形式。假設(shè)信息系統(tǒng)的屬性集為Q={q1,q2,…,qn}，通過編碼將其轉(zhuǎn)化成由0，1組合而成的二進(jìn)制串P={a1,a2,…,an}。ak=0表示屬性qk沒有被選中，ak=1表示屬性qk被選中，其中k∈[1,2,…,n]。

（2）適應(yīng)度函數(shù)

適應(yīng)值函數(shù)是智能優(yōu)化計(jì)算中最核心的部分，可以將一個(gè)粒子的適應(yīng)值對(duì)應(yīng)于該粒子與最優(yōu)目標(biāo)粒子的相關(guān)性。如果適應(yīng)值函數(shù)選取不當(dāng)，無法找到屬性約簡的最優(yōu)解。而目標(biāo)解為保證與最初條件屬性集有同樣依賴度且條件屬性最少的子集。這個(gè)目標(biāo)解包括最小的條件屬性個(gè)數(shù)和最大的依賴度，同時(shí)其還是一個(gè)多目標(biāo)求解問題。因此，需要先將其轉(zhuǎn)換成單目標(biāo)求解問題。

根據(jù)上述分析，建立粒子適應(yīng)值函數(shù)如下：

其中，card(x)表示粒子x中被選中的條件屬性集的個(gè)數(shù)，m表示原始條件屬性集的個(gè)數(shù)，γC′(D)表示當(dāng)前粒子條件屬性子集的依賴度，γC(D)是原始條件屬性全集的依賴性。

為了保證所得結(jié)果是一個(gè)最小屬性約簡，在粒子群進(jìn)化過程中可以動(dòng)態(tài)調(diào)整k1、k2，使搜索路徑朝著最優(yōu)目標(biāo)的方向發(fā)展。建立自適應(yīng)函數(shù)[14]如下：

2.3 屬性約簡算法步驟

根據(jù)上述分析，基于CQPSO算法的粗糙集屬性約簡具體算法流程如下：

步驟1計(jì)算各個(gè)屬性的依賴度，求出條件屬性的核Core(C)；如果 γCore(C)(D)=γC(D)，那么 Core(C)即為最小屬性約簡，輸出結(jié)果結(jié)束；否則轉(zhuǎn)步驟2。

步驟2設(shè)置相關(guān)的參數(shù)，并隨機(jī)初始化粒子種群。

步驟3根據(jù)公式（15）和（16）計(jì)算所有粒子的適應(yīng)值，并初始化Pbest,Gbest。

步驟4根據(jù)云模型，對(duì)粒子進(jìn)行分類，得到相應(yīng)的收縮因子β。

步驟5根據(jù)公式（1）～（6）更新粒子位置，并計(jì)算每個(gè)粒子的適應(yīng)值。

步驟6更新Pbest和Gbest。

步驟7若終止條件滿足，則輸出結(jié)果結(jié)束；否則轉(zhuǎn)步驟4。

算法流程圖如圖5所示。

3 仿真結(jié)果與分析

本文仿真實(shí)驗(yàn)環(huán)境為Matlab R2010a，運(yùn)行環(huán)境基于Windows7操作系統(tǒng)平臺(tái)，內(nèi)存2.00 GB，處理器為Intel?CoreTMi3-2350M CPU@2.30 GHz，并通過對(duì) UCI數(shù)據(jù)庫中的4個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集仿真分析對(duì)比，數(shù)據(jù)集如表2所示。

實(shí)驗(yàn)中分別采用PSO約簡算法、QPSO約簡算法以及提出的云量子粒子群（CQPSO）約簡算法進(jìn)行實(shí)驗(yàn)并分析對(duì)比，并分別取獨(dú)立運(yùn)行10次的平均結(jié)果作為屬性約簡的計(jì)算結(jié)果，如表3所示。

圖5 CQPSO算法實(shí)現(xiàn)流程圖

表2 實(shí)驗(yàn)數(shù)據(jù)集

表3 屬性約簡計(jì)算結(jié)果

由表3可知，對(duì)于4個(gè)實(shí)驗(yàn)數(shù)據(jù)而言，不論從時(shí)間方面還是屬性約簡個(gè)數(shù)，CQPSO算法約簡的結(jié)果更為理想。特別是Sponse數(shù)據(jù)集，約簡個(gè)數(shù)有很大程度的提高；在對(duì)Zoo數(shù)據(jù)集屬性約簡的過程中，時(shí)間有很大縮減。

此外，本文進(jìn)一步比較提出的CQPSO算法、PSO算法及QPSO算法在收斂速度和尋優(yōu)能力方面的差異性，并詳細(xì)描述在進(jìn)化過程中三種算法對(duì)應(yīng)的適應(yīng)值變化。圖6、圖7分別為Sponge和Soybean_large在優(yōu)化進(jìn)程中適應(yīng)值隨迭代次數(shù)變化的曲線。

圖6 Sponge尋優(yōu)迭代曲線

圖7 Soybean_large尋優(yōu)迭代曲線

圖6和圖7的尋優(yōu)曲線圖都表明了迭代次數(shù)與適應(yīng)值兩者之間的關(guān)系：適應(yīng)度越高，最小屬性約簡效果越佳。且與PSO和QPSO約簡算法相比，CQPSO約簡算法具有更好的收斂速度和尋優(yōu)能力。

最后，本文還采用QPSO-SVM[15]進(jìn)行識(shí)別，對(duì)比3種算法屬性約簡后識(shí)別的準(zhǔn)確率，結(jié)果如表4所示。

表4 屬性約簡后識(shí)別準(zhǔn)確率結(jié)果比較 %

表4中，本文提出的算法準(zhǔn)確率相比其他兩種算法較高，尤其是對(duì)數(shù)據(jù)集Vote識(shí)別準(zhǔn)確率高達(dá)95.47%。

4 結(jié)束語

本文針對(duì)屬性約簡中傳統(tǒng)粒子群優(yōu)化算法的收斂速度慢、早熟等問題，提出一種改進(jìn)的云量子粒子群優(yōu)化算法，并應(yīng)用于粗糙集屬性約簡中，得到如下結(jié)論：

通過將云模型與量子粒子群算法結(jié)合，提出云量子粒子群算法（CQPSO），并利用黃金分割理論，劃分粒子種群來確定不同粒子群的搜索方式。在對(duì)經(jīng)典函數(shù)的測(cè)試對(duì)比中，提出的CQPSO收斂速度快，尋優(yōu)精度高，算法性能可靠。

在進(jìn)一步利用CQPSO算法對(duì)UCI數(shù)據(jù)集進(jìn)行屬性約簡過程中，提出的CQPSO算法首先對(duì)核心適應(yīng)值進(jìn)行仿真優(yōu)化，再利用屬性約簡后的結(jié)果進(jìn)行識(shí)別分析。結(jié)果表明，CQPSO算法識(shí)別準(zhǔn)確率高。

：

[1]Jia X，Shang L，Zhou B，et al.Generalized attribute reduct in rough set theory[J].Knowledge-Based Systems，2016，91（1）：204-218.

[2]Song J，Tsang E C C，Chen D，et al.Minimal decision cost reduct in fuzzy decision-theoretic rough set model[J].Knowledge-Based Systems，2017,13（3）：1-9.

[3]Hu Q，Zhang L，Zhou Y，et al.Large-scale multi-modality attribute reduction with multi-kernel fuzzy rough sets[J].IEEE Transactions on Fuzzy Systems，2017.

[4]Dai S P，Liu S J，Zheng S F.A GA-PSO based attribute reduction algorithm for rough set[J].Computer Engineering&Science，2015，37（2）：397-401.

[5]Konar P，Sil J，Chattopadhyay P.Knowledge extraction using data mining for multi-class fault diagnosis of induction motor[J].Neurocomputing，2015，166：14-25.

[6]Inbarani H H，Azar A T，Jothi G.Supervised hybrid feature selection based on PSO and rough sets for medical diagnosis[J].Computer Methods&Programs in Biomedicine，2014，113（1）.

[7]周愷，王艷，紀(jì)志成.混合量子粒子群算法求解模具車間調(diào)度問題[J].系統(tǒng)仿真學(xué)報(bào)，2016，28（6）：1247-1254.

[8]Yao B，Yu B，Hu P，et al.An improved particle swarm optimization forcarton heterogeneousvehicle routing problem with a collection depot[J].Annals of Operations Research，2016，242（2）：1-18.

[9]Sun J，Wu X，Palade V，et al.Convergence analysis and improvements of quantum-behaved particle swarm optimization[J].Information Sciences，2012，193（15）：81-103.

[10]Liu L.Routing of logistics distribution vehicles using cloud adaptive mean particle swarm optimization[J].International Journal of Simulation—Systems，Science&Techno，2016，15（17）.

[11]Berndt D J，Watkins A.Investigating the performance of genetic algorithm-based software test case generation[C]//High Assurance Systems Engineering，2004.

[12]丁進(jìn)良，楊翠娥，陳立鵬，等.基于參考點(diǎn)預(yù)測(cè)的動(dòng)態(tài)多目標(biāo)優(yōu)化算法[J].自動(dòng)化學(xué)報(bào)，2017，43（2）：313-320.

[13]Pawlak Z.Theoretical aspect of reasoning about data[M]//Rough sets：theoretical aspects of reasoning about data.[S.l.]：Kluwer Academic Publishers，1991.

[14]Antón J C á，Nieto P J G，Gonzalo E G，et al.A new predictive model for the state-of-charge of a high-power lithium-ion cell based on a PSO-optimized multivariate adaptive regression spline approach[J].IEEE Transactions on Vehicular Technology，2016，65（6）：4197-4208.

[15]Guo X，Peng C，Zhang S，et al.A novel feature extraction approach using window function capturing and QPSOSVM for enhancing electronic nose performance[J].Sensors，2015，15（7）：15198-15217.