摘  要： 針對遺傳算法局部搜索能力弱和收斂速度慢,，在選擇操作之后加上了禁忌搜索算法，并對交叉操作進(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)值選擇不合適，就會(huì)導(dǎo)致網(wǎng)絡(luò)陷入局部極小,、收斂速度慢,、振蕩等問題[2],。針對以上不足，運(yùn)用遺傳算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值[3],，然后應(yīng)用于入侵檢測,。遺傳算法具有并行搜索能力，但它局部搜索能力差,，會(huì)導(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ī)會(huì)的大小，并且禁忌搜索算法沒有并行搜索能力[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所示。

　?。?）用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ù)值,。

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

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

　?。?）用改進(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ù)是判斷個(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ī)交叉會(huì)導(dǎo)致高適應(yīng)度個(gè)體的優(yōu)秀基因被替代,，從而算法的收斂速度下降。并且個(gè)體經(jīng)過一代一代的選擇之后,，留下的適應(yīng)度高的個(gè)體的基因可能具有高的相似度,，讓這些個(gè)體進(jìn)行交叉，很難產(chǎn)生新的基因,，會(huì)有很多無效交叉操作,，容易發(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

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

　?。?）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ù)挖掘與知識(shí)發(fā)現(xiàn)國際會(huì)議[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.