摘  要： 针对遗传算法局部搜索能力弱和收敛速度慢，在选择操作之后加上了禁忌搜索算法，并对交叉操作进行改进，最后用禁忌搜索作为变异操作，从而加快算法的收敛速度，并用此改进的遗传算法来优化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所示。

　　（1）用BP网络训练初始权值和阈值，如果误差精度满足要求，则结束训练；否则将这些权值和阈值作为初始种群进行下面步骤。

　　（2）编码。采用搜索能力强的二进制编码。

　　（3）用适应度函数计算出各个体的适应度函数值。

　　（4）选择。采用轮盘赌选择方法。

　　（5）用禁忌搜索算法找出适应度更高的个体。

　　（6）用改进的交叉算法进行交叉操作。

　　（7）变异。将禁忌搜索算法作为变异算子。

　　（8）重复进行步骤（4）~（7），直至达到最大进化代数后结束。

　　（9）将得到的最优解作为权值再用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

　　（3）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.