基于改進(jìn)的蜻蜓算法的特征選擇

劉東強(qiáng)， 陳宏偉

(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430068)

近些年來，人們根據(jù)生物種群的各種行為，相繼提出了各種各樣的群體智能優(yōu)化算法，并取得了諸多成果。例如遺傳算法[1]，粒子群優(yōu)化算法[2]，人工蜂群優(yōu)化算法[3]，螢火蟲算法[4]等。這些算法被研究者們很好的運(yùn)用到了社會的各個(gè)領(lǐng)域。蜻蜓算法也是一種新穎的元啟發(fā)式優(yōu)化算法，它模擬蜻蜓的群體行為，是由Seyedali Mirjalili為解決連續(xù)優(yōu)化問題在2015年提出的。蜻蜓算法被許多學(xué)者研究與運(yùn)用，如崔學(xué)婷等人提出了一種混合改進(jìn)蜻蜓算法并將其應(yīng)用于特征選擇[5]；文獻(xiàn)[6]利用二進(jìn)制蜻蜓算法設(shè)計(jì)了一種特征選擇包裝器，提高了特征選擇分類效果；王萬良等人為合理應(yīng)用生產(chǎn)制造中產(chǎn)生的數(shù)據(jù),分析和挖掘出數(shù)據(jù)中的關(guān)鍵特征和潛在信息,以幫助企業(yè)提高效率、降低成本,提出一種改進(jìn)的蜻蜓算法,并將其用于特征選擇[7]。為了提高蜻蜓算法的效率與精度，本文提出了一種改進(jìn)的蜻蜓算法并運(yùn)用于特征選擇。文章在算法的種群初始化過程中引入混沌策略，并將原來的線性權(quán)重做了一個(gè)非線性調(diào)整，最終用具體的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了改進(jìn)后的蜻蜓算法的分類精度更好。

1 蜻蜓算法

蜻蜓算法是一種新的智群優(yōu)化算法，該算法具有很強(qiáng)的分類搜索能力和迭代優(yōu)化能力，已在各個(gè)領(lǐng)域得到了很好的應(yīng)用。蜻蜓算法的主要靈感源于自然界中蜻蜓的群體行為[8]。蜻蜓有兩個(gè)重要的群體行為：狩獵和遷徙。前者稱為靜態(tài)群體，后者稱為動態(tài)群體。在靜態(tài)群中，蜻蜓會成群結(jié)隊(duì)，在一個(gè)小區(qū)域內(nèi)來回飛行，以捕獵其他飛行的獵物，例如蝴蝶和蚊子[9]。在動態(tài)群中，大量的蜻蜓使群在一個(gè)方向上長距離遷移[10]。

基于蜻蜓的群體行為，建立了5個(gè)數(shù)學(xué)模型：

1)分離行為(Si)計(jì)算如下：

其中X是當(dāng)前個(gè)體的位置，Xj表示第j個(gè)相鄰個(gè)體的位置，n是相鄰個(gè)體的數(shù)量。

2)對齊行為(Ai)計(jì)算如下：

其中Vj表示第j個(gè)相鄰個(gè)體的速度，n是相鄰個(gè)體的數(shù)量。

3)聚集行為(Ci)計(jì)算如下：

其中X是當(dāng)前個(gè)體的位置，N是鄰域的數(shù)目，Xj表示第j個(gè)鄰域個(gè)體的位置。

4)覓食行為(Fi)計(jì)算如下：

Fi=X+-X

其中X是當(dāng)前個(gè)體的位置，X+顯示食物來源的位置。

5)避敵行為(Ei)計(jì)算如下：

Ei=X-+X

其中X是當(dāng)前個(gè)人的位置，X-表示敵人的位置。

在進(jìn)行蜻蜓個(gè)體位置更新時(shí)，首先計(jì)算步進(jìn)矢量(ΔX)，步進(jìn)矢量顯示了蜻蜓的運(yùn)動方向，并定義如下：

ΔXt+1=(sSi+aAi+cCi+fFi+eEi)+wΔXt

(1)

其中s、a、c、f和e為各自所對應(yīng)的權(quán)重，Si、Ai和Ci分別表示個(gè)體的分離、對齊和凝聚力，F(xiàn)i表示食物的吸引力，Ei表示敵人的影響力，w為慣性權(quán)重，t為迭代計(jì)數(shù)器。

計(jì)算步進(jìn)矢量后，位置矢量的計(jì)算如下：

Xt+1=Xt+ΔXt+1

2 改進(jìn)的蜻蜓算法

在本文中，提出了一種基于混沌理論的新的蜻蜓優(yōu)化算法。普通的蜻蜓算法和其他許多智能優(yōu)化算法一樣，在迭代的過程中，很容易陷入局部最優(yōu)的陷阱，而真正需要的是全局最優(yōu)值。針對這一缺陷，本文在種群初始化的過程中加入混沌理論，得到覆蓋面更廣的初始種群。為了提高算法的收斂速度，對原蜻蜓算法中的慣性權(quán)重w做了一個(gè)非線性的調(diào)整，大大提高了算法效率與精度。算法的流程圖見圖1。

圖 1 算法流程圖

2.1 基于混沌策略初始化種群

本文中，為了提高初代蜻蜓種群的多樣性，而不影響得到的結(jié)果，并為算法后期的全局搜索與迭代奠定良好的初始種群基礎(chǔ)。本文在種群初始化的過程中，引用Tent混沌序列的逆混沌映射策略，得到一個(gè)品質(zhì)更優(yōu)的初代蜻蜓種群。

在本算法中，每個(gè)蜻蜓個(gè)體的維度為d，在初始化種群的時(shí)候，本文首先生成一個(gè)d維的蜻蜓個(gè)體 (i=1，2,…,n)，然后把生成的個(gè)體通過混沌映射，轉(zhuǎn)化到另外一個(gè)解集中去，進(jìn)而生成一個(gè)新的個(gè)體CXid(i=1，2,…,n)，計(jì)算方法如下：

式中Xid是第i個(gè)蜻蜓個(gè)體的第d維上的值，Xmind和Xmaxd分別是取值的下界和上界，種群CX={CXi,i=1,2,…,n}是通過混沌映射由種群X={Xi,i=1,2,…,n}變化得到。首先把X和CX兩個(gè)種群合并成一個(gè)新的蜻蜓種群，其個(gè)體數(shù)為2n，然后再計(jì)算每個(gè)蜻蜓個(gè)體的適應(yīng)值，并對得到的所有適應(yīng)值進(jìn)行排序，最后取前n個(gè)適應(yīng)值所對應(yīng)的蜻蜓個(gè)體來組成蜻蜓算法的初代種群。

2.2 慣性權(quán)重w的非線性改變

在原蜻蜓算法中，式(1)中的慣性權(quán)重w是一個(gè)線性變化的值，其計(jì)算方法見式(2)。在實(shí)際情況中，隨著算法迭代次數(shù)的增加，算法收斂的速度會慢慢降低，是呈曲線下降的。算法中慣性權(quán)重w收斂的速度和算法整體的收斂速度不一致，這就會降低算法的收斂速度，從而影響算法的整體效率。

w=0.9-t(0.5/tmax)

(2)

式(2)中t為當(dāng)前的迭代次數(shù)，tmax為開始設(shè)置的總迭代次數(shù)。從公式(2)中可以看出，隨著迭代次數(shù)的增加，慣性權(quán)重w會呈直線趨勢變小。在本文中，引用了指數(shù)遞減策略，通過下面公式對慣性權(quán)重進(jìn)行一個(gè)非線性的調(diào)整改變：

式中wmax和wmin分別為公式(2)中慣性權(quán)重w的最大值和最小值：wmax=0.9，wmin=0.4。其中α為調(diào)節(jié)系數(shù)，本文中取α=4，t和T分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。改進(jìn)后的慣性權(quán)重w和原慣性權(quán)重w的對比圖如圖2所示，從圖中可以看出改進(jìn)后的w是呈曲線下降的，相對于原慣性權(quán)重w，其開始的變化速度很快，隨著迭代次數(shù)的增加，變化的速度逐漸變慢，這能更好地適應(yīng)算法的整體收斂速度。

圖 2 權(quán)重對比圖

2.3 特征選擇

特征選擇是一種二進(jìn)制優(yōu)化問題，個(gè)體的位置都是由0或者1來表示。蜻蜓算法能夠很好的解決連續(xù)優(yōu)化問題，它通過將步長向量增加到位置向量的方法來改變個(gè)體的位置，但在二進(jìn)制搜索空間中，種群個(gè)體的位置由0和1表示，此方法就不適用了。根據(jù)先前Mirjalili和Lewis的研究[11]?？梢酝ㄟ^傳遞函數(shù)將連續(xù)優(yōu)化算法轉(zhuǎn)換成二進(jìn)制算法，傳遞函數(shù)一般分為兩種：S型和V型。本文采用V型傳遞函數(shù)，將原連續(xù)優(yōu)化算法轉(zhuǎn)換成了用于特征選擇的二進(jìn)制優(yōu)化算法。

3 實(shí)驗(yàn)結(jié)果與分析

在實(shí)驗(yàn)中，本文先將改進(jìn)后的二進(jìn)制蜻蜓算法(CBDA)與原始的二進(jìn)制蜻蜓算法(BDA)進(jìn)行了比較，使用的數(shù)據(jù)集是兩個(gè)UCI數(shù)據(jù)集：Wine和Sonar。本實(shí)驗(yàn)在Windows10操作系統(tǒng)下進(jìn)行，電腦的相關(guān)配置：操作系統(tǒng)Windows 10, 64 bit，處理器Intel(R) Core(TM) i5-7200U，內(nèi)存16 G，編程語言Python3.5.2。種群的規(guī)模都設(shè)置為30，迭代次數(shù)都設(shè)置為50。通過比較四種算法得到的最優(yōu)個(gè)體的適應(yīng)值來判斷算法對于文本分類中特征選擇的效果。

實(shí)驗(yàn)結(jié)果見圖3、圖4，從圖中可以看出：改進(jìn)后的二進(jìn)制蜻蜓算法的收斂速度明顯要好于原算法。

圖 3 在Wine中函數(shù)適應(yīng)度值

圖 4 在Sonar中函數(shù)適應(yīng)度值

為驗(yàn)證改進(jìn)的蜻蜓算法性能，本文還將改進(jìn)的二進(jìn)制蜻蜓算法(CBDA)和傳統(tǒng)的二進(jìn)制遺傳算法(BGA)、二進(jìn)制粒子群算法(BPSO)進(jìn)行比較。從30次運(yùn)行結(jié)果中獲取每種算法的平均分類精度，然后相互之間進(jìn)行比較，得到表1的結(jié)果，從中可知改進(jìn)后的蜻蜓算法的分類精度要好于其他算法。

表1 平均分類精度

4 結(jié)論

在本文中，將混沌映射和慣性權(quán)重的非線性改變運(yùn)用到蜻蜓算法中，并將改進(jìn)后的蜻蜓算法運(yùn)用于特征選擇來檢驗(yàn)其效果。通過實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)后的蜻蜓算法的收斂速度相對于原算法得到了提高，而且相對于傳統(tǒng)的優(yōu)化算法，其分類精度也更高。