基于克隆选择算法的模式识别

摘 要　该文在人工免疫系统和克隆选择原理的基础上，给出了clonalg算法，并对该算法的实现原理、参数选择等进行了详细研究；给出了利用该算法进行数字识别的实例。 关键词　克隆选择；人工免疫系统；数字识别 1　引言 生物免疫系统是一个高度进化的生物系统，它旨在区分外部有害抗原和自身组织，从而清除抗原并保持有机体的稳定。从计算的角度来看，生物免疫系统是一个高度并行、分布、自适应和自组织的系统，具有很强的学习、识别、记忆和特征提取的能力。人们希望从生物免疫系统的运行机制中获取灵感，开发出面向应用的免疫系统模型——人工免疫系统(artificial immune system， ais)，用于解决实际问题。目前，ais已发展成为计算智能研究的一个崭新的分支。其应用领域逐渐扩展到了信息安全、模式识别、智能优化、机器学习、数据挖掘、自动控制、故障诊断等诸多领域，显示出ais强大的信息处理和问题求解能力以及广阔的研究前景。 克隆选择是一种常用的ais算法。本文主要探讨该算法在数字识别中的应用。 克隆选择原理最先由jerne提出，后由burnet给予完整阐述。其大致内容为：当淋巴细胞实现对抗原的识别(即抗体和抗原的亲和度超过一定阀值)后，b细胞被激活并增殖复制产生b细胞克隆，随后克隆细胞经历变异过程，产生对抗原具有特异性的抗体。克隆选择理论描述了获得性免疫的基本特性，并且声明只有成功识别抗原的免疫细胞才得以增殖。经历变异后的免疫细胞分化为效应细胞(抗体)和记忆细胞两种。 克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖，随后通过遗传变异分化为多样性效应细胞(抗体细胞)和记忆细胞。克隆选择对应着一个亲合度成熟(affinity maturation)的过程，即对抗原亲合度较低的个体在克隆选择机制的作用下，经历增殖复制和变异操作后，其亲合度逐步提高而“成熟”的过程。因此亲合度成熟本质上是一个达尔文式的选择和变异的过程，克隆选择原理是通过采用交叉、变异等遗传算子和相应的群体控制机制实现的。 根据克隆选择原理，decastro提出了克隆选择算法(clonalg算法)模型，并在模式识别、组合优化和多峰值函数优化中得到了验证。其算法的核心在于增殖复制算子和变异算子，前者与个体亲合度成正比，保证群体亲合度逐步增大，后者与个体的亲合度成反比例关系，保留最佳个体并改进较差个体。 2　clonalg算法 clonalg算法是根据克隆选择原理设计的免疫算法。解决问题时，一般把问题定义为抗原，而问题的解就是抗体集合。在特定的形态空间中，随机产生的抗体试图与抗原发生匹配，即尝试解决问题。匹配度高的抗体有可能产生更好的解，被赋予更大的克隆概率参与下一次匹配。 抗体和抗原之间的距离d采用汉明距离，如式(1)所示。

抗体和抗原之间的亲和力aff与它们的距离成反比，即aff=1/d。 免疫算法的实现步骤如下： 步骤1 初始化抗体集合，随机产生n个抗体。 步骤2 计算抗体集合ab中所有抗体与抗原ag的亲和力。 步骤3 选择n个亲和力最高的抗体，组成一个新的抗体集合。并将这n个抗体按照亲和力升序排列。 步骤4 将选中的n个抗体按照对应的亲和力进行克隆，产生新的集合c，亲和力越高的抗体，克隆的数量就越多，总的数量计算公式如式(2)。 nc是总的克隆数，式(2)右边是一个和式，其中第i项代表抗体abi产生的克隆数， 是预设的参数因子，n是抗体集合包含的元素个数。 步骤5 新的集合c按照基因重组概率进行基因重组，产生成熟的克隆集合c*。 步骤6 计算成熟克隆集合的亲和力。 步骤7 从成熟克隆集合中选择n个亲和力最高的抗体作为记忆抗体的候选，亲和力超过现有记忆抗体的候选抗体称为新的记忆抗体。 步骤8 替换掉亲和力最低的d个抗体，并用新的随机抗体补充。 步骤9 如果抗体集合没有达到匹配精度要求且进化代数小于最大进化代数，则转到步骤2，否则算法结束。

3　应用clonalg算法识别数字 模式识别技术是根据研究对象的特征和属性，利用一定的分析算法，确定研究对象的归属和类别，并使结果尽可能符合真实。一般模式识别系统都包括问题描述、系统训练和模式识别几个部分。 本系统要解决的问题是识别0到9这十个数字。每个字符都用一个长度l=120的二进制串表示(每一个像素用一个二进制数表示)。原始字符(待识别的字符)(抗原)如图1所示。

图1 待识别的字符(抗原) 抗体指令集由10个抗体组成，即取n=10。每次选中5个亲和力最高的抗体进行克隆，即n=5。参数 =5。变异率初始值pm=0.05，并根据进化情况进行变化。最大进化代数gen=100，匹配精度取0，即要求完全匹配。 10个抗原(待识别数字)都达到了完全匹配，具体匹配情况如表1所示。 表1 数字0-9的完全匹配代数 抗原(待识别字符) 0 1 2 3 4 5 6 7 8 9 完全匹配代数 36 42 54 47 47 53 49 42 40 53 从表1可以看出，该算法的收敛速度是很快的。 由于篇幅所限，下面仅以数字“3”为例，观察一下算法的实现过程。 图2 识别数字“3”的过程 图2中，第一排按照从左向右的次序：第1幅图是原始字符，第2幅图是随机产生的抗体集，第3幅图和第4幅图分别是进化到第10代和第20代的抗体集。第二排按照从左向右的次序：第1幅图，第2幅图分别是进化到第30代，第40代的抗体集。最后一幅图是进化到第47代的抗体集。进化过程中抗体与抗原的距离变化情况如表2所示。 表2 识别“3”时抗体与抗原的距离d的变化 进化代数 5 10 15 20 25 30 35 40 45 47 抗体与抗原的距离d 30 19 12 8 5 3 1 1 1 0 从表2可以看出，实际上进化到35代时，抗体与抗原的距离d=1，在大多数应用中，这已经可以很好地满足要求了。 4　总结 从上面的讨论可以看出，clonalg算法是一种高效、快速收敛的算法，非常适合应用于模式识别。 参考文献 [1] 阎平凡等著，人工神经网络与模拟进化计算，清华大学出版社，2000 [2] 陈慰峰著，医学免疫学，人民出版社，2001 [3] 李涛著，计算机免疫学，电子工业出版社，2004