基于免疫MHC的否定选择算法孔洞修复方法

A negative selection algorithm hole improvement method based on MHC

否定选择算法(negative selection algorithm,NSA)是人工免疫系统的核心基础算法.孔洞是引起NSA检测率低的重要因素.传统NSA未考虑孔洞的分布,采取在特征空间内通过完全随机的方式盲目生成检测器以修复孔洞,导致孔洞修复效果不佳,并且淘汰无效的检测器也异常耗时.孔洞问题在生物免疫系统中也同样存在.生物免疫系统利用MHC分子针对孔洞产生的特殊形态,对免疫细胞的发育过程进行限定,从而训练出覆盖孔洞的免疫细胞,进而解决孔洞问题.受此启发,本文提出一种基于免疫MHC的否定选择算法——孔洞修复方法MHC-NSA.首先以训练样本生成的维诺图(Voronoi)对形态空间进行划分,利用维诺图的最邻近特性,在维诺图中两类点处快速生成两类检测器,以较小训练代价达到对非自体空间较好的覆盖;其次模拟MHC针对孔洞所具有的特殊形态,对所产生的孔洞位置进行定位,并限定该位置生成孔洞修复检测器,从而提升孔洞修复效果.理论分析表明,MHC-NSA所生成的孔洞修复检测器可将孔洞最高占比降低62.8%,且MHC-NSA的时间复杂度由传统NSA算法的指数阶降低到多项式阶.在UCI数据集Balance Scale上的实验表明,MHC-NSA的检测器训练时间较典型NSA算法代表RNSA,V-Detector和BIORV-NSA在分别降低53.73%,96.43%和92.66%的同时,检测率分别提升69.57%,44%和17.54%.

The negative selection algorithm(NSA)is the key algorithm of the artificial immune system.The hole is an important factor that causes low detection rates of NSAs.Traditional NSAs do not consider hole distribution.To eliminate holes,detectors are randomly generated in the feature space;however,this approach is ineffective,and eliminating invalid detectors is also time consuming.The hole problem also exists in the biological immune system,in which the MHC molecules are used to handle the hole problem.Inspired by the function of MHC,a hole improvement method,namely,the MHC-NSA method,is proposed.First,the feature space is divided by Voronoi,and two types of detectors are generated at two points in Voronoi.Second,the hole improvement detectors are directly generated at the holes by positioning the holes.Theoretical analysis shows that the hole improvement detectors can reduce the highest percentage of holes by 62.8%.Moreover,relative to traditional NSAs,the time complexity of MHC-NSA decreases from the exponential level to the polynomial level.Experiments on the UCI dataset show that compared with RNSA,V-Detector,and BIORV-NSA,the training time of MHC-NSA is reduced by 53.73%,96.43%,and 92.66%and the detection rate of MHC-NSA increases by 69.57%,44%,and 17.54%,respectively.