（计算数学专业论文）基于人工免疫系统的否定选择算法改进相关研究.pdf

摘要 摘要 本文的研究课题是“基于人工免疫系统的否定选择算法改进相关研究”，课题 背景为四川省科技厅应用基础项目一智能入侵检测系统的关键技术研究。 否定选择算法( n e g a t i v es e l e c t i o na l g o r i t h m ，n s a ) 是将免疫学的理论应用到 计算机安全领域的奠基性算法，但是目前对它的研究却相对滞后。传统否定选择 算法在解决网络安全领域问题时存在搜索空间大，运行效率低的问题。本文在分 析其不足的基础上进行了一些改进：改随机生成初始检测器为分段生成初始检测 器；改连续r 位匹配方法为基于相似度的匹配方法。本论文的工作简要介绍如下： 1 介绍了人工免疫系统的研究现状，指出本文的研究意义； 2 介绍了人工免疫系统的生物学原理，阐明了生物免疫系统的重要免疫机制 及其特点； 3 对目前出现的人工免疫算法进行了较全面的介绍，总结出人工免疫算法的 一般框架并对框架进行了细致的阐述和介绍。 4 在分析n s a 相关算子不足的基础上，提出了一些改进方法，由此构造出 新型检测器生成算法n s a b c s s 。最后的仿真实验结果表明，新算法较原 算法有了明显的改进，因此是有效可行的。 关键词：生物免疫系统，人工免疫系统，否定选择算法，免疫算法 a b s t r a c t a b s t r a c t t h er e s e a r c hw o r ko ft h i s p a p e ri s “i m p r o v e m e n t sf o rn e g a t i v es e l e c t i o n a l g o r i t h mb a s e do na i s ”，t h eb a c k g r o u n di st h eb a s i ci t e m - t h ep i v o t a lt e c h n o l o g yo f i n t e l l i g e n td e t e c t i o ns y s t e mw h i c hi sb e l o n g e dt ot h es c i e n c ea n dt e c h n o l o g yb u r e a uo f s i c h u a np r o v i n c e n e g a t i v es e l e c t i o na l g o r i t h m ( n s a ) i st h ef o u n d a t i o n a la l g o r i t h mw h i c hh e l p st h e i m m u n et h e o r yt ob ea p p l i e di nc o m p u t e rs e c u r i t ya r e a , b u tr e c e n t l yw o r kf o rt h i s a l g o r i t h ml a g s t r a d i t i o n a ln s ah a sf a u l t s i nd e a l i n gw i t hp r o b l e m si nn e t w o r ks a f e t y a r e as u c ha sal a r g es e a r c hs p a c ea n dal o w e f f i c i e n c y , b a s e do n ad e e pa n a l y s i so nt h e s e f a u l t s ，w em a k es o m ei m p r o v e m e n t so n i t ：g e n e r a t i n gi n i t i a l d e t e c t o r sb a s e do n c h a r a c t e ro fs u b s e c t i o ni n s t e a do fr a n d o mm e t h o d ；u s i n gan e wm a t c hm e t h o db a s e do n s i m i l a r i t yi n s t e a do fm a t c hm e t h o db a s e do nc o m p a r i n gt w os t r i n g sf o rac o m m o n s u b s t r i n gw h i c hh a sm o r et h a nrb i t s w es u m m a r i z et h em a i nw o r ko ft h i sp a p e ra s f o l l o w s ： f i r s t , w ew i l lg i v eas u m m a r yo nt h ed e v e l o p m e n to fa i s ，t h e s t u d y i n g s i g n i f i c a n c eo ft h i sp a p e ri sa l s op u tf o r w a r d ； s e c o n d ，w ew i l ls e tf o r t ht h eb i o l o g i c a lp r i n c i p l eo fa i s ，s o m ei m p o r t a n ti m m u n e t r a i t sa n dt h ec h a r a c t e r so f b i o l o g i c a li m m u n es y s t e m ； t h i r d ，w ew i l li n t r o d u c ea l lt h ei m m u n e i n s p i r e da l g o r i t h m sw h i c hh a v eb e e n e x i s t e d ag e n e r a li m m u n ea l g o r i t h mf r a m ew i l lb e p u tf o r w a r d ；s o m ei n t e r p r e t a t i o na n d d i s c u s s i o nw i l lb eg i v e no ni t ； f o u r t h ，a f t e rad e e pa n a l y s i so nr e l a t e do p e r a t o ro f n s a , w eg i v es o m ea m e n d a t o r y s t e p s ，n s a b c s si sc o n s t r u c t e dt h e r e b y t h el a s ts i m u l a t i o ne x p e r i m e n t si n d i c a t et h a t t h ea m e n d a t o r ya l g o r i t h mh a so b v i o u si m p r o v e m e n t sc o m p a r i n gt ot h eo l do n e ，s oi t s e f f e c t i v ea n df e a s i b l e k e y w o r d s ：b i o l o g i c a li m m u n es y s t e m ，a r t i f i c i a li m m u n es y s t e m ，n e g a t i v es e l e c t i o n a l g o r i t h m ，i m m u n ea l g o r i t h m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书丽使用过的材料。 与我一同工作的同志对本研究所傲的任何贡献均己在论文中作了明 确的说臻并表示谢意。 签名：王卫氏日期：0 8 年中月z 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：王里氐 导师签名：i 竺筮盗 力矽 日期：力t 州妒年3 - 月f 护日 第一章绪论 第一章绪论 伴随着人类基因技术和医学的发展， 趣日趋浓厚。在漫长的人类进化过程中， 人们对生物学尤其是生命科学的研究兴 生命能够繁衍生息，适应外在不断变化 恶劣环境的能力引起人们的广泛关注。2 0 世纪后半页以来，人们在模拟生命现象 的过程中形成了三大关键技术：神经网络是对大脑信息处理机制的模拟，遗传算 法是对生物进化机制的模拟，免疫算法是对免疫机理的模拟。它们共同组成了智 能计算的核心技术【l 】。 目前对于神经系统和遗传系统已经得到了深入的研究，基于它们工作原理的 各种人工模型及其算法已经被广泛用于工程实践，产生了巨大的科研经济效益1 2 j 。 基于人工免疫系统的免疫算法是对建立在对生物体免疫机理的基础上的一种 新型智能方法，由于目前对生物体免疫机理的认识还不完善，目前出现的研究成 果还不是很多，还未能发展成为像遗传算法那样成熟的通用算法框架。免疫系统 的多种优良特性还有待应用于算法的设计和应用。与此同时，当前已有的免疫算 法的相关算子设计也还不够完善。因此，在人工免疫算法这一领域，还有着广泛 的发展前途和应用空间。 1 1 人工免疫的研究现状 从2 0 世纪5 0 年代末左右开始，国外开始了涉及人工免疫系统的研究。1 9 5 8 年，澳大利亚学者b u m e t 提出了著名的克隆选择学说并因此获得1 9 6 0 的诺贝尔奖。 1 9 7 4 年，丹麦学者j e m e 【3 4 】提出了免疫网络假说，开创了独特性网络理论，给出了 免疫网络的数学框架，随后p e r e l s o n 5 1 对该学说进行进一步阐述。1 9 8 6 年，f a r m e r 6 j 基于免疫网络的假说，构造了一个免疫系统的动态模型并与h o l a n d 的分类器进行 比较，提出了一些有价值的学习算法的构造思想，具有重要的意义。1 9 9 0 年，日 本学者i s h i d a 利用免疫系统解决传感器网络故障问题，成为目前已知的最早的免 疫系统在工程领域的研究成果 7 1 。1 9 9 4 年，美国学者f o r r e s t ，p e r e l s o n 等提出了著 名的否定选择算法【8 】，并首次将免疫用于计算机安全和病毒检测。同时，i b m 公司 也成功的开发了用于病毒防治的计算机免疫系统。1 9 9 7 年，d e a t o n 等提出了一种基 于分子的人工免疫系统【9 】。1 9 9 9 年，h u n t 进一步发展了克隆选择理论，提出了高 电子科技人学硕十学位论文 频变异学说。2 0 0 2 年，d ec a s t r o 和t i m m i s 对否定选择算法进行了改进，在算法 中引入了变异1 1 0 j 。 近年来，人工免疫系统( a r t i f i c i a li m m u n es y s t e m ，a i s ) 在国际上引起了广大研 究人员的普遍关注，成为继神经网络、遗传算法后的又一大研究热点。a i s 己成为 许多国际期刊的重要议题，如e v o l u t i o n a r yc o m p u t a t i o n i e e et r a n s a c t i o no n e v o l u t i o n a r yc o m p u t a t i o n 等，后者在2 0 0 1 年和2 0 0 2 年还相继出版了a i s 专辑。 在国际会议方面，从1 9 9 7 年开始，i e e es y s t e m ，m a na n dc y b e m e t i c s 国际会议每 年均组织专门的a i s 研讨会( w o r k s h o p ) ：其它国际会议如g e c c o ( g e n e t i ca n d e v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ) ，c e c ( c o n g r e s so ne v o l u t i o n a r yc o m p u t a t i o n ) 等也作为主题之一；而第一届人工免疫系统国际学术会议i c a r i s ( 1 s ti n t e r n a t i o n a l c o n f e r e n c eo na r t i f i c i a li m m u n es y s t e m s ) 也于2 0 0 2 年9 月在英国k e n t 大学召开。 从2 0 0 2 年起，人工免疫系统国际学术会议已经连续开了六届。 1 2 论文的研究意义 否定选择算法是人工免疫算法的一种，它的出现为将免疫学的理论应用于计 算机安全领域开辟了研究方向。 否定选择算法逻辑简单，又有不依赖于向非自体学习的优点，在入侵检测、 故障诊断方面可应用性较强。因此也吸引了很多学者的关注。人们在研究的过程 中提出了一些改进的措施【1 1 , 1 2 】。同时，也把这种算法带到了其他领域进行应用【1 3 , 1 4 】。 但与其他免疫算法相比，目前相关的研究成果还是很少。在深入分析否定选 择算法相关算子的基础上，我们发现一些算子设计上存在局限性。基于此，为了 提高否定选择算法的性能和应用前途，我们在否定选择算法的基础上提出了一些 改进方法，由此构造出了一种新型的检测器生成算法n s a b c s s ( n e g a t i v es e l e c t i o n a l g o r i t h mb a s e do i ls i m i l a r i t y ) 。通过仿真实验来验证了n s a b c s s 的算法性能。 1 3 论文的主要工作 本文首先介绍了人工免疫的发展过程及研究现状，接下来将介绍人工免疫系 统的生物学原理和人工免疫算法的研究。这些相关理论知识的介绍为我们后面的 研究内容做好理论上的支持。 在此之后进入论文的核心部分，在人工免疫算法中本文选择了将免疫学的理 2 第一章绪论 论应用于计算机安全领域的奠基性算法否定选择算法作为研究方向，通过对否定 选择算法一些算子的改进，构造出了一种基于否定选择的新型检测器生成算法 n s a b c s s 。基于k d d c u p 9 9 的仿真实验结果表明，n s a b c s s 在多方面较传统否定 选择算法有着明显的改善。 1 4 论文结构 第一章绪论。介绍了人工免疫的发展过程及研究现状，指出了论文的研究意 义，给出了论文的主要工作和论文的结构。 第二章人工免疫系统的生物学原理。本章将介绍人工免疫系统的理论基础 生物体免疫原理。通过这些内容的介绍有助于我们更好的理解人工免疫系统。 第三章人工免疫算法的研究。本章将全面介绍目前出现的各类人工免疫算 法，提出免疫算法的一般框架，并对免疫算法的框架进行介绍和分析。 第四章基于人工免疫系统的否定选择算法改进相关研究。本章提出了一种基 于否定选择原理的新型检测器生成算法n s a b c s s 。与原算法相比，在初始检测器 生成和否定选择匹配方法方面作了改进。k d d c u p 9 9 数据集上的仿真实验结果表明， n s a b c s s 的性能比n s a 有明显提高。 第五章论文总结及展望。对本文工作进行概括性的总结并指出进一步的研究 方向。 3 电子科技人学硕七学彼论文 第二章人工免疫系统的生物学原理 入工免疫系统主要是借鉴生物免疫系统的信息处理机制，发展新的算法，从 而为复杂问题的解决提供新思路。因此在研究基于人工免疫系统的免疫算法之前 了解一下人工免疫系统的理论基础一生物学免疫原理是徽有登要豹。本章首先将简 要阐述几个常用的免疫术语及其在在人工免疫系统中的含义，接着将介绍生物免 疫系统的免疫机制及其特点，并将人工免疫系统与生物免疫系统俸毖较，从中可 以唐观看到人工免疫系统与生物体免疫系统中元素的映射关系。 2 1 免疫学术语介绍 ( 1 抗原：一般攒麓刺激梳体免疫系统雩| 发免疫应答焉产生抗体和致敏漭巴缨 胞，并能与之发生特异性结合而产生免疫效应的物质。在人工免疫系统中，一般 指问题及其约束，与进化算法中适应度函数相似。 ( 2 ) 抗体：指免疫系统受到抗原刺激后，识别该抗原的b 细胞克隆扩增分化为 浆细胞所产生的一种爱自质分子，也称免疫球蛋白分子。在人工免疫系统中一般 指阀题的候选解，与进化算法中的个体相似，抗体的集合称为抗体群。在具体应 用中，一般抗体是以编码的形式出现的，常用的编码形式有二进制和十进制。比 如位串“0 。1 1 一l 一0 1 0 - 0 ”就可以代表一个抗体结构为，位二进铡数的抗体。 ( 3 ) 抗体一抗原的亲和力：抗体与抗原之间的结合能力。在人工免疫系统中对应 着候选解对西标函数值的适应性大小。 ( 4 ) 疫苗：是指根据进化环境或待求问题的先验知识，所得到对最佳个体基因 的估计。在实际应用中随着具体的问题的不同两不同，疫苗所包含的信息量和准 确性对问题的解决至关重要。 ( 5 ) 记忆单元：在人工免疫系统中，记忆单元是由特定抗体组成的抗体群，用 予保持抗体多样性，以及求解过程中的最优解。 ( 6 ) 克隆：生物的无性繁殖过程。在人工免疫系统中的克隆算子是基于克隆选 择学说，充分结合了选择、扩展、变异和交叉的综合算子。 ( 7 ) 免疫应答：是指免疫系统识别并消灭入侵机体的病原体的过程。在人工免 疫系统中表现为抗体识别外来入侵并加以清除的过程。 4 第二章人工免疫系统的生物学原理 2 2 免疫机制 免疫细胞从未成熟到成熟，识别杀死抗原后将形成免疫记忆，产生免疫反馈。 这就是免疫机制中三个重要阶段：自体耐受、免疫应答和免疫反馈。 2 2 1 自体耐受 免疫耐受( i m m u n o l o g i c a lt o l e r a n c e ) 是指：免疫活性细胞接触抗原性物质是表 现的一种特异性的无应答状态。 免疫系统中随机产生的受体由于体细胞的高频变异，能和自体结合，引起自 体免疫，自体免疫将导致免疫系统攻击自体。而实际上正常的免疫系统是不会攻 击自体的，对自体抗原不会产生应答。针对自身抗原呈现的免疫耐受称为自体耐 受( s e l f t o l e r a n c e ) 。自体耐受是对自体抗原不应答的一种免疫耐受，区分自体( s e l f ) 和非自体( n o n s e l f ) 是免疫系统的一个主要功能。 细胞发展过程中，两种主要的对立功能作用于免疫系统。第一种，产生足够 的、多样的免疫受体以识别变化广泛的外部抗原，第二种，必须避免对自体产生 应答，即自体耐受。 2 2 2 免疫应答 抗原进入机体以后，免疫细胞对抗原分子的识别、活化、分化和效应过程， 称为免疫应答( i m m u n er e s p o n s e ) 。 免疫应答分为：固有免疫应答( i n n a t ei m m u n er e s p o n s e ) 和适应免疫应答 ( a d a p t i v ei m m u n er e s p o n s e ) 。固有免疫应答不能在遇到特异性病原体时改变和应 答，在遇到病原体后迅速产生抵制作用，使得适应免疫应答有时间建立更加特异 的免疫应答。适应免疫应答能适应或学习以识别特异抗原，并对其保持记忆，以 便下次更加快速的应答。 按照抗原次序可以把适应免疫应答分为初次应答( p r i m a r yr e s p o n s e ) 和二次应 答( s e c o n d a r yr e s p o n s e ) 。初次应答发生在抗原初次进入机体，需要首先刺激有限的 特异性克隆扩增，才能达到足够的亲和力阈值，所以初次应答比较缓和；机体受 到相同的抗原刺激后，多数情况下会产生二次应答，二次应答有了初次应答的记 忆，所以反应更加迅速，无需重新学习。 免疫应答的产生、发展和最终效应是一个相当复杂，但又有规律的过程。一 电子科技人学硕十! 学位论文 般可以分为三个阶段：免疫细胞对抗原分子的识别过程，即抗原分子与免疫细胞 相互作用；免疫细胞的活化和分化过程，即免疫细胞之间的相互作用；效应细胞 和效应分子的排异作用，免疫效应细胞和抗原发挥作用，将抗原消灭并从体内清 除。 2 2 3 免疫反馈 当抗体产生以后，可不断与抗原结合并消灭抗原，最终所有入侵抗原被清除， 免疫应答中止。抗体对免疫应答具有反馈调节作用，抗体是免疫应答的产物，抗 体产生之后又可以抑制其后的抗体产生。 外来抗原入侵机体后，启动免疫应答，产生效应分子或效应细胞，来清除外 来抗原。在免疫应答后期，效应细胞抑制免疫应答，这对于维护免疫系统稳定性 具有重要作用。 在计算机免疫系统中，反馈是系统将信息输送出去，又将结果输送回来，并 对系统的再输出产生影响，从而起到控制和优化作用。免疫反馈的主要作用是应 付系统中存在的内部和外部的不确定性。如果系统实际运行的行为和期望的行为 存在偏差，反馈可以使系统动态行为的偏差逐渐减小。 2 3 生物免疫系统的特点【1 5 】 生物免疫系统有效保护自身不受外部有害物质的侵害，在抵御各种病毒、细 菌的过程中表现出种种精妙复杂的免疫机能，现对免疫系统的特点总结如下： ( 1 ) 识别：免疫系统能够识别大量不同的抗原模式，并对其进行响应。除此之 外，免疫系统还能够区分自我和非我细胞，以维持自身机体的平衡。 ( 2 ) 特征提取：在抗原被提交给淋巴细胞之前，免疫系统能够通过抗原提呈细 胞提取出抗原的特征。 ( 3 ) 多样性：在免疫系统中有产生和维持多样性的两个主要过程。第一个过程 是通过基因库中的基因片段的再结合产生受体因子。通过对有限的基因片断重组， 免疫系统能够产生几乎无限的形式多样的受体，这样能够为免疫系统提供较大的 抗原覆盖空间。第二个过程，称为体细胞高频变异，免疫细胞响应入侵抗原时进 行自身的再生，再生过程中，它们以较高的频率进行体细胞变异，并且生成特异 模式的受体分子，这样能够增加免疫受体的多样性。 ( 4 ) 学习：体细胞高频变异后要经历一个选择过程，此过程也使得免疫系统能 6 第二章人： 免疫系统的生物学原理 够较好的调整其对入侵抗原的响应。该过程又称为亲和力成熟。亲和力成熟过程 能够保证免疫系统更快、更好地执行模式识别的任务。免疫网络理论是免疫系统 具有学习能力的另外一个有力的例子。免疫网络理论指出：免疫系统有一个由相 互识别的细胞和分子组成的动态组合，入侵抗原的出现引起了免疫网络的扰动， 结果，在入侵抗原出现之前内部表现为稳定状态的免疫网络必须重新自阻止它的 行为模式，以适应扰动。因此，入侵抗原要求免疫网络调整自身以适应这个新元 素。 ( 5 ) 记忆：在对给定的抗原响应之后，一些细胞和分子集合将被给予迅速增加 的生存周期，以便将来同一或类似的抗原再次入侵时提供更快、更有力的免疫响 应，这个过程称为免疫响应的成熟过程，能够使得这些细胞和分子成功地维护对 抗原的快速识别能力。 ( 6 ) 分布式检测：在免疫系统内部有一个固有的分布状态，没有一个集中控制 点：每一个免疫细胞都能够在任何位置受到入侵机体的新抗原的刺激，并对其进 行响应。 ( 7 ) 自调整：免疫系统动力学指出免疫系统是通过其内部的细胞和分子相互作 用来控制的，而不是通过某个中心控制点来控制的。当病毒成功地被消灭掉以后， 免疫系统将恢复其正常的稳定状态，直到又有抗原进行入侵。免疫网络理论清楚 地分析了这种自调整机制。 2 4 生物免疫系统与人工免疫系统的比较 人工免疫系统是模仿生物免疫系统的一种智能方法，它将生物免疫系统的组 成元素映射成解决普通工程问题的对应原型，力图通过模仿生物免疫系统的免疫 机理来为实际中遇到的工程难题寻求一条解决的途径。人工免疫系统的出现为我 们处理工程问题提供了一种新的选择。 下面给出人工免疫系统与生物免疫系统的一个近似映射关系，从中可以发现 人工免疫系统对生物免疫系统的模仿和借鉴。 7 电子科技人学硕十学位论文 表2 - 1 生物免疫系统与人j j ：免疫系统的映射关系 生物免疫系统人工免疫系统 抗原 抗体 抗原、抗体的绑定 亲和力 抗体的浓度抑制 克隆扩增 自体耐受 免疫应答 工程应用问题 问题的候选解 模式匹配 模式匹配的程度 消除冗余解 通过交叉、变异算子对优解 进行变化产生新解 否定选择算法 识别外部入侵数据并加以清除 2 5 本章总结 本章介绍了人工免疫系统的理论基础一生物学的免疫原理。本章首先解释了 一些免疫学常用术语，然后深入讨论了免疫学的核心机n - 自体耐受、免疫应答 和免疫反馈。这些机制是给予研究人员启发最多的一些机制，是人工免疫系统的 理论基础。随后，本章总结出生物体免疫系统的基本特点，通过这些特点可以看 出免疫体系统工作的精妙性和复杂性，这些特点是人工免疫系统应该借鉴和模仿 的。最后，给出了一张人工免疫系统与生物免疫系统的映射图表，从中可以直观 发现人工免疫系统与生物免疫系统元素的映射关系。 8 第三章人：i i 免疫算法的研究现状 第三章人工免疫算法的研究现状 受生物免疫系统启发而产生的人工免疫系统给人工免疫算法准备了深厚的理 论基础，研究人员在长期的工程应用研究中，将人工免疫系统的理论运用于各种 科学计算任务，设计出了多种算法，这里统称之为人工免疫算法。本章节首先将 对目前现有的人工免疫算法进行介绍，然后总结出入工免疫算法的基本框架并对 其进行分析，阐明免疫算法的运行原理。 3 1 人工免疫算法的研究与发展 人工免疫算法在长期的发展中形成了多种形式各异的算法，为了更好的描述 算法的发展状况，本章将免疫算法加以分类。四川大学李涛教授在计算机免疫 学中提出可以将免疫算法大致分类为基于群体的免疫算法和基于网络的免疫算 法【1 6 l ，前者构成的系统中的元素之问没有直接的联系，系统组成元素直接和系统 环境相互作用。后者构成的系统中部分或者全体的系统元素能够相互作用。 基于群体的免疫算法的代表是否定选择算法、肯定选择算法、克隆选择算法。 3 1 1 基于群体的免疫算法 3 1 1 1 否定选择算法 生物免疫系统保护生物体组织不受外来病毒的入侵，并清除病变的细胞和坏 死的细胞残骸。为了实现这些功能，首先必须知道如何区分自我和非我，通过杀 死那些对自我产生应答的细胞来实现对自体的保护，那些通过选择的免疫细胞则 成为成熟的免疫细胞，从而实现对自体的耐受。 否定选择算法对这一生物免疫过程进行了模拟，随机生成的检测器要通过与 自我集( 这里的自我集随着具体应用的不同而不同) 进行匹配，如果能够产生匹配， 即相当于生物体细胞的应答，则应被丢弃，因为这样的检测器会对自体细胞造成 伤害。如果该检测器对于自我集中的所有元素不匹配，则通过否定选择而成为合 格的成熟检测器，即相当于免疫细胞通过自体耐受称为成熟免疫细胞。算法的框 图如图3 一l 所示。 9 电子科技人学硕士学位论文 图3 1 否定选择算法 2 0 0 2 年，c a s t r o 和t i m m i s 对其进行了修改，将变异引入其中。当未成熟检测 器匹配了自体集时，不是删除该检测器，而是对其进行有导向性的变异，使之远 离自体。 3 1 1 2 肯定选择算法 肯定选择算法与否定选择算法非常相似，作用则刚好相反，保留与自我集匹 配的检测器，清除与自我集不匹配的检测器。 算法框图如图3 - 2 所示。 图3 2 肯定选择算法 由于否定选择算法和肯定选择算法都是以自我集为参照物，通过自我的变化 来发现异常的发生，所以适用于那些未知环境下故障诊断和计算机安全检测等情 况。 3 1 1 3 克隆选择算法【1 7 1 b u m e t 等根据生物学和遗传学的发展，特别是免疫学自身的发展如自身免疫、 1 0 第三章人：免疫算法的研究现状 免疫耐受等现象的启示下，提出了著名的克隆选择学说。该学说中心思想有以下 几点： ( 1 ) 体内本身存在有识别各种抗原的免疫细胞克隆，它们的识别作用通过细胞 表面的受体完成。 ( 2 ) 抗原选择结合相应受体的免疫细胞，使之活化、分化和增殖，最后形成抗 体，产生效应细胞和记忆细胞。 ( 3 ) 胎生期免疫细胞与抗原物质相接触，则可被破坏、排除或使之失活，处于 抑制状态。由于失去对抗原的应答能力，形成了天然耐受状态，此种受抑的细胞 克隆，称为禁忌细胞克隆。 ( 4 ) 免疫细胞克隆可因突变产生与自身抗原起反应的细胞克隆，形成自身免疫 疾病【1 引。 克隆选择是生物体免疫系统自适应抗原刺激的动态过程，在这一过程中，所 体现出来的学习、记忆、抗体多样性等生物特性，是人工免疫系统所应该借鉴的。 模仿生物体的克隆选择原理而产生的克隆选择算法的代表是d ec a s t r o 等在 2 0 0 0 年提出的克隆选择算法( c s a ) 。具体算法如下【1 9 】： ( 1 ) 生成候选解集p ，p 是由记忆单元( m ) 和保留种群( ) 组成，即： p = e + m ：根据亲合度测量，选择，1 个个体( e ) ： ( 2 ) 复制( 克隆) 种群中这n 个最好的个体，生成一个克隆临时种群( c ) ，克隆规 模和抗体一抗原的亲合度成正比； ( 3 ) 对克隆临时种群进行高频变异，这里高频变异和抗体一抗原的亲合度相对 应，由此获得了一个变异后的抗体群( c ) ： ( 4 ) 从c + 中重新选择改进的个体组成记忆单元m 。p 中一些个体也被c 中其 他改进的个体所取代。 ( 5 ) 利用新产生的抗体代替d 个旧抗体( 引入多样性) 。亲合度低的抗体容易被 取代。 该算法的框图如图3 3 所示。 电子科技人学硕十学何论文 图3 - 3 克隆选择算法( c s a ) 与遗传算法相比较，克隆选择算法首先将基于概率的轮赌法改变为基于抗体一 抗原亲合力的比例选择；其次，构造了记忆单元，从而将遗传算法记忆单个最优 个体改变为记忆一个最优解的群体；最后，通过新旧抗体的替换，增加了种群的 多样性。 k i m 等在h o f i n e y r 的基础上提出了一种动态克隆选择算法d y n a m i c s ，应用于 解决连续变化环境中的异常检测问题 2 0 1 。d y n a m i c s 试图提取使得系统产生适应性 的关键变量。 3 1 2 基于网络的免疫算法 基于网络的免疫算法一般是指基于免疫网络学说建立的人工免疫网络学习算 法。根据j e r n e 的独特性学说理论，免疫细胞和分子除能识别外来入侵抗原之外， 还能够相互识别。因此，免疫细胞一方面能够因识别抗原或免疫细胞而被激活， 另一方面又因被其他的免疫细胞识别而被抑制。免疫细胞的受激程度可用下式表 示 s2 虬一叱+ 4 ( 3 一1 ) 1 2 第三章人：l ：免疫算法的研究现状 其中，虬代表网络刺激，m 。代表网络抑制，4 代表抗原刺激，免疫细胞的受激 程度决定了它的再生率和变异率。 目前比较有影响的是t i m m i s 在2 0 0 0 年提出的r a i n ( r e s o u r c el i m i t e da r t i f i c i a l i m m u n en e t w o r k ) 算法和d ec a s t r o 与v o nz u b e n 的a i n e t ( a r t i f i c i a li m m u n e n e t w o r k ) ，建立在这两个免疫网络学习算法之上的免疫网路模型r l a i s 和a i n e t 也是目前最有影响的免疫网络模型。 这里先以r a i n 作例子来介绍免疫网络学习算法的基本原理，接下来介绍一 下r l a i s 和a i n e t 免疫网络模型。 3 1 2 1r a i n 免疫网络算法【2 l 】 t i m m i s 把每一个网络元素类比于一个b 细胞，而该网络元素不仅仅只是一个 抗体，它还同时包括了该抗体的受激程度及其拥有的网络资源数量记录。 免疫网络从输入的抗原中选取一个子集作为初始的网络细胞，将所有抗原模 式与每一个网络细胞进行比较，按公式( 3 - 2 ) 计算出该网络细胞的受激程度；根据 受激程度来分配网络资源，受激程度大的细胞进行克隆扩增，同时对所有的网络 细胞进行与受激程度成反比的变异，选择变异后的克隆细胞重组网络，这个过程 不断重复，直到迭代次数完成或者免疫网络趋向一个稳定区。公式( 3 2 ) 如下： i i ，“ 置= ( 1 - o , ，) + ( 1 - d i ，。) 一口，。 ( 3 2 ) ，；i 七= l七= i 其中，m 为抗原数量，以为相连的b 细胞数量，口，为抗原，和b 细胞f 之问 e u c l i d e a n 距离，口。为b 细胞f 和与之相连的b 细胞k 之间的e u c l i d e a n 距离。 3 1 2 2r l a s i 网络模型2 2 】 1 9 9 5 年，h u n t 和c o o k e 在j e m e 模型的基础上提出了一个用于机器学习的工 程免疫模型，这是一个由b 细胞组成的用于d n a 分类的网络。实验抗原是d n a 序列。通过免疫网络学习算法的训练，该模型能够较好的检测出训练模式，且具 有一定的自组织性。 t i m m i s 在2 0 0 0 年对该模型进行了改进，提出了一种更为通用的模型，这就是 资源受限人工免疫系统( r l a i s ) 。t i m m i s 认为免疫网络是由一些识别球( a r b ) 及 其联系构成。每个识别球通过受激水平竞争资源( 这里的资源是b 细胞) ，不能获得 资源的a r b 将被淘汰。 a r b 的受激水平由下式计算： 电子科技人学硕十学1 j i 7 = 论文 墨= ( 1 - d , ，) + ( 1 - d ，。) 一( 口，。) ( 3 3 ) j = t k = ik = l 式中，脚是a r b 所接触的抗原的数量，n 是互相连接的b 细胞数目。口i 表 示抗原和抗体之间的几何距离；口。表示联系的b 细胞问的几何距离。 免疫网络模型的训练类似于前面的r a i n 算法，只不过网络细胞变成a r b 。具 体说来，免疫网络的a r b 通过与训练集中的抗原进行匹配计算其受激水平，以此 为标准来分配资源( b 细胞) ，这个过程中受激较低的a r b 将被清除；然后对高受 激水平的a r b 进行复制扩张和进行与受激水平成反比的变异复制；最后选取与网 络中a r b 亲和力小的a r b 进入网络进行重构。多次重复该训练过程直到网络趋 向稳定。 3 1 2 3a i n e t 网络模型【2 3 ，2 4 】 受独特性免疫调节网络的启发，d ec a s t r o 在2 0 0 0 年构造了一种免疫网络算法 a i n e t 。 与r l a i s 不同，a i n e t 的初始网络细胞是随机生成的抗体集，而r l a i s 的初始 a r b 集合则是抗原的随机子集。在算法的迭代过程中，a i n e t 把抗体网络依次呈现 给单个抗原，历经克隆、细胞超变异、选择和免疫抑制生成对单个抗原的记忆抗 体集，当全部抗原提呈完毕后，组合所有的抗体集m 和上一代的记忆抗体集m 生 成当代记忆抗体集m ，再根据网络抑制对m 进行削减。算法在预先设定的条件下 结束：可以是完成了迭代步数，可以是网络中细胞达到规定的数目，也可以是抗 原和m 间的误差达到规定的精度。 3 1 3 免疫进化算法 与前面介绍的基于群体的和基于网络的免疫算法不同，免疫进化算法是将进 化算法理论与免疫原理综合起来考虑的一种新型算法。它是在传统进化算法的基 础上，引入了免疫系统的免疫特性，发展起来的一种新型优化算法。 以遗传算法为代表的进化算法采用交叉和变异算子实现群体和群体中个体的 信息交换，在进化算法的迭代过程中不难发现，上述两个遗传算子都是在一定发 生概率的条件下，随机地、没有指导的实现的。因此，它们在为群体中的个体提 供进化机会的同时，也无可避免地产生了退化( 早熟和多样性下降) 的可能。在某 些情况下，这种退化还相当明显。另一方面，每一个待求的实际问题都会有自身 的一些基本的、显而易见的特征信息或知识。然而遗传算法的交叉和变异算子却 1 4 第三章人j ：免疫算法的研究现状 相对固定，再求解问题时，可变的灵活性小。显然有效地利用这部分信息给算法 带来效率上的提高。 进化算法的不足和人工免疫系统的特点给构造新的算法指明了出路。由此诞 生的新的算法就是我们这里所称的免疫进化算法。目前这方面的算法已经很多， 主要包括：引入疫苗接种理论的免疫优化算法【2 5 1 、引入自我调节机制的免疫算法 【2 6 】、基于免疫抗体记忆的免疫算法【2 7 】、基于免疫应答的免疫优化算法【2 8 】等。 本章以西安电子科技大学王磊1 2 5 】的博士论文为参考，介绍免疫进化算法的代 表性算法，包括免疫算法、免疫策略和免疫规划。 3 1 3 1 免疫算法 免疫进化算法在进化算法理论框架的基础上引入了一个新的算子一免疫算子 ( i m m u n eo p e r a t o r ) ，对于免疫算法来说，这里的免疫算子是指接种疫苗和免疫选 择。接种疫苗是为了提高种群适应度，免疫选择是为了防止群体的退化。具体说 来，它们分别是： 接种疫苗：设个体x ，给其接种疫苗是指按照先验知识来修改x 的某些基因位 上的基因或其分量，使所得个体以较大的概率具有更高的适应度。这一操作应该 满足如下两点：第一，若个体y 的每一基因位上的信息都是错误的，即每一位码都 与最佳个体不同，则对任一个体工，x 转移为y 的概率为o ；第二，若个体工的每 个基因位都是正确的，即x 已经是最佳个体，则x 以概率l 转移为工。设有群体 c = ( 玉，x 2 ，h ) ，对c 接种疫苗是指在c 中按比例口随机抽取r a = a n 个个体而进行 的操作。疫苗是从对问题的先验知识中提炼出来的，它所包含的信息量及其准确 性对算法的性能起着重要的作用。 免疫选择：这一操作一般分两步完成。第一步是免疫检测，即对接种了疫苗 的个体进行检测，若其适应度仍不如父代，说明在交叉、变异的过程中出现了严 重的退化现象。这时，该个体被父代中所对应的个体所取代；第二步是退火选择， 即在目前的子代群体邑= ( ，x 2 ，吒) 中以概率： 题型 p p ( x ) 2 丢( 3 - 4 ) 艺e 五 i = l 选择个体薯进入新的父代群体，其中厂( 蕾) 为个体再的适应度， 互) 为趋近于0 的 温度控制序列。需要指出的是在免疫策略中，免疫选择仅指免疫检测而没有退火 电子科技大学硕十学位论文 选择。 免疫算法的框图如图( 3 4 ) 。以下给出免疫算法的基本步骤： ( 1 ) 随机产生初始父代种群4 ： ( 2 ) 根据先验知识抽取疫苗； ( 3 ) 若当前群体中包含最佳个体，则算法停止运行并输出结果；否则继续； ( 4 ) 对于目前的第七代父本种群4 进行交叉操作，得到种群色： ( 5 ) 对色进行变异操作，得到种群c ； ( 6 ) 对q 进行接种疫苗操作，得到种群q ： ( 7 ) 对4 进行免疫选择操作，得到新一代父本4 转步骤( 3 ) 。 3 1 3 2 免疫规划 免疫规划在进化算法的基础上引入了免疫的概念和方法，是为了从理论上探 讨在处理疑难问题是利用局部特征信息寻找全局最优解的可行性与有效性。具体 来说，新算法利用局部特征信息以一定的强度干预全局并行的搜索进程，抑制或 避免求解过程中的一些重复和无效的工作，以克服原进化规划算法中变异操作的 盲目性。在具体操作上，免疫规划通过对问题的分析获得疫苗，借助疫苗接种和 免疫选择两个步骤来构造免疫规划算法，免疫算子的构造与前面的免疫算法是一 样的。 与免疫算法不同的是，子代种群眈= ( j ，d 2 ，d ) 中个体d 进入新的父代群 体的概率是 f ( d 掣 删。2 聂瘤 o 。5 厂( d 掣 式中，互是单调递减趋于o 的退火温度控制序列。 免疫规划的框图如图( 3 5 ) 所示。 免疫规划的执行步骤： ( 1 ) 初始化：首先，根据要求确定解的精度。由于固有的计算误差，我们不能 要求最大值点，就是理论上的最大值点，故设要求的误差精度为1 0 ：其次，在 中随机产生个个体。这些个体的每一分量均为，位小数，并由此构成初始的父代 种群4 i ： ( 2 ) 根据先验知识抽取疫苗h ； 1 6 第三章人：i j 免疫算法的研究现状 图3 4 免嫒算法 ( 3 ) 计算当前第k 代父本种群4 所有个体的适应度，并进行停机条件的判断。 若条件满足，则停止运行并输出结果；否则继续； ( 4 ) 对当前的父代群体4 进行变异操作，生成子代群体反。设 4 = ( 口1 ，口2 ，a ) ，a qcr “，i = l ，2 ，n 。对个体a 进行变异按式( 3 6 ) 产生新 的个体b 6 ；= 衫+ 彰，歹= l ，2 ，刀 ( 3 - 6 ) 式中，彰为不超过随机变量矿n ( o ，岛) 的最大，位小数，方差露根据下式进行计 算 岛= 篇 ( 3 7 ) 式中，瓦即为退火选择中所用到的序列，而_ r v o 应充分大，以保证在搜索初期使 所有的个体都有较大的进化机会；m ，和m ，的取值与q 的形状与大小有关，并且 m ，0 。另外，对群体进行变异操作指的是对群体中的每一个个体均进行变异。 ( 5 ) 对群体或进行接种疫苗操作，得到种群q ： 屯子科技人学硕十学位论文 ( 6 ) 对群体g 进行免疫选择操作，得到新一代父本4 并转至第( 3 ) 步。 图3 - 5 免疫规划算法流程图 3 1 3 3 免疫策略 同免疫进化对进化算法的改进一样，免疫策略是在进化策略的基