改進的飛蛾撲火優化算法在網絡入侵檢測系統中的應用

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

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

0 引言

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

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

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

1 相關算法

1.1 飛蛾撲火優化算法

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

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

火焰的集合為F，其中Fi為第i個火焰，Fij為第i個火焰對應位置：

MFO優化算法是近似于求全局最佳的三元組：

MFO=(I,P,T)

(1)

I是一種產生隨機飛蛾種群和其對應的適應度值的函數，其系統模型如下：

I:φ→{M,OM}

(2)

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

P:M→M

(3)

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

T:M→{true,false}

(4)

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

M=I()

whileT(M) is equal to false

M=P(M);

End

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

Mi=S(Mi,Fj)

(5)

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

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

(6)

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

Di=|Fj-Mi|

(7)

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

1)火焰F是其對應飛蛾M的歷史最優解。

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

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

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

(8)

其中：N為初始火焰數量，T為迭代的總次數，L為當前迭代次數。

MFO算法的流程：

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

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

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

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

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

6)根據M計算出適應度值OM；

7)判斷是否達到結束條件，否則跳轉到第2)步。

1.2 粒子群優化算法

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

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

(9)

xij=xij+vij

(10)

學習因子c1、c2一般位于[0,2]內，rand為位于[0,1]的隨機數，pbest為歷史最優解，gbest為全局最優解。

PSO算法的流程如下：

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

2)評價每個微粒的適應度；

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

4)對所有粒子，將它當前適應度值對比全局最優適應度值，如果較好，將其作為粒子的全局最優適應度值gbest；

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

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

7)未達到結束條件則轉第2)步。

2 融合粒子群的二進制飛蛾撲火優化算法

2.1 提出的融合算法

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

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

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

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

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

(11)

其中：Fij為中每只飛蛾的歷史最優解，F1j為到這一代為止的所有飛蛾的歷史最優解。飛蛾先向Fij和F0j的方向移動，更新公式如下：

Mij=vij+Mij

(12)

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

Di=|Fj-Mi|

(13)

飛蛾M對應火焰的距離螺旋飛行的方式尋找最優解。

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

(14)

2.2 種群初始化

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

(15)

2.3 飛蛾移動改進

如果對PMFO中飛蛾更新的結果直接進行二進制轉換會導致速度影響過大或者距離Di影響過大，從而導致飛蛾更新處于停止狀態，所以PMFO的飛蛾的距離更新公式(15)改成如下:

Di=|Fi-Mi|/numAttribute

(16)

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

2.4 二進制轉化

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

(17)

(18)

其中：Mij為飛蛾更新后的位置，rand是[0,1]內的隨機數。

2.5 適應度函數

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

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

(19)

其中：λ為特征數量,accuracy為正確率，fitness為飛蛾的適應度值。

2.6 二進制算法流程

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

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

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

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

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

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

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

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

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

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

10)判斷是否達到結束條件，否則跳轉到第2)步。

3 仿真實驗

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

3.1 數據初始化

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

(20)

其中：v為當前數值，mA為該列最小值，MA為該列最大值，v′為更新后的數值。

3.2 實驗結果與分析

實驗中各種算法初始種群數量為10，最大迭代次數為50，實驗中參數說明如表1中所示。

表1 各種算法參數設置

表2～4分別記錄著3種分類器6種算法，仿真實驗運行20次的結果。

表2 SVM分類器的實驗結果

圖1為在3種分類器下6種算法對應的適應度曲線。其中最優適應度值、最差適應度值、平均適應度值主要衡量算法的效果，標準差主要衡量算法的穩定性，運行時間主要衡量算法的運行效率，適應度曲線主要衡量算法的收斂性和跳出局部最優的能力。

實驗1用Wake[21]工具箱中的SVM作為分類器，其中向量機種類為分類向量機，核函數類型為高斯函數，核函數中的gamma函數值為1.0，即向量機種類為分類向量機，核函數類型為高斯函數，核函數中的gamma函數值為1.0，其他參數為默認參數。

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

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

實驗2用Wake工具箱中的KNN作為分類器，其中參數K=10，即離待測點最近的10個的點參與投票分類。

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

表3 KNN分類器的實驗結果

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

表4 Naive Bayes分類器的實驗結果

3.3 實驗結論

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

4 結語

本文提出了一種融合粒子群的二進制飛蛾撲火優化算法，通過結合PSO全局搜索能力強、收斂于全局最優解的特性，以彌補 MFO全局搜索能力弱、收斂速度過快的缺陷。實驗結果證明BPMFO算法在時間效率、求解、穩定性和算法的收斂性具有較好效果，因此本文提出的BPMFO算法在網絡入侵檢測方面具有實用價值。