（模式识别与智能系统专业论文）人工免疫算法及sopc实现.pdf

哈尔滨1 _ 程大学硕+ 学位论文 摘要 s o p c ( s y s t c mo np r o g r a m m a b l ec h i p ，片上可编程系统) 是a l t e r a 公司提 出的一种灵活、高效的s o c 解决方案。它将处理器、缓存、存储器、i o 口、 高速总线等系统设计需要的功能模块集成到一个f p g a 器件上，构建成一个 可编程的片上系统。它是可编程系统，具有灵活的设计方式，可裁减、可扩 充、可升级，并具备软硬件在系统可编程的功能。 入工免疫算法是目前新兴的一种智能方法，它是以生物免疫系统的功能、 特点和作用机理为基础而设计出的计算模型。它具有很强的学习、识别、记 忆和特征提取的能力，能够解决传统计算方法难于解决的许多复杂问题，因 而近年来成为研究的热点，并在诸多领域中得到了广泛的应用。 本文运用免疫算法对t s p 问题和函数优化问题进行了研究，针对现有算 法中存在的不足之处进行了改进，最终在s o p c 上进行了实现。 首先，针对课题需要，确定系统包括f p g a 、s d r a m 、f l a s h 、复位 按钮、4 个7 段数码管、串口资源。接着编制硬件平台，进行全编译和系统 优化，最终将硬件设计下载到目标板上。 其次，针对t s p 问题，在信息熵免疫算法基础上，对编码方式、交叉算 子、变异算子进行了改进，同时加入了预处理。针对函数优化问题，在免疫 克隆算法的基础上，采用二进制编码，将该函数的值空间映射到位串空间中， 然后在位串空间进行免疫克隆选择操作，结果通过解码过程还原成数值解再 进行亲和力评估。 实验表明无论是处理9 城市的t s p 问题，u l e y s s e s l 6 问题还是函数优化 问题，免疫算法在s o p c 上能更快得到全局最优解并且算法均具有抗退化能 力。含有智能算法的s o p c 系统具有较高的技术含量，很强的实用性和巨大的 市场潜力，为向功能多、体积小、重量轻、使用方便的掌上型仪器奠定基础。 关键词：人工免疫算法；片上可编程系统；信息熵免疫算法；免疫克隆算法 哈尔滨工程大学硕+ 学位论文 a b s t r a c t s o p ci sak i n do ff l e x i b l ea n de f f i c i e n ts o cs o l u t i o nd e v e l o p e db ya l t e r a i n t e g r a t i n gp r o c e s s o r ，c a c h e ，m e m o 巧，i 0p o r ta n dh i g h s p e e db u si n t oas i n g l e f p g ac h i p ，s o p cb o a s t so fa d v a n t a g e ss u c ha sf l e x i b l ed e s i g n i n g ，t a i l o r a b l e ， e x t e n s i b l e ，u p g r a d e a b l ea n ds o f t w a r e h a r d w a r ep r o g r a m m a b l e a r t i f i c i a li m m u n ea l g o r i t h m ，a ne m e r g i n gi n t e l l i g e n tm e t h o d ，i sac a l c u l a t i o n m o d e ld e s i g n e do nt h eb a s i so fb i o l o g i c a li m m u n es y s t e m sf u n c t i o n s ，f e a t u r e s a n dm e c h a n i s m s w i t hs o u n dp e r f o r m a n c ei ns t u d y ，r e c o g n i t i o n ，m e m o r i z a t i o n a n dc h a r a c t e re x t r a c t i o n ，i tc a ns o l v em a n yc o m p l e x p r o b l e m st h a ta r ed i f f i c u l tf o r t r a d i t i o n a la l g o r i t h m s t h e r e f o r e ，a i sh a sb e c o m ear e s e a r c hf o c u si nr e c e n ty e a r s a n dh a sb e e nw i d e l ya p p l i e di nm a n yf i e l d s i n t h ep a p e r ，i m m u n ea l g o r i t h mi sa p p l i e di ns o l v i n gt s pp r o b l e ma n d f u n c t i o no p t i m i z a t i o n s o m ei m p r o v e m e n t sa r em a d eo nt h ea l g o r i t h ma c c o r d i n g t ot h ep r o b l e m sa r i s i n ga n dt h e ni m p l e m e n t e do ns o p c f i r s t l y ，t om a k es u r et h ec o m p o s i t i o no ft h es y s t e mt h a ti n c l u d e sf p g a ， s d r a m ，f l a s h ，r e s e t t i n gb u t t o n ，4s e v e n - s e g m e n tn i x i et u b e sa n ds e r i a l r e s o u r c e t h e nt h eh a r d w a r ep l a t f o r mi se s t a b l i s h e da n dt h eh a r d w a r ed e s i g n i n gi s d o w n l o a d e dt ot h et a r g e tb o a r da f t e rw h o l ec o m p i l i n ga n ds y s t e mo p t i m i z a t i o n s e c o n d l y ，o nt h eb a s i so fi n f o r m a t i o ne n t r o p yi m m u n ea l g o r i t h ma n d c o n s i d e r i n gt h ef e a t u r e so ft s pp r o b l e m ，c o d i n gm e t h o d ，c r o s so p e r a t o ra n d v a r i a t i o no p e r a t o ra r ei m p r o v e da n dp r o - p r o c e s s i n gm e c h a n i s mi si n t r o d u c e d w h i l e i ns o l v i n gf u n c t i o no p t i m i z a t i o np r o b l e m ，o nt h eb a s i so fi m m u n ec l o n e a l g o r i t h m ，b i n a r yc o d i n gi sa d o p t e dt om a pt h ev a l u es p a c et ob i ts t r i n gs p a c e w h e r e i ni m m u n ec l o n es e l e c t i o ni s c o m p l e t e d t h er e s u l t i sr e d u c e dt ot h e n u m e r i c a ls o l u t i o nt h r o u g hd e c o d i n gf o ra f f i n i t ye v a l u a t i o n t h ee x p e r i m e n td e m o n s t r a t e st h a ts o p c ，w i t hl e s sr e s o u r c et h a np c ，y i e l d s 哈尔滨i ：程大学硕十学位论文 ab e t t e rp e r f o r m a n c ei ns o l v i n g9 - c i t yt s pp r o b l e m ，u l e y s s e sl6p r o b l e ma n d f u n c t i o no p t i m i z a t i o np r o b l e mi nt e r m so fs p e e da n dd e g r a d a t i o nr e s i s t a n e e a n s o p cs y s t e mi n t e g r a t i n gi n t e l l i g e n ta l g o r i t h m si sv e r yp r a c t i c a la n dh o l d sg r e a t m a r k e tp o t e n t i a l ，l a y i n gd o w ng r o u n d f o rt h ep r o d u c t i o no fc o n v e n i e n tp a l m i n s t r u m e n tt h a tf e a t u r e sm u l t i f u n c t i o n ，s m a l lv o l u m ea n dl o ww e i g h t k e yw o r d s ：a r t i f i c i a li m m u n ea l g o r i t h m ；s o p c ；i n f o r m a t i o ne n t r o p yi m m u n e a l g o r i t h m ；i m m u n ec l o n ea l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：象尉f 日期： 皮c 年弓月c 口日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 班授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：礁壮 日期：6 汹c i 年3 月，o 日 导师( 签字) ：茗私佛 泐c i 年? 月，护日 哈尔滨工程大学硕+ 学位论文 1 1 研究背景及意义 第l 章绪论 本课题以人工免疫算法的研究及其在s o p c 上的实现为背景，解决旅行 商问题和多峰值函数优化问题。 旅行推销员问题( 简称t s p ) 于1 9 3 2 年由k m e n g e r 提出以来，己引起各 领域许多研究者的兴趣。它是组合数学中一个古老而又困难的问题，也是组 合优化中研究最多的问题之一，但至今尚未彻底解决。其描述为一推销员要 到若干城市推销货物，从某一城市出发，经过其余各城市一次且仅一次，然 后回到出发点，求其最短行程。有许多问题都可以归结为t s p 问题，如电路 板钻孔路线选择【l 】、车辆路线问题f 2 】、计划任务，】、连锁店货物配送路线f 4 】、管 道铺设、火炬接力等问题。 多峰函数优化问题，传统的基于导数或其它启发式信息的搜索算法( 如梯 度爬山法，模拟退火方法等) ，均存在着如何避免陷于局部极值点，发现全局 最优解的问题。此类函数用于测试智能算法优越性，函数在最优解附近有许 多局部最优解干扰算法搜索，对于般的智能算法搜索较困难。 本课题所研究的硬件平台的设计和软件开发是人工免疫算法及s o p c 实 现的关键技术。对于硬件平台设计而言，在满足系统需求的前提下，某些需 要的功能既可以用软件也可以用硬件实现，最终采用什么方式需要根据系统 设计要求权衡。软件开发环节容易修改或是增删，查错也比较容易。另外采 用s o p c 技术能有效缩短研发周期，对产品升级都有很大的促进作用。 本课题研究的意义在于，s o p c 所具有的资源很少，利用免疫算法处理较 复杂的旅行商问题和函数优化问题，能够迅速得到全局最优解，避免陷于局 部极值点。含有智能算法的s o p c 系统具有较高的技术含量、很强的实用性和 巨大的市场潜力，也代表了当代电子仪器的一种发展趋势，为向功能多、体 积小、重量轻、使用方便的掌上型仪器奠定基础。 一一 一 哈尔滨工程大学硕士学位论文 m l 1 2 人工免疫算法的发展现状 生物免疫系统是一种具有高度分布性的自适应的学习系统，它具有完善 的机制来抵御外来病原体的入侵。由于生物免疫系统具有强大的信息处理能 里，尤其是能够在完全并行和分布的方式下实现复杂的计算。 1 9 7 4 年，美国诺贝尔奖获得者，生物学家、医学家、免疫学家j e m e 提 出的免疫网络理论引起各方关注i 5 l 。继该文之后，f a r m e r 、p e r e l s o n 、b e r s i n i 、 v a r e l a 等理论免疫学者分别在1 9 8 6 和1 9 8 9 年、1 9 9 0 年发表了有关论文，在 免疫系统启发实际工程应用方面奠定了基础【6 - 9 1 ，其中f a r m e r 关于免疫系统 与机器学习的研究是具有创造性和开拓性的工作，是第一个可以用于工程领 域的人工免疫模型。 且前关于人工免疫系统的研究成果主要涉及计算机安全、数据挖掘、机 器人、异常和故障诊断、优化、模式识别、机器学习、分子生物学、图像处 理、集体智能、自动控制等领域。 免疫算法研究重点集中在以下几方面t l o l 【- t l ： 1 免疫算法的有效性评价；目前的免疫算法多种多样，应用范围也很广 泛，一般在研究中只与有限的其他算法在某一个问题上比较其性能，缺乏全 面、有效的评价指标和体系。虽然免疫算法也是面向问题的，但过于多样化 的算法性能不利子免疫算法的持续发展。我们需要探索出一般的理论，以与 其他算法在理论上证明其针对某一领域的问题的有效性。 2 并行免疫算法：并行性是免疫系统的内部机理。与遗传算法、人工神 经网络等计算智能方法相比，免疫算法同样应该具有强大的并行计算特性。 深入研究并挖掘免疫算法的并行特性，相信会为大规模并行算法和并行计算 机的研究提供一种强大的支持，在组合优化求解方面，算法的并行性也将会 为n p 问题找到新的有效求解途径，对突破冯氏计算结构也有很大帮助。并行 免疫算法需要在免疫并行处理机制、编码方式、通信接口、计算复杂性以及 基于现代计算机或者其他计算硬件结构设计方面开展研究。 3 免疫算法在网络系统等复杂系统中的应用。比如，由于免疫系统与神 经网络和内分泌网络互相影响，网络智能将成为免疫算法应用的新方向。再 2 一 哈尔滨t 程大学硕士学位论文 嗣薯宣宣宣i i 宣暑暑i i 暑皇置i 宣昌昌i 宣i 宣i i i i ；i - 二二二i 二= 二二_ 毫薯i i 宣宣宣i 暑 者，免疫算法能增强复杂系统的鲁棒性，而且免疫性与鲁棒性之间存在的必 然联系使得免疫算法将在鲁棒系统中得到较好的应用。 1 3 嵌入式系统的发展现状 嵌入式系统是嵌入到对象体系中的专用计算机系统。i e e e ( 国际电气和 电子工程师协会) 对嵌入式系统的定义为：嵌入式系统是“用于控制、监控 或者辅助操作机器和设备的装置”。目前国内普遍认同的嵌入式系统的定义 为：以应用为中心，以计算机技术为基础，软硬件可裁剪，对功能、可靠性、 成本、体积、功耗等有严格要求的专用计算机系统。 从2 0 世纪7 0 年代单片机的出现到今天各种各样的嵌入式处理器、微控制 器的大规模应用，嵌入式系统已有了近3 0 年的发展历史，其主要的发展阶段 有： 第一阶段是无操作系统的嵌入算法阶段，以单芯片可编程控制器为核心 的系统，同时具有与监测、伺服、显示设备相配合的功能。这种系统大部分 应用在一些专业性极强的工业控制系统中，一般没有操作系统的支持，通过 汇编语言编程对系统进行直接控制。这一阶段系统的主要特点是：系统结构 和功能都相对单一，存储容量较小，几乎没有用户接口。由于这种嵌入式系 统使用简便、价格很低，以前在国内工业领域应用较为普遍，但是已经远远 不能适应高效的、需要大容量存储介质的现代化工业控制和新兴的信息家电 等领域的需求。 第二阶段是以嵌入式c p u 为基础、以简单操作系统为核心的嵌入式系统。 这一阶段系统的主要特点是：c p u 种类繁多，通用性比较弱，系统开销小， 效率高：操作系统具有一定的兼容性和扩展性；应用软件较专业，用户界面 不够友好；系统主要用来控制负载以及监控应用程序运行。 第三阶段是以嵌入式操作系统为标志的嵌入式系统。这一阶段系统的主 要特点是：嵌入式操作系统能运行于不同类型的微处理器上，兼容性好；操 作系统内核小、，效率高，并且具有高度的模块化和扩展性；具有文件和目录 管理、设备支持、网络支持、图形窗口以及用户界面等功能：具有大量的a p i ( 应用程序接e 1 ) ，开发应用程序简单；嵌入式应用软件丰富。 哈尔滨下程大学硕士学位论文 第四阶段是以网络技术为标志的嵌入式系统，是一个正在迅速发展的阶 段。随着网络控制技术与信息家电、工业控制技术等结合日益密切，嵌入式 设备与网络技术的结合将代表着嵌入式技术的真正未来。 1 4 本文的结构安排 本文在阅读大量文献的基础上，首先有针对性的介绍了生物免疫系统的 一些概念、系统组成、功能原理及其其对人工免疫原理的启示；同时概述了 人工免疫系统的主要研究内容和应用，并将其与其他方法进行了比较。其次， 介绍了嵌入式系统的分类和基本要求；同概述了基于n i o sn 软核s o p c 系统 构架，及s o p c 设计流程。最后编制系统硬件平台，在此平台上，运用信息 熵免疫算法处理t s p 问题和免疫克隆算法解决函数优化问题。 全文共分五章，具体安排如下： 第一章简述了人工免疫系统应用和嵌入式系统的现状，分析了将人工免 疫算法应用于s o p c 上的原因，在此基础上给出了本文的主要研究内容。 第二章简要介绍了生物免疫系统的基本概念、主要构成及功能，在此基 础上详细介绍了人工免疫系统的一些仿生机理、研究内容及主要应用，并将 其与人工神经网络、进化计算等进行了比较。 第三章首先阐述了嵌入式系统理论，然后描述了基于n i o s l l 软核的 s o p c 系统构架、详细叙述了s o p c 技术、n i o s l i 软核处理器的分类和特征、 a v a l o n 总线的规范，i pc o r e 概念、s o p c 设计的流程。 第四章首先介绍了s o p c 系统硬件构成，分析个硬件模块的电路原理及 功能。在此基础上，针对课题需要完成对硬件平台的设计，为软件开发提供 支持。 7 第五章简要介绍了两种的免疫算法( 信息熵免疫算法和免疫克隆算法) ， 分别讨论了算法的优点与不足，针对信息熵免疫算法和t s p 问题特点，在编 码方式，亲和力大小，交叉算子和变异算子上做出了相应的改进。在处理函 数优化时，在免疫克隆算法的基础上，针对其特点，采用二进制编码，并将 该函数的值空间映射到位串空间中，然后在位串空间进行免疫克隆选择操作。 两种算法最终在s o p c 上进行了实现。 4 哈尔滨t 程大学硕士学位论文 第2 章人工免疫系统 生物免疫系统所具有的多样性、耐受性、免疫记忆、分布式并行处理、 自学习、自适应和鲁棒性的特点，激发人们探索其运行机理，并构造人工免 疫系统来模拟生物免疫系统的优良特性。研究生物免疫系统的科学就是医学 免疫学。一些免疫学专家在理论免疫学方面己经做了许多深入的研究，用数 学描述免疫系统的运行原理、机制，各种分子、组织和器官之间的相互作用， 建立了许多免疫学理论，有一些已被实验免疫学所验证，有些则存在争议， 但没有妨碍人工免疫系统的发展，生物免疫系统的许多性质启发了计算机科 学家利用生物免疫系统机制解决工程和科学问题。 2 1 生物免疫系统 2 1 1 生物免疫系统的基本概念 。为了便于更好地理解生物免疫系统的主要功能和作用机制，先介绍一下 免疫系统中的一些基本概念啕。 ( 1 ) 免疫 免疫系统收到外来病毒或分子刺激后产生的一系列复杂变化，免疫 ( 硫m u n i 妫是机体对“自己”和“异己( 非己) ”识别、应答过程中所产生的生物学 效应的总和，正常情况下免疫应答的结果对机体有利，起到免疫保护、免疫 稳定和免疫监视等生理性保护。在免疫缺陷及功能失调或免疫应答过程不足 时，则造成病理损伤或超过敏反应。 ( 2 ) 抗原 抗原( a n t i g e n ) 是指能刺激机体机体免疫系统引发免疫应答而产生抗体和 ( 或) 致敏淋巴细胞，并能与之发生特异性结合而产生免疫效应的物资。抗 原不是免疫系统的有机组成部分，但是免疫应答的始动因子。抗原具有两个 重要特性：一是免疫原性( i m m u n o g e n i c i t y ) ，指抗原进入免疫机体后能够促使 机体产生抗体或刺激淋巴细胞产生免疫应答的特性；另一个是特异反应性 ( s p e c i f i cr e a c t i v i t y ) ，指抗原能够与抗体特异性结合的特性，这种结合反应的 5 一 哈尔滨工程大学硕士学位论文 特异性可能是生物学中已知的最特异的反应。 ( 3 ) t 细胞 t 淋巴细胞在胸腺中成熟，功能包括调节其他细胞的活动以及直接袭击 宿主感染细胞。t 细胞可分为毒性t 细胞和调节t 细胞两类。而调节t 细胞 又可分为辅助性t 细胞和抑制性t 细胞。辅助性t 细胞的主要作用是激活b 细胞，与抗原结合时分泌作用于b 细胞并帮助刺激b 细胞的分子。毒性t 细胞能够清除微生物入侵者、病毒或者癌细胞。 ( 4 ) b 细胞 b 淋巴细胞来源于骨髓淋巴样前体细胞，成熟的b 细胞存在子淋巴结、 血液、脾、扁桃体等组织和器官中。b 细胞是体内产生抗体的细胞，在清除 病原体过程中受到刺激，分泌抗体结合抗原，但其发挥免疫作用要受t 辅助 细胞的帮助。 ( 5 ) 抗体 抗体是b 细胞接受抗原刺激后，所分泌的具有免疫功能，并能与抗原发 生特异性结合的免疫球蛋白。抗体可分为分泌型和膜型，前者主要存在于血 液及组织液中，发挥各种免疫功能；后者构成b 细胞表面的抗原受体。 ( 6 ) 免疫记忆 免疫系统的一个重要特征是好交往性，它不仅能记忆已出现抗原的结构， 而且对相同抗原的再次入侵或相似抗原的出现做出快速的反应，能成功地毁 灭被识别的抗原。免疫记忆是免疫系统的重要特性，有助于加快再次免疫应 答过程。 ( 7 ) 亲和力 亲和力是抗体的表位与抗原的对位的匹配程度。 2 1 2 生物免疫系统组成和结构分析 免疫系统是一种由众多细胞、分子和组织等子系统构成的复杂系统，这 些子系统之间存在着复杂的相互联系，具有能识别“自己 和“非已”，清除和 消灭异物的功能。免疫系统的结构要素如图2 1 所示，此系统由先天性免疫 系统和自适应免疫系统组成。先天性免疫系统是一种与生俱有的天然防御系 统，不具有特异性，具有识别一定微生物和立即摧毁这种微生物的能力。它 6 哈尔滨工程大学硕士学位论文 包含一种被称为补体的血蛋白质，这能帮助和增加抗体的活动能力，尤其是 首次遇上的许多传染物质( 抗原) 。这种系统的主要作用在于能辨析自我和非 自我，参与自我和非自我辨析，对推动自适应免疫起着重要的作用。自适应 免疫系统是后天形成的一种防御系统，能自适应学习外来入侵病毒物质或分 子的模式结构，清除或中立这种分子或物质。 免疫系统具有较强的免疫防御功能，即免疫防护、免疫稳定及免疫监视。 其中免疫防护具有抗病原侵袭的作用；免疫稳定具有消除损伤或衰老细胞及 免疫调控的作用；免疫监视具有消除癌变细胞或病毒感染细胞的功能。免疫 的目标是摧毁来自外界的细菌或其他的入侵者。 免疫系统 ，f 骨髓 f 中枢免疫器官 胸腺 免疫器官11 法氏朗 【外周免疫器官 ，rt 淋巴细胞 f 免疫活性细胞tb 淋巴细胞 免疫细胞 第三群细胞 lr 抗原呈递细胞 l 免疫辅佐细胞t 巨细胞 免疫分子j 补体 r 抗体 l 单核 l 淋巴因子 图2 1 免疫系统的组成 在抗原激励下，免疫系统的运行机制可简要地归纳为以下四步，图形描 述如图2 2 所示。 ( 1 ) 巨噬细胞分化抗原为颗粒状物质，主要组织性相容性物质与这种颗粒 状质结合形成粘液物质，抗原呈递细胞将这些物质呈递到巨噬细胞的表面。 ( 2 ) 通过识别的途径，被激活的t 细胞分化和分泌淋巴因子或化合物质信 号，并驱动免疫系统的b 细胞应答。 ( 3 ) b 细胞对来自激活的t 细胞的信号作出反应，但不像t 细胞那样，b 细胞能自由地识别部分抗原。即使无t 细胞的作用，b 细胞仍对抗原作出反 应，t 细胞仅对b 细胞应答抗原起到调控作用。 7 兰竺二年 甓燃卜l 亘递细胞作用抗原r 卜- 上1呈型塑! t 细胞受体识别1jb 细胞应答ii 无应答b 细胞 t 细胞分化淋巴因子i i 克隆选择 i 重构ij 中立ii 被清除 淋巴因子激活b 细胞i 细胞繁殖及分化h 向记忆细胞分化 翌奎三箜竺翌h 查塑些垫 t 骊嗣除抗原l 图2 2 免疫系统的运行机制 ( 4 ) 当b 细胞被激活时，b 细胞就分化和繁殖，这种细胞能分泌出抗体蛋 白质，这些抗体能游离出来。抗体通过缠住已发现的抗原，并中立这些抗原 以至毁灭它们，其他多余的t 细胞和b 细胞变为记忆细胞。 2 1 3 免疫应答 免疫应答( i m m u n er e s p o n e ) 是指抗原进入机体后，免疫细胞对抗原分子的 识别、活化、分化和效应过程。这一过程是免疫系统各部分生理功能的z l l 主 要有两种类型：一种是遇病原体后，固有免疫系统首先产生的迅速而短时间 的应答，即固有性免疫应答( i n n a t ei m m u n er e s p o n s e ) t 3 j ；另一种就是适应性免 疫系统产生的适应性免疫应答( a d a p t i v ei m m u n er e s p o n s e ) 0 4 1 。 固有免疫应答是固有免疫系统执行固有免疫功能的结果，适应性免疫应 答的执行者是前面介绍的t 及b 淋巴细胞，故又称为抗原特异性免疫应答 ( 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 ) t 1 5 】。 适应性免疫应答又分为初次和二次免疫应答，如图2 3 所示。初次免疫 应答发生在免疫系统遭遇某种病原体第一次入侵时。此时免疫系统产生大量 抗体，帮助清除体内抗体。在初次免疫应答后免疫系统首次遭遇异体物质并 将其清除体外，但免疫系统中仍保留一定数量的b 细胞作为免疫记忆细胞， 8 哈尔滨工程大学硕士学位论文 这使得免疫系统能够在再次遭遇同种异物后能快速反应并反击抗原，这个过 程称为二次免疫应答。 抗体 图2 3 免疫应答示意图 出现在二次应答中的抗体一般比初次应答出现的抗体对抗原具有更高的 亲和力，这种现象称为免疫应答成熟陋t 7 1 。从初次应答到二次应答过程中， 抗体亲和力的增加表明免疫应答成熟是一个连续过程( 强化学习) 。这些亲和 力更高的抗体被选入记忆细胞池中。该现象己经被用于设计人工免疫算法， 解决优化问题。 初次应答可以看作是免疫系统学习、识别、记忆外部入侵物质特性的过 程，二次应答过程则可看作是免疫系统利用免疫记忆杀死入侵物质的过程。 免疫应答及记忆是许多人工免疫系统模型的基础。 2 2 人工免疫系统 人工免疫系统是借鉴、利用生物免疫系统( 主要是人类免疫系统) 各种原 理和机制而发展的各类信息处理技术、计算技术及其在工程和科学中应用而 产生的各种智能系统的统称。人工免疫系统是一个跨越多学科的研究领域， 是与生物免疫系统相对应的工程概念渺j 。 2 2 1 生物免疫系统的启示 生物免疫系统是生物体的一个高度进化、复杂的功能系统，它能自适应 9 哈尔滨工程大学硕士学位论文 应地识别排除侵入机体的抗原性异物，并且具有的分布性、自适应性和动态 平衡特点，可用来借鉴建立人工免疫网络模型，为智能控制提供一种新颖而 有效的方法，而它具有的学习、记忆、识别功能，又可用来开发免疫学习算 法，实现智能信息处理。除此之外，抗原提呈细胞的特征提取能力、免疫细 胞增殖的阈值原理、免疫网络的超动力学特性、免疫应答的概率性检测能力 等也都对我们开发人工免疫系统有着良好的启示【1 9 】。 研究人工免疫系统，可以遵循下述的基本框架进行： ( 1 ) 描述待解决的问题 将其中的所有部分与人工免疫系统中的组成相对应，这包括变量、常量、 主体、功能以及描述和求解问题必要的参数。 ( 2 ) 选定求解问题所用的免疫原理 受生物免疫系统的启发，人们从中汲取出来的模型、算法和过程都是普 遍性的，可以应用到不同的方面，而且基于现有开发成果的变化还可以演变 出新的内容，甚至开发出许多现在未知的潜在的免疫机制。 ( 3 ) 设计人工免疫系统 设计一个人工免疫系统要涉及到几个方面的内容，如确定将要用的免疫 机理，产生这些机理的抽象模型，利用这些免疫机制( 算法) 控制系统的行为( 动 态的和超动态的1 等。 ( 4 ) a i s 向实际问题的逆映射 完成问题的求解之后，还要把由a i s 表示的结果翻译( 解码) 到原始问题 的领域。 2 2 2 人工免疫系统的研究内容和范围 人工免疫系统结合了如人工神经网络和机器推理等原有一些智能信息处 理的特点，在解决大规模复杂性问题方面具有很大的潜力。有鉴于此，近年 来人们对a i s 及相应算法的研究逐渐活跃起来。目前人工免疫系统的研究内 容和范围主要包括三个方面【2 】： 1 免疫计算智能系统 自然免疫系统是发展智能技术的启发源泉，研究人员己经开发了许多基 于免疫系统的计算技术，包括各种基于免疫原理的免疫算法、人工免疫网络 l o 哈尔滨工程大学硕士学位论文 和免疫计算系统等。 ( 1 ) 根据生物免疫系统原理发展新的算法，主要有阴性选择算法、克隆选 择算法、免疫遗传算法、免疫优化算法，以及为完成各种特定任务而设计的 基于免疫原理的算法等，可统称为免疫算法。 ( 2 ) 根据生物免疫系统原理建立的人工模型，包括人工免疫网络模型和 人工免疫系统模型两种形式。各种免疫网络学说，如独特型网络、互联耦合 免疫网络、免疫反应网络和对称网络等，可借鉴用于建立人工免疫网络认知 模型。 ( 3 ) 与人工神经网络、模糊系统等结合建立混合智能系统，比如利用免 疫、神经网络、模糊技术建立智能计算系统；利用免疫系统抗体多样性的遗 传机制改进遗传算法的搜索优化。 人工免疫系统涉及的研究内容和应用范围较为广泛，己超出了仅仅作为 计算工具研究的范围，但从目前的研究和应用来看，多数仍以发展基于免疫 原理的计算方法为主。 2 免疫工程应用研究 包括各种免疫计算智能技术在工程中的应用研究，建立利用免疫系统原 理及特性解决工程问题的人工智能系统。如保安系统、疾病诊断系统、各种 计算机安全和网络入侵诊断和检测系统等。 3 人工免疫系统理论研究 例如借助数学模型、非线性、复杂、混沌、计算智能等理论深入研究人 工免疫系统的机制。 预计今后a i s 的研究将围绕着算法机理的深入探讨、算法的数学理论分 析、面向工程应用的a i s 算法模型完善、计算智能方法的融合、面向进化设 计的a i s 模型研究埽】几个方面展开。 2 2 3人工免疫系统的历史 f a r m e r 等率先基于免疫网络的相关学说给出了免疫系统的动态模型，并 探讨了免疫系统与其他人工智能方法的联系，开始了入工免疫系统的研究 【2 0 】。此时相关研究成果比较少见，直到1 9 9 6 年1 2 月，在日本首次举行了基 于免疫性系统的国际专题讨论会，首次提出了“人工免疫系统”的概念。随后， 哈尔滨下程大学硕十学位论文 人工免疫系统进入了发展期，相关论文和研究成果正在逐年增加。1 9 9 7 年和 1 9 9 8 年i e e es y s t e m s ，m a na n dc y b e r n e t i c s 国际会议成立了“人工免疫系统及 应用分会”。 2 2 4 人工免疫系统算法的研究 因为对免疫机理的认识还不十分系统深入，所以，有关人工免疫系统算 法( 以下简称免疫算法) 的研究成果并不多。目前人工免疫系统领域中几类比 较有代表性的算法有： 1 基于免疫网络学说的人工免疫网络模型 从生物学观点出发建立的免疫系统( 包括免疫网络) 模型一般都很复杂， 不适合人工智能的应用；因此，a l e x a n d e rt a r a k a n o v 等试图在建立形式蛋白 ( f o r m a lp r o t e i n ) 模型的基础上，为人工免疫系统建立一个正式的模型碡o a l e x a n d e rt a r a k a n o v 还探讨了有关免疫生物芯片的结构；但是，他们的研究 多专注于免疫功能单元间的相互作用，对网络涉及不多。在人工免疫系统中， 虽然已经有了i s h i g u r o 等提出的一种互联耦合免疫网络模型1 2 2 1 | t a n g 等提出 的一种与免疫系统中b 细胞和t 细胞之间相互反应相类似的多值免疫网络模 型【4 3 】；h e r z e n b e r g 等提出的一种更适合于分布式问题的松耦合网络结构【2 3 】； 然而目前，两个比较有影响的人工免疫网络模型是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 l l l l l n es y s t e m ，r l a i s ) t 2 j 和d ec a s t r o 等的趟e t 【2 5 捌。 需要指出的是，免疫网络的相关机理已经被广泛地用于计算机网络，尤 其是网络安全方面的研究z 7 】，但这些多是思想上的。 2 基于免疫特异性的否定( 阴性) 选择算法 计算机的安全问题与生物免疫系统所遇到的问题具有惊人的相似性，两 者都要在不断变化的环境中维持系统的稳定性。免疫系统分布的、灵活的、 自适应和鲁棒的解决方式，正是计算机安全领域所期望得到的。f o r r e s t 根据 免疫系统的自己非己的区别原则，研究了一种检测变化的否定选择算法 4 t j 。 该算法与t 细胞成熟过程中经历的“否定选择”过程中有着相似的原理：随机 产生检测器，删除那些检测到自己的检测器，以使那些检测到非己的检测器 保留下来。算法简述如下： 1 2 哈尔滨工程大学硕十学位论文 ( 1 ) 定义自己长度为三的有限个字母串的类集s 是一个需要保护监视的 集合。例如，s 可以是程序或数据文件( 任何软件) 。 ( 2 ) 产生一个检测器的集合r ，每一个都不能与s 集合中的任一个相匹 配，采用部分匹配的原则，而不是精确或完美匹配，即2 个串至少在，个位 置上能区别出来。这里，是可选择的参数。 ( 3 ) 监视，不断地将检测器r 与受监视集合s 进行匹配，一旦发生匹配， 就表示己发生一个变化，检测器是按照不能与s 中的任串相匹配设计的。 否定选择算法为免疫在计算机网络安全领域的应用奠定了理论基础。近 年来，随着计算机网络的飞速发展，安全问题也从简单的计算机病毒检测， 扩展到基于主机的入侵检测和网络安全，这些都可以从免疫系统的信息处理 机制中获得启示。 3 克隆选择算法 克隆选择学说是生物免疫系统理论的重要学说。克隆意为无性繁殖，即 通过无性繁殖( 如细胞丝分裂) 可连续传代并形成群体，常用于细胞水平的描 述。克隆选择学说所描述的记忆、学习和进化等特性使得人工免疫系统研究 者对其倍感趣。 1 9 5 8 年b u m e t 等人提出了著名的克隆选择学说。其中心思想为：抗体是 天然的产物，以受体的形式存在于细胞表面，抗原可与之选择性地反应。抗 原与相应抗体受体的反应可导致细胞克隆性增殖，该群体具有相同的抗体特 异性，其中某些细胞克隆分化为抗体生成细胞，另一些形成免疫记忆细胞以 参加之后的二次免疫反应。克隆选择是生物体免疫系统自适应抗原刺激的动 态过程。 国内的研究者虽然已经开始重视对人工免疫系统的研究，但是更多关注 的是利用免疫机理对进化算法的改进，虽然这些算法多数都被冠以免疫算法 的名字，但本质上可以说只是利用了免疫系统的有关机理对遗传算法进行改 进。相比较而言，对免疫网络的研究要比对克隆选择的研究深入些，已有的 算法仅给出了算法框架，缺乏对克隆选择机理的深入分析以及其他算法的深 入对比研究，有关收敛性分析等理论研究就更少。 4 免疫进化算法 进化算法作为一种有向随机搜索的优化方法得到了广泛应用。然而在实 哈尔滨工程大学硕士学位论文 际应用中也存在一些需要改进之处：无法保证收敛到全局最优解，群体中最 好个体的丢失，进化过程的过早收敛等。将进化与免疫结合起来考虑，能得 到更有效的优化算法。在进化算法的框架上，引入免疫系统的诸多特性，发 展起来了许多免疫优化算法。主要包括：引入疫苗接种理论的免疫优化算法 t 2 s 】、引入自我调节机制的免疫算法1 2 9 、基于免疫应答的免疫优化算法1 3 0 、具 有免疫体亲近性特征的遗传算法 3 1 1 、借鉴独特性网络调节的进化算、法【，2 】、具 有免疫体亲近性特征的遗传算法 3 3 1 等。这些改进算法可以较快求出满足一定 精确度要求的最优解，对解决工程应用问题具有应用价值【，一1 。 2 2 5 人工免疫系统的应用领域 人工免疫系统应用研究近1 0 年不断扩展，表2 1 给出主要的人工免疫系 统应用领域以及相关技术、免疫原理【3 筇。 表2 1 人工免疫系统主要应用领域 应用领域 示例 控制、规划电压调节器的控制，复杂动力学系统自适应控制，电网规划 组合优化t s p 问题，c d m a 多用户检测 图像处理图像分割，立体匹配 数据处理多成分混合色谱信号的解析 知识发现数据库知识发现 故障监测和诊断加工工具破损检测，旋转机械在线故障诊断 机器人多智能体决策系统，分布式自动机器人系统等 网络安全病毒防护与入侵检测 表2 1 包括模型或技术的简单描述，以及其使用的免疫学机制的信息、 表示形式和应用意图。从表2 1 中可以看出，现有的人工免疫系统基于生物 免疫系统的不同机制，具有多样性表现形式，这使得人工免疫系统与生物免 疫系统在多样性方面非常一致，其应用领域也表现出多样性，其研究手段从 借鉴其他计算智能方法到理论研究也表现出多样性，比如利用进化计算、主 体等技术研究、设计人工免疫系统。因此人工免疫系统是一个开放式的研究 领域，不断借鉴计算机科学、人工智能、机器学习、生物学、医学等多个学 科和领域的技术与知识而发展，并解决实际问题。近两年，国内在人工免疫 1 4 哈尔滨工程大学硕士学位论文 系统领域的研究发展较快，以西安交大、中国科大等为主的一些国内著名大 学的研究人员已经在优化、计算机安全等领域取得了进一步的成果。 2 2 6 人工免疫系统与其他方法的比较 1 人工免疫系统与进化计算 免疫算法和进化计算都采用群体搜索策略，并且强调群体中个体间的信 息交换，因此有许多相似之处。首先在算法结构上，都要经过“初始种群的产 生一评价标准计算_ 种群间个体信息交互一新种群产生”这一循环过程，最终 以较大概率获得问题的最优解；其次在功能上，二者本质上都具有并行性， 在搜索中不易陷入极小值，都有与其他智能策略结合的固有优势；然后在主 要算子上，多数免疫算法都采用了进化计算算子上，多数免疫算法都采用了 进化计算方法的主要算子；最后，也正是因为二者存在共性，有关二者集成 的智能策略一免疫进化算法，已成为免疫算法研究和应用的最成功的领域之 一。 但是，它们之间也存在区别：( 1 ) 免疫算法在记忆单元基础上运行，确保 了快速收敛于全局最优解：而进化算法则是基于父代群体，标准遗传算法不 能保证概率收敛；( 2 ) 免疫算法评价标准计算是计算亲和性，包括抗体- 抗原的 亲和度以及抗体抗体亲和度，反映了真实的免疫系统的多样性；而进化算法 则是简单计算个体的适应度；( 3 ) 免疫算法通过促进或抑制抗体的产生，体现 了免疫反应的自我调节功能，保证了个体的多样性；而进化算法只是根据适 应度选择父代个体，并没有对个体多样性进行调节，这也是免疫策略用于改 进进化算法的切入点；( 4 ) 虽然交叉变异等固有的遗传操作在免疫算法中广泛 应用，但是免疫算法新抗体产生还可以借助克隆选择、免疫记忆、疫苗接种 等传统进化算法中没有的机理。 2 人工免疫系统与人工神经网络 神经网络和人工免疫网络都是由大量高性能单元组成的，具有容噪、泛 化能力和记忆能力，以及通过竞争实现的并行处理能力。但是神经网络获得 所识别对象内部镜像图是通过归纳实现的，即不断压缩原始图像，而人工免 疫网络先构造一充分