否定选择算法

文章编号:1007-4929(2006)01-0034-03基于免疫系统的生态水利黄　尧1,仇　蕾1,苏奕绿2(1.河海大学商学院,江苏南京210098;2.广东省飞来峡水利枢纽管理局,广东清远511825) 摘　要:从人与自然和谐相处、人类社会可持续发展的理念和人体免疫学的角度探讨生态水利系统管理理论和方法的有关内容,包括生态水利的免疫系统分析及其网络模型构造,生态水利安全的预警系统及其指标体系、反馈机制、实现途径等,并对生态水利建设的远景目标和实现途径进行了探讨。

关键词:免疫;生态水利;模型构造;预警系统;指标体系 中图分类号:T V213 文献标识码:AEcological Hydraulic Engineering Base on Immune systemHUANG Yao1,QIU Lei1,SU Yi-lu2(mercial colleg e,H ohai Unive rsity,N anjing210098,China;2.F eilaixia Wa te r Conser vancy M anagement Bureau of G uang do ng Pr ovince,Qing yuan511825,China)A bstract:F rom the point of har monious relation be tw een mankind and natural,sustainable dev elo pment of society and immunolog y, this paper studied management theo ry and method fo r eco lo gical hy dr aulic enginee ring,including analy sis o f immunity sy stem of eco-log ical hy dr aulic eng ineering and its netwo rk model co nstr uction,early-alarm sy stem and its index sy stem,feedback mechanism a nd realiza tion route fo r the safety of eco log ical hydraulic engineering.A lso,the future g oal and its realiza tion route w ere discussed in the paper.Key word:immunity;ecolog ical hy dr aulic eng ineering;mo del co nst ruc tion;ear ly-alarm sy stem;inde x system 我国水利正处在从工程水利到资源水利和生态水利的转变,随着人们认识水平的提高和对生态问题重视程度的加强,生态水利逐渐深入人心。

一种优化黑洞覆盖的阴性选择算法傅龙天;徐戈;陈滕林【摘要】引入集成学习算法,采用可变匹配阀值策略,从训练样本来源、自体耐受学习过程、匹配规则等三个方面进行改进,提出了一个E-NSA模型.仿真实验证明本模型提高了检测率,优化了黑洞覆盖空间,并具备较强的自适应能力.【期刊名称】《哈尔滨师范大学自然科学学报》【年(卷),期】2015(031)001【总页数】4页(P41-44)【关键词】阴性选择算法;人工免疫;集成学习【作者】傅龙天;徐戈;陈滕林【作者单位】闽江学院;闽江学院;闽江学院【正文语种】中文【中图分类】TP30 引言丹麦学者Jeme［1］在1974年提出了一个人工免疫模型，Forrest等［2-3］后来提出了阴性选择算法和计算机免疫学概念，从此推动了计算机免疫学的全面发展，例如Lee等［4-5］学者利用免疫学原理实现计算机病毒检测．虽然人工免疫原理在各个领域获得很大的成功，但本身仍然存在一些不足之处，例如自体耐受过程在初始阶段学习不充分，匹配规则采用固定阀值导致黑洞问题等．Watkins和Timmis［6］对阴性选择算法(Negative Selection Algorithm)进行了并行性改造，增强了算法的并行能力;舒才良等［7］提出了在数据不完备情况下的改进算法，引入了分类器融合投票决策思想;翟宏群等［8］利用模糊思想，采用最优搜索原理对降低黑洞数量起了一定的作用;伍海波［9］通过改进成熟检测器的生成机制及改变匹配阀值，来解决成熟检测器生成效率低和容易产生黑洞问题．上述学者的各种改进措施都起到了一定的效果，但多数只考虑了问题局部，未做全局考虑，例如黑洞的产生根源不只是匹配阀值的问题，还和训练样本来源有关系．该文首先扩展训练样本来源;其次在自体耐受学习中过程引入集成学习中的Stacking算法;匹配规则调整为可变阀值．通过三个方面的改进来提高检测精度，优化黑洞覆盖空间．1 阴性选择算法及其分析自然界的生物经过进化大部分形成了天然的免疫机制，当抗原第一次入侵免疫系统时，生物体产生应激反应作出第一次应答，并学习完成自体耐受过程，产生免疫记忆;当抗原再次入侵时激发二次应答，识别该抗原［10］．这种学习防御机制引入计算机领域后，形成了人工免疫识别系统(AIRS)，阴性选择算法是其核心算法之一，算法描述如下:步骤1:从系统自动随机生成初始化训练样本，形成初始的未成熟检测器，当未成熟检测器与自体集中的样本匹配，如果匹配成功则淘汰，否则存活，形成若干成熟检测器．步骤2:经过步骤1的多次重复迭代，生成数量足够的成熟检测器．步骤3:利用步骤2获得的成熟检测器检测待检样本，采用r-连续位匹配规则检测待检样本，如果匹配成功，则认为识别了该待检样本．阴性选择算法从诞生到现在成功地应用到了各行各业，取得了良好的效果，但也暴露出了其不足之处，主要表现在三个方面:首先训练样本较少时生成的成熟检测器也较少，这对检测精度有很大的影响，只有在成熟检测器越来越多的情况下，检测精度才令人满意;其次未成熟检测器的来源是随机生成的，训练样本不够典型，代表性不强，这样将不可避免地产生黑洞;再次阴性选择算法采用r-连续位(r-contiguousbits)匹配规则，匹配阀值固定不变，这也是产生黑洞的重要原因．该文针对阴性选择算法的不足提出一个改进模型E-NSA，即在训练学习过程引入集成学习(Ensemble Learning)算法的Stacking算法，改善自体耐受学习过程;扩展训练样本来源，把非自体抗原加入到训练样本中，使训练样本更具代表性;把原算法的固定匹配阀值改成阀值可变，使得匹配过程更灵活，降低黑洞数量．2 改进模型E-NSA2．1 模型定义Stacking算法分为两层［11］，第一层首先构造多个弱分类器，产生一个与原数据集大小相同的新数据集，用这个新数据集和一个新算法构成第二层的强分类器，然后融合．该文把自体集和非自体集作为训练样本，其形式化定义如下所示:定义1 训练样本数据集D(其中包含了自体集和非自体抗原集中的数据样本)，作为多分类器融合算法的输入，描述如下所示:D={(x(1)，y(1))，(x(2)，y(2))，…，(x(N)，y(N)}其中N为样本的数量定义2 构造Stacking算法的第一层弱分类器h1，表示第t个不同的分类器，用于对训练样本数据集D进行预测分类．其中Lt函数表示通过训练样本集D的学习得到第t个分类器ht，描述如下所示:定义3 构造矩阵Zit为Nxt的矩阵，用于计算样本x(i)对于分类器ht的分类结果，该结果可以是样本x(i)属于分类ht的概率，描述如下所示:定义4 构造一个新数据集D'，通过定义3的循环迭代计算，可获得样本x(i)对于分类器ht的预测结果，数据集D'用于记录预测结果，描述如下所示:定义5 构造Stacking算法的第二层强分类器h'，即利用数据集D'形成新的分类器，用于融合弱分类器的预测结果，描述如下所示:定义6 分类器融合，即利用第二层的强分类器h'，对第一层分类器的预测结果再进行一次的预测分类，即分类器融合，描述如下所示:定义7 匹配度，设I是长度为L的二进制字符，P和Q是长度相等的二进制字符串，描述如下所示:其中MatchRate(P，Q)表示P和Q的匹配程度，Len(Pi，Qj)表示P在Q上相应位置上匹配的长度，Len(P)表示字符串 P的长度，当MatchRate(P，Q)的值为1是，表示P和Q完全相等，即完全匹配．定义8 连续匹配度con_MatchRate(P，Q)，函数max(Len(Pi，Qj))表示字符串P在字符串Q上相应位置连续匹配的最大长度，描述如下所示:定义9 字符匹配函数，Match(P，Q)表示两字符串P和Q的匹配操作函数，其中r表示匹配阀值，描述如下所示:当匹配函数Match(P，Q)为1时表示两个字符串匹配，在匹配操作过程中，匹配阀值r是可变的，当连续匹配度大于r/len(P)时，调整ri=ri-1+1．2．2 模型算法实现该模型由学习训练算法和匹配算法组成，学习算法引入Stacking算法用于改善耐受过程;匹配算法目的在于调整匹配阀值，实现灵活匹配降低黑洞数量．学习训练算法是阴性选择算法的重要组成部分，首先把自体集合非自体抗原集作为训练样本，根据式(1)循环t次构造分类器(弱分类器)，利用式(2)循环计算概率矩阵，即计算样本x(i)的分类结果;然后把分类结果构造成新的数据集D'，并构造新的分类器(强分类器);最后根据式(5)利用新构造的分类器进行融合，从而得到熟检测器．匹配算法采用自适应模糊策略，首先根据式(6)(7)计算匹配度和连续匹配度;再根据式(8)判断是否匹配．在实际应用中，出现连续匹配时(即循环执行本算法)，匹配阀值可自动调整，即当连续匹配度大于r/len(P)时，匹配阀值调整为ri=ri-1+1．3 仿真实验为了验证本模型的有效性，该文做了两组实验用于比较阴性选择算法和E-NSA模型的性能，并分析实验现象．3．1 实验环境使用IBM服务器X3650M4 7915i31作为实验机，主要配置:CPU为Intel至强E5-2600，内存 8GB，500GB硬盘，操作系统为 Microsoft Windows2003，云平台使用 Google Compute Engine，开发工具为Visual Studio2010．为了保证实验机纯净环境，除操作系统自带软件外，不再安装其他软件．该文选取美国哥伦比亚大学的数据测试集(2D Synthetic Data)［12］，从中选取2000 个病毒样本作为非自体抗原集合，1500个正常程序样本作为自体集合．从自体集合随机选取500个样本，从非自体抗原集合随机抽取500个样本，共同组成训练样本集合;从病毒样本中随机选取1500个，再从正常程序样本中随机选取1000个作为待检测样本集合．3．2 实验结果及分析为了得到真实可靠数据，进行了两组实验，每组实验进行50次，取平均值．第一组实验从训练样本集合中随机选取200个样本，用于比较阴性选择算法和E-NSA模型的检测率和误检率，实验结果如图1所示．从图1(a)可以看出该文提出的E-NSA模型相对阴性选择算法检测率更高，特别是在成熟检测器数量较少时检测率的差距较大．因为ENSA模型引入了Stacking算法，改善了学习过程，并且训练样本加入了非自体抗原，使得训练样本更具有代表性，提高了检测精度阴性选择算法的斜率，随着成熟检测器数量增加斜率减小程度越来越少，说明成熟检测器的数量对检测精度的影响很大，而E-NSA模型的检测精度对成熟检测器的数量的依赖明显更小，因为其斜率变化较小．从图1(b)可以看出E-NSA模型的误检率也相对低的多．图1 检测率和误检率比较图第二组实验从训练样本集合中随机选取200个样本，用于比较阴性选择算法和E-NSA模型的黑洞数量，实验结果如图2所示．图2 黑洞覆盖空间比较图从图2可以看出E-NSA模型相对阴性选择算法黑洞覆盖空间更高一些，这是因为E-NSA模型采用了可变匹配阀值，在获得成熟检测器和样本检测这个两个过程中都有明显的优势;另外E-NSA模型扩展了学习训练样本，生成的成熟检测器更具代表性，黑洞覆盖空间自然也更高．4 结语针对性阴性选择算法的不足提出了一个改进模型 E-AIRS，该模型引入集成学习的Stacking算法;扩展了训练样本来源，使训练样本更具代表性，改善了训练学习过程;采用可变匹配阀值，使得黑洞覆盖空间明显提高．通过仿真实验证明E-AIRS模型相对于阴性选择算法，具备检测精度较高、误检率较低、黑洞覆盖空间更高的优势;另外本模型对训练样本的要求较低(把自体集和非自体抗原集作为训练样本)更贴近现实，增加了进一步应用推广的可能性．参考文献［1］ Aydin I，Karakose M ，Akin E．An adaptive artificial immune system for fault classification ［J］．Journal of Intelligent Manufacturing，2012，23(5):1489-1499．［2］ Chang S Y，Yeh T Y．An artificial immune classifier for credit scoring analysis［J］．Applied Soft Computing，2012，12(2):611-618．［3］ Nicholas，W．，Pradeep，R．，Greg S．，Lundy，L．Artificial immune systems for the detection of credit card fraud:an architecture，prototype and preliminary results［J］．Information Systems Journal，2012，22(1):53-76．［4］ Binh L N，Huynh T L，Pang K K．Combating Mobile Spam through Botnet Detection using Artificial Immune Systems［J］．Journal ofUniversal Computer Science，2012，18(6):750-774．［5］ Samigulina G A．Development of decision support systems based on intellectual technology of artificial immune systems［J］．Automation and Remote Control，2012，73(2):397-403．［6］ Watkins A，Timmis J．Exploiting parallelism inherent in AIRS，an artificial immune classifier ［EB/0L］． (2012)［2012-01］．http://www．cs．kent．ac．uk/?abw5/．［7］舒才良，严宣辉，曾庆盛．不完备数据下的免疫分类算法［J］．计算机工程与应用，2012，48(20):172-176．［8］翟宏群，冯茂岩．一种改进的变阈值阴性选择免疫算法［J］．南京师范大学学报:工程技术版，2011，11(3):78-82．［9］伍海波．一种改进的否定选择算法在入侵检测中的应用［J］．计算机应用与软件，2013，30(2):174-176．［10］郭蓉，姜童子，黄葵．Aβ3-10s基因疫苗免疫AD小鼠诱导Th2型免疫反应的研究［J］．中风与神经疾病杂志，2013，30(5):112-118．［11］侯勇，郑雪峰．集成学习算法的研究与应用［J］．计算机工程与应用，2012，48(34):17-22．［12］程春玲，柴倩，徐小龙，熊婧夷．基于免疫协作的P2P网络病毒检测模型［J］．计算机科学，2011，38(10):60-63．。