改進(jìn)的飛蛾撲火優(yōu)化算法在網(wǎng)絡(luò)入侵檢測系統(tǒng)中的應(yīng)用

徐 慧，方 策，劉 翔，葉志偉

(湖北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，武漢430068)(*通信作者電子郵箱xuhui@mail.hbut.edu.cn)

0 引言

網(wǎng)絡(luò)入侵檢測系統(tǒng)(Network Intrusion Detection System, NIDS)[1]能及時檢測網(wǎng)絡(luò)入侵事件，減小網(wǎng)絡(luò)入侵的破壞。NIDS主要以系統(tǒng)日志的方式作為數(shù)據(jù)源，判斷待檢測數(shù)據(jù)是否屬于正常數(shù)據(jù)，但是并不是每一項(xiàng)數(shù)據(jù)都可以幫助我們篩選攻擊數(shù)據(jù)，所以對數(shù)據(jù)進(jìn)行特征選擇[2]是提升NIDS的可靠性和時效性的有效方法之一。對數(shù)據(jù)特征選擇就是保留數(shù)據(jù)中貢獻(xiàn)度較大特征，去掉一些冗余特征甚至噪聲特征，目前特征選擇的主要算法有二進(jìn)制粒子群優(yōu)化(Binary Particle Swarm Optimization, BPSO)算法[3]、遺傳算法[4]、二進(jìn)制灰狼優(yōu)化(Binary Grey Wolf Optimization, BGWO)算法[5]、二進(jìn)制布谷鳥搜索(Binary Cuckoo Search, BCS)算法[6]等; 但它們或多或少都存在一些問題，例如遺傳算法隨機(jī)性比較大，BGWO算法易陷入局部最優(yōu)等。

飛蛾撲火優(yōu)化(Moth-Flame Optimization, MFO)算法[7-8]是2015年由Mirjalili等提出的一種智能優(yōu)化算法，它源于飛蛾圍繞火焰飛行的行為模擬, MFO已被證明在電力[9]、工程[10]、網(wǎng)絡(luò)[11]和加工制造[12]等方面具有很好的效果。MFO算法中飛蛾只根據(jù)自己的火焰更新位置，所以局部搜索能力很強(qiáng)，但全局收斂性較差，而且易陷入局部最優(yōu)。為此，文獻(xiàn)[13]中結(jié)合了Lévy飛行搜索策略提出了一種LMFO(Moth-Flame Optimization algorithm based on Lévy flights)算法，Lévy飛行搜索策略具有小步移動多、偶爾大步移動的特點(diǎn)，擴(kuò)大了MFO的搜索范圍; 文獻(xiàn)[14]中提出一種縱橫交叉混沌捕焰優(yōu)化算法，采用縱橫交叉機(jī)制，將火焰之間和火焰的不同維度之間相互結(jié)合，并引入混沌算子，提高了算法精確度和跳出局部最優(yōu)能力。

盡管MFO算法應(yīng)用和改進(jìn)比較廣泛，但還沒有應(yīng)用于網(wǎng)絡(luò)入侵檢測中, 因此，本文嘗試將MFO結(jié)合粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法以提升MFO的全局搜索能力和收斂速度。

1 相關(guān)算法

1.1 飛蛾撲火優(yōu)化算法

對MFO中M表示飛蛾的集合，OM表示飛蛾M所對應(yīng)的自適度的值,F為火焰的集合，OF表示火焰F對應(yīng)的自適度的值。飛蛾F和火焰M都是函數(shù)的解，飛蛾和火焰的不同之處在于它們的更新方式不同，火焰是飛蛾目前為止的歷史最優(yōu)解。飛蛾撲火算法的近似優(yōu)化如下：

飛蛾的集合為M，其中Mi為第i個飛蛾，Mij為第i個飛蛾對應(yīng)位置：

火焰的集合為F，其中Fi為第i個火焰，F(xiàn)ij為第i個火焰對應(yīng)位置：

MFO優(yōu)化算法是近似于求全局最佳的三元組：

MFO=(I,P,T)

(1)

I是一種產(chǎn)生隨機(jī)飛蛾種群和其對應(yīng)的適應(yīng)度值的函數(shù)，其系統(tǒng)模型如下：

I:φ→{M,OM}

(2)

P是搜索飛蛾周圍空間的主函數(shù)，P函數(shù)接受矩陣M并返回其更新的最終值：

P:M→M

(3)

T是飛蛾更新的截至條件，若T不滿足，則程序會一直運(yùn)行

T:M→{true,false}

(4)

使用I、P和T描述MFO算法的框架一般定義如下：

M=I()

whileT(M) is equal to false

M=P(M);

End

I()函數(shù)初始化飛蛾種群M，用P函數(shù)移動搜索飛蛾M周圍空間，迭代更新飛蛾M直至迭代停止條件T(M)滿足。該算法的啟發(fā)是飛蛾的橫向飛行，為了建立這種數(shù)學(xué)模型，飛蛾借助火焰的更新的函數(shù)如下：

Mi=S(Mi,Fj)

(5)

每個飛蛾相對于火焰的位置的更新函數(shù)如下：

S(Mi,Fj)=Diebt·cos(2πt)+Fj

(6)

其中:Di表示飛蛾到火焰的距離，b是一個常量定義螺旋線的形狀，t是一個屬于[-1,1]內(nèi)的隨機(jī)數(shù)，Di的計(jì)算公式如下：

Di=|Fj-Mi|

(7)

由于飛蛾的更新公式為式(6)，已知函數(shù)為y=et·cos(2πt)時，當(dāng)t屬于[-1,1]內(nèi)的隨機(jī)數(shù)時，離飛蛾位置越近的點(diǎn)更新到的可能性越大，這樣容易使得飛蛾易陷入局部最優(yōu)。為了使飛蛾盡量避免局部最優(yōu)，又可以根據(jù)最優(yōu)值移動自身，又能節(jié)省時間，所以火焰更新的模型如下：

1)火焰F是其對應(yīng)飛蛾M的歷史最優(yōu)解。

2)每一代火焰更新后，會根據(jù)其適應(yīng)度值，按照從大到小的順序排列，所以第一只飛蛾總是會根據(jù)適應(yīng)度最好的值更新。

3)為了節(jié)省開銷，飛蛾和火焰的數(shù)量會根據(jù)運(yùn)行的代數(shù)不同，不斷減少，但飛蛾和火焰的數(shù)量始終相同，該函數(shù)公式為：

flame_no=round(N-L(N-1)/T)

(8)

其中：N為初始火焰數(shù)量，T為迭代的總次數(shù)，L為當(dāng)前迭代次數(shù)。

MFO算法的流程：

1)用式(2)初始化飛蛾種群M,根據(jù)M計(jì)算出適應(yīng)度值OM；

2)M、OM的位置不變，對M、OM排序得到火焰F和其適應(yīng)度值OF；

3)根據(jù)式(8)求出飛蛾的數(shù)量，去掉末尾的飛蛾和火焰；

4)用式(7)求出飛蛾與其對應(yīng)火焰的距離Di；

5)將Di代入到式(6)中，計(jì)算出每只飛蛾更新之后的值；

6)根據(jù)M計(jì)算出適應(yīng)度值OM；

7)判斷是否達(dá)到結(jié)束條件，否則跳轉(zhuǎn)到第2)步。

1.2 粒子群優(yōu)化算法

PSO算法是在由Reynolds等通過鳥類集體飛行捕食得到的啟發(fā)，整個鳥群好像在一個中心的控制下移動，假設(shè)整個區(qū)域中只有一個地方有食物，那么找到事物最簡單的辦法就是向著離事物最近的鳥移動。現(xiàn)將空間中的鳥假設(shè)成一個粒子，每個粒子既有社會認(rèn)知能力也有自我認(rèn)知能力，社會認(rèn)知能力及整個種群中最優(yōu)解，自我認(rèn)知能力及個體到目前位置的最優(yōu)解，每個粒子都會隨機(jī)地向著種群中的最優(yōu)解和該個體的歷史最優(yōu)解移動，每只飛蛾的每個維度都有自己的速度Vi=(vi1,vi2,…,vij)T和移動距離Xi=(xi1,xi2,…,xij)T,移動速度和移動距離的更新公式如下所示：

vij=vij+c1rand(pbestij-xij)+c2rand(gbestj-xij)

(9)

xij=xij+vij

(10)

學(xué)習(xí)因子c1、c2一般位于[0,2]內(nèi)，rand為位于[0,1]的隨機(jī)數(shù)，pbest為歷史最優(yōu)解，gbest為全局最優(yōu)解。

PSO算法的流程如下：

1)初始化種群隨機(jī)位置，種群N和其速度V；

2)評價每個微粒的適應(yīng)度；

3)對所有微粒，將它當(dāng)前適應(yīng)度值對比其歷史最優(yōu)適應(yīng)度值，如果較好，將其作為粒子的歷史最優(yōu)適應(yīng)度值pbest；

4)對所有粒子，將它當(dāng)前適應(yīng)度值對比全局最優(yōu)適應(yīng)度值，如果較好，將其作為粒子的全局最優(yōu)適應(yīng)度值gbest；

5)將得到的pbest和gbest代入式(9)中得到速度V；

6)將速度V代入到式(10)中得到新的位置；

7)未達(dá)到結(jié)束條件則轉(zhuǎn)第2)步。

2 融合粒子群的二進(jìn)制飛蛾撲火優(yōu)化算法

2.1 提出的融合算法

在二進(jìn)值群體優(yōu)化算法中要考慮到平衡算法的局部搜索能力和算法的全局搜索能力。飛蛾撲火優(yōu)化算法的原理是利用每只飛蛾只圍繞著自己所對應(yīng)的火焰做螺旋飛行運(yùn)動以尋找最優(yōu)解，有較強(qiáng)的局部搜索能力，但是全局搜索能力較弱。

考慮到應(yīng)用于網(wǎng)絡(luò)入侵檢測的特征優(yōu)化時，MFO算法全局搜索能力差、易陷入局部最優(yōu)，通過融合PSO算法，以獲取更好的全局搜索能力。在此基礎(chǔ)上，本文提出融合粒子群的飛蛾撲火優(yōu)化(Moth-Flame Optimization integrated with Particle swarm optimization, PMFO)算法。

MFO中飛蛾的更新方式是以每只飛蛾圍繞火焰螺旋飛行的方式找最優(yōu)解MFO中每只飛蛾只收斂于自己所對應(yīng)的火焰一點(diǎn)，這樣不僅局部搜索能力差，而且易陷入局部最優(yōu), 所以讓飛蛾先向全局最優(yōu)解F1(由于每次迭代火焰F都會按照適應(yīng)度值從大到小排序，所以F1為全局最優(yōu)解)和每個粒子所對應(yīng)的火焰Fi(火焰Fi為第i個飛蛾的歷史最優(yōu)解)的方向移動，再用式(6)作局部搜索，使飛蛾的搜索范圍加大，效果更好。PSO改進(jìn)MFO算法改進(jìn)公式如下：

PMFO與MFO相比飛蛾的位置更新方式不同，每只飛蛾都對應(yīng)著自己的速度Vi=(vi1,vi2,…,vij)T，速度更新公式如下：

vij=vij+c1rand(Fij-xij)+c2rand(F1j-xij)

(11)

其中：Fij為中每只飛蛾的歷史最優(yōu)解，F(xiàn)1j為到這一代為止的所有飛蛾的歷史最優(yōu)解。飛蛾先向Fij和F0j的方向移動，更新公式如下：

Mij=vij+Mij

(12)

這時飛蛾已經(jīng)向前飛行了一段距離，之后再用飛蛾更新后的位置求與火焰之間的距離Di，公式如下：

Di=|Fj-Mi|

(13)

飛蛾M對應(yīng)火焰的距離螺旋飛行的方式尋找最優(yōu)解。

Mij=Di·ebtcos(2πt)+Fij

(14)

2.2 種群初始化

在二進(jìn)制算法中，粒子特征的值只能為0或1，1代表這項(xiàng)特征被選中，0則代表未選中。一般情況，特征有50%的幾率被選中是種群初始化的常用方法，被選中粒子的初始化函數(shù)如下：

(15)

2.3 飛蛾移動改進(jìn)

如果對PMFO中飛蛾更新的結(jié)果直接進(jìn)行二進(jìn)制轉(zhuǎn)換會導(dǎo)致速度影響過大或者距離Di影響過大，從而導(dǎo)致飛蛾更新處于停止?fàn)顟B(tài)，所以PMFO的飛蛾的距離更新公式(15)改成如下:

Di=|Fi-Mi|/numAttribute

(16)

其中numAttribute為特征的數(shù)量。為了緩解PMFO中速度過大的影響，對速度V設(shè)置上限和下限Vmax和Vmin。

2.4 二進(jìn)制轉(zhuǎn)化

為了解決上述算法在二進(jìn)制空間中的位置更新問題，本文使用sigmoid函數(shù)將飛蛾更新后的實(shí)數(shù)值映射到[0,1]內(nèi)，來實(shí)現(xiàn)飛蛾位置的“0”和“1”轉(zhuǎn)換。二進(jìn)制轉(zhuǎn)換公式如下：

(17)

(18)

其中：Mij為飛蛾更新后的位置，rand是[0,1]內(nèi)的隨機(jī)數(shù)。

2.5 適應(yīng)度函數(shù)

特征優(yōu)化的目的是去掉以一些對結(jié)果影響不大或者是對結(jié)果判斷有負(fù)面影響的特征，以達(dá)到提高速度和正確率的目的，所以粒子適值求解步驟如下：

先找到個體特征中為0的值，在數(shù)據(jù)集中將這些屬性都去掉，再將數(shù)據(jù)放到分類器中求出正確率accuracy。傳統(tǒng)方法直接將accuracy作為適應(yīng)度值，本文使用文獻(xiàn)[15]提出的一種適應(yīng)值求解方法，適應(yīng)度函數(shù)如下：

(19)

其中：λ為特征數(shù)量,accuracy為正確率，fitness為飛蛾的適應(yīng)度值。

2.6 二進(jìn)制算法流程

融合粒子群的二進(jìn)制飛蛾撲火優(yōu)化(Binary Moth-Flame Optimization integrated with Particle swarm optimization，BPMFO)算法的流程描述如下。

1)用式(15)初始化飛蛾種群M,根據(jù)M計(jì)算出適應(yīng)度值OM；

2)M、OM的位置不變，對M、OM排序得到火焰F和其適應(yīng)度值OM；

3)根據(jù)式(8)求出飛蛾的數(shù)量，去掉末尾的飛蛾和火焰；

4)用式(11)更新飛蛾速度V，如果速度越界，則速度為Vmax或Vmin；

5)已知速度V，用式(12)更新飛蛾F位置；

6)將更新后的飛蛾位置代入式(16)中，求出飛蛾與其對應(yīng)火焰的距離Di；

7)用式(14)計(jì)算出每只飛蛾更新之后的值；

8)用式(17) 、(18)將飛蛾更新后的值轉(zhuǎn)化為二進(jìn)制；

9)根據(jù)M代入到分類器中得到正確率accuracy,將得到的accuracy代入到式(19)中，計(jì)算出適應(yīng)度值OM；

10)判斷是否達(dá)到結(jié)束條件，否則跳轉(zhuǎn)到第2)步。

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)考慮將提出的二進(jìn)制粒子群改進(jìn)飛蛾撲火優(yōu)化BPMFO算法與二進(jìn)制飛蛾撲火優(yōu)化(Binary Moth-Flame Optimization, BMFO)算法、二進(jìn)制粒子群優(yōu)化(BPSO)算法、二進(jìn)制遺傳算法(Binary Genetic Algorithm, BGA)、二進(jìn)制布谷鳥搜索(BCS)算法，二進(jìn)制灰狼優(yōu)化(BGWO)算法進(jìn)行對比實(shí)驗(yàn)，分別使用支持向量機(jī)(Support Vector Machine, SVM)[17]、K最近鄰(K-Nearest Neighbors,KNN)算法[18]和樸素貝葉斯分類器(Naive Bayes Classifier, NBC)[19]分類，得到最后的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)環(huán)境為Window7 操作系統(tǒng)，處理器為 Intel Core i7-3630QM CPU 2.40 GHz，內(nèi)存為4.00 GB，程序用Java編寫。

3.1 數(shù)據(jù)初始化

實(shí)驗(yàn)數(shù)據(jù)采用網(wǎng)絡(luò)入侵中常用數(shù)據(jù)集KDD CUP 99 數(shù)據(jù)集，KDD CUP 99 分為測試集和訓(xùn)練集，一共大約有500萬條數(shù)據(jù)，本文使用其中測試集大約10%數(shù)據(jù)，在50萬條數(shù)據(jù)集中抽取5 000條數(shù)據(jù)，其中一半歸為訓(xùn)練集一半歸為測試集，將數(shù)據(jù)集中的攻擊類型都?xì)w為abnormal類，其他數(shù)據(jù)類型歸為normal類。數(shù)據(jù)一共包含有41維特征，其中3個字符串特征，38個數(shù)值型特征[20]。實(shí)驗(yàn)中，先對數(shù)據(jù)進(jìn)行預(yù)處理，將字符串特征對應(yīng)成數(shù)值特征，再對數(shù)據(jù)集進(jìn)行0-1標(biāo)準(zhǔn)化處理，處理公式如下：

(20)

其中：v為當(dāng)前數(shù)值，mA為該列最小值，MA為該列最大值，v′為更新后的數(shù)值。

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

實(shí)驗(yàn)中各種算法初始種群數(shù)量為10，最大迭代次數(shù)為50，實(shí)驗(yàn)中參數(shù)說明如表1中所示。

表1 各種算法參數(shù)設(shè)置

表2～4分別記錄著3種分類器6種算法，仿真實(shí)驗(yàn)運(yùn)行20次的結(jié)果。

表2 SVM分類器的實(shí)驗(yàn)結(jié)果

圖1為在3種分類器下6種算法對應(yīng)的適應(yīng)度曲線。其中最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值主要衡量算法的效果，標(biāo)準(zhǔn)差主要衡量算法的穩(wěn)定性，運(yùn)行時間主要衡量算法的運(yùn)行效率，適應(yīng)度曲線主要衡量算法的收斂性和跳出局部最優(yōu)的能力。

實(shí)驗(yàn)1用Wake[21]工具箱中的SVM作為分類器，其中向量機(jī)種類為分類向量機(jī)，核函數(shù)類型為高斯函數(shù)，核函數(shù)中的gamma函數(shù)值為1.0，即向量機(jī)種類為分類向量機(jī)，核函數(shù)類型為高斯函數(shù)，核函數(shù)中的gamma函數(shù)值為1.0，其他參數(shù)為默認(rèn)參數(shù)。

圖1 6種算法通過SVM、KNN和NBC三種分類器的適應(yīng)度值比較

在實(shí)驗(yàn)1中，BPMFO在最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值和標(biāo)準(zhǔn)差優(yōu)于其他二進(jìn)制優(yōu)化算法，也更加穩(wěn)定。雖然運(yùn)行時間比BCS算法長38 s，但是最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值比BCS多約0.062、0.078和0.088。BPMFO相對于原MFO算法更易跳出局部最優(yōu)，實(shí)驗(yàn)中的求解效果也優(yōu)于其他算法(如表2和圖1(a)所示)。

實(shí)驗(yàn)2用Wake工具箱中的KNN作為分類器，其中參數(shù)K=10，即離待測點(diǎn)最近的10個的點(diǎn)參與投票分類。

在實(shí)驗(yàn)2中，BPMFO的最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值略低于BGWO，但時間上縮短了約230 s。在算法穩(wěn)定性方面略低于BMFO和BPSO，但在算法效果和運(yùn)行效率方面優(yōu)于這兩種算法。BPMFO運(yùn)行時間比BCS多約30 s，但在最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值比BCS高約0.010、0.042、0.025，方差也只有BCS的一半。BPMFO相對于其他算法收斂性適中，且具有一定跳出局部最優(yōu)的能力(如表3和圖1(b)所示)。

表3 KNN分類器的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)3用Wake工具箱中的樸素貝葉斯作為分類器。實(shí)驗(yàn)3中，BPMFO的最優(yōu)適應(yīng)度值高于BGWO，但最差適應(yīng)度值、平均適應(yīng)度值略低于BGWO，但運(yùn)行時間比BGWO短約12.4 s。在算法穩(wěn)定性方面略低于BMFO和BPSO，但在最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值和運(yùn)行效率方面比BMFO和BPSO高。雖然在時間上比BCS低0.7 s，但是最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值比BCS高約0.023、0.032、0.027，并且在算法穩(wěn)定性上優(yōu)于BCS算法。BPMFO相對于其他算法收斂性適中，具有一定跳出局部最優(yōu)的能力、且實(shí)驗(yàn)的求解效果略低于BGWO，但優(yōu)于其他算法(如表4和圖1(c)所示)。

表4 Naive Bayes分類器的實(shí)驗(yàn)結(jié)果

3.3 實(shí)驗(yàn)結(jié)論

本節(jié)使用了BPMFO、BMFO、BPSO、BGA、BCS、BGWO共6種優(yōu)化算法，分別采用SVM、KNN、NBC三種分類器進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)證明了提出的BPMFO算法具有較好的求解能力，相對于傳統(tǒng)PSO、遺傳算法(Genetic Algorithm, GA)來說運(yùn)行時間大幅度縮減，雖然在實(shí)驗(yàn)2和實(shí)驗(yàn)3中，求解效果低于BGWO，但是運(yùn)行時間只有BGWO的1/3，相對于原MFO算法，改進(jìn)原算法易陷入局部最優(yōu)并且收斂過快的缺陷，在算法求解能力上也有所提升，同時BPMFO也具有相當(dāng)不錯穩(wěn)定性，應(yīng)用于網(wǎng)絡(luò)入侵檢測中有很好的效果。

4 結(jié)語

本文提出了一種融合粒子群的二進(jìn)制飛蛾撲火優(yōu)化算法，通過結(jié)合PSO全局搜索能力強(qiáng)、收斂于全局最優(yōu)解的特性，以彌補(bǔ) MFO全局搜索能力弱、收斂速度過快的缺陷。實(shí)驗(yàn)結(jié)果證明BPMFO算法在時間效率、求解、穩(wěn)定性和算法的收斂性具有較好效果，因此本文提出的BPMFO算法在網(wǎng)絡(luò)入侵檢測方面具有實(shí)用價值。