摘  要： 針對遺傳算法局部搜索能力弱和收斂速度慢，在選擇操作之后加上了禁忌搜索算法，并對交叉操作進行改進，最后用禁忌搜索作為變異操作，從而加快算法的收斂速度，并用此改進的遺傳算法來優化BP神經網絡的權值。實驗證明，采用該方法優化BP神經網絡權值，能克服BP神經網絡收斂速度慢、局部極小問題。

　　關鍵詞： 入侵檢測；BP神經網絡；遺傳算法；禁忌搜索算法

0 引言

　　現在已有許多方法運用于入侵檢測系統來確保網絡的安全性，最常用的是將神經網絡與入侵檢測技術相結合[1]。但是神經網絡性能的好壞依賴于初始權值，如果權值選擇不合適，就會導致網絡陷入局部極小、收斂速度慢、振蕩等問題[2]。針對以上不足，運用遺傳算法來優化BP神經網絡的權值[3]，然后應用于入侵檢測。遺傳算法具有并行搜索能力，但它局部搜索能力差，會導致早熟發生[4-6]。

　　為了解決上述問題，本文將遺傳算法與禁忌搜索算法結合起來[7]，在選擇操作之后加入了禁忌搜索算法，以便能更好地找出適應度函數值大的個體；同時改進了交叉算子，并用禁忌搜索算法作為遺傳算法的變異算子進行局部搜索，很大程度上保證了種群多樣性，提高了算法的收斂速度。因此，兩種算法結合起來優化BP神經網絡的權值，可以在一定程度上克服BP神經網絡收斂速度慢和容易陷入局部極小的問題。

1 基于改進的BP神經網絡入侵檢測原理

　　1.1 改進的BP神經網絡入侵檢測方法模型

　　遺傳算法具有并行搜索能力，但是它收斂速度慢并且局部搜索能力弱[8]。禁忌搜索算法具有強大的局部搜索能力，但它對初始解具有較強的依賴性，初始解選取的好壞決定了算法得到最優解機會的大小，并且禁忌搜索算法沒有并行搜索能力[9]。本文將兩種算法混合使用，并用來優化BP神經網絡權值，這樣不僅保留了兩種算法的優點，而且兩種算法各自的優點可以彌補對方的不足，混合算法具有并行搜索能力、爬山能力強的優勢，能夠克服遺傳算法爬山能力差、禁忌搜索算法單點出發的弱點，最終能尋找出更好的解，然后用此最優解來初始化BP神經網絡的權值。將以上思想引入到入侵檢測中，提出了基于改進的BP神經網絡入侵檢測模型，如圖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

　　//創建BP神經網絡

　　3 net=train（Bpnet，is，eo）         //訓練神經網絡

　　4 If oe<=ee

　　5 Then break·

　　6 Else Popu=init（iw）          //初始化種群

　　7 Cpopu=code（Popu）//編碼

　　8 For i=0 to 200

　　 //計算適應度值

　　10 Dis=rank（Fit）     // 分配適應度值

　　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 算法的具體實現步驟

　　基于改進的BP神經網絡入侵檢測算法的主要步驟如下，算法流程圖如圖2所示。

　?。?）用BP網絡訓練初始權值和閾值，如果誤差精度滿足要求，則結束訓練；否則將這些權值和閾值作為初始種群進行下面步驟。

　　（2）編碼。采用搜索能力強的二進制編碼。

　?。?）用適應度函數計算出各個體的適應度函數值。

　?。?）選擇。采用輪盤賭選擇方法。

　?。?）用禁忌搜索算法找出適應度更高的個體。

　?。?）用改進的交叉算法進行交叉操作。

　?。?）變異。將禁忌搜索算法作為變異算子。

　?。?）重復進行步驟（4）~（7），直至達到最大進化代數后結束。

　?。?）將得到的最優解作為權值再用BP神經網絡訓練，若滿足精度要求，則算法結束；否則繼續訓練，直至達到精度要求為止。

2 改進的BP神經網絡入侵檢測方法研究

　　2.1 適應度函數

　　適應度函數是判斷個體適應環境能力大小的標準，保留適應度大的個體，淘汰適應度小的個體，一代一代選擇下去，提高了群體的平均適應度[10]。本文將BP神經網絡的誤差函數的倒數作為適應度函數，誤差越小，適應度就越大。即適應度函數F=1/E，E為誤差函數。

　　2.2 選擇操作

　　遺傳算法最常用的選擇方法是輪盤賭選擇、隨機抽樣選擇和錦標賽選擇法。前兩種方法隨機性太強，有時連適應度較高的個體也無法選擇；而錦標賽選擇法容易產生超級個體[11]。

　　文中先用輪盤賭選擇方法選出個體，然后將選出的個體作為禁忌搜索的初始解，運用其強大的局部搜索能力進一步搜索適應度大的個體，這樣即使由于選擇方法的隨機性造成適應度大的個體被淘汰，也可以用禁忌搜索算法來繼續搜索出適應度大的個體。而且禁忌搜索可以接受劣解，所以也增加了群體的多樣性。

　　2.3 改進的交叉操作

　　交叉操作決定著遺傳算法的全局搜索能力，個體之間的隨機交叉會導致高適應度個體的優秀基因被替代，從而算法的收斂速度下降。并且個體經過一代一代的選擇之后，留下的適應度高的個體的基因可能具有高的相似度，讓這些個體進行交叉，很難產生新的基因，會有很多無效交叉操作，容易發生早熟現象，從而導致局部極小[12]。

　　本文對遺傳算法的交叉算子進行改進，計算個體之間的相似度，根據相似度進行分類，將相似度大于0.5的個體分在不同類，不同類的個體之間可以進行交叉；相似度小于0.5的個體分在同類中，彼此之間不能進行交叉操作。適應度大的個體給予較小的交叉概率，從而能夠保留一部分優秀基因；適應度小的個體設置較大的交叉概率，進而可以淘汰掉這一部分個體。首先將個體按照適應度大小進行從大到小的排序，復制1/4適應度值高的個體直接進入下一代，這樣有利于優秀基因的保留。然后按照適應度值大小排序的序列，從適應度值高的個體開始與不同類的基因按照交叉概率進行交叉。因為適應度值低的個體交叉概率大，所以這樣就把適應度值低的個體淘汰掉了，并且適應度值高的個體與適應度值低的個體交叉之后產生了新的個體，也保證了群體的多樣性，取交叉操作之后的適應度值高的個體的3/4，與之前復制的1/4適應度值高的個體組成了一個新的群體。

　　用字符串編輯距離來衡量兩個字符串的相似度，一個字符串經過插入、刪除和替換三種操作可以變換為另一個字符串，最少的操作步數稱為兩個字符串的編輯距離。

　　定義1 相似度=1-（編輯距離/字符串最大長度）

　　例如：有兩個字符串Str1=AABCE，Str2=AADCBA

　　（1）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 變異操作

　　變異操作是產生新個體至關重要的一步，但變異算子只能對基因進行局部突變，變異概率小。本文用禁忌搜索算法作為變異算子，提高了種群多樣性，并且使得遺傳算法同時具有全局搜索能力和局部搜素能力，它能接受劣解，一定程度上能緩解早熟現象的發生。

3 入侵檢測MATLAB仿真實驗及結果

　　試驗數據來源于具有權威性的數據挖掘與知識發現國際會議[13]，并用MATLAB7.0進行仿真驗證其性能。選取神經網絡輸入層節點數為10，隱含層節點為15，輸出層為1；隱含層與輸出層激勵函數為tansig，訓練函數為traingda，目標精度為0.005，最大訓練周期為500；遺傳算法初始種群大小為200，最大進化代數為200，選擇概率為0.8，交叉率為0.8。

　　將數據和設置好的參數分別用到單獨的基于BP神經網絡、遺傳算法優化的神經網絡和本文將遺傳算法和禁忌搜索算法結合起來的基于改進的BP神經網絡中，并用MATLAB7.0對三種神經網絡分別進行入侵檢測仿真，結果如圖3~圖5所示。

　　從以上三個圖可以看出：基于改進的BP神經網絡入侵檢測能取得更好的效果，單獨的基于BP神經網絡的入侵檢測在25 Epochs之前收斂比較快，25 Epochs之后收斂速度有所變慢，并且在500 Epochs時仍未收斂；采用基于遺傳算法的BP神經網絡入侵檢測方法在20 Epochs之前收斂速度很快，在20 Epochs~130 Epochs之間收斂速度明顯下降，并且到140 Epochs了才收斂；采用基于改進的BP神經網絡入侵檢測方法一直收斂速度很快，并在70 Epochs時就已經完全收斂。

　　同時，為了進一步說明改進的BP神經網絡的入侵檢測方法的性能，通過對試驗所用數據集中最常見的攻擊類型進行測試，并將三種神經網絡用于入侵檢測中的檢測率與誤報率進行對比，結果如表1所示。其中：

　　誤報率=被誤報為入侵的正常樣本數／正常樣本總數

　　檢測率=檢測出的入侵樣本數／入侵樣本總數

　　由表1可以看出，對比三種神經網絡，本文的方法不僅收斂速度快，且對各種攻擊的檢測率明顯較高、誤報率較低，所以基于改進的BP神經網絡入侵檢測方法的性能得到了明顯的提升。

4 結論

　　本文的方法在解決BP神經網絡的局部極小與收斂速度上有明顯優勢，充分利用了遺傳算法與禁忌搜索的優點，不僅能在全局搜索最優解，也可以對局部進行搜索，增強了搜索能力，提高了檢測率，減少了誤報率，進而提升入侵檢測的性能。

參考文獻

　　[1] 呂杰.改進BP神經網絡在入侵檢測中的研究及應用[D].廣州：廣東工業大學，2008.

　　[2] 周政.BP神經網絡的發展現狀綜述[J].山西電子技術，2008（2）：90-92.

　　[3] 李偉超，宋大猛，陳斌.基于遺傳算法的人工神經網絡[J].計算機工程與設計，2006，27（2）：316-318.

　　[4] 朱紅萍，鞏青歌，雷戰波.基于遺傳算法的入侵檢測特征選擇[J].計算機應用研究，2012，29（4）：1417-1419.

　　[5] 張鳳斌，楊永田，江子揚.遺傳算法在基于網絡異常的入侵檢測中的應用[J].電子學報，2004，32（5）：875-877.

　　[6] 周貴旺，孫敏.改進遺傳算法優化的BP神經網絡入侵檢測研究[J].微型機與應用，2010，29（21）：65-68.

　　[7] 紀穎，李蘭英，石敏，等.基于遺傳和禁忌搜索B合的軟硬件劃分算法[J].計算機工程與應用，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] 王凌.智能優化算法及其應用[M].北京：清華大學出版社，2001.

　　[13] 張新有，曾華燊，賈磊.入侵檢測數據集KDD CUP99研究[J].計算機工程與設計，2010（22）：4809-4812.