多层动态克隆选择算法的研究

论文导读：所以有必要用否定选择算法对新生成的子检测器做一个判定。遗传算法是克隆选择算法的核心。否定选择，多层动态克隆选择算法的研究。
关键词：入侵检测，否定选择，克隆选择
 

1.引言

克隆选择是基于人工免疫机制的入侵检测系统中一个重要组成部分。Forrest小组提出的静态克隆选择算法能够在一个静态数据集上建立一个有效的误用检测器，但它最大的缺点是不能适应网络流的变化，即不具有自适应性[1]。在Forrest的静态克隆选择算法中，首先产生随机检测器集合D，D中的检测器都是经过随机产生器产生，再经否定选择后送到集合D中，D中的检测器初始适应度值为0。否定选择的目的，是为了排除和“自体”匹配的无效检测器，使随机产生的检测器，先和“自体”数据库中的所有记录进行比较，若匹配，则丢弃；否则，送入检测器集合D。由于“自体”数据库非常大，因此进行否定选择的时间很长。

J. Kim此此算法略作改进[2]，使否定选择函数返回一个特定的值，作为检测器的初始适应度值，检测器的优劣由适应度值的大小来衡量。可以把适应度值限制在0和1之间，在进行否定选择时，计算产生的每个随机检测器和“自体”数据库中的每个“自体”模式匹配的相异度值，否定选择函数返回这些相异度的平均值，并把这个返回值作为这个检测器的初始适应度值。即

其中：fitness(i)为随机产生的第i个随机检测器；N为自体数据库中“自体”模式的个数；dissimilarity(antibody(i),self (j))为产生的第i个随机检测器和“自体”数据库中第j个“自体”模式匹配的相异度值。论文格式，否定选择。

静态克隆选择算法在一定程度上改进了否定选择算法。但是，传统的克隆选择算法是在静态的抗原数据集基础上进行模式识别的，这种方法对先前已经收集到的数据具有较好的效果[3]。不过，现实环境中(比如网络中的入侵检测)，不停的有新的入侵模式, 也就是说AIS每天面对的可能是各种不同的抗原。更重要的是, 现实中某时刻被认为Self(正常行为模式)，到了下一时刻可能就成了Nonself(异形模式)。因此，我们要求AIS除了具备先前已经描述的具有识别新的未知模式的能力外，当识别器的识别能力不再正确的时候，它应该随时被替换[4]。

2.否定选择算子

检测系统选择两个双亲检测器，采用交叉、变异的方法去产生后代检测器，并用后代检测器中更优的子检测器去代替父检测器中检测效果较差的检测器。由于两个父检测器随机选取，交叉、变异的过程中可能产生无效的检测器，所以有必要用否定选择算法对新生成的子检测器做一个判定，当后代检测器与任一自体抗原匹配时，这个后代检测器就被淘汰。当一个无效后代检测器产生时，检测系统就用同一对双亲检测器基因算子产生一个新的后代检测器。当产生有效后代检测器失败次数超过T时，检测系统就选择一对新的双亲检测器产生新的后代检测器。论文格式，否定选择。

3.遗传选择算子

遗传算法是克隆选择算法的核心。遗传算法的基本原理是直接由自然行为类推而来。每个个体根据问题的好坏被赋予一个适应度。适应度越高的个体有更高的机会与其他个体交叉繁殖进行再生，新产的个体被称为后代，它们共享一些来自于它们双亲的特征。那些适应度较低的个体因为不太可能被选出来，最后都会灭亡。克隆选择算法用遗传算法作为遗传算子，随机选择成熟的检测器，这样能产生更新更优的子检测器。用遗传算法产生的新的子检测器中，有更优的，但也有更不合格的，所以需要用否定选择算法对他们作一个选择。遗传算法是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化，具有广泛适用性的搜索方法。所有自然种类都是适应环境而得以生存，这一自然适应性是遗传算法的主旋律。论文格式，否定选择。遗传算法搜索结合了达尔文适者生存和随机信息交换，前者消除了解中不适应因素，后者利用原有解中己有知识，从而有力地加快了抽索讨程。

下面举例说明基本方法。对于一个给定的优化问题，设目标函数

F=(x,y,z), (x,y,z),FR

要求(x0,y0,z0)使得

F=f(x0,y0,z0)=max(f(x,y,z))

其中 (x,y,z)为自变量，是(x,y,z)的定义域，(x,y,z) 可以是数值，也可以是符号；F为实数，是解的优劣程度或适应度的一种度量；f 为解空间(x,y,z) 到实数域FR的一种映射，那么遗传算法的求解步骤如下:

（1）编码

用一定比特数的0,1二进制码对自变量x,y,z进行编码形成基因码链，每一码链代表一个个体，表示优化问题的一个解。如x有16种可能取值x0,x1，…x15，则可以用4bit的二进制码0000-1111来表示。将x,y,z的基因码组合在一起则形成码链。

（2）产生群体

t=0，随机产生n个个体组成一个群体P(t)，该群体代表优化问题的一些可能解的集合。当然，一般来说，它们的素质都很差，遗传算法的任务是要从这些群体出发，模拟进化过程，择优汰劣，最后得出非常优秀的群体和个体，满足优化的要求。

（3）评价

按编码规则，将群体P(t)中的每一个体的基因码所对应的自变量取值(xi,yi,zi)代入(4-l)式，算出其函数值Fi ,i=1,2,…,N。Fi越大，表示该个体有较高的适应度，更适应于f所定义的生存环境，适应度F为群体进化时的选择提供了依据。

（4）选择(复制)

按一定概率从群体P(t)中选取M对个体，作为双亲用于繁殖后代，产生新的个体加入下一代群体P(t+1) 中。一般P,与F,成正比，就是说，适合于生存环境的优良个体将有更多的繁殖后代的机会，从而使优良特性得以遗传。选择是遗传算法的关键，它体现了自然界中适者生存的思想。

（5）交叉

对于选中的用于繁殖的每一对个体，随机地选择同一整数n，将双亲的基因码链在此位置相互交换，如个体x,y在位置3经交叉产生新个体x’,y’，它们组合了父辈个体x,y的特征，即

x=x1x2x3x4x5[00011]

y=y1y2y3y4y5[11100]

x’=x1x2x3x4x5[00000]

y’=y1y2y3y4y5[11100]

交叉体现了自然界中信息交换的思想。论文格式，否定选择。

（6）变异

以一定概率凡从群体P(t+1)中随机选取若干个体，对于选中的个体，随机选取某一位进行取反运算，即由10或由01。同自然界一样，每一位发生变异的概率是很小的。变异模拟了生物进化过程中的偶然基因突变现象。遗传算法的搜索能力主要是由选择和交叉赋予的，变异算子则保证了算法能搜索到问题解空间的每一点，从而使算法具有全局最优，它进一步增强了遗传算法的能力。

对产生的新一代群体进行重新评价选择、交叉、变异，如此循环往复，使群体中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度值不再提高，则迭代过程收敛，算法结束。

4.多层动态克隆选择算法

为了有效解决上面的问题，对静态克隆选择算法进行改进。引入几个重要的参数和与先前有所不同的新的免疫细胞，称为记忆识别器。即成熟识别器集中除了一般的经过克隆选择生成的成熟识别器之外，还包括记忆识别器。一个参数是生命期限，指的是成熟识别器参与模式识别的期限，当一个成熟识别器不能在规定的期限内识别出Nonself，说明该识别器并不是理想的识别器，应该被去掉；另一个参数是记忆计数器，每当成熟识别器识别出一个异形模式，则该计数器自动增加，当超过预先设定好的阀值时，说明该成熟识别器具有较高的识别效率，因此将其作为记忆识别器加入到成熟识别器集合中。这样，识别器集合具有了多层次性。同时，为了适应Self和Nonself的动态变化，用新增的抗原对成熟识别器进行再选择，去掉那些不再有用的识别器，以降低伪肯定率(误判)。

算法描述：首先初始化识别器种群，计算种群中每个检测器的适应值，在适应值高的检测器中随便选择两个检测器进行克隆繁殖产生子检测器，让子检测器通过一个否定选择过程去掉那些能够识别自体的检测器，这样就得到了成熟的检测器集合。下面是另一个再选择过程，因为我们动态的增加了自体或非自体，所以有必要对成熟的检测器进行一次再选择过程，通过再选择过程的检测器经过监测而达到激活阀值的就激活，而没达到激活阀值的就等待或者死亡。论文格式，否定选择。

算法分析：算法能动态的适应不断变化的网络环境，能够根据环境的要求动态的优化检测器。而在检测器通过初次选择成为成熟检测器后又通过一个再选择过程，这个过程能很好的配合动态新增自体或非自体，因为每次动态新增加了自体或者非自体后原来的一些检测器可能会改变它的属性，如原来合格的成熟检测器可能因为新增自体而变为无效检测器，这个在选择过程就能够把它过滤掉，从而能在保持误报率不变的基础上提高检测率。论文格式，否定选择。

结束语

由于遗传算法的特点，静态克隆选择算法产生的检测器有可能是无效检测器，所以本文提出了一种多层动态克隆选择算法，对每次动态克隆的新检测器再次检测，判断其有效性，从而过滤掉无效低检测器但是本算法也增加了算法的复杂度，这也是日后需要改进的地方。

参考文献
[1]S.Forrest,Hofmeyr,Somayaji.ComputerImmunology.CommunicationsoftheACM,1997,40(10):88~96
[2]J.Kim,P.Bentley.TowardsanArtificialImmuneSystemforNetworkIntrusionDetection:AnInvestigationofDynamicClonalSelection.TheCongressonEvolutionaryComputation，Honolulu,2002:1015~1020.
[3]M.Balazinska,E.Merlo,M.Dagenais,etl.Advancedclone-analysistosupportobject-orientedsystemrefactoring.Proceedings.SeventhWorkingConferenceonReverseEngineering,Brisbane,2000:98~107.
[4]ZejunWu,YiwenLiang.Integratedplatformofartificialimmunesystemforanomalydetection.WSEASTransactionsonInformationScienceandApplications,2005,2(2):144~149