基于克隆选择原理的免疫识别算法研究

2011-06-12 08:55傅慧
网络安全技术与应用 2011年5期
关键词:亲和力免疫系统自体

傅慧

南昌陆军学院 江西 330103

0 引言

人工免疫系统(Artificial Immune Systems,AIS)是继神经计算、进化计算之后的自然计算的研究新方向,己经迅速成为研究热点,主要是通过深入探索生物免疫系统所蕴含的信息处理机制,建立相应的工程模型和算法,用于解决各种复杂问题。

1 免疫系统

生物免疫系统将所有的细胞分为两类:Self细胞(自我)和NonSelf细胞(非我)。Self细胞指自身健康,没有被感染、破坏的细胞;NonSelf细胞指病毒、细菌、寄生虫等有害物质和自身被感染、破坏的细胞。免疫就是识别Self和NonSelf,并消灭NonSelf,是为了保证机体完整性的一种生理学反应。用集合表示有这么一个关系:对于集合域X,它包括两个子集自体集合S和非自体集合N,则有自体集合S⊆X和非自体集合N⊂X,而且S∪F=X且S∩F=φ。

2 人工免疫算法

人工免疫系统抽取生物免疫系统所蕴含的信息处理机制,建立用于解决各种复杂问题的工程模型和算法,这些模型和算法都力图集中体现以上的生物免疫系统的相应特点。

人工免疫算法(Artificial Immune Algorithlum,AIA)是模拟人体免疫学原理而设计的一种新型算法,是自然免疫系统在进化计算的一个实现。

人工免疫算法的基本流程如图1。

STEP1:初始化AIA的抗原。对运行过程所需参数和数据进行设置,包括初始化运行参数、基因库以及确定抗体的编码方式和构造初始抗体集,通常可以在解空间中随机产生N个候选解作为初始抗体,N为抗体群中抗体的数目。

图1 人工免疫算法的基本流程

STEP2:计算亲和力(affinity)。亲和力是一个抗体结合部位与一个抗原决定基结合的牢固性,结合自抗原分离的可能越小。用来表示抗原和抗体之间、抗体和抗体之间结构的相信程度。设定亲和力的计算函数为 Affinity(B,G),一般使用介于0到1之间的实数表示,Affinity(B,G)值越大说明抗体B和抗原G之间匹配得越好。

STEP3:产生新的抗体。调用人工免疫算法,初识抗体通过人工免疫算法的作用产生新的抗体。

STEP4:调用Affinity(B,G),计算新抗体的亲和力。

STEP5:若新抗体中有与抗原匹配的抗体,则结束,否则转到STEP6。

STEP6:抗体选择。按照“优胜劣汰”的自然选择机制,在原有的N个有效抗体和新产生的若干个体抗体中选择出N个与抗原匹配得较好的抗体构成新的抗体群,在进行选择操作时,应依据抗体之间的排斥力限制进入新抗体群中的相同抗体的数目,以保持抗体群中抗体的多样性,增强抗体群的免疫力,选择完成后转到STEP3。

3 基于克隆选择的免疫识别算法

克隆选择学说早在1958年就由Burnet建立,描述了获得性免疫的基本特性,并且生命只有成功识别抗原的免疫细胞才得以增殖,经变异后的免疫细胞分化为效应细胞(抗体)和记忆细胞两种。但计算领域的克隆选择算法(Colonel Selection Algorithm,CSA)却直到2001年才由D.castro和von Zuben明确提出,能够完成机器学习和模式识别的任务,并可以用来解决优化问题。其核心是复制(克隆)和变异。前者与个体的亲和度成正比,保证群体亲和度逐步增大,后者与个体的亲和度成反比,保留最佳个体并改进较差个体。

克隆选择算法是基于群体的免疫算法,是一种模拟免疫系统的学习过程的进化算法,它模拟这一过程进行优化。也是抗体集进行群体更新的策略(如图2)。

图2 基于克隆选择的免疫识别算法

STEP1:抽取抗原集合中的一个抗原。

STEP2:计算与抗体集合中每个抗体的亲和力;从中选择n个亲和力最高的抗体。

STEP3:对选择出来的抗体进行克隆增殖,目的是确定对各抗体所在邻域做局部搜索的次数。克隆规模正比于抗体的亲和度,即亲和度高的抗体得到的局部搜索的机会较多。

STEP4:对克隆产生的个体进行突变,用来对各抗体所在的邻域进行局部搜索,变异位数反比于其同抗原的亲和力,即对亲和度较高的抗体,则在其较小的邻域范围内做精细搜索。

STEP5:压缩选择,在抗体群中选择具有最高亲和度的n个抗体组成新一代抗体群,更新抗体集合。

STEP6:如果满足终止条件,则结束;否则转至STEP1继续执行。

从算法流程分析得知,克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖,随后通过遗传变异分化为多样性效应细胞(如抗体细胞)和记忆细胞。克隆选择对应着一个亲和力成熟(affinity maturation)的过程,即对抗原亲和力较低的个体在克隆选择机制的作用下,经历增殖复制和变异操作后,其亲和力逐步提高而“成熟”的过程,本质上是一个达尔文式的选择和变异的过程。

4 结论

利用人工免疫的基本原理来解决计算机系统的安全问题,主要也是区分“自体”和“非自体”的问题,人工免疫系统是具有自学习、自适应、自组织的高度复杂性系统的代表,己经迅速成为研究热点,其研究成果已应用到计算机安全、模式识别、机器学习、机器人控制、异常和故障检测、数据挖掘和分析及复杂优化问题求解等诸多领域。

[1]刘若辰,杜海峰,焦李成.免疫多克隆策略[J].计算机研究与发展.2004.

猜你喜欢
亲和力免疫系统自体
身体的保护伞——免疫系统
一类具有抗原性的肿瘤-免疫系统的定性分析
自体血清在干眼症治疗中的应用进展
保护好你自己的免疫系统
Staying healthy
高端访谈节目如何提升亲和力
高端访谈节目如何提升亲和力探索
亲和力在播音主持中的作用探究
脂肪推土机 Bulldozer “自体脂肪填充”大揭秘!
将亲和力应用于播音主持中的方法探讨