摘  要： 針對遺傳算法局部搜索能力弱和收斂速度慢，在選擇操作之后加上了禁忌搜索算法,，并對交叉操作進(jìn)行改進(jìn),，最后用禁忌搜索作為變異操作，從而加快算法的收斂速度,，并用此改進(jìn)的遺傳算法來優(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ù)值大的個體,；同時改進(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)點,，而且兩種算法各自的優(yōu)點可以彌補(bǔ)對方的不足，混合算法具有并行搜索能力,、爬山能力強(qiáng)的優(yōu)勢,，能夠克服遺傳算法爬山能力差、禁忌搜索算法單點出發(fā)的弱點,，最終能尋找出更好的解,，然后用此最優(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

　　 //計算適應(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)步驟

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

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

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

　?。?）用適應(yīng)度函數(shù)計算出各個體的適應(yīng)度函數(shù)值,。

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

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

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

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

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

　?。?）將得到的最優(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ù)是判斷個體適應(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 選擇操作

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

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

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

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

　　本文對遺傳算法的交叉算子進(jìn)行改進(jìn)，計算個體之間的相似度,，根據(jù)相似度進(jìn)行分類,，將相似度大于0.5的個體分在不同類，不同類的個體之間可以進(jìn)行交叉；相似度小于0.5的個體分在同類中,，彼此之間不能進(jìn)行交叉操作,。適應(yīng)度大的個體給予較小的交叉概率，從而能夠保留一部分優(yōu)秀基因,；適應(yīng)度小的個體設(shè)置較大的交叉概率,，進(jìn)而可以淘汰掉這一部分個體。首先將個體按照適應(yīng)度大小進(jìn)行從大到小的排序,，復(fù)制1/4適應(yīng)度值高的個體直接進(jìn)入下一代,，這樣有利于優(yōu)秀基因的保留。然后按照適應(yīng)度值大小排序的序列,，從適應(yīng)度值高的個體開始與不同類的基因按照交叉概率進(jìn)行交叉,。因為適應(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)重要的一步,，但變異算子只能對基因進(jìn)行局部突變,，變異概率小。本文用禁忌搜索算法作為變異算子,，提高了種群多樣性,，并且使得遺傳算法同時具有全局搜索能力和局部搜素能力，它能接受劣解,，一定程度上能緩解早熟現(xiàn)象的發(fā)生。

3 入侵檢測MATLAB仿真實驗及結(jié)果

　　試驗數(shù)據(jù)來源于具有權(quán)威性的數(shù)據(jù)挖掘與知識發(fā)現(xiàn)國際會議[13]，并用MATLAB7.0進(jìn)行仿真驗證其性能,。選取神經(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，最大進(jìn)化代數(shù)為200,，選擇概率為0.8,，交叉率為0.8。

　　將數(shù)據(jù)和設(shè)置好的參數(shù)分別用到單獨的基于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所示,。

　　從以上三個圖可以看出：基于改進(jìn)的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了才收斂,；采用基于改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)入侵檢測方法一直收斂速度很快，并在70 Epochs時就已經(jīng)完全收斂,。

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

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

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

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

4 結(jié)論

　　本文的方法在解決BP神經(jīng)網(wǎng)絡(luò)的局部極小與收斂速度上有明顯優(yōu)勢,，充分利用了遺傳算法與禁忌搜索的優(yōu)點,，不僅能在全局搜索最優(yōu)解,，也可以對局部進(jìn)行搜索，增強(qiáng)了搜索能力,，提高了檢測率,，減少了誤報率，進(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ī)工程與設(shè)計，2006,，27（2）：316-318.

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

　　[5] 張鳳斌，楊永田,，江子揚.遺傳算法在基于網(wǎng)絡(luò)異常的入侵檢測中的應(yīng)用[J].電子學(xué)報,，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ī)工程與應(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ī)工程與設(shè)計，2010（22）：4809-4812.