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

傅慧

南昌陆军学院 江西 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.