（电路与系统专业论文）基于人工免疫网络的分类算法及其应用.pdf

摘要 摘要 人工免疫网络算法是基于免疫学原理特别是独特型免疫网络原理提出的应用 于智能计算领域的奠基性算法。然而目前不少人工免疫网络分类算法都或多或少 的存在一些缺陷，其一是算法机制的问题：网络规模庞大、计算复杂、对抗原采 用一次递呈，这些导致了算法运行效率低；其二是应用领域比较窄，多数集中于 标准数据的分类与聚类。 基于此，针对复杂数据分类与图像处理问题，本文分别提出了一种新的人工 免疫网络分类算法、基于自适应p s o 的人工免疫网络分类算法以及基于人工免疫 网络的关联规则挖掘算法，具体研究工作如下： 1 提出了一种新的人工免疫网络分类算法。该算法利用每个类别对应单个 b 细胞的策略，简化网络规模并减少了同类别b 细胞之间的抑制操作， 同时引入了新的基于对训练样本正确识别率的亲合度评价函数，实现了 基于抗原的优先级的选择策略。实验结果表明，该算法在分类精度上具 有一定的优势，鲁棒性更好。 2 提出了基于自适应p s o 的人工免疫网络分类算法。该方法将自适应权值 的p s o 算法引入到人工免疫网络算法的变异算子中，同时采用各个b 细 胞包含抗原( 即训练样本) 所有类别的信息的策略。使得该算法具有良好的 全局搜索能力以及快速的收敛速度。 3 提出了基于人工免疫网络的关联规则挖掘算法。该方法将数据挖掘中的 关联规则引入人工免疫网络算法中，用寻找最优关联规则来替代最佳聚 类中心。对比实验表明，该方法在处理多类别以及名词性( n o m i n a l ) 特征 数据时具有令人满意的分类精度和收敛速度。 本课题得到国家自然科学基金( n o 6 0 8 0 3 0 9 8 ) ，国家教育部博士点基金 ( n o 2 0 0 7 0 7 0 1 0 2 2 ) 的资助。 关键词：人工免疫系统独特型免疫网络人工免疫网络分类图像 a b s t r a c t i i i a b s t r a c t a r t i f i c i a li m m u n en e t w o r k ( a i n ) a l g o r i t h mi 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 h i sb a s e do ni m l t l u l l et h e o r ya n de s p e c i a lt h ei d i o t y p i ci m m u n en e t w o r k ( i r n ) t h e o r y a n da i nh a sb e e na p p l i e di n t ot h ef i e l do fi n t e l l i g e n tc o m p u t i n g h o w e v e r , t h e r ea r e s o m es h o r t c o m i n g si nt h em o s te x i s t i n ga i nc l a s s i f i c a t i o na l g o r i t h m s o nt h eo n eh a n d ， t h es h o r t c o m i n g sl i ei nt h em e c h a n i s mo fa l g o r i t h ms u c ha sl a r g e - s c a l en e t w o r k , c o m p l e xc o m p u t a t i o n ，a n do n l yo n c ep r e s e n t i n gt h ea n t i g e n s ，w h i c hr e s u l t e di nt h e p r o b l e mo fl o we f f i c i e n c y o nt h eo t h e rh a n d ，t h e yl i ei nt h en a r r o wa p p l i c a t i o n s ，m o s t a i n a l g o r i t h m sf o c u so nt h es t a n d a r dd a t a s e t sc l a s s i f i c a t i o na n dc l u s t e r i n g a f t e ra n a l y z i n ga b o v ep r o b l e m sa n da i mt os o l v ec o m p l e xd a t ac l a s s i f i c a t i o na n d i m a g ec l a s s i f i c a t i o np r o b l e m s ，t h r e ea i n c l a s s i f i c a t i o na l g o r i t h m sa r ep r o p o s e di nt h i s p a p e r , t h em a i nw o r kc a nb eo u t l i n e da sf o l l o w s ： ( 1 ) an e w a r t i f i c i a li m m u n en e t w o r kc l a s s i f i c a t i o na l g o r i t h mi sp r o p o s e d i nt h e p r o p o s e da l g o r i t h m ，o n l yo n eb c e l li su s e dt od e n o t es i n g l ec l a s si no r d e rt or e d u c e t h es c a l eo fn e t w o r k ，a n da v o i dt h es u p p r e s s i o no p e r a t i o nb e t w e e nb c e l l s ，m o r e o v e r , a n e wa f f i n i t yf u n c t i o nb a s e do nt h ec o r r e c tr a t ei sp r o p o s e dt or e a l i z et h ee v a l u a t i o n s t r a t e g yb a s e do na n t i g e np r i o r i t y t h er e s u l t so fe x p e r i m e n t si n d i c a t et h a tt h en e w a l g o r i t h mh a sb e r e ra c c u r a c ya n dr o b u s t n e s s ( 2 ) as e l f - a d a p t i v ep s ob a s e da r t i f i c i a li m m u n en e t w o r kc l a s s i f i c a t i o na l g o r i t h m i sp r o p o s e d t 1 1 i sm e t h o da p p l i e st h es e l f - a d a p t i v ep s oi n t ot h em u t a t i o np r o c e s so f t h ea r t i f i c i a li m m u n en e t w o r ka l g o r i t h m m o r e o v e r ，t h es t r a t e g yo fe v e r yb c e l l c o n t a i n i n ga l lt y p e so fi n f o r m a t i o nf o ra n t i g e n si su s e di nt h ep r o p o s e da l g o r i t h m s o t h en e w a l g o r i t h mh a sg o o dg l o b a ls e a r c ha b i l i t ya n df a s tc o n v e r g e n c es p e e d ( 3 ) a na s s o c i a t er u l e sm i n i n ga l g o r i t h mb a s e do na r t i f i c i a li m m u n en e t w o r ki s p r o p o s e d t l l i sm e t h o di n t r o d u c e st h ea s s o c i a t i o nr u l e su s e di nt h ed a t am i n i n gi n t ot h e a r t i f i c i a li m m u n en e t w o r ka l g o r i t h m a n di tu s e sr e s e a r c h i n gt h eo p t i m a la s s o c i a t i o n r u l e st or e p l a c ef i n d i n gt h eb e s tc l u s t e rc e n t e r c o m p a r a t i v ee x p e r i m e n t ss h o wt h a tt h e m e t h o dh a ss a t i s f a c t o r yc l a s s i f i c a t i o na c c u r a c ya n dc o n v e r g e n c es p e e di nd e a l i n gw i m m u l t i c l a s sa n dn o m i n a la t t r i b u t e sd a t a t h i s p a p e rw a ss u p p o r t e db yt h e n a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n ( n o 6 0 8 0 3 0 9 8 ) a n db yt h en a t i o n a lr e s e a r c hf o u n d a t i o nf o rt h ed o c t o r a lp r o g r a mo f h i g h e re d u c a t i o no fc h i n au n d e rg r a n tn o 2 0 0 7 0 7 010 2 2 k e y w o r d s ：a r t i f i c i a li m m u n es y s t e mi d i o t y p i ci m m u n en e t w o r ka r t i f i c i a l i v 基于人工免疫网络的分类算法及其应用 i m m u n en e t w o r kc l a s s i f i c a t i o n i m a g e 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期塑生f ：生 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表的论文与本论文工作成果有关时署名单位仍然为西安电子科技大 学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文 的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的 论文在解密后遵守此规定)， 本人授权西安电子科技大学图书馆保存学位论文，并同意将论文在互联网上 发布。 本人签名：垣! 刍壹 导师签名：童：l 孟应 日期竺丝：! ! = 日期趁 q ：f ：坦 第一章绪论 第一章绪论 从二十世纪后半页末n - 十一世纪初，随着人类基因技术和医学的发展，人 们对生物学尤其是生命科学的研究兴趣日渐浓厚。在地球漫长的生物进化史中， 生物能够繁衍生息，适应外界环境变迁的能力引起了人们的研究兴趣。生物体存 在四大信息处理系统：神经系统( b r a i nn e r v o u ss y s t e m s ) 、遗传系统( g e n e t i c s y s t e m s ) 、免疫系统( i m m u n es y s t e m s ) 和内分泌系统( e n d o c r i n es y s t e m s ) 。人 们在模拟生命现象的前三大处理系统的过程中，慢慢地形成了三大智能计算核心 技术：人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 算法，遗传算法( g e n e t i c a l g o r i t h m ，g a ) 和免疫算法( i m m u n ea l g o r i t h m ，i a ) 。 众所周知，目前对神经网络系统和遗传系统的研究已经相当成熟，人们在它 们的基础上设计了各种模型以及算法，并将它们广泛应用到工程实践中，从而产 生了巨大的科研经济效益。而基于人工免疫系统的免疫算法是建立在生物免疫机 理基础上的一种新型计算智能方法。由于目前对生物免疫机理的认识还不完善， 因此人工免疫系统算法还未能发展成为像遗传算法那样的通用算法框架。免疫系 统的多种优良特性还有待应用于人工免疫系统算法的设计与应用。与此同时，当 前免疫进化算法的相关算子的设计还不够完善。因此在人工免疫算法领域的发展 和应用空间是相当广阔的【l j 。 1 1 人工免疫系统的研究现状 从2 0 世纪5 0 年代末开始，人们并开始了对人工免疫系统的研究。b u m e t 于 1 9 5 8 年提出了著名克隆选择学说，他因此获得了1 9 6 0 的诺贝尔奖。1 9 7 4 年， j e r n e 2 , 3 j 提出了免疫网络学说，开创了独特性网络理论，给出了免疫网络的数学框 架。随后p e r e l s o n t 4 1 对该学说作出了更深入的阐述。1 9 8 6 年f 黜e r 【5 】构建了一个 免疫系统的动态模型，提出了一些有价值的学习算法。1 9 9 0 年，日本学者i s h i d a 利用免疫系统解决传感器网络故障问题，成为已知的首个工程领域研究成果| 6 1 。 目前在人工免疫系统领域占主导地位的是克隆选择学说和免疫网络学说。细胞克 隆选择学说的要点是外来抗原选择出原先处于静止状态的互补细胞克隆，被选择 细胞克隆的激活、增殖和效应功能是免疫应答的细胞学过程，而针对自身抗原的 细胞克隆则被抑制或消除，因而对外来抗原的识别是关键的因素。免疫网络学说 的观点是建立在自身识别上，认为免疫系统淋巴细胞上分布的特异性抗原受体可 变区) 组成内网络，通过免疫细胞相互识别v 区上的抗原决定簇来实现免疫系 统的功能；对外来抗原的应答，是建立在识别自身抗原基础上的反应。 目前为止，人工免疫系统对免疫网络的仿生成果很多，主要集中在计算机网 2 基于人工免疫网络的分类算法及其应用 络安全应用领域，将人工免疫网络模型引入到数据挖掘领域是近年来的研究热点。 h u n t 和c o o k e 提出了一种称为c o o k e 网络的人工免疫系统网络【_ ，并将其应用于 d n a 序列的模式识别，后来该模型被成功用于欺诈检测系统j i s y s 的开发【8 】。t a n g 等人提出了多值免疫网络模型( m u l t i p l e v a l u e di m m u n en e t w o r k ，m v i n ) t 9 1 ，它的 主要思想是用一种多值特征集合的学习机制来模拟b 细胞和t 细胞之间的相互反 应和调节作用并使用特征集合来分类输入的数据。与一般的人工免疫网络模型不 同，该模型不仅模拟了b 细胞而且加入了t 细胞的辅助和抑制作用。d ec a s t r o 等 人提出使用演化的免疫网络来实现数据分析【l 们，该方法模拟生物免疫系统中抗体 克隆和选择的过程，将数据集作为抗原集合，生成的抗体集合则作为数据聚类结 果。仿真实验发现，该算法在聚类分析阶段难以确定簇的数量，甚至在已知簇的 数量的情况下也可能偏离正确的聚类中心。但是该算法能够极大地减少数据冗余， 且生成的抗体集合能够反映数据集的结构特征。2 0 0 1 年，他们又提出a i n e t 模型 【l ，a i n e t 与h u n t - c o o k e 最大的不同在于：a i n e t 没有考虑刺激的概念，而只有亲 和度的概念，a i n e t 的训练过程，一部分由克隆选择驱动，另一部分用抗体的相互 作用来移除冗余，以发现数据模式。t i m m i s 和n e a l 提出资源有限的人工免疫系 统( r e s o u r c el i m i t e da r t i f i c i a li m m u n es y s t e m ，r l a i s ) t 1 2 j ，此模型引入了人工识别 球( a r t i f i c i a lr e c o g n i t i o nb a l l ，a r b ) 的概念。r l a i s 利用人工识别球来代表分类细 胞，所有的a r b s 基于它们受激励程度进行竞争。a r b 受激励的程度越高，它就 能代表越多的b 细胞，当某个a r b 不能代表任何一个b 细胞时，它将会从网络 中删除。r l a i s 能很好的控制种群的规模，后来w a t l d n s 和t i m m i s 对此算法作 了一系列的改进l l 孓”】。n e a l 等人在r l a i s 的基础上提出了自稳定人工免疫系统 ( s e l f - s t a b i l i z i n ga r t i f i c i a li m m u n es y s t e m ，s s a i s ) 1 1 6 j ，用于时变数据的连续分析， 其与r l a i s 的主要区别在于此模型并没有给出一个资源限制水平，并且每个a r b 能够控制其自身水平的资源( 分散控制) 。另外，s s a i s 模型计算刺激水平时， 不考虑b 细胞间的抑制。超稳态记忆免疫网络( m e t a - s t a b l em e m o r yi m m u n e n e t w o r k ，m s m i n ) 是沿用a i n e 的思想【1 7 1 ，对s s a i s 的改进，用于数据分析、 聚类和人工免疫记忆。2 0 0 2 年n a s r a o u i 提出基于r l a i s 的模糊人工免疫系统【l 引， 用于聚类、网页特征描述和网络挖掘。近几年来，人工免疫系统方面的研究已经 成为热点，相关会议和期刊收录文章的持续增加【1 9 琊】，也证明了这一点。 1 2 论文的研究意义 人工免疫网络算法是人工免疫系统算法的一种，它的出现为将免疫学的理论 应用于复杂问题( 大规模的数据挖掘、s a r 图像分类、纹理图像分类以及遥感图 像的目标识别等) 开辟了研究方向。 第一章绪论 至今人工免疫网络算法研究成果很多，其中至今被同领域专家最为关注的是 t a n g 的多值免疫网络，d ec a s t r o 的进化人工免疫网络( a i n e t ) 幽j 和t i m m i s 的资源 受限人工免疫系统( r l a i s ) ，这三类不同的免疫网络算法有其各自的优势，然而， 不可避免的它们也有其各自不同的局限性，r l a i s 性能依赖网络b 细胞的数目的 选择，当选择的b 细胞太多会导致网络太庞大，没有代表性；当资源过少时，又 会导致某些模式不能被识别。a i n e t 中需设置过多的参数，另外对抗原的一次提呈 可以获得局部最优抗体但并不能保证获得全局最优网络。钟燕飞等人在文献【2 5 2 6 1 中将t a n g 的多值免疫网络应用到多光谱遥感影像的分类中。该方法计算复杂度比 较低，而且抗体的形成也比较新颖，具有一定的实用价值，然而因为该方法是直 接读取多光谱遥感影像的灰度信息，所以分类精度不是很高而且推广能力不强。 基于此，为了提高人工免疫网络的性能和应用前途，我们在人工免疫算法的基础 上提出了一些改进方法，提出了一些新的基于人工免疫网络的分类算法。并通过 实验来验证它们的性能。 1 3 论文的主要工作 本文首先介绍了人工免疫系统的发展过程及研究现状，接下来将介绍人工免 疫系统的生物学原理和部分人工免疫系统算法。这些相关理论知识的介绍为我们 后面的研究做好理论上的支持。 在此之后进入论文的核心部分，在人工免疫算法中本文选择了人工免疫网络 算法作为研究方向。通过发现现有人工免疫网络算法中存在的不足，并对部分算 子或者网络机制作了部分调整，提出了三种新的基于人工免疫网络的分类算法。 基于复杂数据、s a r 图像、纹理图像以及遥感图像的实验结果表明，新算法具有 一定的实际应用价值。 1 4 论文结构安排 第一章绪论。介绍了人工免疫系统的发展过程及研究现状，指出了论文的研 究意义，给出了论文的主要工作和论文的结构。 第二章详细介绍人工免疫系统的生物学原理及算法研究。本章将介绍人工免 疫系统以及独特性免疫网络的理论基础一生物免疫原理。通过这些内容的介绍有 助于我们更好的理解人工免疫网络。最后介绍了人工免疫网络的相关算法。 第三章提出一种新的人工免疫网络分类算法。本章提出了一种新的基于人工 免疫网络的分类算法( an e wa r t i f i c i a li m m u n en e t w o r kc l a s s i f i c a t i o na l g o r i t h m ， a i n c ) 。采用了5 组u c i 的连续数据和4 组混合特征数据以及3 幅s a r 图像对 4 基于人工免疫网络的分类算法及其应用 算法的性能进行了全面测试，结果表明，与模糊c 均值算法( f u z z yc m e a n s ，f c m ) 、 多值免疫算法( m u l t i p l e v a l u e di m m u n en e t w o r ka l g o r i t h m ，m v r n ) 和克隆选择算法 ( c l o n a ls e l e c t i o na l g o r i t h m ，c s a ) 相比，新算法在分类精度上具有一定的优势。 第四章基于自适应p s o 的人工免疫网络分类算法。本章归纳与总结前一章 算法的基础上提出了一种基于自适应p s o 的人工免疫网络分类算法( a r t i f i c i a l i m m u n en e t w o r kc l a s s i f i c a t i o na l g o r i t h mb a s e do ns e l f - a d a p t i v ep s o ，s p a i n c ) 。采 用了4 组u c i 的标准数据、两幅纹理图像、3 幅s a r 图像以及一组遥感图像集对 算法的性能进行了全面测试，结果表明，与基于普通变异的人工免疫网络分类算 法( a r t i f i c i a li m m u n en e t w o r kc l a s s i f i c a t i o na l g o r i t h m ，a i n c ) 相比，s p a i n c 在分 类精度与收敛速度上都具有一定的优势；而它的分类精度同样优于基于p s o 变异 的人工免疫网络分类算法( a r t i f i c i a li m m u n en e t w o r kc l a s s i f i c a t i o na l g o r i t h mb a s e d o np s o ，p s o a i n c ) 。 第五章一种基于人工免疫网络的关联规则挖掘算法。本章在总结上一章算法 不足的基础上提出了一种基于人工免疫网络的关联规则挖掘算法( a na s s o c i a t e r u l e sm i n i n ga l g o r i t h mb a s e do na r t i f i c i a li m m u n en e t w o 咄a i n a r m ) 。采用了4 组 u c i 的大规模数据、一组遥感图像集和3 幅s a r 图像对算法的性能进行了全面测 试，结果表明，与基于自适应p s o 的人工免疫网络分类算法相比，新算法很好的 解决了基于自适应p s o 的人工免疫网络分类算法中出现的难以处理多类别以及 类别属性为名词性( n o m i n a l ) 特征的分类问题。 第六章总结与展望。对本文工作进行概括性的总结与展望。 第二章人工免疫系统的生物学原理及算法研究 第二章人工免疫系统的生物学原理及算法研究 自然免疫系统是人工免疫系统的生物学源泉。人工免疫系统的发展是建立在 人类对自然免疫系统的认识和研究基础上的。因此在研究基于人工免疫系统的免 疫算法之前有必要了解一下人工免疫系统的理论基础一生物学免疫原理。本章的 安排如下：首先将简要介绍几个常用的免疫术语1 及其它们在人工免疫系统中的 含义，接着将介绍生物免疫系统的免疫机制及其特点，并将免疫算法与生物免疫 系统作比较，反应出它们的内在关系，最后将介绍人工免疫系统的相关算法。 2 1 免疫学术语介绍 ( 1 ) 抗原：一般指能刺激机体免疫系统引发免疫应答而产生抗体和致敏淋巴细 胞，并能与之发生特异性结合而产生免疫效应的物质。在人工免疫系统中，一般 指问题及其约束或者是训练样本。 ( 2 ) 抗体：指在免疫系统受到抗原刺激后，识别该抗原的b 细胞克隆变异分化 为浆细胞所产生的一种蛋白质分子，也称免疫球蛋白分子。在人工免疫系统中一 般指问题的候选解，抗体的集合称为抗体群。在具体应用中，一般抗体是以编码 的形式出现的，常用的编码形式有十进制和二进制。比如位串“0 0 1 1 0 1 0 1 ” 就可以用来表示一个抗体结构为八位二进制数的抗体。 ( 3 ) 抗体抗原的亲和力：抗体与抗原之间的结合能力。在人工免疫系统中对应 着候选解对目标函数值的适应性大小，即适应度值。 ( 4 ) 疫苗：是指根据进化环境或待求问题的先验知识，所得到对最佳个体基因 的估计。在实际应用中随着具体的问题的不同而不同，疫苗所包含的信息量和准 确性对问题的解决至关重要。 ( 5 ) 记忆细胞：记忆细胞由两种方式得到：体液免疫中的b 细胞分化产生浆细 胞和记忆细胞；细胞免疫中，t 细胞增殖分化产生效应t 细胞和记忆细胞。记忆 细胞的作用是在下一次抗原入侵时快速增殖分化产生抗体杀灭抗原。在人工 免疫系统中，记忆细胞是由特定抗体组成的抗体群，用于保持抗体多样性，以及 求解过程中的最优解。 ( 6 ) 克隆：生物的无性繁殖过程。在人工免疫系统中的克隆算子是基于克隆选 择学说，充分结合了选择、扩展、变异和交叉的综合算子。 ( 7 ) 免疫应答：是指免疫系统识别并消灭入侵机体的病原体的过程。在人工免 疫系统中表现为抗体识别外来入侵并加以清除的过程。 6基于人工免疫网络的分类算法及其应用 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 ) 1 2 刀；另一种就是适应性免疫 系统产生的适应性免疫应答( a d a p t i v ei m m u n er e s p o n s e ) 2 8 j 。固有免疫应答不能在 遇到特异性病原体时改变的应答，在遇到病原体后迅速产生抵制作用，使得适应 免疫应答有时间建立更加特异的免疫应答。适应免疫应答又称为抗原特异性免疫 应答( a n t i g e n - s p e c i f i ci m m u n er e s p o n s e ) 2 9 1 ，它能适应或学 - j 以识别特异抗原，并 对其保持记忆，以便下次更加快速的应答。 按照抗原次序可以把适应免疫应答分为初次应答( 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 ) 。初次应答发生在抗原初次进入机体，需要首先刺激有限 的特异性克隆扩增，才能达到足够的亲和力阈值，所以初次应答比较缓和；机体 受到相同的抗原刺激后，多数情况下会产生二次应答，二次应答有了初次应答的 记忆，所以反应更加迅速，无需重新学习。 免疫应答的产生、发展和最终效应是一个相当复杂，但又有规律的过程。一 般可以分为三个阶段：免疫细胞对抗原分子的识别过程，即抗原分子与免疫细胞 相互作用；免疫细胞的活化和分化过程，即免疫细胞之间的相互作用；效应细胞 和效应分子的排异作用，免疫效应细胞和抗原发挥作用，将抗原消灭并从体内清 除。 第二章人工免疫系统的生物学原理及算法研究 7 2 2 3 免疫反馈 当抗体产生以后，可不断与抗原结合并消灭抗原，最终所有入侵抗原被清除， 免疫应答中止。抗体对免疫应答具有反馈调节作用，抗体是免疫应答的产物，抗 体产生之后又可以抑制其后的抗体产生。 外来抗原入侵机体后，启动免疫应答，产生效应分子或效应细胞，来清除外 来抗原。在免疫应答后期，效应细胞抑制免疫应答，这对于维护免疫系统稳定性 具有重要作用。 在计算机免疫系统中，反馈是系统将信息输送出去，又将结果输送回来，并 对系统的再输出产生影响，从而起到控制和优化作用。免疫反馈的主要作用是应 付系统中存在的内部和外部的不确定性。如果系统实际运行的行为和期望的行为 存在偏差，反馈可以使系统动态行为的偏差逐渐减小。 2 3 生物免疫系统与人工免疫系统的关系 免疫计算智能研究在人工免疫系统( a r t i f i c i a li m m u l l es y s t e m ，趾s ) 研究中是 最为广泛和活跃的研究内容。根据免疫学理论划分，现有免疫计算智能主要有基 于独特型免疫网络理论的算法、基于阴性选择的算法和基于克隆选择的算法，以 及与其他计算智能混合三种形式。具体到某一算法，所依据的免疫机制都是其中 一种机制，或者几种机制结合在一个算法或模型中。 人工免疫系统将生物免疫系统的组成元素映射成解决普通工程问题的对应原型， 力图通过模仿生物免疫系统的免疫机理来为实际中遇到的工程难题寻求一条解决 的途径。人工免疫系统的出现为我们处理工程中复杂问题提供了一种新的选择。 表2 1 生物免疫系统与一般免疫算法的映射关系 生物免疫系统免疫算法 抗原 抗体 抗原识别 亲和力 抗体间的浓度抑制 克隆增殖 免疫应答 要解决的问题 最优候选解 确定问题类型 模式匹配的程度 冗余解的删除 对优解通过复制，交叉，变异产生新解 识别外部入侵数据并清除 表2 1 给出一般人免疫算法与生物免疫系统的一个近似映射关系，从中可以 基于人工免疫阿络的分类算法及其麻片i 发现人工免疫系统对生物免疫系统的模仿和借箍 ”i 。 2 4 人工免疫网络 人工免疫网络是人工免疫系统的一个分支，它是一种新的智能计算方法。1 9 7 4 年j e m e 继b e m e t 的克隆选择学说后提出免疫系统内部调节的独特型( i d i o t y p e ) 和抗独特型( a n t i i d i o t y p e ) 的独特型免疫网络理论。这一方面的研究工作使他于 1 9 8 4 年获得诺贝尔奖。独特型免疫网络理论认为在抗原刺激发生之前，机体处于 一种相对的免疫稳定状态，当抗原进入机体后打破丁这种平衡，导致了特异抗体 分子的产生，当达到一定量时将引起抗免疫求蛋白分子独特型的免疫应咎，即抗 独特型抗体的产生。因此抗体分子在识别抗原的同时，也能被其它抗独特型抗体 分子所识别。这一点无论对血液中的抗体分子或是存在于淋巴细胞表面作为抗原 受体的免疫球蛋白( i g ) 分予都是样的。在同一动物体内一组抗体分子上独特型 决定簇可被另一组抗独特型抗体分予所识别。而一组淋巴细胞表面抗原受体分子 亦可被另一组淋巴细胞表面抗独特型抗体分子所识别。这样在体内就形成了淋巴 细胞与抗体分子所组成的网络结构。网络学说认为，这种抗独特型抗体的产生在 免疫应答调节中起着重要作用。使抗体刺激增殖的克隆受到抑制而不至于无休 止地进行增殖，藉以维持免疫应答的稳定平衡【“啦】。简化的j e m e 免疫网络结构 如图2 1 所示。 图21 简化的免疫网络结构示意图 从图中可以清楚地看出机体的免疫网络主要由淋巴细胞构成：第一组为抗 原反应细胞( a r c ) ，它可通过其抗原受体对外来抗原起反应，网络正是以该细胞 为主体并与另外三组淋巴细胞构成的：第二组为独特型反应细胞( i r c ) 或独特型组 ( 1 d i o l y p es e t ) ，它能识别a r c 上的独特型决定麟，从而抑制a r c 对外来抗原起 反戍；第二三维为内部影像组( i n t e r n a li m a g es e t ) ，其抗原受体上的独特型与外来抗 第二章人工免疫系统的生物学原理及算法研究 9 原相同，故能被a r c 识别，并激发a r c 增殖；第四组为非特异性平行组 ( n o n - s p e c i f i cp a r a l l e ls e 0 ，其抗原结合的特异性与a r c 不同，但其抗原受体上的 独特型( i d ) 与a r c 上的i d 相同，故能被i r c 识别，从而间接抑制a r c 的增殖， 加强对网络的抑制作用。二、三、四组淋巴细胞也可以各自成为主体，再分别与 另外三组淋巴细胞结合而构成网络，如此下去，在体内形成一种网络系统。 2 5 人工免疫系统算法 目前在人工免疫系统中占主导地位的是克隆选择算法和人工免疫网络算法。 本节将对这两种算法作一些简单的介绍。 2 5 1 克隆选择算法 b u r n e r 等根据生物学发展，特别是免疫学自身的发展如自身免疫、免疫耐受 等现象的启示下，提出了著名的克隆选择学说。该学说认为，当抗原侵入生物体 内时，其免疫系统能在机体内选择出识别和消灭相应抗原的抗体，主要借助克隆 ( 无性繁殖) 使之激活、分化和增殖，以增加该抗体的数量，通过进行免疫应答最 终清除抗原。外来抗原与成熟淋巴细胞表面的抗原受体发生特异性结合，识别抗 原的特异性淋巴细胞的克隆迅速扩增，对机体的保护性功能起放大功效，并有效 地再循环和归巢到抗原入侵和存留的部位，产生效应清除抗原。它的中心思想包 括以下几点： ( 1 ) 体内本身存在有识别各种抗原的免疫细胞克隆，它们的识别作用通过细胞 表面的受体完成。 ( 2 ) 抗原选择结合相应受体的免疫细胞，使之活化、分化和增殖，最后形成抗 体，产生效应细胞和记忆细胞。 ( 3 ) 胎生期免疫细胞与抗原物质相接触，则可被破坏、排除或使之失活，处于 抑制状态。由于失去对抗原的应答能力，形成了天然耐受状态，此种受抑的细胞 克隆，称为禁忌细胞克隆。 ( 4 ) 免疫细胞克隆可因突变产生与自身抗原起反应的细胞克隆，形成自身免疫 疾病。 克隆选择是生物体免疫系统在受到抗原入侵后，表现出的自适应抗原刺激的 动态过程，而人工免疫系统借鉴正是这一过程中，所体现出来的学习、记忆、抗 体多样性等生物特性。 模仿生物体的克隆选择原理而产生的克隆选择算法的代表是d e c a s t r o 等，他 们在2 0 0 0 年提出的著名的克隆选择算法( c s a ) 。具体算法如下【3 3 】： ( 1 ) 根据相关条件产生候选解集尸； l o 基于人工免疫网络的分类算法及其应用 ( 2 ) 复制( 克隆) 种群p 中刀个最好的个体( 记为厶) ，生成一个克隆临时种群( c ) ， 克隆规模跟抗体、抗原的亲合度值成正比； ( 3 ) 对克隆临时种群进行高频变异，这里的变异概率和抗体一抗原的亲合度相 关，变异后得到群体( c ) ； ( 4 ) 从c 中重新选择一部分优秀的个体( 即亲和度最高个体) 添加到p 中， 同时死亡一部分亲和度低的个体； ( 5 ) 利用新产生的抗体乃代替d 个旧抗体( 引入多样性) 。亲合度低的抗体容易 被取代。 该算法的大致流程图如图2 2 所示。 作为一种全局优化搜索算法，克隆选择算法在算法实现上兼顾全局搜索和局 部搜索，并构造记忆单元，将遗传算法的记忆单个最优个体变为记忆一个最优解 的群体。最后，通过新旧抗体的替换，增加了种群的多样性。 2 2 克隆选择算法( c s a ) 流程图 2 5 2 人工免疫网络相关算法 根据j e m e 的独特性免疫网络理论，免疫细胞和分子除能识别外来抗原之外， 第二章人工免疫系统的生物学原理及算法研究l l 还能够相互识别。因此免疫细胞一方面能够因识别抗原或免疫细胞而被激活，另 一方面又因被其他的免疫细胞识别而被抑制。免疫细胞的受激励程度可用下式表 示 s = 虬一+ 4( 2 - 1 ) 其中，地代表网络激励，代表网络抑制，彳，代表抗原刺激，免疫细胞的受刺 激程度决定了它的克隆规模、变异概率以及存亡与否。 目前在人工免疫网络算法领域比较有影响的有t i m m i s 的资源有限的人工免 疫网络算法( r e s o u r c el i m i t e da r t i f i c i a li m m u n es y s t e m ，r l a i s ) ，d ec a s t r o 与v o n z u b e n 的进化人工免疫网络( a r t i f i c i a li m m u n en e t w o r k , a i n e t ) 和t a n g 的多值免疫 网络( m u l t i p l e - v a l u e di m m u n en e t w o r k , m v i n ) 。建立在这三个免疫网络学习算法 之上的免疫网络模型r l a i s 、a i n e t 和m v i n 也是目前最有影响的免疫网络模型。 下面将对这三种模型作简单的介绍。 r a i n 免疫网络算法 t i m m i s 【1 6 】把每一个网络元素类比于一个b 细胞，而该网络元素不仅仅只是一 个抗体，它还同时包括了该抗体的受激程度及其拥有的网络资源数量记录。 免疫网络从输入的抗原中选取一个子集作为初始的网络细胞，将所有抗原模 式与每一个网络细胞进行比较，按公式( 2 2 ) 计算出该网络细胞的受激程度；根据 受激程度来分配网络资源，受激程度大的细胞进行克隆扩增，同时对所有的网络 细胞进行与受激程度成反比的变异，选择变异后的克隆细胞重组网络，这个过程 不断重复，直到最大迭代次数或者免疫网络趋于稳定。公式( 2 2 ) 如下： m一行 岛= ( 1 - d , a ) + ( 1 - d i , k ) 一口。j i ( 2 2 ) j = l k = lk = l 其中，m 为抗原的数量，刀为相连的b 细胞数量，d ，为抗原和b 细胞f 之 间的距离，d j , k 为b 细胞f 和与之相连的b 细胞k 之间的距离。这里的距离测度 采用的是欧氏距离。 r l a s i 网络模型 1 9 9 5 年，h u n t 和c o o k e 在j e m e 免疫网络模型的基础上提出了一个用于机器 学习的工程免疫模型【i 川，这是一个由b 细胞组成的用于d n a 分类的网络。实验 抗原是d n a 序列。通过免疫网络学习算法的训练，该模型能够较好的检测出训 练模式，且具有一定的自组织性。 t i m m i s 在2 0 0 0 年对该模型进行了改进，提出了一种更为通用的模型，这就 1 2 基于人工免疫网络的分类算法及其应用 是资源有限的人工免疫系统( r l a i s ) 。t i m m i s 认为免疫网络是由一些识别球 ( a r a ) 及其它们之间的相互联系构成。每个识别球通过受激水平竞争资源( 这里的 资源是b 细胞) ，不能获得资源的a r b 将被淘汰。 a r b 的受激水平由公式( 2 3 ) 计算得到： 墨= ( 1 - d r a ) + ( 1 - d t 。) 一q ，。 ( 2 3 ) i = 1 k = ik = l 式中，m 是a r b 所接触的抗原的数量，r l 是互相连接的b 细胞数目。d o 表 示抗原和抗体之间的几何距离；d t 表示联系的b 细胞间的几何距离。,