搜索
1.1遗传算法在入侵检测中的应用遗传算法已经以很多的方式应用于入侵检测中。一类方法是直接使用遗传算法产生出分类规则；另一类方法是应用不同的人工智能方法获取规则，而用遗传算法来选择更适合的特征或对一些函数参数进行优化。本文使用第一类方法直接使用遗传算法产生出分类规则。1.1.1数据分析与染色体编码大样本数据，一般指样本量大、数据结构复杂、离散度大的样本数据。在预测、回归分析以及图像处理、模式识别等领域中涉及大样本数据处理时，一般首先要对大样本数据聚类分析，得到对象数据集的关联规则，然后才能进一步进行相关的研究工作。本文的研究就是基于大样本数据进行的，首先对样本进行聚类分析，本节将用遗传算法对训练集聚类，得出规则集。首先从“KDDCup1999Data”中选取了8维数据作为训练集。其中，前面7维数据为分类规则，第8维数据为标记位，它唯一确定了数据的属性。具体的8维数据属性如表5.4所示。单个TCP连接的基本属性表5.4特征名称特征描述数据类型src_bytes从源端到目的端传输的字节数连续型dst_bytes从目的端到源端传输的字节数连续型count两秒内对同一主机发出的连接数目连续型srv_count两秒时间内与当前连接使用相同服务的连接数连续型dst_host_count过去两秒时间内对同一主机发出的连接数连续型dst_host_srv_count两秒内与当前连接同样的服务的连接数连续型dst_host_same_src_port_rate对于同一端口的连接所占的百分比连续型falg标记该数据的类型（正常数据或攻击数据）离散型由于正常数据与攻击数据间存在着本质的区别，因此正常数据与正常数据的相似度较高，攻击数据与攻击数据的相似度较高，正常数据与攻击数据的相似度较低。由此，可以明确地将正常数据与攻击数据分离。通过聚类确定两个聚类中心，将训练集通过算法分成两个类，一类为正常数据，另一类为攻击数据。通过数据分析，可以使用二进制对训练集进行编码。如图5.1所示。图5.1染色体编码示意图每一条染色体标记了训练集中所有数据的类型，1代表正常数据，0代表攻击数据。染色体的长度即为训练集的规模。1.1.2适应度函数1.1.3选择方式(赌轮选择法)通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为(1)1.1.4交叉方式鉴于该算法种群染色体长的特点，单点交叉显得不足，而随机多点交叉在算法的实现上比较复杂。因此，在该算法中引入了基因的概念，将染色体分成一个一个的基因片断。在该算法中，染色体的编码凡是决定了染色体的长度成百上千。若染色体的长度为N，单个基因片断的长度为M，则整个染色体被分割成N/M个基因。对每个基因进行单点交叉，整体上看就相当于对整条染色体进行了多点交叉，确21||||||iiiicxCieieiixCcxmCxmJxmJC个类别，待聚类数据，为类别的中心，越小聚类结果越好NjjiixfxfxP1)()()(保了交叉的范围足够大，更好地产生出新的种群。改进后的多点交叉既保留了多点交叉的优点，又方便了算法的实现，还体现了自然界遗传的真实特点。1.1.5变异方式变异借鉴了基因片断的引入，在每个基因片断上进行单独的变异。1.1.6终止条件在基本遗传算法中，介绍了一般采用最大代数作为算法的停止准则。该方法简单易行，但是并不准确。应为可能在最大代数之前算法已经收敛很长时间，这将浪费大量的时间作无谓的计算；也可能在最大迭代次数时算法还没有收敛，这将影响到算法的准确率。除了将最大迭代次数作为停止准则外，还可以根据种群的收敛程度，即种群中适应值的一致性来判断是否算法停止。在算法过程中保留历史最好的个体的适应值，使用公式(2)判断种群是否收敛。||FFi(2)公式(2)中，F为最后M个历史最好个体的适应值，F为F的平均值，是一个足够小的常量。通过控制的值可以控制在最后M历史最优值的方差小于的时候认为算法达到收敛。1.1.7算法流程从以上分析可得出用于该模型中遗传算法的流程。概括的讲，该算法的大体步骤如下：第1步：装载数据，选出训练集，将数据标准化。第1步：随机建立初始种群。第2步：计算出各个体的适应值。第3步：选择。第4步：交叉，将选出的父代两两间进行多点交叉，所产生的新个体添入新种群。第5步：变异，随机地改变某个个体的某一字符，将新个体添入新种群。第6步：判断终止条件，若终止条件满足则计算分类准确度并测试、输出结果，否则转第3步。算法的流程图如图所示。图1遗传算法流程图1.1.8算法参数确定在该遗传算法中种群最大迭代次数eranum设为1000，基因长度GaLen设为20。剩下需要确定的算法参数有种群规模popsize，交叉概率pCross和变异概率pMutation。通过测试发现，种群规模popsize对算法的收敛有很大影响。当种群规模popsize为5的时候，种群收敛时迭代次数一般在100次以内，随着交叉率pCross和变异率pMutation的增加迭代次数增加，但是分类准确率非常低，30%-60%不等，随着交叉率pCross和变异率pMutation的增大分类准确率增大。当种群规模popsize增加到20的时候，种群收敛时的迭代次数基本都在200次以上，并且随着交叉率pCross和变异率pMutation的变化而改变，这时候分类准确率一般都在90%以上。当种群规模popsize继续增加的时候，发现种群收敛时的迭代次数没有太大的改变，分类准确率也没有太大的提高，但是算法的执行时间却增加了。因此认为popsize=20是一个合理、有效的设定。在种群规模popsize=20的时候测试交叉率pCross和变异率pMutation发现，当交叉率pCross=0.9，变异率pMutation=0.05的时候种群收敛效果非常好，分类准确率达到98%以上，并且种群收敛时的迭代次数在210次左右。综合考虑以上测试情况，种群规模popsize取20，交叉概率pCross取0.9，变异概率pMutation取0.05，这时候的收敛速度和收敛效果都很好。