摘  要： 針對遺傳算法局部搜索能力弱和收斂速度慢，在選擇操作之后加上了禁忌搜索算法，并對交叉操作進(jìn)行改進(jìn)，最后用禁忌搜索作為變異操作，從而加快算法的收斂速度，并用此改進(jìn)的遺傳算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值。實(shí)驗(yà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)在已有許多方法運(yù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ùn)用遺傳算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值[3]，然后應(yīng)用于入侵檢測。遺傳算法具有并行搜索能力，但它局部搜索能力差，會導(dǎo)致早熟發(fā)生[4-6]。

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

1 基于改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)入侵檢測原理

　　1.1 改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法模型

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

　　 //計(jì)算適應(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 算法的具體實(shí)現(xiàn)步驟

　　基于改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)入侵檢測算法的主要步驟如下，算法流程圖如圖2所示。

　　（1）用BP網(wǎng)絡(luò)訓(xùn)練初始權(quán)值和閾值，如果誤差精度滿足要求，則結(jié)束訓(xùn)練；否則將這些權(quán)值和閾值作為初始種群進(jìn)行下面步驟。

　　（2）編碼。采用搜索能力強(qiáng)的二進(jìn)制編碼。

　　（3）用適應(yīng)度函數(shù)計(jì)算出各個(gè)體的適應(yīng)度函數(shù)值。

　　（4）選擇。采用輪盤賭選擇方法。

　　（5）用禁忌搜索算法找出適應(yīng)度更高的個(gè)體。

　　（6）用改進(jìn)的交叉算法進(jìn)行交叉操作。

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

　　（8）重復(fù)進(jìn)行步驟（4）~（7），直至達(dá)到最大進(jìn)化代數(shù)后結(jié)束。

　　（9）將得到的最優(yōu)解作為權(quán)值再用BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練，若滿足精度要求，則算法結(jié)束；否則繼續(xù)訓(xùn)練，直至達(dá)到精度要求為止。

2 改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法研究

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

　　適應(yīng)度函數(shù)是判斷個(gè)體適應(yīng)環(huán)境能力大小的標(biāo)準(zhǔn)，保留適應(yīng)度大的個(gè)體，淘汰適應(yīng)度小的個(gè)體，一代一代選擇下去，提高了群體的平均適應(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 選擇操作

　　遺傳算法最常用的選擇方法是輪盤賭選擇、隨機(jī)抽樣選擇和錦標(biāo)賽選擇法。前兩種方法隨機(jī)性太強(qiáng)，有時(shí)連適應(yīng)度較高的個(gè)體也無法選擇；而錦標(biāo)賽選擇法容易產(chǎn)生超級個(gè)體[11]。

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

　　2.3 改進(jìn)的交叉操作

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

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

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

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

　　例如：有兩個(gè)字符串Str1=AABCE，Str2=AADCBA

　　（1）Str1=AABCE（將B替換成D）→Str1=AADCE

　　（2）Str1=AADCE（將E替換成B）→Str1=AADCB

　　（3）Str1=AADCB（插入A）→Str1=AADCBA=Str2

　　總共需要三次變換（將B替換成D，將E替換成B，插入A），所以編輯距離就是3。那么Str1和Str2的相似度=1-3/6=1/2。

　　2.4 變異操作

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

3 入侵檢測MATLAB仿真實(shí)驗(yàn)及結(jié)果

　　試驗(yàn)數(shù)據(jù)來源于具有權(quán)威性的數(shù)據(jù)挖掘與知識發(fā)現(xiàn)國際會議[13]，并用MATLAB7.0進(jìn)行仿真驗(yàn)證其性能。選取神經(jīng)網(wǎng)絡(luò)輸入層節(jié)點(diǎn)數(shù)為10，隱含層節(jié)點(diǎn)為15，輸出層為1；隱含層與輸出層激勵(lì)函數(shù)為tansig，訓(xùn)練函數(shù)為traingda，目標(biāo)精度為0.005，最大訓(xùn)練周期為500；遺傳算法初始種群大小為200，最大進(jìn)化代數(shù)為200，選擇概率為0.8，交叉率為0.8。

　　將數(shù)據(jù)和設(shè)置好的參數(shù)分別用到單獨(dú)的基于BP神經(jīng)網(wǎng)絡(luò)、遺傳算法優(yōu)化的神經(jīng)網(wǎng)絡(luò)和本文將遺傳算法和禁忌搜索算法結(jié)合起來的基于改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)中，并用MATLAB7.0對三種神經(jīng)網(wǎng)絡(luò)分別進(jìn)行入侵檢測仿真，結(jié)果如圖3~圖5所示。

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

　　同時(shí)，為了進(jìn)一步說明改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)的入侵檢測方法的性能，通過對試驗(yàn)所用數(shù)據(jù)集中最常見的攻擊類型進(jìn)行測試，并將三種神經(jīng)網(wǎng)絡(luò)用于入侵檢測中的檢測率與誤報(bào)率進(jìn)行對比，結(jié)果如表1所示。其中：

　　誤報(bào)率=被誤報(bào)為入侵的正常樣本數(shù)／正常樣本總數(shù)

　　檢測率=檢測出的入侵樣本數(shù)／入侵樣本總數(shù)

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

4 結(jié)論

　　本文的方法在解決BP神經(jīng)網(wǎng)絡(luò)的局部極小與收斂速度上有明顯優(yōu)勢，充分利用了遺傳算法與禁忌搜索的優(yōu)點(diǎn)，不僅能在全局搜索最優(yōu)解，也可以對局部進(jìn)行搜索，增強(qiáng)了搜索能力，提高了檢測率，減少了誤報(bào)率，進(jìn)而提升入侵檢測的性能。

參考文獻(xiàn)

　　[1] 呂杰.改進(jìn)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].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（2）：316-318.

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

　　[5] 張鳳斌，楊永田，江子揚(yáng).遺傳算法在基于網(wǎng)絡(luò)異常的入侵檢測中的應(yīng)用[J].電子學(xué)報(bào)，2004，32（5）：875-877.

　　[6] 周貴旺，孫敏.改進(jìn)遺傳算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)入侵檢測研究[J].微型機(jī)與應(yīng)用，2010，29（21）：65-68.

　　[7] 紀(jì)穎，李蘭英，石敏，等.基于遺傳和禁忌搜索B合的軟硬件劃分算法[J].計(jì)算機(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].計(jì)算機(jī)工程與設(shè)計(jì)，2010（22）：4809-4812.