摘 要： 針對遺傳算法局部搜索能力弱和收斂速度慢，在選擇操作之后加上了禁忌搜索算法，并對交叉操作進行改進，最后用禁忌搜索作為變異操作，從而加快算法的收斂速度，并用此改進的遺傳算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值。實驗證明，采用該方法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)權(quán)值，能克服BP神經(jīng)網(wǎng)絡(luò)收斂速度慢、局部極小問題。
關(guān)鍵詞： 入侵檢測；BP神經(jīng)網(wǎng)絡(luò)；遺傳算法；禁忌搜索算法
0 引言
現(xiàn)在已有許多方法運用于入侵檢測系統(tǒng)來確保網(wǎng)絡(luò)的安全性，最常用的是將神經(jīng)網(wǎng)絡(luò)與入侵檢測技術(shù)相結(jié)合[1]。但是神經(jīng)網(wǎng)絡(luò)性能的好壞依賴于初始權(quán)值，如果權(quán)值選擇不合適，就會導(dǎo)致網(wǎng)絡(luò)陷入局部極小、收斂速度慢、振蕩等問題[2]。針對以上不足，運用遺傳算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值[3]，然后應(yīng)用于入侵檢測。遺傳算法具有并行搜索能力，但它局部搜索能力差，會導(dǎo)致早熟發(fā)生[4-6]。
為了解決上述問題，本文將遺傳算法與禁忌搜索算法結(jié)合起來[7]，在選擇操作之后加入了禁忌搜索算法，以便能更好地找出適應(yīng)度函數(shù)值大的個體；同時改進了交叉算子，并用禁忌搜索算法作為遺傳算法的變異算子進行局部搜索，很大程度上保證了種群多樣性，提高了算法的收斂速度。因此，兩種算法結(jié)合起來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值，可以在一定程度上克服BP神經(jīng)網(wǎng)絡(luò)收斂速度慢和容易陷入局部極小的問題。
1 基于改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測原理
1.1 改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法模型
遺傳算法具有并行搜索能力，但是它收斂速度慢并且局部搜索能力弱[8]。禁忌搜索算法具有強大的局部搜索能力，但它對初始解具有較強的依賴性，初始解選取的好壞決定了算法得到最優(yōu)解機會的大小，并且禁忌搜索算法沒有并行搜索能力[9]。本文將兩種算法混合使用，并用來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)權(quán)值，這樣不僅保留了兩種算法的優(yōu)點，而且兩種算法各自的優(yōu)點可以彌補對方的不足，混合算法具有并行搜索能力、爬山能力強的優(yōu)勢，能夠克服遺傳算法爬山能力差、禁忌搜索算法單點出發(fā)的弱點，最終能尋找出更好的解，然后用此最優(yōu)解來初始化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值。將以上思想引入到入侵檢測中，提出了基于改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測模型，如圖1所示。
部分代碼如下：
Input：
is：input sample iw：initial weights
ee：expected error tf：transfer function
tff：training function nn：number of neurons in each layer
Output：
oe：output error eo：expected output
1 Begin
2 Bpnet=createNet（minmax（is），nn，tf，tff
//創(chuàng)建BP神經(jīng)網(wǎng)絡(luò)
3 net=train（Bpnet，is，eo） //訓(xùn)練神經(jīng)網(wǎng)絡(luò)
4 If oe<=ee
5 Then break·
6 Else Popu=init（iw） //初始化種群
7 Cpopu=code（Popu）//編碼
8 For i=0 to 200
//計算適應(yīng)度值
10 Dis=rank（Fit） // 分配適應(yīng)度值
11 Sel=select（Dis）//選擇
12 TabuSear=search（Sel） //禁忌搜索
13 Cro=recombin（Tabusear）//交叉
14 TabuSear=search（Cro） //禁忌搜索
15 Npopu=insert（Cpopu，TabuSear）//更新種群
16 EndFor
1.2 算法的具體實現(xiàn)步驟
基于改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測算法的主要步驟如下，算法流程圖如圖2所示。
?。?）用BP網(wǎng)絡(luò)訓(xùn)練初始權(quán)值和閾值，如果誤差精度滿足要求，則結(jié)束訓(xùn)練；否則將這些權(quán)值和閾值作為初始種群進行下面步驟。
（2）編碼。采用搜索能力強的二進制編碼。
?。?）用適應(yīng)度函數(shù)計算出各個體的適應(yīng)度函數(shù)值。
（4）選擇。采用輪盤賭選擇方法。
（5）用禁忌搜索算法找出適應(yīng)度更高的個體。
（6）用改進的交叉算法進行交叉操作。
?。?）變異。將禁忌搜索算法作為變異算子。
（8）重復(fù)進行步驟（4）~（7），直至達(dá)到最大進化代數(shù)后結(jié)束。
（9）將得到的最優(yōu)解作為權(quán)值再用BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練，若滿足精度要求，則算法結(jié)束；否則繼續(xù)訓(xùn)練，直至達(dá)到精度要求為止。
2 改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法研究
2.1 適應(yīng)度函數(shù)
適應(yīng)度函數(shù)是判斷個體適應(yīng)環(huán)境能力大小的標(biāo)準(zhǔn)，保留適應(yīng)度大的個體，淘汰適應(yīng)度小的個體，一代一代選擇下去，提高了群體的平均適應(yīng)度[10]。本文將BP神經(jīng)網(wǎng)絡(luò)的誤差函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，誤差越小，適應(yīng)度就越大。即適應(yīng)度函數(shù)F=1/E，E為誤差函數(shù)。
2.2 選擇操作
遺傳算法最常用的選擇方法是輪盤賭選擇、隨機抽樣選擇和錦標(biāo)賽選擇法。前兩種方法隨機性太強，有時連適應(yīng)度較高的個體也無法選擇；而錦標(biāo)賽選擇法容易產(chǎn)生超級個體[11]。
文中先用輪盤賭選擇方法選出個體，然后將選出的個體作為禁忌搜索的初始解，運用其強大的局部搜索能力進一步搜索適應(yīng)度大的個體，這樣即使由于選擇方法的隨機性造成適應(yīng)度大的個體被淘汰，也可以用禁忌搜索算法來繼續(xù)搜索出適應(yīng)度大的個體。而且禁忌搜索可以接受劣解，所以也增加了群體的多樣性。
2.3 改進的交叉操作
交叉操作決定著遺傳算法的全局搜索能力，個體之間的隨機交叉會導(dǎo)致高適應(yīng)度個體的優(yōu)秀基因被替代，從而算法的收斂速度下降。并且個體經(jīng)過一代一代的選擇之后，留下的適應(yīng)度高的個體的基因可能具有高的相似度，讓這些個體進行交叉，很難產(chǎn)生新的基因，會有很多無效交叉操作，容易發(fā)生早熟現(xiàn)象，從而導(dǎo)致局部極小[12]。
本文對遺傳算法的交叉算子進行改進，計算個體之間的相似度，根據(jù)相似度進行分類，將相似度大于0.5的個體分在不同類，不同類的個體之間可以進行交叉；相似度小于0.5的個體分在同類中，彼此之間不能進行交叉操作。適應(yīng)度大的個體給予較小的交叉概率，從而能夠保留一部分優(yōu)秀基因；適應(yīng)度小的個體設(shè)置較大的交叉概率，進而可以淘汰掉這一部分個體。首先將個體按照適應(yīng)度大小進行從大到小的排序，復(fù)制1/4適應(yīng)度值高的個體直接進入下一代，這樣有利于優(yōu)秀基因的保留。然后按照適應(yīng)度值大小排序的序列，從適應(yīng)度值高的個體開始與不同類的基因按照交叉概率進行交叉。因為適應(yīng)度值低的個體交叉概率大，所以這樣就把適應(yīng)度值低的個體淘汰掉了，并且適應(yīng)度值高的個體與適應(yīng)度值低的個體交叉之后產(chǎn)生了新的個體，也保證了群體的多樣性，取交叉操作之后的適應(yīng)度值高的個體的3/4，與之前復(fù)制的1/4適應(yīng)度值高的個體組成了一個新的群體。
用字符串編輯距離來衡量兩個字符串的相似度，一個字符串經(jīng)過插入、刪除和替換三種操作可以變換為另一個字符串，最少的操作步數(shù)稱為兩個字符串的編輯距離。
定義1 相似度=1-（編輯距離/字符串最大長度）
例如：有兩個字符串Str1=AABCE，Str2=AADCBA
?。?）Str1=AABCE（將B替換成D）→Str1=AADCE
（2）Str1=AADCE（將E替換成B）→Str1=AADCB
?。?）Str1=AADCB（插入A）→Str1=AADCBA=Str2
總共需要三次變換（將B替換成D，將E替換成B，插入A），所以編輯距離就是3。那么Str1和Str2的相似度=1-3/6=1/2。
2.4 變異操作
變異操作是產(chǎn)生新個體至關(guān)重要的一步，但變異算子只能對基因進行局部突變，變異概率小。本文用禁忌搜索算法作為變異算子，提高了種群多樣性，并且使得遺傳算法同時具有全局搜索能力和局部搜素能力，它能接受劣解，一定程度上能緩解早熟現(xiàn)象的發(fā)生。
3 入侵檢測MATLAB仿真實驗及結(jié)果
試驗數(shù)據(jù)來源于具有權(quán)威性的數(shù)據(jù)挖掘與知識發(fā)現(xiàn)國際會議[13]，并用MATLAB7.0進行仿真驗證其性能。選取神經(jīng)網(wǎng)絡(luò)輸入層節(jié)點數(shù)為10，隱含層節(jié)點為15，輸出層為1；隱含層與輸出層激勵函數(shù)為tansig，訓(xùn)練函數(shù)為traingda，目標(biāo)精度為0.005，最大訓(xùn)練周期為500；遺傳算法初始種群大小為200，最大進化代數(shù)為200，選擇概率為0.8，交叉率為0.8。
將數(shù)據(jù)和設(shè)置好的參數(shù)分別用到單獨的基于BP神經(jīng)網(wǎng)絡(luò)、遺傳算法優(yōu)化的神經(jīng)網(wǎng)絡(luò)和本文將遺傳算法和禁忌搜索算法結(jié)合起來的基于改進的BP神經(jīng)網(wǎng)絡(luò)中，并用MATLAB7.0對三種神經(jīng)網(wǎng)絡(luò)分別進行入侵檢測仿真，結(jié)果如圖3~圖5所示。
從以上三個圖可以看出：基于改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測能取得更好的效果，單獨的基于BP神經(jīng)網(wǎng)絡(luò)的入侵檢測在25 Epochs之前收斂比較快，25 Epochs之后收斂速度有所變慢，并且在500 Epochs時仍未收斂；采用基于遺傳算法的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法在20 Epochs之前收斂速度很快，在20 Epochs~130 Epochs之間收斂速度明顯下降，并且到140 Epochs了才收斂；采用基于改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法一直收斂速度很快，并在70 Epochs時就已經(jīng)完全收斂。
同時，為了進一步說明改進的BP神經(jīng)網(wǎng)絡(luò)的入侵檢測方法的性能，通過對試驗所用數(shù)據(jù)集中最常見的攻擊類型進行測試，并將三種神經(jīng)網(wǎng)絡(luò)用于入侵檢測中的檢測率與誤報率進行對比，結(jié)果如表1所示。其中：
誤報率=被誤報為入侵的正常樣本數(shù)／正常樣本總數(shù)
檢測率=檢測出的入侵樣本數(shù)／入侵樣本總數(shù)
由表1可以看出，對比三種神經(jīng)網(wǎng)絡(luò)，本文的方法不僅收斂速度快，且對各種攻擊的檢測率明顯較高、誤報率較低，所以基于改進的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法的性能得到了明顯的提升。
4 結(jié)論
本文的方法在解決BP神經(jīng)網(wǎng)絡(luò)的局部極小與收斂速度上有明顯優(yōu)勢，充分利用了遺傳算法與禁忌搜索的優(yōu)點，不僅能在全局搜索最優(yōu)解，也可以對局部進行搜索，增強了搜索能力，提高了檢測率，減少了誤報率，進而提升入侵檢測的性能。
參考文獻
[1] 呂杰.改進BP神經(jīng)網(wǎng)絡(luò)在入侵檢測中的研究及應(yīng)用[D].廣州：廣東工業(yè)大學(xué)，2008.
[2] 周政.BP神經(jīng)網(wǎng)絡(luò)的發(fā)展現(xiàn)狀綜述[J].山西電子技術(shù)，2008（2）：90-92.
[3] 李偉超，宋大猛，陳斌.基于遺傳算法的人工神經(jīng)網(wǎng)絡(luò)[J].計算機工程與設(shè)計，2006，27（2）：316-318.
[4] 朱紅萍，鞏青歌，雷戰(zhàn)波.基于遺傳算法的入侵檢測特征選擇[J].計算機應(yīng)用研究，2012，29（4）：1417-1419.
[5] 張鳳斌，楊永田，江子揚.遺傳算法在基于網(wǎng)絡(luò)異常的入侵檢測中的應(yīng)用[J].電子學(xué)報，2004，32（5）：875-877.
[6] 周貴旺，孫敏.改進遺傳算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)入侵檢測研究[J].微型機與應(yīng)用，2010，29（21）：65-68.
[7] 紀(jì)穎，李蘭英，石敏，等.基于遺傳和禁忌搜索B合的軟硬件劃分算法[J].計算機工程與應(yīng)用，2009，45（20）：81-83.
[8] Ge Jike， Qiu Yuhui， Wu Chunming， et al. Summary of genetic algorithms research[J]. Application Research of Computers， 2008，25（10）：2911-2916.
[9] PHAM D T， KARABOGA D. Intelligent optimisation techniques[M]. New York： Springer，2000.
[10] WHITLEY D. A genetic algorithm tutorial[J]. Statistics and Computing， 1994，4（2）：65-85.
[11] HARIK G R， LOBO F G， GOLDBERG D E. The compact genetic algorithm[C]. IEEE Transactions on Evolutionary Computation， 1999，3（4）：287-297.
[12] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2001.
[13] 張新有，曾華燊，賈磊.入侵檢測數(shù)據(jù)集KDD CUP99研究[J].計算機工程與設(shè)計，2010（22）：4809-4812.