（计算机应用技术专业论文）硬件免疫系统与算法研究.pdf

摘要 摘要 人工免疫系统( a n i f i c i a l i m m u n es v s t e m ：越s ) 是受生物免疫学原理启发而 建立的智能计算方法。人工免疫系统的研究旨在通过挖掘生物免疫系统内在的信 息处理机制，建立新的工程计算模型和算法，用于解决多种复杂的信息处理问题。 人工免疫系统是生物免疫学与计算机科学相结合而形成的交叉研究领域，已经成 为计算智能领域中新兴的研究热点。 硬件免疫系统( h a r d ei m m u n es y s t e m ：h w i s ) 是人工免疫系统领域中新 出现的研究分支，近年来开始受到关注。它以人工免疫系统中的模型和算法为基 础，探索用于实现容错硬件系统的新途径，为复杂硬件系统的在线故障检测建立 新的模型和方法。 本文旨在为硬件免疫系统在实际应用中面临的不完整自我集问题和脏自我 集问题寻找可行的解决方案，并针对单片机i p 核程序“跑飞”故障的检测问题 设计和实现一个自适应硬件免疫系统。具体而言，本文的主要研究工作包括以下 几个方面： ( 1 ) 针对单片机i p 核程序“跑飞 故障的检测问题，设计并实现了一个简 单的硬件免疫系统。该系统具备基本的故障检测功能，其有效性在f p g a 实验平 台上得到了验证。然后，针对实际应用环境的特点，指出了硬件免疫系统可能面 临的不完整自我集问题和脏自我集问题，并为应对这两个问题初步建立了一种自 适应的硬件免疫系统框架。 ( 2 ) 针对硬件免疫系统在实际应用中面临的不完整自我集问题，通过借鉴 生物免疫系统中的协同刺激机制，提出了一种基于协同刺激机制的自身耐受算法 以及几种不同的检测器集合更新策略，使得硬件免疫系统既能够减少由于自我集 不完整而导致的误报，又能够减少由于更新检测器集合而增加的漏报。这些算法 和策略的有效性在模拟实验中得到了验证。该部分研究为硬件免疫系统较好地实 现自身耐受提f j ”了途径。 ( 3 ) 针叉j 7 j 包疫系统在实际应用中面临的脏自我集问题，提出了基于协 同刺激机制的，；- i ： i 同的脏自我集处理策略，以及针对自身反应候选检测器的受 体编辑机制。脏自我集处理策略使硬件免疫系统能够通过补充新的检测器，来减 少由脏自我集内的非我个体导致的漏报；而受体编辑机制则能提高生成新检测器 的成功率。这些策略的有效性在模拟实验中得到了验证。该部分研究为解决硬件 免疫系统的脏自我集问题提供了可行的途径。 ( 4 ) 针对多、j 应用中单片机i p 核程序“跑飞故障的检测问题，设计并实 摘要 现了一个自适应的硬件免疫系统。该系统能够在协同刺激机制的协助下实现自我 集和检测器集的自动更新，从而即能够减少由不完整自我集导致的误报，也能够 减少由脏自我集导致的漏报。该系统对于解决不完整自我集问题和脏自我集问题的有效性在f p g a 实验平台上得到了验证。 本文首先构建了用于检测单片机i p 核程序“跑飞故障的具备基本故障检 测功能的硬件免疫鏊鞭? 鳕薹型雾薹琵冀燮鉴羹季薹冀羹雾蓁茎蓉蠹蚕霎霞薹蓁 萋錾囊羹熏薹羹碲菰篓：篓蚕鋈薹薰冀基囊攀鍪器薹雾塑蚕蚕j 囊毳矬蘸霪囊 堕萋羹冀薹錾蓁蜒薹蓁骂薹羹羹羹! 鬟囊薹荔羹錾雾篓噗雾霪臻霸疆薹墓鬟粪雾 薹冀熏薹囊篓i 军囊羹羹蠢等驯萋篓篓薹薹霪篓冀；霪唰臻毳燮妻霞鞠蕊弼蔡錾 塞委冀霎墓蚕雾薹篓= 冀雾羹雾蘸墼篓薹羹：醋巍鸶餮型丽冀萎薹震蠢簦雾雾甏 i 婪震冀鞭r e n k i a nd e c i e n c i a ，o e i r a l s ，p o n u g a l ，2 0 0 6 ，p p 4 0 4 4 17 a t a r a k a n o v d ，d a s g u p t a ，a ni m m u n o c h i pa r c h i t e c t u r ea n di t se m u l a t i o n ，”i np r o c n a s a d o dc o n f e r e n c eo ne v ol v a b l eh a r d w a r e ，2 0 0 2 ，p p 2 6 1 2 6 5 a b s t r a c t c o n t r i b u t i o nt om ef i e l do fh w i s ，b u ta l s oav a l u a b l ee x 锄p l eo fm ei n d u s t r i a l 印p l i c a t i o n so f t h eh a r d w a r ei m m u n es y s t e m s k e yw o r d s ：a n i f i c i a l i m m u l l es y s t e m ，h a r d w a u r ei m n m es y s t e m ，f a u l td e t e c t i o n ， n e g a t i v es e l e c t i o na l g o r i t h m ，c o s t i m u l a t i o nm e c h a n i s m v 插图目录 图4 5 针对一个自身反应候选检测器d 的受体编辑流程5 1 图4 6 脏自我集处理策略1 1 的流程图5 2 图4 7 脏自我集处理策略1 1 的流程描述5 3 图4 8 脏自我集处理策略1 2 的流程图5 3 图4 9 脏自我集处理策略1 2 的流程描述5 3 图4 1 0 脏自我集处理策略2 1 的流程图5 4 图4 1 1 脏自我集处理策略2 1 的流程描述5 4 图4 1 2 脏自我集处理策略2 2 的流程图5 5 图4 1 3 脏自我集处理策略2 2 的流程描述5 6 图4 1 4 模拟实验系统框图5 6 图5 1 用于检测单片机i p 核程序“跑飞”故障的自适应硬件免疫系统框图6 7 图5 2 故障检测阶段的工作流程6 8 图5 3 自我集和检测器集更新阶段的工作流程6 9 图5 4 协同刺激信号源的电路实现一7 0 图5 5 自适应硬件免疫系统的寄存器传输级电路原理图7 0 图5 6 顶层电路模块的部分代码7 l 图5 7 用于测试的单片机程序7 2 图5 8 本实验中f p g a 芯片e p 2 c 3 5 的资源使用情况7 4 图5 9 一般情况下非法状态迁移出现时几个关键节点的波形7 5 图5 1 0 误报发生以及自我集更新过程中几个关键节点的波形7 7 图5 1 1 检测器集合更新过程中几个关键节点的波形7 8 图5 1 2 检测器集合更新完成时几个关键节点的波形7 8 图5 1 3 脏个体导致的漏报发生过程中几个关键节点的波形7 9 图5 1 4 自我集更新过程中几个关键节点的波形7 9 图5 1 5 检测器集合更新过程中以及更新完成时几个关键节点的波形8 0 v 第l 章绪论 第1 章绪论 人工免疫系统( a n i f i c i a l i m m u n es y s t e m ：a i s ) 是计算智能领域中近年来新 兴的研究热点，是生物免疫学和计算机科学相结合而形成的交叉研究领域。人工 免疫系统的研究旨在借鉴生物免疫学的已有研究成果，挖掘和发现生物免疫系统 内在的信息处理机制，建立起有效的计算模型和算法，用于解决多种复杂的信息 处理问题。 硬件免疫系统( h a r d 眦ei m m u i l es y s t e m ：h w i s ) 是人工免疫系统领域中近 年来出现的一个研究分支。它将人工免疫系统的模型和算法应用到硬件容错 ( h a u r d 、v a r ef a u l tt 0 1 e r a n c e ) 研究中，探索新的硬件系统故障检测途径，为复杂 电路系统的故障检测建立新的模型和方法。 本章首先简要描述了生物免疫系统的基本概念和功能，回顾了人工免疫系统 的发展历程，介绍了人工免疫系统的研究现状；接着对硬件免疫系统的概念，模 型和研究现状进行了概述；然后介绍了本文主要的研究内容与创新之处，给出了 本文的组织安排；最后是本章小结。 1 1 人工免疫系统概述 1 1 1 生物免疫学的基本概念 免疫学是生命科学的前沿领域，也是现代医学的支撑学科之一。按照传统定 义，免疫( i m m u n e ) 是指免除传染病，免疫性( i m m u n i t y ) 是指机体的抗感染 能力，而免疫学( i n l n l u n o l o g y ) 则是阐明机体的抗病机制和防止免疫应答不良 后果的学科 1 】。近代免疫学已超越了单纯的抗感染范畴，成为一门研究机体分 辨自身和非己( s e l f n o n s e l f ) ，并清除非己成分的机制的学科，而免疫一词则被 重新定义为对抗原性异物的识别和清除 1 ，2 】。 免疫包括固有免疫( i 衄a t ei n u n 嘶t ) r ，也称为先天性免疫) 和适应性免疫 ( a d 印t i v ei m m u n i 妙，也称为获得性免疫，即a c q u i r e di m m 叽时) 1 ，3 ，4 】。固 有免疫是非特异性免疫，是机体先天就具备的外来物抵抗机制，能够以抗原非特 异性应答( 炎症反应等) 方式识别和清除病原体。固有免疫在所有时间都是持续 发生的，在抗原入侵前就已经存在【l 】。适应性免疫是特异性免疫，是在机体的 发育过程中通过不断地与抗原接触而获得的免疫性，能够以抗原特异性应答方式 识别和清除病原体。适应性免疫包括t 细胞、b 细胞的成熟分化，对抗原的识别， 第1 章绪论 发挥效应作用和产生免疫记忆几个部分。适应性免疫能够随着机体的发育不断学 习和完善，是免疫系统进化的高级形式 1 】。无脊椎动物和脊椎动物都具有固有 免疫性，而适应性免疫只存在于脊椎动物的有颌类中【1 。 生物免疫系统是高度复杂的分布式动态自适应系统，主要包括免疫器官、免 疫细胞和免疫分子三个组成部分。以下对这几个部分分别作简要介绍。 免疫器官包括中枢免疫器官( 胸腺和骨髓) ，外周免疫器官和组织( 脾脏、 淋巴结和粘膜免疫系统) 以及免疫细胞的再循环系统。中枢免疫器官是免疫细胞 产生和分化的场所，外周免疫器官和组织是淋巴细胞定居和发生免疫应答的场 所，而再循环系统则实现淋巴细胞在体内的迁移和流动【i 】。 免疫细胞( i m m 眦l o c y t e ) 泛指所有参与免疫应答或与免疫应答有关的细胞， 主要包括三类：参与适应性免疫的t 、b 淋巴细胞，参与固有免疫的单核巨噬细 胞、自然杀伤细胞( n k 细胞) 、树突状细胞( d c 细胞) 等【l ，4 】。在适应性免疫 应答中，t 细胞通过其表面的受体进行对抗原的识别，并能够通过一定的机制激 活b 细胞。被激活的b 细胞能够产生与抗原相对应的抗体来清除抗原。t 、b 等 细胞群体通过基因变异和重组，它们的结构和相应的分子( 如抗体) 能够显示出 高度的异质性，从而使机体具有识别大量的抗原并进行特异性应答的能力【1 】。 免疫分子是指参与免疫细胞的发育和分化、固有免疫应答、抗原识别、免疫 细胞信号传导以及免疫细胞凋亡和裂解的分子，在免疫系统中发挥着重要的调节 和信息传递作用【1 1 。 生物免疫系统能够抵抗外来入侵并保持体内环境的协调与稳定，其主要功能 将在下一小节中作简要介绍。 1 1 2 生物免疫系统的主要功能和特点 生物免疫系统是一个并行的，分布式的动态自适应系统，具备学习和记忆能 力。它能够从环境中学习新的抗原模式并记住遇到过的抗原模式，能够对抗原进 行识别和分类，并对抗原进行适当的应答。在生物体中，免疫系统主要发挥三方 面功能f 1 ：( 1 ) 免疫防御：免疫防御是免疫系统担负的最重要的功能。免疫系 统能够抵御外来入侵，识别并清除对机体构成威胁的外来非己成分。( 2 ) 免疫监 视：免疫系统能够监视体内新出现的非己成分，包括肿瘤和衰变凋亡的细胞等。 因基因突变而致癌的威胁在机体中是时刻存在的，免疫系统能够在细胞开始发生 癌变时将其消灭在萌芽状态。( 3 ) 维持内环境稳定：该功能包括免疫系统对机体 自身应答的耐受和调节。同时，免疫系统与神经内分泌系统能够相互协调和平衡， 共同维持体内环境的稳定。免疫系统以上三方面功能的发挥依赖予它所具备的下 列几种特点和能力f 1 ，3 5 。 2 第l 章绪论 ( 1 ) 免疫识别 能使机体产生特异性免疫应答并与免疫应答产物相结合的物质被称为抗原 ( 锄t i g e n ) 。抗原可能来自人体自身，也有可能来自体外。固有免疫主要识别病 原体相关的非蛋白质抗原，而适应性免疫主要通过淋巴细胞识别蛋白质抗原 1 】。 免疫细胞通常难以识别整个抗原分子，而仅通过受体来识别抗原大分子上的一个 特定的部分，称为表位( e p i t o p e ) 或抗原决定簇。表位能够与免疫细胞表面的抗 原受体或游离的抗体分子相结合，而免疫应答的特异性针对的也是表位而不是完 整的抗原分子 1 】。在适应性免疫识别中，不同的抗原通过多样的淋巴细胞受体 对淋巴细胞克隆进行选择，而淋巴细胞受体的多样性则来源于受体基因的重组和 变异。淋巴细胞受体的多样性是特异性产生的基础 1 】。 ( 2 ) 免疫应答 免疫细胞的受体和抗原结合后即启动相应的信号传导，从而激活免疫细胞， 启动免疫应答。免疫应答分为非抗原特异性应答和抗原特异性应答。根据特异性 应答的时间先后，又可分为初次应答和二次应答 1 ，4 。初次应答潜伏期长，应 答强度较低。二次应答潜伏期短，应答强度较大。在应答过程中，被激活的淋巴 细胞发生增殖和分化，产生效应细胞、效应分子和记忆细胞。效应细胞和效应分 子可清除相应的抗原，而记忆细胞则为进行二次应答作好准备【1 】。 ( 3 ) 免疫调节 免疫系统对免疫应答的强度具有自我感知能力，从而能够对免疫应答的强度 进行反馈调节 1 ，4 】。免疫调节是一个十分复杂的过程，至今仍是免疫学研究要 解决的主要问题之一。在该领域的研究中，有两个最具代表性的学说，即f m b 啪e t 的克隆选择学说 6 】和n k j e m e 的独特型网络学说【7 】。 克隆选择学说( c l o n a ls e l e c t i o n t h e o 巧) 认为，当某种抗原与某个淋巴细胞 克隆的受体发生结合时，便选择性地激活了这一克隆，进而使该克隆发生扩增并 产生大量抗体。扩增后的克隆所产生的抗体分子的特异性与被选择的淋巴细胞克 隆的表面受体相同。与抗原具有较高亲和度的淋巴细胞会转化为记忆细胞，当以 后再遇到同类抗原时能够进行快速应答 6 】。 独特型网络学说( i d i o t ) ，p i cn e t 、o r kt l l e o 巧) 阐述了免疫系统在动态环境中 怎样保持稳定【7 】。该学说认为，在淋巴细胞与抗体分子所组成的网络中，抗体 之间的相互刺激和抑制关系能使多种抗体的数量达到平衡。在抗原刺激发生前， 机体处于一种相对稳定状态。当有抗原侵入时平衡被打破，识别抗原的抗体的浓 度提高( 进行免疫应答) ，使抗原得到抑制。同时网络中各元素之间的相互关系 制约了某种抗体浓度的无限扩大，从而保证适当的应答强度，并且使网络又达到 新的稳定状态。这样，系统既能保持动态稳定又能及时对外部刺激产生应答 7 】。 3 第l 章绪论 ( 4 ) 免疫记忆 免疫记忆是适应性免疫的重要特征。免疫系统对某种抗原发生初次应答 过程中，被激活的淋巴细胞发生增殖和分化，产生记忆细胞。当免疫系统再次遇 到该种抗原时，会发生由记忆性淋巴细胞主导的增强的二次应答。二次应答比初 次应答的反应时间更短，应答强度更大。由于二次应答的发生取决于原先遇到过 的抗原是否再次出现，因此适应性免疫的抗原特异性是在二次应答中体现的 1 】。 ( 5 ) 免疫耐受 免疫耐受是指淋巴细胞在接触某些抗原物质时所表现出的一种特异性无应 答或低应答状态。按照耐受形成的机制，免疫耐受可以分为天然耐受与获得耐受 两种。针对自身抗原所呈现的免疫耐受称自身耐受( s e l f t o l e r a n c e ，即免疫系统不 对自身抗原发生免疫应答) 。免疫耐受是自身耐受的基础，是维持机体自身稳定 的重要机制 1 ，4 】。 1 1 。3 人工免疫系统的发展历程 人工免疫系统研究开始于二十世纪八十年代，与人工神经网络( a n j n c i a l n e u r a ln e t w o r k s ：a 1 、n ) 和进化计算( e v 0 1 u t i o n a r yc o m p u t a t i o n ) 一样，都是受 生物系统中的机制启发而建立的智能计算方法，用于解决各种科学和工程问题。 人工免疫系统已经成为了计算智能( c o m p u t a t i o n a n t e i l i g e n c e ) 领域中的一个重 要分支和研究热点。 随着生物免疫学的不断发展，免疫学的研究成果受到了科学和工程领域中越 来越多的研究和开发人员的重视，并开始逐渐地被其他学科的研究所借鉴和吸 收，从而推动了相关交叉学科的发展。人工免疫系统( a n i f i c i a ii m m u n es y s t e m s ： a i s ) 研究就是在这样一个学科交叉的大背景下诞生的。 生物免疫学中的非选择原理 1 ，8 】，克隆选择学说 6 】和免疫网络学说【7 】为人 工免疫系统的研究提供了免疫学基础。1 9 8 6 年，j d f a m l e r 等人在其论文中首 先将免疫学原理引入工程应用，为建立基于免疫原理的计算系统迈出了第一步 f 9 1 ；1 9 9 0 年，f j 。e l a 和j s t e w a n 在论文【1 0 中讨论了免疫网络的收敛性和 对环境的适应性，为免疫网络理论的工程应用提供了理论支持；yi s h i d a 提出了 p d p 学习算法以及p d p 免疫网络模型 1 1 】；h b e r s m 和f j v a r e l a 则尝试将免 疫网络理论应用于自适应问题求解 1 2 】，他们的工作进一步在免疫学理论与工程 应用需求之间搭起了桥梁；1 9 9 4 年，s f o r r e s t 等人提出了非选择算法( n e g a t i v e s e l e c t i o n a l g o r i t ：n s a ) f 1 3 】，为人工免疫系统在信息安全方面的应用奠定了 基础；1 9 9 7 年，s f o r r e s t 和a s o m a y a i i 等人提出了计算机免疫的概念 1 4 ，1 5 】。 至此，人工免疫系统研究领域由萌芽阶段过渡到发展阶段。 4 第l 章绪论 随着研究的开展，人工免疫系统领域开始受到科研院所、高校和产业界的重 视，并且已有多个国际会议的讨论主题涉及到这一领域。2 0 0 2 年，第一届人工 免疫系统国际会议“ls ti n t e m a t i o n a lc o n f e r e n c eo na n i n c i a li m m u n es y s t e m s ” ( i c a 对s 2 0 0 2 ) 在英国召开。i c a 融s 会议每年举行一次，主要探讨人工免疫 系统理论和应用研究的最新进展，已经成为人工免疫系统研究领域最主要的国际 会议。第七届人工免疫系统国际会议“7 t hi n t e m a t i o n a lc o n f e r e n c eo na n i 丘c i a l i m m u n es y s t e m s ”( i c a 砌s 2 0 0 8 ) 将于2 0 0 8 年8 月在泰国的普吉岛举行。现在， 随着人工免疫系统的研究逐渐步入成熟，该领域已经进入了稳步发展时期。 1 1 4 人工免疫系统的研究内容与现状 人工免疫系统是计算智能研究领域中一个较年轻的分支。它借鉴生物免疫系 统中的各种机制，建立了多种计算模型和算法，为计算智能的发展起到了显著的 推动作用。 从信息处理角度来看，生物免疫系统是一个复杂的信息处理系统，具有并行 计算、分布式处理、动态自适应、海量数据存储和模式识别等多种信息处理机制。 因此，生物免疫系统吸引了信息科学领域的众多研究人员对其中的各种信息处理 机制进行研究和挖掘，并借鉴这些机制建立了多种计算模型，用来更好地解决多 种科学和工程问题 3 ，5 】。一般认为，人工免疫系统是受生物免疫系统启发，以 生物免疫系统的功能、原理、特征以及相关的免疫学理论为基础而建立的用于解 决多种复杂的信息处理问题的智能计算方法。 在人工免疫系统所借鉴，模仿和讨论的多种生物免疫理论中，非选择( 即t 细胞的成熟和效应机制) 【1 ，8 ，克隆选择学说【6 和免疫网络学说 7 】是最主要的 三种免疫学依据。因此，这三种理论构成了人工免疫系统研究的主要理论来源， 并由此发展出了多种人工免疫模型和算法。其中，被研究和应用最多的算法和模 型主要有三种，即非选择算法 1 3 】、克隆选择算法 1 6 ，1 7 】和人工免疫网络 1 8 ，1 9 】。 这些模型和算法已经被应用于诸如信息安全、故障检测、模式识别等多个领域。 此外，人工免疫系统中的算法和模型也与其他智能计算算法和模型发生了结合， 在与其他算法互补的过程中展现出了越来越广阔的应用前景。 自诞生以来，人工免疫系统吸引了大量的科研和工程人员的兴趣，在理论研 究和应用开发方面都取得了一定的进展 2 ，2 0 2 2 】。本小节以下内容将分别简要介 绍人工免疫系统的三种主要算法和模型，最后也将简要介绍其它研究热点以及人 工免疫系统的应用研究情况。由于本文的研究内容主要应用了非选择算法，所以 本小节以下篇幅将重点介绍非选择算法及其研究进展。 5 第1 章绪论 ( 1 ) 非选择算法 非选择算法是人工免疫系统研究领域的基础算法之一。免疫学认为生物免疫 系统能够通过t 细胞( 一种主要的淋巴细胞) 来区分自我( s e l c 即正常细胞和 分子等) 和非我( n o n s e l f ，即细菌、病毒等病原体) 【1 】。一般情况下，所有新 产生的未成熟t 细胞必须经历一个成熟过程，即非选择( n e g a t i v es e l e c t i o n ) 过 程。在该过程中，自身反应( s e l f - r e a c t i v e ，即与自身蛋白质分子发生结合) 的t 细胞被清除，从而使得最终进入血液循环的成熟t 细胞只能识别非我抗原。而被 t 细胞识别到的非我抗原将被t 细胞介导的免疫应答清除【1 】。 检测器集合生成过程 异常检测过程 图1 1 非选择算法的流程框图【1 3 】 n o 受生物免疫系统中t 细胞的成熟和效应机制的启发，s f o r r e s t 等人提出了 非选择算法( n e g a t i v es e i e c t i o na l g o r i t h m ：n s a ) ，用于进行变化检测 1 3 ，2 3 】。 该算法的核心思想是：随机产生候选检测器，删除检测到自我的候选检测器，从 而使那些只能检测到非我的检测器组成检测器集合。在检测过程中，任何与检测 器集合匹配的个体都被视为非我【1 3 ，2 3 。这里的候选检测器也被称为“未成熟 检测器”，而最终生成的不与自我匹配的检测器也被称为“成熟检测器”。n s a 的流程分为两个阶段，即检测器集合生成阶段和异常检测阶段，如图1 1 所示。 s f o r r e s t 等人提出的非选择算法中的检测器编码为字符串型式，而字符串 之间的匹配操作采用部分匹配规则( p a r t i a lm a t c l l i n gr u l e ) 【1 3 】。在最典型的， 连续位( ，c o n t i g u o u s - b i t s ) 部分匹配规则中，如果两个等长的字符串在连续，个 对应的位置上相同，则它们被看作相互匹配。这里，代表匹配阂值。例如，当r 为8 时，二进制字符串“0 1 1 0 1 1 1 0 0 1 ”和“1 1 1 0 1 1 1 0 0 0 ”在，_ 连续位部分匹配规 则下是匹配的，因为二者的中间8 位“1 1 0 1 l1 0 0 ”相同。采用部分匹配的好处是 可以用较少的检测器覆盖较大的非我空间，但同时会带来“洞”( h o l e s ，即检测 器集合无法覆盖的非我个体) 的问题 2 4 】。 作为人工免疫系统的主要算法之一，非选择算法一直是一个研究热点。因此， 关于非选择算法的后继研究工作也比较多。例如，d h a e s e i e e r 等人提出了一种线 6 第l 章绪论 性时间的检测器集合生成算法和种贪心的检测器集合生成算法，并且对部分匹 配规则导致的非我空间中的“洞”的问题进行了研究【2 3 ，2 4 】；m a y a r a 等人提出 了一种新的检测器生成算法，并对几种不同的检测器生成算法进行了比较【2 5 】； j b a l t h r o p 等人针对网络入侵检测问题提出了，- c h u n k s 部分匹配规则 2 6 ：f g o n z a l e z 等人提出了一种随机的实值空间非选择算法 2 7 】；z j i 和d d a s g u p t a 提出了检测器覆盖区域大小可变的实值空间非选择算法【2 8 ，2 9 】；z j i 和d d a s g u p t a 还对非选择算法中检测器的非我空间覆盖面和覆盖能力进行了研究 【3 0 】：l j g o n z a l e z 提出了一种用于异常检测的自适应的可进化非选择算法，该 算法利用自适应方法来调节检测器集合进化过程中的变异概率【3 1 】；文献【3 2 】提 出了一种检测器的自适应生成算法，能够根据实际情况不断地对检测器集合进行 调整，对各种异常检测问题都具有一定的适用性；张衡等人提出了一种，可变非 选择算法，其中每个检测器都带有一个独立的部分匹配阈值，不同检测器的匹配 阈值可以不同，从而增加了检测器集合的非我空间覆盖率，减少了“洞”的存在 3 3 】；针对“洞”的问题，文献【3 4 】提出了一种厂刚 选择算法( ，口n s a ) ，其中 的每个检测器都拥有一个部分匹配阈值数组，用来存储自检测器的每一位开始算 起的部分匹配阈值，从而扩大了单个检测器的非我空间覆盖面，而且能够解决 “洞”的问题；文献 3 5 】提出了一种海明距离部分匹配规则下的启发式的检测器 生成算法；通过借鉴a va h o 和m j c o r a s i c k 的多模式匹配算法 3 6 】，文献 3 7 】 提出了一种基于状态图的快速非选择算法，使得输入字符串与检测器集合之间的 匹配操作的时间复杂度大为降低；何中等人提出了一种检测器长度可变的非选择 算法，其中每个检测器都拥有独立的字符串长度，且不同检测器的长度可以不同， 从而可以消除“洞”的存在，并且能够明显减少冗余检测器的数量 3 8 】；在文献 【3 9 】中，z j i 和d d a s g u p t a 回顾了非选择算法的发展历程，并依照几个不同的 标准对不同的非选择算法进行了分类比较。 ( 2 ) 克隆选择算法 以f m b u m e t 提出的克隆选择学说( c l o m ls e l e c t i o nt h e o r y ) 6 】为基础， l n d c a s t r o 和f j vz u b e n 提出了克隆选择算法c l o n a l g 1 6 ，1 7 】，可以用 于解决学习，优化和模式识别问题。该算法具有种群大小的动态调节能力，全空 间搜索能力，以及多个最优解的定位能力等多种有价值的特性。 关于克隆选择算法的后续研究很多，如j k i m 和p j b e n t l e y 提出了动态克 隆选择算法( d y n a 血cc l o n es e l e c t i o na l g o r i t h m ) 用于进行网络入侵检测 4 0 】， 并对其免疫记忆特性进行了研究【4 1 ，4 2 】；杜海峰和焦李成等人提出了自适应动 态克隆选择算法( a d a p t i v ed y n a m i cc l o n es e l e c t i o na l g o r i l h m ) 【4 3 】，等等。 7 第1 章绪论 ( 3 ) 人工免疫网络 n k j e m e 提出的独特型网络学说( i d i o t y p i cn e 咖r kt h e o 拶) 认为生物免 疫系统通过一个由相互连接的抗体组成的独特型网络( i d i o 妙p i cn e t w o r k ) 来对 入侵的抗原进行应答，同时保持免疫系统的动态稳定【7 】。n k j e m e 的独特型网 络学说 7 】以及对免疫网络学说的后续研究工作，包括j d f a m l e r 等人的工作 9 】， f j v 缸e l a 等人的工作 1 0 】以及a s p e r e 】s o n 等人的工作f 4 4 ) 等，奠定了人工免 疫网络模型( a n i f i c i a li m m u n en e t w o r k ：a i n ) 的理论基础。 j e h u n t 和d e c 0 0 k e 于1 9 9 6 年提出了一种人工免疫网络模型，用于进 行d n a 序列的模式识别【1 8 】；j t i m m i s 等人以j e h u n t 和d e c o o k e 的模型 为基础，针对数据分析问题，于2 0 0 0 年提出了址n e ( a n m c i a li m m u n en e t w o r k ) 网络模型【4 5 】，于2 0 0 1 年提出了资源受限的人工免疫系统模型并引入了人工识 别球( a n i n c i a lr e c o g n i t i o nb a l l ：a r b ) 的概念 4 6 】：与j e h u n t 和d e c o o k e 的模型有关的后续工作还有文献 4 7 5 0 】等。ln d c a s t r o 和fj vz u b e n 在2 0 0 1 年提出了a j n e t 人工免疫网络模型，用于进行数据分析 1 9 】；与a i n e t 模型有关的 工作还有【5 1 5 4 】等。另外，日本宫崎大学的z t 觚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 km o d e l ) 【5 5 ，5 6 】；j c g a l e a n o 等人在论文 5 7 】中对不同的人工免疫网络模型做了比较。 ( 4 ) 其他研究热点 随着人工免疫系统研究领域的不断深入和扩展，生物免疫学中的原理正在被 越来越多地借鉴并且应用于智能算法、模型的研究中。例如，生物免疫学中的危 险理论【5 8 】已经开始被人工免疫系统研究所借鉴，并且被应用于入侵检测和故障 检测中 5 9 6 1 1 ；j g r e e n s m i t h 等人通过模拟生物免疫系统中的树状细胞的功能， 提出了树状细胞算法( d e n d r i t i cc e l la l g o r “h m ) 6 2 ，6 3 ，该算法已经逐渐成为 人工免疫系统研究领域中的主要算法之一；而a t a r a k a j l o v 和d d a s g u p t a 提出 了用于并行处理大批量数据的免疫芯片( i m m u n o c h i p ) 的体系结构设计【6 4 1 。 随着人工免疫系统研究的发展，人工免疫系统的算法和模型与计算智能领域 中的其他算法和模型发生了结合，并且成为了新的研究热点。 进化算法( e v o l u t i o n a r ya l g o r i t h m ：e a ) 【6 5 ，6 6 】作为一类随机搜索的优化方 法，具有通用性、便于并行处理等优点，得到了广泛的研究和应用。近年来，人 工免疫算法与进化算法的结合成为了一个研究热点，国内研究者在此方面进行了 卓有成效的工作。中国科学技术大学以王煦法教授为首的研究组在国内率先开展 了关于人工免疫系统的研究工作，并且开展了免疫学原理与进化算法相结合的研 究工作。王煦法教授等人于1 9 9 9 年将免疫原理与遗传算法 6 7 】相结合，提出了 一种基于免疫原理的遗传算法，即免疫遗传算法( i m m u n eg e n e i ca j g o r j h l ： 8 第l 章绪论 i g a ) 【6 8 】。i g a 算法的主题思想有两点：( 1 ) 在g a 中，将进化个体对应为免 疫系统中的抗体，通过抗体的浓度调节机制，在确保群体收敛性的同时维持抗体 的多样性，提高遗传算法的全局搜索能力；( 2 ) 利用生物免疫系统的记忆特性， 对系统已经碰到过的相似的问题，加快搜索速度，提高遗传算法的总体搜索能力 6 8 】。曹先彬教授等人提出了基于免疫网络调节的改进遗传算法( i d i o t ) r p i c n e t 、) r o r kr e g u l a t i o n b a s e dg e n e t i ca l g o r i t h m s ：i n r g a ) 6 9 】，一种免疫进化策略 【7 0 】，以及一种基于免疫识别的免疫优化算法【7 1 ，7 2 】；刘克胜等人将免疫优化算 法应用于t s p 问题求解 7 3 】：文献 7 4 】提出了基于免疫调节机制的免疫遗传算法； 文献【7 5 】将免疫遗传算法应用于求解频率分配问题：文献【7 6 7 8 】对进化非选择算 法( e v o l u t i o n a 巧n e g a t i v es e l e c t i o na l g o r i t h m s ：e n s a ) 进行了研究。诺瓦东南 大学( n o v as o u m e a s t e mu n i v e r s 砖) 的l j g o n z a l e z 等人针对异常检测问题提 出了自适应的演化的非选择算法 3 1 】。同时，西安电子科技大学以焦李成教授为 首的研究组也对免疫学原理与进化算法的结合进行了研究。焦李成教授等人于 2 0 0 0 年提出了一种免疫遗传算法【7 9 】，提出利用先验知识和引入免疫算子来解决 传统遗传算法中出现的退化现象，并且加快收敛速度 8 0 ，8 1 】；刘若辰等人将克 隆选择学说应用于对进化策略( e v o l u t i o n a r ys t r a t eg ) ，：e s ) 的改进，提出了免疫 单克隆策略算法【8 2 】和免疫多克隆策略算法 8 3 】；焦李成教授等人还出版了专著 8 4 。 人工神经网络( a n i f i c i a ln e u r a ln e t w o r k s ：砧叮n ) 也是计算智能研究领域的 一个主要分支。近年来也出现了人工免疫系统与人工神经网络的结合研究工作， 例如l n d c a s t r o 等人的 8 5 ，8 6 】，d h k i m 等人的 8 7 】，和yz h o u 等人的 8 8 】 等。人工免疫系统研究也与数据挖掘研究发生了结合，如f g o n z a l e z 等人将非 选择算法和分类算法相结合用于异常检测 8 9 】，屈建平等人用k 均值聚类算法对 非选择算法进行了改进 9 0 】，刘静等人提出了一种免疫进化聚类算法【9 1 】。 现在，人工免疫系统的研究和应用已经延伸至多个领域，包括优化问题求解 5 3 ，6 8 ，7 0 7 3 ，7 5 ，7 7 7 9 ，8 4 ，9 2 9 4 】，信息安全 4 ，2 6 ，4 0 ，6 0 ，9 5 一1 0 7 】，容错和故障 检测【6 1 ，1 0 8 - 1 1 5 】，数据挖掘 4 5 ，4 6 ，4 8 ，4 9 ，5 1 ，9 1 ，1 1 6 ，1 1 7 】，机器人控制【1 0 7 ， 1 1 8 1 2 0 】，模式识别【1 8 ，5 5 ，5 6 ，1 2 1 】等。中国科学技术大学王煦法教授领导的研 究小组在人工免疫系统的优化问题求解和网络安全应用方面都开展了研究工作 【4 ，6 8 ，7 0 - 7 3 ，7 5 ，7 7 ，7 8 ，9 3 ，9 4 ，9 9 - 1 0 2 ，1 0 6 ，1 0 7 ，1 2 2 】。 1 2 硬件免疫系统概述 硬件免疫系统( h a r d 、v a r ei n u i l u n es y s t e m ：h w i s ) 是受生物免疫系统启发而 9 第1 章绪论 建立的种新的硬件容错( h a r d w a r ef a u l tt 0 l e r a n c e ) 实现途径，是一种新的硬 件故障检测方法 1 0 9 】。它将人工免疫系统中的模型和算法应用到硬件容错研究 1 2 3 ，1 2 4 】中来，为复杂电路系统的故障检测提供新的模型和算法。硬件免疫系 统是人工免疫系统研究中一个较年轻的分支，近年来开始收到关注。 1 。2 1 已有的故障检测技术概述 故障检测( f a u i td e t e c t i o n ) 技术是数字系统设计领域中的一个重要研究方 向，是实现容错( f a u l tt o l e r a n c e ) 的关键一环【1 2 3 ，1 2 4 】。因为在一个数字系统 中，只有首先检测到故障的发生，才有可能采取补救措施来减小和消除故障的影 响。已有的硬件电路故障检测方法可以分为离线故障检测和在线故障检测两大 类。离线的故障检测方法主要是指故障测试技术f 1 2 5 】，本文的研究不涉及。随 着硬件电路系统规模和复杂性的不断增加，系统可靠性下降的同时，故障检测尤 其是在线的检测越来越困难。本文所讨论的硬件免疫系统的模型与算法所针对的 就是复杂数字时序电路的在线故障检测问题。 在已有的在线故障检测方法中，应用广泛的检错码( e 肿r - d e t e c t j n gc o d e ) ， 纠错码( e r r o r - c o r r e c t i n gc o d e ：e c c ) ，n 模冗余( n m o d u l a rr e d u n d a n c y ：n m r ) 【1 2 4 】等属于传统的线故障检测技术；在线的内建自测试( b u i l t i ns e l f - t e s t ：b i s t ) 是一种专门针对现场可编程门阵列( f i e l dp r o g r a m m a b l eg a t ea r r a y ：f p g a ) 的 在线故障检测方法 1 2 6 i 基于信号处理的方法如小波分析等也得到了应用 【1 2 7 1 3 0 ；近年来，随着复杂非线性系统故障检测和诊断的需求的增加，神经网 络，专家系统和模糊逻辑等人工智能理论也在复杂系统的在线故障检测和诊断中 得到了研究和应用 1 2 9 1 3 4 】。 在己有的在线故障检测方法中，检错码技术应用广泛且实现简单，但检测能 力有限；n 模冗余方法虽然可靠，但是实现代价较大；在线b i s t 只适用于拥有 运行时增量重配置能力的f p g a 芯片的故障检测，适用面小；基于神经网络，专 家系统和模糊逻辑等人工智能理论的方法虽然为故障检测开辟了新的途径，但不 易用硬件实现。硬件电路系统的在线故障检测需要新的理论和技术来满足以下几 个要求：( 1 ) 能够适应实际应用环境；( 2 ) 有足够的故障覆盖率；( 3 ) 硬件实现 代价合理。 1 2 2 免疫电子学概念的提出 从故障检测的角度来讲，生物免疫系统在生物体内所发挥的抗原识别作用正 类似于在线的故障检测，其检测的对象是外来的入侵抗原，如细菌和病毒等。1 9 9 9 i o 第l 章绪论 年，英国y o r k 大学的a m t y r r e u 教授在文章 1 3 5 】中从免疫学的角度审视了计 算机系统的容错问题。他认为，生物免疫系统是一个非常出色的容错系统，它能 够检测到入侵的抗原并将其清除，从而保持正常运行 1 3 5 。a m t y r r e l l 相信， 生物免疫系统的很多特点和机制应该可以被计算机系统的设计所借鉴，从而提高 计算机系统的可靠性【1 3 5 】。他将硬件电路系统抽象为有限状态机( f i n i t es t a t e m a c h i n e ：f s m ) ，并列举出了生物免疫系统与硬件电路系统在容错方面的诸多相 似特征，如表1 1 。基于这些相似性，a m t y r r e u 设想将生物免疫系统中的“自 我一非我识别的概念引入到容错计算机系统的设计中，从而设计出拥有类似于b 细胞的异常检测功能和类似于t 细胞的错误恢复功能的免疫计算机系统 1 3 5 】。 在1 9 9 9 年发表的这篇论文中，a m t y 玎e u 第一次提出了i m m u n o t r o n i c s ( 即 i n u n u n o l o g i c a le l e c t r o n i c s 的简称) 这个新概念，也就是“免疫电子学 【1 3 5 】。 硬件免疫系统的研究由此为硬件系统的容错设计指出了一条新的途径。 表1 1 生物免疫系统与硬件电路系统在容错