2 基于网格的实值否定选择算法

2.1 引言

在过去的十年间，人工免疫系统作为一种解决复杂计算问题的新方法引起了广泛的关注。当前，对人工免疫的研究主要集中在四个方面：否定选择算法、免疫网络、克隆选择、危险理论和树突状细胞算法。否定选择算法通过模拟生物系统的T细胞成熟过程中的免疫耐受机制，删除自反应候选检测器来识别非自体抗原，并成功应用于模式识别、异常检测、机器学习、故障诊断等。

否定选择算法是由Forrest等提出的。该算法采用字符串或二进制串来编码抗原（样本）和抗体（检测器），采用r-连续位匹配方法来计算抗原和检测器间的亲和力，被称为SNSA。Forrest等提出的否定选择算法中，采用二进制字符串表示抗原和抗体，并采用r连续位匹配算法计算抗体与抗原的匹配程度，成功应用于异常检测系统。之后，Balthrop等指出了r-连续位匹配存在的漏洞并提出了改进的r-chunk匹配机制。张衡等提出了r-可变否定选择算法，何申等提出了检测器长度可变否定选择算法。

Li指出，在SNSA算法中，检测器的生成效率是非常低的。候选检测器通过否定选择变为成熟检测器。假定Ns为训练集大小，P′为任意抗原和抗体之间的匹配概率，Pf为失败率；则候选检测器的数量为N = - ln（Pf）/[P′(1 -P′) Ns]，与Ns成指数关系，且SNSA的时间复杂度为O（N·Ns）。

在实际应用中，很多问题都是在实值空间定义和研究的，Gonzalez等提出了实值否定选择算法（RNSA）。该算法采用实值空间[0,1]n的n维向量对抗体和抗原进行编码，采用Minkowski距离计算亲和力。Ji等提出了一种变半径的实值否定选择算法（V-Detector），得出了更好的结果。该算法通过计算候选检测器的中心与自体抗原的最近距离，来动态决定一个成熟检测器的半径。同时，该算法提出了一种基于概率的方法来计算检测器的覆盖率。Gao等提出了一种基于遗传原理的否定选择算法，Gao、Chow等提出了一种基于克隆优化的否定选择算法。这两种算法的检测器通过优化算法的处理，来获得更多的非自体空间覆盖率。Shapiro等在否定选择算法中引入了超椭圆体检测器，Ostaszewski等引入了超矩形检测器。这些检测器相比球形检测器，可以以较少的检测器达到同样的覆盖率。Stibor等提出了自体检测器分类方法。在该方法中，自体被看成是有初始半径的自体检测器，而且在训练阶段自体的半径可以通过ROC（接收工作特征）分析动态确定，提高了检测率。Chen等提出了一种基于自体集层次聚类的否定选择算法。该算法通过对自体集进行层次聚类预处理来改进检测器的生成效率。Gong等将检测器分为自体检测器和非自体检测器，分别覆盖自体空间和非自体空间，用自体检测器代替自体元素从而减少计算代价。

还有一些研究将其他人工智能算法引入否定选择算法中，来提高检测器的生成效率。Gao等和Abdolahnezhad等提出了一种基于遗传原理的否定选择算法，Idris将粒子群优化策略与否定选择算法结合起来，Lima等将小波变换引入否定选择算法中。

由于成熟检测器的生成效率较低，否定选择算法的时间代价严重限制了它们的实际应用。本书提出了一种基于网格的实值否定选择算法，记为GBRNSA。该算法分析了自体集在形态空间的分布，并引入了网格机制，来减少距离计算的时间代价和检测器间的冗余覆盖。理论分析和实验结果表明，GBRNSA降低了检测器的数量、时间复杂度及误报率。