（计算数学专业论文）二代人工免疫系统及其在垃圾邮件过滤中的应用.pdf

摘要 摘要 随着电子邮件日益广泛的使用，如何有效地避免和防范垃圾邮件的侵扰已成为 一个亟待解决的问题。由于传统垃圾邮件过滤技术存在对变异性较强的邮件动态 适应性弱和分类准确率低等缺点。受生物免疫系统自我保护机制的启发，研究人 员把人工免疫系统的相关算法应用于垃圾邮件过滤领域，取得一定研究成果，但 还是存在正确肯定率和正确否定率不能平衡和初始检测器生成太慢等缺点。 在人工免疫领域，2 0 0 2 年兴起的基于危险理论的相关算法在入侵检测中取得 了较为突出的成果，由于入侵检测和垃圾邮件过滤具有较大的相似性，所以本文 将危险理论的相关算法应用于垃圾邮件过滤，并对已有算法的缺陷作出改进。2 0 0 7 年兴起的二代人工免疫系统对提高人工免疫算法的准确率提供了重要的指导思 想。 本文以科技攻关项目( 项目编号：0 3 g g 0 0 6 0 2 1 ) 为研究基础。从第一代人工免 疫系统存在的缺点和现有垃圾邮件过滤技术的局限性出发，以树突状细胞算法为 主线，危险理论和二代人工免疫系统为理论基础，提出了基于二代人工免疫系统 的一个新算法( 带训练的树突状细胞算法) ，实现并成功应用于垃圾邮件过滤。该 算法还可用于其它需要分类的领域中，如文本挖掘、入侵检测、模式识别等。 本文主要完成了以下工作： 1 通过生成垃圾邮件的危险信号，把人工免疫学中危险理论最新研究成果树 突状细胞算法用于垃圾邮件过滤。 2 通过改进抗原生成方式、抗原提呈次序和抗原提呈次数，使得树突状细胞 算法具有更高的准确率。 3 把树突状细胞算法和传统人工免疫系统的克隆选择算法有机地组织在一 起，形成一个完整的基于二代人工免疫系统带训练的树突状细胞算法( t - d c a ) ， 进一步提高垃圾邮件过滤的准确率。 关键词：二代人工免疫系统，危险理论，树突状细胞算法，垃圾邮件过滤 a b s t r a ( 了r a bs t r a c t w i mt h ef o w m gu s eo fe m a i l ，i ti su r g e n tt or e s o l v et h es e v e r ep r o b l e mo fs p a i n t h et r a d i t i o n a la n t i s p a mt e c h n o l o g yh a sl o wc l a s s i f i c a t i o na c c u r a c yr a t ea n dh a sn o t d y n a m i ca d a p t i v e s o ，t h er e s e a r c h e r sp u tt h ee x i s t i n gi m m u n e i n s p i r e dt e c h n i q u e st o a n t i s p a mf i e l da n da c h i e v e dc e r t a i nr e s u l t s b u tt h et r u ep o s i t i v er a t ea n dt h et r u e n e g a t i v er a t ec a nn o tb a l a n c ew e l l a tt h ef i e l do fa r t i f i c i a li m m u n e , a l g o r i t h m sb a s e do nd a n g e rt h e o r yh a sb e e nm a d e m o r ep r o m i n e n tr e s u l t si nt h e2 0 0 2 b e c a u s eo fi n t r u s i o n d e t e c t i o na n ds p a r ef i l t e r i n g h a sm o r es i m i l a r i t y , t h i st h e s i sa p p l i e da l g o r i t h m sb a s e do nd a n g e rt h e o r yt os p a m f i l t e r i n ga n di m p r o v e dt h ea l g o r i t h m s i n2 0 0 7 ，t h er i s eo fs e c o n d - g e n e r a t i o na r t i f i c i a l i m m u n es y s t e mp r o v i d e sa l li m p o r t a n ti d e at oi m p r o v et h ea c c u r a c yo fa r t i f i c i a li m m u n e a l g o r i t h m t l l i st h e s i sb a s e do nt h es c i e n t i t l ea n dt e c h n o l o g i c a lp r o j e c t ( s e r i a ln u m b e ro ft h e p r o j e c t ：0 3 g g 0 0 6 0 21 ) f r o mt h e l i m i t a t i o n so ff i r s t g e n e r a t i o na r t i f i c i a li m m u n e s y s t e m sa n dt h ed i s a d v a n t a g eo fe x i s t i n gs p a mf i l t e r i n gt e c h n o l o g y , d e n d r i t i cc e l l a l g o r i t h ma st h em a i nl i n e d a n g e r o u st h e o r ya n ds e c o n d g e n e r a t i o na r t i f i c i a li m m u n e s y s t e ma st h et h e o r e t i c a lf o u n d a t i o n 。t h i st h e s i sp u tf o r w a r das e c o n dg e n e r a t i o n a r t i f i c l a li m m u n es y s t e mb a s e da l g o r i t h mi m p l e m e n t a t i o na n ds u c c e s s f u l l ya p p l i e dt o t h ef i e l do fs p a mf i l t e r i n g 1 1 1 ei m p r o v e m e n t so fe x i s t i n ga l g o r i t h ma n dt h ep r o p o s e d a l g o r i t h mc a l lb eu s e df o rt h ee l a s s i f i c a t i o no fo t h e rn e c e s s a r ya r e a s ，s u c ha st e x tm i n i n g ， i n t r u s i o nd e t e c t i o n , p a t t e r nr e c o g n i t i o n , e t c m a i nr e s e a r c hc o n t e n t s ： 1 b yg e n e r a t i n gd a n g e r o u ss i g n a l ，a p p l i e dt h el a t e s tr e s e a r c hr e s u l t so fd a n g e r t h e o r yd e n d r i t i cc e l la l g o r i t h mt os p a mf i l t e r i n g 2 b yi m p r o v i n g t h ew a yo fa n t i g e ng e n e r a t i n g 、t h eo r d e ro fa n t i g e n - p r e s e n t i n ga n d a n t i g e n - p r e s e n t i n g ，a l l o w sah i g h e ra c c u r a c yr a t eo fd e n d r i t i cc e l la l g o r i t h m 3 p u td e n d r i t i cc e l la l g o r i t h ma n dt h ec l o n es e l e c t i o na l g o r i t h mb a s e do nt h e t r a d i t i o n a la r t i f i c i a li m m u n es y s t e mt o g e t h e rt of o r mac o m p l e t es e c o n d g e n e r a t i o n a r t i f i c i a li m m u n es y s t e m b a s e dd e n d r i t i cc e l l a l g o r i t h mw i t ht r a i n i n g ( t - d c a ) ，t 0 f u r t h e ri m p r o v es p a l nf i l t e ra c c u r a c y k e yw o r d s ：s e c o n d g e n e r a t i o na r t i f i c i a li m m u n es y s t e m s ，d a n g e rt h e o r y , d e n d r i t i cc e l l a l g o r i t h m ，a n t i - s p a m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 日期：z 9 7 年乡月居日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：毯丝拖导师签名： 吼年j 月歹日 第一章绪论 1 1 免疫系统概论 1 1 1 生物免疫系统简介 第一章绪论 生物免疫系统中数人类的免疫系统最复杂，也最具研究价值，所以一般情况 下所说的生物免疫系统都是指人体免疫系统。 人体是一个极为复杂的有机体，可以把人体分为不同的层次来看待。人体的 结构层次如图1 1 所示。细胞组成组织，如肌肉和结缔组织；组织组成器官，如心， 脑和胸腺；器官组成系统，如心血管系统和免疫系绀旧。 人体 广一。一。- 。- - - - 1广。- 。- - ：免疫 ； ：大脑 ：淋巴 ； ：阑尾 ：心血管 ： ：脾脏 ：骨骼肌 ： ：膀胱 ：内分泌 ： ：肾脏 ：呼吸。心脏 ：生殖 ： ：肺 ：消化：胃 ：神经 ： ：胸腺 ：外皮：肝脏 ：肌肉： ； 上皮i i 树突状i i 一一， ：单核 ： ； ；肌肉； 上皮 i i + 1 神经r 1 成纤维i il 结缔i i 表皮l ： 一。一一一 - ! i i 系统器官 i i _ - _ _ _ _ _ - _ - - _ _ - - - - _ _ _ i 图1 1 人体结构层次图 细胞是生命有机体最基本的结构和功能组成单元，人体大约由1 0 1 4 个细胞组 成。细胞表层含有一种称为受体蛋白( r e c e p t o r p r o t e i n s ) 的特殊分子。通过受体蛋 白之间一系列的合成和反应，细胞能与生存环境和其它细胞发生交互并调节自身 的行为。相对于受体有一种称为配体蛋白( 1 i g a n dp r o t e i n s ) 的特殊分子，受体相 电子科技大学硕士学位论文 当于一把锁，配体相当于一把钥匙。 当配体激活受体以后，受体就开始改变所属细胞的代谢及功能，并能通过合 成受体生成其它分子。生成的分子可以分成如下三类： a 、其它受体的配体。 b 、细胞因子( c y t o k i n e s ) ：是一类能在细胞间传递信息、具有免疫调节和效应 功能的蛋白质。 c 、趋化因子( c h e m o k i n e s ) ：能加快细胞的移动速度。 从结构上讲，免疫系统是分子、细胞、组织、器官和循环系统的合成体【3 】。免 疫细胞由淋巴系统产生并在淋巴系统中成熟，通过心血管和淋巴系统运输到身体 的各个部分。人体充满着各种微生物，这些微生物通过消耗人体拥有的资源来生 长和繁殖，如果任其发展会对人体组织造成损伤。免疫学中把微生物对人体的损 伤叫做病变，相应的微生物叫做病原体。从功能上人体免疫系统就是定位和清除 病原体保持人体处于一个健康的平衡状态。 1 1 2 天然免疫与自适应免疫 统。 生物免疫系统被分为两个相互关联的子系统：天然免疫系统和自适应免疫系 表1 1 天然免疫系统和自适应免疫系统的属性差别 属性 天然免疫系统自适应免疫系统 组成细胞树突状细胞( d e n d r i t i cc e l l ，t 细胞、b 细胞 d c ) 、自然杀伤( n k ) 细胞、 巨噬细胞 受体 生殖系编码、无需重排、无需 基因片段编码、需要体细 克隆增生胞重排、克隆增生 抗原识别方式 保存分子的模式通过细胞的结构细节 免疫应答分泌细胞因子和趋化因子克隆扩张和分泌细胞因 子 响应时间 立即响应延迟响应 天然免疫系统分别有以下三种作用【4 】： a 、早期感染过程中的抗原识别( 非特异性识别) 。 2 第一章绪论 b 、引发自适应免疫系统的免疫应答。 c 、决定自适应免疫系统的应答类别。 自适应免疫系统的主要作用是识别抗原( 特异性识别) 并留下长期记忆。从 表1 1 中能清楚地看到两种免疫系统属性的差别。 天然免疫细胞是通过生殖编码的，也就是说同一种类型的细胞拥有相同的受 体。而白适应免疫细胞是通过基因片段编码并需要体细胞重排，所以分布在全身 各处同一类型的自适应免疫细胞拥有不同的受体。受体不同，识别的抗原就相异。 所以说天然免疫是非特异性的而自适应免疫是特异性的并具有记忆功能。 1 1 3 人工免疫系统( a i s ) 二十世纪八十年代，f a r m e r 等人率先基于免疫网络学说给出了免疫系统的动 态模型，并探讨了免疫系统与其它人工智能方法的联系，开始了人工免疫系统的 研究。直到1 9 9 6 年1 2 月，在日本首次举行了基于免疫性系统的国际专题讨论会， 首次提出了“人工免疫系统”( a i s ) 的概念。随后，人工免疫系统进入了兴盛发展时 期，d d a s g u p t a 和焦李成等认为人工免疫系统已经成为人工智能领域的理论和应 用研究热点，相关论文和研究成果正在逐年增加。1 9 9 7 和1 9 9 8 年i e e e 国际会议 还组织了相关专题讨论，并成立了“人工免疫系统及应用分会”。d d a s g u p t a 系统 分析了人工免疫系统和人工神经网络的异同，认为在组成单元及数目、交互作用、 模式识别、任务执行、记忆学习、系统鲁棒性等方面是相似的，而在系统分布、 组成单元间的通信、系统控制等方面是不同的，并指出自然免疫系统是人工智能 方法灵感的重要源泉。g a s p e r 等认为多样性是自适应动态的基本特征，而a i s 是 比g a 更好地维护这种多样性的优化方法【5 】。 免疫算法是基于免疫机理提出的高效的学习和优化算法，是a i s 理论研究的 主要内容。比较常见的算法有：克隆选择算法( c l o n es e l e c t i o na l g o r i t h m ，c s a ) ， b 细胞网络算法( & c e l la l g o r t h m ) ，否定选择算法( 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 m m u n eg e n e t i ca l g o r i t h m ，i g a ) 等。2 0 0 2 年u w ea i c k e l i n 教授把危险理论【6 】引入到了人工免疫领域后人工免疫系统的研究进入新的研究阶 段。一部分研究人员开始把目光放在天然免疫层的研究，提出了一系列基于危险 理论的算法，但这些算法的应用都只局限在入侵检测中。 j a m i ep a u lt w y c r o s s 博士于2 0 0 7 年提出了第二代人工免疫系统的概念【。7 1 ，他 认为天然免疫层起到的作用应该被体现在人工免疫系统( a r t i f i c i a li m m u n es y s t e m s ， 电子科技大学硕士学位论文 a i s ) 中，人体免疫系统是一个完整的系统，那么人工免疫系统也不应该忽略天然 免疫层的作用。 图1 2 显示了第一代和第二代人工免疫系统之间的关系。从本质上讲，第一代 人工免疫系统只是模拟了人体的自适应免疫层，而第二代人工免疫系统同时模拟 了人体的自适应免疫层和天然免疫层。关系就是二代人工免疫系统在已有基于自 适应免疫系统算法的基础上增加基于天然免疫系统的算法，然后形成一个完整的 基于两个子系统的人工免疫算法。 图1 2 第一代和第二代人工免疫系统的相互关系 1 2 垃圾邮件过滤技术概论 自从互联网普及以来，电子邮件逐渐成为人们生活中便捷的通信手段之一。 然而，随之产生的垃圾邮件像瘟疫一样蔓延，污染网络环境，占用大量传输、存 储和运算资源，影响了网络的正常运行。业内人士分析：一旦垃圾邮件占到互联 网总数据流量的三分之一以上，将会造成巨大的存储需求，甚至对信息安全系统 的有效性构成威胁。 对垃圾邮件的定义至今还没有一个比较明确的描述，然而它们的诸多表征已 经得到了业界人士的广泛的认可，例如：垃圾邮件通常是未经收件人主动请求又 无法拒收的、大量的邮件内容相似并且隐藏或伪造发件人身份、地址、标题信息 等。垃圾邮件的内容形形色色，常见的包括广告、色情信息，还有病毒或蠕虫引 起邮件深度扩散等诸多类型。由于垃圾邮件数量多，具有反复性、强制性、欺骗 性、不健康性或传播速度快等特点，严重干扰了人们正常生活，浪费用户的时间、 4 第一章绪论 精力甚至造成很多额外的经济支出和信息安全隐患。 因此，对反垃圾邮件的研究已经成为互联网发展技术的重要课题之一。目前， 垃圾邮件过滤技术上可划分为基于地址的过滤和基于内容的过滤。 1 2 1 基于地址的过滤 基于地址的过滤主要有黑、白名单和逆向地址解析技术。 1 黑、白名单 黑名单，也称其为拒绝名单，当服务器收到邮件后，先到“黑名单上查找， 如果发件人的邮件地址或d 地址在名单中，则拒绝接收或丢弃【8 】。白名单，有时 候也被称为安全名单，从这些名单发送来的邮件被认为是安全的。黑名单和白名 单占用系统资源少，易于实施，但名单需要人工维护和经常更新：而且垃圾邮件发 送者经常伪造或更改邮件地址，并采用一个更广泛的口地址区间以逃避反垃圾邮 件手段的检测。因此该类技术仅起补充作用。 2 逆向地址解析 逆向名字解析对发送者的p 地址进行逆向域名解析。通过d n s 查询来判断发 送者的母与其声称的名字是否一致，如果与其d n s 记录不符，则予以拒收【s 】。这 种方法可以有效过滤掉来自动态m 的垃圾邮件，对于某些使用动态域名的发送者， 也可以根据实际情况进行屏蔽。逆向名字解析需要进行大量的d n s 查询，从而耗 用大量的系统资源和网络资源。这种方法具有很大的局限性。 1 2 2 基于内容的过滤 目前基于内容的垃圾邮件判别方法可以大体分成基于规则的方法和基于概率 统计的方法。前者常常得出人们可以理解的显式规则；后者往往通过某种计算表 达式推出结果。不管是基于规则的方法还是基于概率统计的方法，在使用时都经 历从训练到过滤的过程。通过已有的i j i i 练集合( 正例+ 反例) 训练出相应的垃圾邮件 规则，然后将规则应用到新的邮件判定中去。在实际系统中可能还会加入人机交 互过程，通过用户对判定结果的认可与否对已有的垃圾邮件规则进行更新。基于 规则的方法通过训练得到显式规则( 通常用产生式表示，如：i f 邮件包含 a d v e r t i s o n 髓t 且邮件包含! ! ! t h e n 该邮件为垃圾邮件) 。规则方法学习的过程实际上 是归纳总结的过程，通过考查大量的训练样本，归纳总结出其中规律性的东西来 电子科技大学硕士学位论文 形成规则【9 】。基于规则方法的主要优点是可以生成人们易于理解的规则。缺点是在 规律性不明显的应用领域效果较差。 主要方法有贝叶斯分类算法【l o 】、最大熵算法【1 1 】、神经网络方法和传统人工免 疫算法【1 2 】。贝叶斯分类算法和最大熵算法的表现与训练集的相关性很大，采用不 同的数据集，最终效果可能不尽如意，对那些变异性较强的垃圾邮件动态适应性 较弱，神经网络方法的训练效率又太低。而传统人工免疫算法有很好的动态适应 性但是错误肯定率( f p r ) 和错误否定率( f n r ) 至少有一项太高不能满足实际要求。 除此之外，还有病毒检测技术和分布协作技术。本文研究重点是免疫算法和 针对邮件数据的算法结果，并不关心垃圾邮件的搜集、邮件预处理和过滤系统构 建。关于邮件的预处理和系统搭建的技术已经很成熟，本文就不再赘述了。 1 3 研究内容及主要创新点 针对传统垃圾邮件过滤技术对变异性较强的邮件动态适应性较弱的缺点，文 献 1 3 1 1 4 1 5 中把人工免疫的相关算法用于垃圾邮件过滤领域，但最终的计算结 果均不理想，主要是正确否定和正确肯定不能很好的平衡，保证一个在可接收的 范围时另一个值就完全不能接受。还有就是效率的问题，传统人工免疫系统中初 始检测器大部分是随机生成，初始检测器要通过自体耐受后才能用于邮件检测， 随机生成的初始检测器往往要通过很长时间的耐受才能得到足够数量的可用的成 熟检测器。 2 0 0 2 引入人工免疫研究的危险理论的相关算法都只应用于入侵检测中，由于 入侵检测和垃圾邮件过滤具有交大的相似性，所有本文尝试把危险理论的相关算 法应用于垃圾邮件过滤，并对已有算法的缺陷作出改进。2 0 0 7 年兴起的二代人工 免疫系统的研究对提高人工免疫算法的准确率提供了重要的指导思想。 从第一代人工免疫系统的存在缺点和现有垃圾邮件过滤技术的局限性出发， 本文以树突状细胞算法为主线，危险理论和二代人工免疫系统为理论基础，提出 了基于二代人工免疫系统的一个算法实现并成功应用于垃圾邮件过滤领域。文中 改进和提出的算法均可用于其它存在二分类的领域中，如文本挖掘、入侵检测、 模式识别等。 论文的主要工作如下： 首先，研究垃圾邮件涉及的相关技术、免疫系统相关基础知识和传统人工免 6 第一章绪论 疫算法。 其次，通过生成垃圾邮件的危险信号，把人工免疫学中危险理论最新研究成 果树突状细胞算法( d c a ) f 1 6 ，1 7 】引入到垃圾邮件过滤领域。 再次，通过改进抗原生成方式、抗原提呈次序和抗原提呈次数，使得树突状 细胞算法具有更高的准确率。 最后，把树突状细胞算法和传统人工免疫系统的克隆选择算法有机地组织在 一起，形成一个完整基于二代人工免疫系统带训练的树突状细胞算法( t - d c a ) ， 进一步提高垃圾邮件过滤的准确率。 1 4 论文的组织结构安排 第二章介绍传统人工免疫系统中所涉及的算法，并说明各种算法的优缺点和 使用场合。 第三章介绍危险理论及以危险理论为基础的树突状细胞算法，并把该算法应 用于垃圾邮件过滤。重点说明树突状细胞算法的改进、垃圾邮件信号的产生和该 算法与其它同类算法各方面的比较。 第四章介绍二代人工免疫系统组成。重点是把树突状细胞算法和克隆选择算 法相结合，形成一个完整基于二代人工免疫系统的新算法，带训练的树突状细胞 算法( t - d c a ) 。 第五章为结束语，根据算法的准确率和效率，提出后期需要进一步研究的问 题，描述了二代人工免疫系统的发展前景。 7 电子科技大学硕士学位论文 第二章传统人工免疫系统 传统人工免疫系统由相对独立的一序列基本算法组成【1 8 】，对主要算法分别描 述如下： 2 1 否定选择算法 否定选择算法【1 9 】是对自适应免疫细胞( b 细胞和t 细胞) 成熟过程的模拟， 用经历过耐受的检测器模拟成熟的免疫细胞。算法主要包括了两个阶段：耐受和 检测。 a 、耐受。 耐受阶段主要负责检测器的生成。耐受过程如图2 1 所示： 图2 1 否定选择算法的耐受过程 b 、检测。 在检测阶段，检测器检测受保护系统是否发生异常。检测过程如图2 2 所示： 否定选择算法( n a g t i v es e l e c ta l g r i t h e m ，n s ) 是人工免疫学中比较受关注的 理论。19 9 4 年，美国学者f o r r e s t ，p e r e l s o n 等人率先提出，用该算法来生成检测 器集，完成检测器的耐受，并提出了计算机免疫系统这一概念。最初的n s 算法检 测器生成效率低，大部分研究人员都把注意力集中在检测器的生成算法上。也有 第二章传统人工免疫系统 一部分研究人员更注重n s 算法的基本理论，在n s 算法的基础上提出了肯定选择 算法( p o s i t i v es d e c ta l g o r i t h m ，p s ) 。2 0 0 2 年e b n e r 提出把检测器的空间提升到 连续空间中，提出了实值否定选择算法( r e a l v a l u e dn e g a t i v es e l e c t i o n ，r v n s ) 和实值肯定选择算法( r e a l v a l u e dp o s i t i o ns e l e c t i o n ) 。之后，主要研究n s 算法性 能，增大检测器的覆盖面积，缩小检测器覆盖漏洞。2 0 0 4 年d a s g u p t a 提出了检测 器大小可变的实值否定选择算法，可以算是当前最新的n s 算法。n s 算法取得了 广泛的应用，但由于有自身无法克服的缺陷，使得一部分研究人员开始寻找新的 算法。 2 2 克隆选择算法 图2 - 2 否定选择算法的检测过程 1 9 5 8 年，澳大利亚学者b u m e t 率先提出了克隆选择原理。1 9 8 4 年他本人对该 理论作了进一步完整。1 9 9 9 年，h u n t 进一步发展了克隆选择理论，并且提出了高 频变异学说。 克隆选择原理被用来解释免疫系统是怎么与抗原作战的。当外部细菌或病毒 侵入机体后，b 细胞开始大量克隆并消灭入侵者，那些能够识别抗原的细胞根据识 别的程度通过无性繁殖达到增生的目的：与抗原具有越高的亲和力，该细胞就能 产生更多的后代。在细胞分裂的过程中，个体细胞还经历了一个变异的过程，其 结果使它们与抗原具有更高的亲和力：父代细胞与抗原具有越高的亲和力，则它 们就经历越小的变异。 如图2 3 所示，针对于动态克隆选择算法，标准的克隆选择算法【l8 】包含如下几 个方面： 9 电子科技大学硕士学位论文 维持免疫细胞在功能上与指令集的不连贯性； 受最大刺激的细胞的选择与克隆； 没有受刺激的细胞的死亡； 亲和力成熟和更高亲和力克隆的再选择； 多样性的生成和维护； 与细胞亲和力成比列的高频变异。 图2 - 3 标准克隆选择算法 ) 卜 标准克隆选择算法分6 部完成，每执行完6 步，生成新一代的免疫细胞。 生成候选方案的一个集合( p ) ，它由记忆细胞( m ) 的子集和加上剩余群体 ( e ) ( p = + m ) 选择n 个具有较高亲和力的个体。 克隆这n 个最好的个体，组成一个临时的克隆群体( c ) 。与抗原亲和力越 高，个体在克隆时的规模也就越大。 把克隆群体提交到高频变异，根据亲和力的大小决定变异。产生一个成熟 的抗体群体( c ) 。 对c 进行再选择，组成记忆细胞集合m 。p 中的一些成员可以被c 。中的其 1 0 ，_lrj、l 第二章传统人工免疫系统 它一些改进的成员替换掉。 生成d 个新的抗体取代p 中d 个低亲和力的抗体，保持多样性。 2 3 动态克隆选择算法( d y n a m i c s ) 1 9 9 9 年，h o f m e y r l 2 0 1 提出可以通过三种不同类型检测器的相互协调作用使得人 工免疫系统具有更好的自适应性。这三类检测器分别是：未成熟检测器、成熟检 测器和记忆检测器。2 0 0 2 年k i m 和b e n t l e y 根据h o f i n e y r 的理论提出了动态克隆 选择算法( d y n a m i ce l o n a ls e l e c t i o na l g o r i t h m ，d y n a m i c s ) 。动态克隆选择算法的主 要目的是使人工免疫系统具有更高的自适应性并减少需要人工确定的参数。动态 克隆选择算法的伪码如下所示： b e g i n 创建初始的未成熟检测器集合，大小随机； g e n e r a t i o n n u m b e r = 1 ； w h i l e ( g e n e r a t i o n _ n u m b e r m a x _ g e n e r a t i o n ) b e g i n 用记忆检测器去提呈抗原 检测是否有记忆检测器匹配非自体抗原； 检测是否有记忆检测器匹配自体抗原； 用成熟检测器去提呈抗原 检测是否有成熟检测器匹配非自体抗原； 检测是否有成熟检测器匹配自体抗原； 生成新的记忆检测器； 删除原有的成熟检测器； 用未成熟检测器去提呈抗原 检测是否有未成检测器匹配自体抗原； 删除任何匹配自体抗原的未成熟检测器； 生成新的成熟检测器； e n d 补充新的未成熟检测器 电子科技大学硕士学位论文 w h i l e ( 未成熟和成熟检测器个数之和小于指定值) b e g i n 随机生成一个检测器； 将生成的检测器加入到未成熟检测器集合； 。 e n d e n d 动态克隆选择算法首先通过随机方式生成初始的未成熟检测器，然后用否定选 择算法对未成熟检测器进行耐受，删除那些匹配自体抗原的检测器，直到非记忆 检测器的数目达到算法的指定值( 算法的输入) 。每次迭代使得未成熟的检测器年 龄加1 ，当未成熟检测器的年龄为t ( 算法的输入) 时，该检测器就进化为成熟检 测器。 对应t + 1 代的检测器都是刚刚进化而来的成熟检测器，用这些检测器去提呈一 个全新的抗原集合。如果检测器能正确识别一个抗原那么该检测器的匹配数加l ， 当所以的抗原都被提呈过后，需要检查检测器的两个指标： a 、检测器的匹配数是否大于指定值a ( 算法输入) 。 b 、检测器的年龄是否大于l ( 算法输入) 。 匹配数大于指定值a 的成熟检测器进化为记忆检测器，年龄大于l 的成熟检测器 被删除系统。 当系统运行到t + 2 代的时候，抗原通过记忆细胞检测，如果被记忆细胞检测为 异常数据则发出警告，如果被确认为异常数据，从抗原集合中删除该抗原。剩下 的抗原将通过成熟检测器检测，被成熟检测器提呈后的剩下的抗原将用于对未成 熟检测器的耐受作用。 2 4 基于网络的免疫算法 根据免于网络理论，免疫细胞的一部分抗体分子能像入侵的抗原一样被其它 免疫细胞识别。这就使系统中的免疫细胞相互联系起来。当一个免疫细胞识别出 一个抗原或者另一个免疫细胞时，那么它就被激活。另一方面，当免疫细胞被其 它的免疫细胞所识别时，它将被抑制。来自于网络中的细胞的刺激和抑制的总和， 再加上对抗原的识别，就可以计算出一个免疫细胞的受刺激程度s 。如式( 2 1 ) 所示 s = n s t 一s 。+ 4 ( 2 1 ) 1 2 第二章传统人工免疫系统 其中，圯代表网络刺激，代表网络抑制，而4 代表抗原刺激，一个细胞的受 刺激程度决定了它再生和遗传变异的几率。 一般来说，有两种不同的免疫网络模型：连续的和离散的。连续的免疫网络 模型基于常微分方程，比较典型的模型有f a r m d 冽等人于1 9 8 6 年提出的模型和 v a r e l a 与c o u t i n h o 于1 9 9 1 年提出的模型。这些连续模型已经成功应用于自动导航 系统、优化问题和自动控制领域。但是这些微分方程不是总能找到解析方法的， 而且通常情况下还需要数值积分来学习系统的行为。现在i n e t 是免疫网络的研究 热点，它在数据挖掘、数据分类、数据聚类、优化问题上都有广泛的应用。 电子科技大学硕士学位论文 第三章危险理论 3 1 危险理论的产生及简介 根据人工免疫系统( 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 ，在第一代a i s 基础上包含了危险理论( d a n g e rt h e o r y ，d n 等天然免疫机制的a i s 叫做第二代 a i s 7 】。危险理论是第二代a i s 的核心理论，下面对其进行详细叙述。 由于传统n s 算法有伸缩性差、检测效率低、错误判断概率高等缺点，根据 1 9 9 4 年m a t z i n g e r 在生物免疫( b i o l o g i c a li m m u n e ，b i ) 领域提出的危险理论模型【2 3 1 ， 2 0 0 2 年u w ea i c k e l i n 把危险理论1 6 弓1 入到了人工免疫领域。在b i 领域，危险理论 并不是一个完善的理论，m a t z i n g e r 给出的只是一个设想并没有具体的试验数据， 至今还是一个争论的焦点。人工免疫里并不关心在危险理论在b i 领域争论，而只 是关心它能否给我们解决问题带来方便。 生物免疫系统( b i o l o g i c a li m m u n es y s t e m ，b i s ) 被认为由三个相互关联的部分组 成：物理屏障层( 皮肤、体液等) 、天然免疫层( t l 细胞、巨噬细胞等) 、自适应免疫 层。一代a i s 中只讨论自适应免疫层【6 】，二代a i s 理论统一了天然免疫和自适应 免疫【6 ，2 4 。传统人工免疫学是基于自体与非自体区分的理论基础上，危险理论认为 仅仅区分自体非自体是不够的，因为传统免疫学不能很好地解释很多现象【2 3 1 ，比 如： 肠道微生物和食物并不属于人体自身，不能划分为自体，但是免疫系统并 不对这类物质产生免疫作用。 传统免疫学不能很好地解释自免疫疾病现象。 生物在成长过程中需要不断地吸收外界物质，会导致非自体向自体转换的 矛盾过程。 传统免疫学也不能解释器官成功移植问题，按理应该对非自体产生免疫作 用，不可能移植成功。 ， m a t z i n g e r 提出要想跳出免疫学研究的困境，必须抛弃自体非自体划分的思 想。危险理论只关心有害和无害不再关心自体与非自体。核心思想是免疫系统不 再对非自体发生免疫作用而是对有害物质产生免疫应答，也就是说属于自己的并 不一定安全，外界的并不一定具有危害性。 在b i s 中细胞的不正常死亡就是一个危险信号，具体危险信号的产生【6 】如下图 1 4 第三章危险理论 3 - 1 所示： 抗体 抗原 细胞 细胞损伤 危险信号 图3 - 1 危险理论模型 当细胞处于抑制状态时会发出一个警报信号，抗原提呈细胞根据该警报信号 捕获相应的抗原并提呈给淋巴细胞，淋巴细胞根据抗原提呈细胞的提呈产生相应 的抗体并对抗体进行克隆扩张。对于危险信号的内在性质m a t z i n g e r 认为需要做进 一步研究，可能是正信号( 释放某种物质) ，也可能是负信号( 缺少某种关联) 。区分 危险和不危险是危险理论及其应用的核心。 也可以使用二值信号模型瞵】系统来理解危险理论模型，该模型中包含了两个 信号：抗原识别信号( 信号1 ) 、协调刺激信号( 信号2 ) 。代表危险理论的二值信号模 型必须满足下列三条规则【6 1 ( 淋巴细胞) ： 规则l ：同时收到两个信号时被激活，只收到信号l 无信号2 时死亡，只 收到信号2 无信号1 是忽略信号2 规则2 ：信号2 只能由抗原提呈细胞发出，信号l 可以由任何细胞发出。 规则3 ：激活后经过一段时间后进入休息状态，不接收任何信号。 所有淋巴细胞的状态都由以上三条规则确定，但是有两种情况除外：未成熟 的细胞不能收到信号2 ：成熟的细胞只对信号1 产生免疫应答，忽略信号2 。综上 所述，危险理论可以看成是免疫信号理论的扩展。 在细胞的正常死亡( a p o p t o s i s ) 过程中会发出安全信号，并把树突状细胞吸引 到其周围，然后被吸引过来的树突状细胞将会发现并吞噬掉该死亡细胞。在这个 过程中几乎没有细胞碎片残留在机体组织中。被树突状细胞吞噬的细胞中的蛋白 1 5 口口 游 电子科技大学硕士学位论文 质被呈现给免疫系统，以后免疫系统遇到类似的蛋白质将视为正常蛋白质。相对 于主导2 0 世纪免疫学的中心耐受理论，该动态过程叫做周边耐受。树突状细胞在 危险理论中起到传递信息，接收信息等重要作用，下一节将对树突状细胞作详细 描述。 3 2 树突状细胞( d e n d r i t i cc e l l s ，d c s ) 于1 8 6 8 年，树突状细胞首先被l a n g e r h a n s 在研究皮肤的细胞成分时发现 2 6 1 。 当时对免疫系统的了解很少加上树突状细胞呈现形状是树突状，l a n g e r h a n s 当时把 d c s 误认为是神经细胞( 下文中均把树突状细胞简称为d c s ) 。 尽管d c s 发现的很早，但其功能还是1 4 0 年后研究天然免疫系统时才得出详 细的描述。近年来对d c s 的研究相当活跃，涌现了大量的研究论文。除了技术、 设备和实验方法的进步，研究人员热衷于d c s 研究的主要原因是因为d c s 是控制 自适应免疫系统的枢纽。 d c s 是抗原提呈细胞，它的主要作用是给t 细胞收集、处理和提呈抗原。每 个初始t 细胞只能识别一类特别的抗原，而这个t 细胞只能通过一类特殊的d c s 来激活。把这种细胞叫做初始t 细胞是因为该细胞产生后从未识别过抗原。d c s 除了能提呈抗原外还能促使受体从其生成环境中接收有用信号。这种受体包括一 类叫做t o l l 样受体( t o l l 1 i k er e c e p t o r s ，t l r s ) 的受体。d c s 尽管充当免疫系统交互的 枢纽，但是它也能够产生信号。针对细胞的坏死和正常凋零d c s 能产生两类不同 的信号：危险信号和安全信号。d c s 的行为取决于两个条件： 收到信号的密集成度和信号量的大小。 d c s 的当前状态。 d c s 产生于白血细胞中的一类单核细胞。当一个单核细胞离开血液循环定居 到一个局部组织时，这个单核细胞就叫做未成熟d c 。d c s 在任何时候都必需处于 未成熟、半成熟和成熟三种状态之一。三种状态下的d c s 表面都具有相同类型的 受体，说明它们是同一类细胞。如图3 2 所示，在显微镜下未成熟的d c s 和其它 两个状态的d c s 有显著的区别【2 7 1 。未成熟d c s 的功能是收集抗原、呈现抗原和收 集处理组织细胞坏死或正常凋零的信号。 1 6 电子科技大学硕士学位论文 t 细胞结合的成功率。在从组织移动到淋巴结的过程中，d c s 的表面发生变化以增 加细胞表面积变成m d c s ，这样就进一步增加了m d c s 和t 细胞结合的成功率【3 0 】。 因为m d c s 拥有更大的表面积，所以它更适合于抗原呈现而不仅仅是收集抗原。 m d c s 的表面越大越便于t 受体结合最适合的抗原。 m d c s 最重要的功能在于它能产生一种叫做白细胞介素1 2 的蛋白质，该类蛋 白质能激活t 细胞。另外m d c s 能产生促进抗原呈现的刺激分子( c s m s ) 3 1 】。生 成在组织中的i d c s 的主要目的是通过接收p a m p 信号和危险信号来产生白细胞介 素1 2 和刺激分子( c s m s ) 。 3 2 3 半成熟d c s 与m d c s 相反，当i d c s 接收到安全信号后就发展成半成熟d c ( s e m i m a t u r e d c s ，s m d c s ) 。它与m d c s 在结构上极为相似，也能提呈抗原，但是不能激活t 细胞。与m d c s 相似s m d c s 收到安全信号后也能产生一种蛋白质叫做白细胞介素 1 0 而不是白细胞介素1 2 。白细胞介素1 0 能够抑制t 细胞结合抗原。抗原的收集 和安全信号的产生相当于一个耐受过程，这就导致了t 细胞以后遇到类似结果抗 原时的不反应现象。研究表明安全信号对d c s 的影响要大于p a m p 和危险信号， 并且能抑制白细胞介素1 2 的产生促进产生白细胞介素1 0 【3 2 1 。这种机制能阻止免疫 系统的过度反应。从本质上将，这些机制都是为了降低免疫系统的错误肯定率和 防止免疫系