（计算机应用技术专业论文）人工免疫算法在tsp中的应用研究.pdf

西南交通大学硕士研究生学位论文第f 页 摘要 随着免疫学理论研究的不断发展，人们对生物免疫系统的认识不断深入，提出了人 工免疫系统，该系统已经被广泛应用于科学研究和工程实践的众多领域。 免疫算法( i m m u n ea l g o r i t h m ，简称i a ) 构造简单，在一定条件下具有强大的搜索 能力和全局收敛性。由于使用随机搜索技术，保证了算法全局收敛性，但其局部寻优的 性能受到损害，且收敛速度也不理想。而蚁群算法( a n tc o l o n y a l g o r i t h m ，简称a c a ) 充分利用了目标问题的信息，局部寻优能力强，收敛速度快，但是，容易陷入局部最优 的陷阱。可以说，丛提供了全局性的点搜索方法，而a c a 提供了局部性的面搜索方法， 两类方法各有利弊。 针对认存在的上述问题，本文对其进行改进得到了一种基于蚁群的免疫算法( t h e i m m u n e a l g o r i t h mb a s e d o na n tc o l o n y ，简称i a a c ) ，该算法利用a c a 局部寻优能力强、 收敛速度快的优点，结合其正反馈的思想，逐渐在每只蚂蚁所走过的禁忌表中形成较优 解，然后将这些较优解的片段提取出来作为认的疫苗，在群体更新阶段注入n ，求解 问题。这样既保持了种群的多样性，又避免了每次迭代中由于新更新的抗体亲和力低而 被淘汰。此方法利用了点面结合的方法进行搜索，使得两种算法互为补充。 针对旅行商问题( t r a v e l i n gs a l e m a np r o b l e m ，简称t s p ) 中存在的亲和力计算方法 值域范围较大的缺点，本文根据当前代中最优解和最差解设计了一种计算亲和力的方法， 其值域为 o ，1 ，亲和力越接近l ，抗体越趋于最优解，亲和力越接近0 ，抗体越差。 本文把i a a c 算法应用到t s p 中，在v i s u a lc 蛳0 平台上对b i a 和i a a c 进行了 仿真，并对标准的t s p l i b 中的八个问题( u l e y s s e s l 6 、u l e y s s e s 2 2 、a t t 4 8 、e i l 5 1 、b e r l i n 5 2 、 s t 7 0 、e i l 7 6 、g r 9 6 ) 进行了测试，测试结果表明，该方法求解t s p 是有效的。 关键词：生物免疫系统；免疫算法；克隆选择；蚁群算法；t s p 西南交通大学硕士研究生学位论文第li 页 a b s t r a c t w i t ht h ec o n t i n u o u sd e v e l o p m e n to fi m m u n o l o g i c a lt h e o r y , p e o p l eh a v eh a dad e e p u n d e r s t a n d i n go fb i o l o g i c a li m m u n es y s t e m ，a n dp r o p o s e da r t i f i c i a li n l i n u n es y s t e m i th a s b e e nw i d e l yu s e di ns c i e n t i f i cr e s e a r c ha n de n g i n e e r i n gp r a c t i c ei nm a n ya r e a s w i t has i m p l es 们k t i l r e ，i m m u n ea l g o r i t h m ( i a ) h a sg l o b a lc o n v e r g e n c eu n d e rc e r t a i n c o n d i t i o n s b yu s i n gr a n d o ms e a r c h i n gm e t h o d , i ag u a r a n t e e si t sg l o b a lc o n v e r g e n c e ，w h i l ei t s a b i l i t yo ff i n d i n gl o c a lo p t i m a li sa f f e c t e d ，a n dt h ec o n v e r g e n c es p e e do fi ai sa l s on o tg o o d t h ea n tc o l o n ya l g o r i t h m ( a c a ) n s e sm u c hm o r ei n f o r m a t i o no ft h et a r g e tp r o b l e m 。t h e c o n v e r g e n c es p e e di sm u c hb e t t e r , a n dt h ea b i l i t yo ff i n d i n gl o c a lo p t i m a li sb e t t e r , h o w e v e r , i t w i l lf a l li n t ot h et r a po fl o c a lo p t i m u m i tc a nb es a i d ，i as u p p l i e sag l o b a lp o i n ts e a r c h i n g t e c h n i q u e ，a n da c as u p p l i e sal o c a ls u r f a c es e a r c h i n gt e c h n i q u e t w om e t h o d sb o t hh a v e a d v a n t a g e sa n dd i s a d v a n t a g e s f o rt h ea b o v ep r o b l e m so fi a ，t h i st h e s i si m p r o v e si ta n dg e t st h e1 1 t l m u n ea l g o r i t h m b a s e do na n tc o l o n y ( l 气a c ) i tu s e dt h es t r o n gl o c a lo p t i m i z a t i o na b i l i t ya n dt h ef a s t c o n v e r g e n c es p e e d t h et h e s i sc o m b i n e sw i t l lt h ei d e ao fi t sp o s i t i v ef e e d b a c kt op r o d u c ea b e t t e rs o l u t i o ni nt h et a b o ol i s t ，a n de x t r a c t i n gi a sv a c c i n ef r o mt h e s eb e t t e rf r a g m e n t s ， i n j e c t i n gv a c c i n ei n t ot h eu p d a t i n gs t a g eo ft h eg r o u pt os o l v et h ep r o b l e m b yt h i sw a y , i tn o t o n l yk e e p st h ed i v e r s i t yo f p o p u l a t i o n , b u ta l s oa v o i d st h er e n e w e da n t i b o d y sw h i c h h a v eal o w a f f i n i t yb e i n ge l i m i n a t e di ne a c hi t e r a t i o n t h i sm e t h o da l l o w sp o i n ta n ds u r f a c es e a r c h , m a k i n gt h et w om e t h o d sc o m p l e m e n te a c ho t h e r i nv i e wo ft h et o ol a r g es c o p ei na f f i n i t yc a l c u l a t i o nm e t h o do ft r a v e l i n gs a l e m a n p r o b l e m ( t s p ) ，t h i st h e s i sd e s i g n sam e t h o do fc a l c u l a t i n ga f f a n i t yt h r o u g ht h eo p t i m a l s o l u t i o na n dt h ew o r s ts o l u t i o no fc u r r 饥tg e n e r a t i o n i t sr a n g ei sz e r ot oo n e i ft h ea f f i n i t y c l o s e st oo n e ，a n t i b o d yw i l lc l o s et ot h em o r ee x c e l l e n ts o l u t i o n o nt h ec o n t r a r y , a n t i b o d yi s w o r s ew h i l ea f f i n i t yi sc l o s e rt oz e r o t h i st h e s i sa p p l i e di a a ct ot s p , a n ds i m u l a t e db i aa n di a a cb yu s i n gt h ev i s u a lc 抖 6 0p l a t f o r m i ta l s ot e s t e dt h ee i g h te x a m p l e so fs t a n d a r dt s p l i bi n c l u d i n gu l e y s s e sl6 u l e y s s e s 2 2 ，a t t 4 8 ，e i l 51 ，b e r l i n 5 2 ，s t 7 0 ，e i l 7 6 ，a n dg r 9 6 t h et e s tr e s u l t ss h o w e dt h a tt h e m e t h o df o rs o l v i n gt s pi se f f e c t i v 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 ；i m m u n ea l g o r i t h m ；c l o n a ls e l e c t i o n ；a n tc o l o n y a l g o r i t h m ；t s p 西南交通大学曲南父迥大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西 南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密函，使用本授权书。 ( 请在以上方框内打“”) 学位论文作者签名：壑莲锛 指导老师签名： 为移j 匆 日期：加o 辱6a1 b 日期：参厂秒多仁 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： 1 在b i a 的基础上，结合a c a 的优点，设计了一种i a a c ，该算法利用蚁群算法 正反馈的思想逐渐形成较优解，并将这些较优解的片段抽取出来作为认的疫苗，在群 体更新阶段注入认，充分利用了队全局性的点搜索和a c a 局部性的面搜索，使得两种 算法互相补充，提高了算法的求解精度和收敛速度。本文把改进后的算法用于t s p 问题 的求解，取得了良好的效果。 2 针对t s p 问题的特点及其原有亲和力计算方法的值域范围较大，很难衡量抗体 的好坏，本文采用了一种利用当前代中最优解和最差解计算抗体亲和力的方法，用于改 进后的免疫算法，实验结果表明该方法使得算法的搜索性能得到了提高。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。 除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的 研究成果。对本文的研究做出贡献的个人和集体，均己在文中作了明确的说明。本人完 全意识到本声明的法律结果由本人承担。 学位论文作者签名：赵蓬锄 日期： k o l o 年6 怠1q 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 研究背景及意义 生物免疫系统具有良好的多样性、耐受性、免疫记忆、分布式并行处理、自组织、 自学习、自适应和鲁棒性等特点【l 】。人工免疫算法是基于生物免疫系统的基本原理机制， 模仿了人体的免疫系统。人工免疫算法从体细胞理论和网络理论得到启发，实现了类似 于生物免疫系统的抗原识别、细胞分化、记忆和自我调节的功能。免疫系统是一个分布 式、自组织和具有高度并行处理能力的强鲁棒性的自适应复杂系统。 人工免疫系统( a r t i f i c i a li m m u n es y s t e m ，简称a i s ) 是继人工神经网络、进化计算 之后的又一智能计算研究新方向，为当前智能信息处理领域提供了一种有效的工具。随 着免疫学理论研究的不断发展，人们对生物免疫系统的认识也随之不断的深入。 人工免疫系统是模仿自然免疫系统功能的一种智能方法，它实现了一种受生物免疫 系统启发，通过学习外界物质的自然防御机理的学习技术，其作为一种高效的分布式并 行信息处理系统，其研究成果已在机器学1 2 1 、知识发掘【3 1 、函数优化 4 1 、组合优化【5 】、 智能控, i j t 6 1 、计算机安全【7 】等领域展示出巨大的魅力，引起了广大研究者的高度重视。 优化问题求解是人工智能的一个重要的应用领域【8 】，优化问题也一直是人们感兴趣 的问题之一。由于该问题的普遍性和重要性，几十年来得到了广泛和深入的研究。直到 现在，仍有许多学者在对优化问题做更为深入的研究工作。正是因为这些持续的研究工 作，才不断涌现出新的理论和方法，满足了科学与技术发展的需要，也为人工免疫系统 的发展提供了基础。基于免疫系统原理开发的各种模型和算法已经引起了人们的极大重 视，其在科学研究和工程实践上将会有越来越多的应用。 近些年来在生物领域的研究发现免疫行为能够很好的阻止早熟现象，有效的提高寻 优速度，因而对免疫算法( i m m u n e a l g o r i t h m ，简称i a ) 的改进和提高具有重要的作用。 如果将认与求解优化问题的一般搜索方法相比较，那么抗原、抗体、抗原和抗体之间的 亲和力分别对应于优化问题的目标函数、优化解、解与目标函数之间的匹配程度。用抗 体之间的亲和力来保证可行解的多样性，通过计算抗体与抗原之间的亲和力来促进较优 抗体的遗传和变异，用记忆细胞单元来保存择优后的可行解来抑制相似可行解的继续产 生并加速搜索到全局最优解，同时，当相似问题再次出现时，能较快的产生适应该问题 的较优解甚至最优解。由于人工免疫算法的内容是多样化的，以至于目前人们还无法统 一描述人工免疫系统以及建立相应的理论模型。所以目前人工免疫算法正处于面向问题 的研究阶段。人工免疫算法为解决日趋复杂多样的工程任务提供了新的思想和方法，所 西南交通大学硕士研究生学位论文第2 页 以研究如何根据免疫优化理论以及模拟生物免疫优化行为来设计新的有效优化算法是非 常有意义的研究方向。 1 2 研究现状 计算机免疫是基于生物免疫系统的基本原理，是一种新兴的智能信息处理方法，在 计算机网络安全、模式识别等领域中具有广阔的应用前景。 在国外，1 9 9 4 年，美国学者f o r r e s t 、p e r e l s o n 等人提出了否定选择算法【9 】，用来生成 检测器，完成了检测器的耐受过程，并提出了计算机免疫系统的概念。同时，美国著名 公司m m 也较早地开始了对计算机免疫系统的研究，已经成功地开发了用于病毒防止的 计算机免疫系统。1 9 9 7 年，d e a t o n 等人提出了种基于分子的人工免疫系统【lo 】，用来模 仿自然免疫系统的这种能力，目的是为了保护计算机免受计算机病毒和其他因素的破坏。 经过长时间的研究，d a s g u p t a 于1 9 9 9 年建立了一套计算机免疫系统【1 1 1 ，用来抵御外来 入侵，保障计算机系统的安全。同时，d a s g u p t a 及其学生一直致力于否定选择算法的研 究，并应用到计算机安全和异常检测及工业应用中。2 0 0 2 年，c a s t r o 和t i m m i s 对否定 选择算法做了一定的修改【1 2 】，把变异引进到其中。同年，k i m 和b e n t l e y 提出了动态克 隆选择算法【1 3 】( d y n a m i c s ) ，主要用于网络入侵检测( n i d s ) 。至此，计算机免疫在理 论上已日趋完善了。 2 0 0 2 年6 月，i e e et r a n s a c t i o no ne v o l u t i o n a r yc o m p u t a t i o n 出专刊报道了有关人工 免疫的研究成果，2 0 0 2 - - 一2 0 0 3 年，国际上举办了有关人工免疫的学术会议近2 0 次。2 0 0 2 年9 月，在英国k e n t 大学成功地召开了i c a r i s ( 1 吼i n t e r n a t i o n a lc o n f e r e n c eo na r t i f i c i a l i m m u n es y s t e m s ) ，标志着人工免疫系统的研究发展进入了一个新的快速发展阶段。随后 每年举办一次，并与2 0 0 8 年8 月举行了第7 届国际人工免疫系统会议。召开第一届人工 免疫系统国际学术会议之后，在美国、英国、日本等西方国家掀起了一股研究开发计算 机免疫系统的热潮，进一步吸引了众多领域的专家学者从各个不同的学科和角度开展研 究，并在许多工程领域中取得了巨大的成绩。 在国内，早在1 9 9 0 年，西南交通大学的靳蕃教授等人在神经网络与神经计算机原 理应用一书中就已经指出“免疫系统所具有的信息处理与肌体防卫功能，从工程角度 来看，具有非常深远的意义【14 】，。1 9 9 7 年国内已经有免疫计算的文章出现。从2 0 0 1 年开 始，有关人工免疫系统的博士硕士学位论文也相继涌现。2 0 0 2 年武汉大学的梁意文教授 利用免疫原理对大规模网络入侵检测和预警技术进行了研究f 1 5 】f 埔切。2 0 0 3 年，四川大学 的李涛教授提出了基于免疫的大规模网络入侵动态取证以及网络安全风险检测与控制等 技术【1 8 】【1 9 】【2 0 】【2 l 】。同年，中国科学技术大学研制了一个“基于人工免疫的入侵预警系统”， 该系统具有较好的未知入侵预警能力。如今，人工免疫系统已成为继人工神经网络和遗 传算法之后又一新的智能研究热点。至1 j 2 0 0 8 年，已有许多研究将人工免疫系统用于数值 西南交通大学硕士研究生学位论文第3 页 优化、工程优化以及计算机安全等问题。 1 3 本文主要研究内容及组织结构 本文的具体工作包括： ( 1 ) 用蚁群算法提取疫苗，将其注射到认的群体更新中，对认进行了改进一基于 蚁群的免疫算法( l a a c ) ，并把改进后的算法与已有算法进行了比较，然后将其用于t s p 问题的求解，取得了良好的效果。 ( 2 ) 针对t s p 问题的特点，本文设计了一种计算抗体亲和力的方法，用于改进后的 免疫算法，实验结果表明该亲和力的计算方法使得算法的搜索性能得到了提高。 ( 3 ) 在v i s u a lc + + 6 o 环境下对b i a 和i a a c 进行了仿真实验，测试了t s p l i b 中的 八个典型问题，并对测试结果进行了分析。 ( 4 ) 根据本文所做研究，总结了本文的工作及对人工免疫算法的一些经验和结论， 并对认的未来研究提出了展望。 与具体的工作相对应，本文的内容安排如下： 第1 章为绪论部分，主要介绍了人工免疫算法的背景、研究意义及研究现状，并对 本文所做的工作以及本文的内容安排做了说明。 第2 章介绍了有关人工免疫理论的生物学基础及人工免疫系统的一些基本概念、基 本原理及与其他智能计算方法的关系。 第3 章介绍了人工免疫算法的基本概念和框架及对目前比较流行的几种认进行了 阐述，并分析了免疫算法的特点。 第4 章首先简要的介绍了蚁群算法的基本原理，然后根据人工免疫算法和蚁群算法 的理论思想，结合t s p 问题，对基本免疫算法进行改进得到了基于蚁群的免疫算法 ( i a a c ) 一用蚁群算法提取疫苗并注射到n 的群体更新中，并与已有算法进行了比较 分析。 第5 章针对t s p 问题，设计了一种亲和力的计算方法，实现了基本免疫算法和基于 蚁群的免疫算法在t s p 问题中应用的仿真实验，并对t s p l i b 中的八个典型问题进行了 测试，对仿真结果进行了必要的说明和分析，测试结果表明基于蚁群的免疫算法优于基 本免疫算法。 西南交通大学硕士研究生学位论文第4 页 第2 章免疫理论的生物学基础及人工免疫系统 2 1 免疫理论的生物学基础 2 1 1免疫学的基本概念 队的生物学基础是自然免疫系绀2 2 1 。免疫系统是一个由执行免疫功能的器官、组 织、细胞、和分子等组成的复杂系统，它是生物系统保护机体、抵抗细菌、病毒和其他 致病因子入侵的基本防御系统，它能够识别自身与异己抗原，并通过免疫应答排除抗原 性异物，维持机体的生理平衡。免疫系统的结构及其行为特性极为复杂，关于其内在规 律的认识，免疫学家们仍在进行不懈的努力。生物免疫过程的宏观描述如图2 1 所示。 图2 1 生物免疫过程 为了便于了解免疫系统的基本原理，促进基本免疫机理的算法和模型用于解决工程 实际问题，有必要先简单介绍下一些基本概念和技术术语。这些概念和术语主要包括： ( 1 ) 免疫：所谓“免疫”，顾名思义即免除瘟疫。用现代的观点来讲，人体具有一种 “生理防御、自身稳定与免疫监视”的功能叫“免疫”。免疫是指机体免疫系统识别自身 与异己物质，并通过免疫应答排除抗原性异物，以维持机体生理平衡的功能。换言之， 免疫是指免疫系统抵御外部入侵，使其机体免受病原侵害的应答反应【2 3 1 。 ( 2 ) 免疫应答：是指抗原进入机体后，免疫细胞对抗原分子的识别、激活、分化、 增殖和效应的过程，是免疫系统各部分生理的综合体现，包括了抗原提呈、淋巴细胞活 化、特异识别、免疫分子形成、免疫效应，以及形成免疫记忆等一系列的过程，用来动 态地适应不断变化的外界环境。 ( 3 ) 抗原与抗体：诱导免疫系统产生免疫应答的物质称为抗原( a n t i g e n ) ，包括侵入 机体的各种细菌和病毒，以及发生了突变的自身细胞( 如癌细胞) 等；能与抗原进行特 西南交通大学硕士研究生学位论文第5 页 异性结合的免疫细胞称为抗体( a i l t i b o d y ) ，免疫系统主要依靠抗体来对入侵抗原进行清 除以保护有机体【2 3 】。 ( 4 ) 亲和力( a f h n 埘) ：免疫细胞的表面受体和抗原决定基都是复杂的含有电荷的三 维结构，二者的结构和电荷越互补，就越有可能相互结合，结合的强度即是亲和力。 ( 5 ) 变异( m u t a f i o n ) ：在生物免疫系统中，b 细胞与抗原结合后被激活，然后产生 高频变异。这种克隆扩增期间产生的变异形式，使得免疫系统能够适应不断变化的外来 入侵。 ( 6 ) t 细胞：即t 淋巴细胞，它在胸腺中成熟，功能包括调节其他细胞的活动和直接 袭击宿主感染细胞。t 细胞可分为毒性t 细胞和调节性t 细胞两类。而调节性t 细胞又 可分为辅助性t 细胞和抑制性t 细胞。辅助性t 细胞的主要作用是激活b 细胞，与抗 原结合时分泌，作用于b 细胞并帮助刺激b 细胞的分子。毒性t 细胞能够清除微生物入 侵者、病毒或者癌细胞。 ( 7 ) b 细胞：即b 淋巴细胞，来源于骨髓淋巴样前体细胞，成熟的b 细胞存在于淋 巴结、血液、脾、扁桃体等组织和器官中，b 细胞是体内产生抗体的细胞，在清除病原 体过程中受到刺激，分泌抗体结合抗原，但其发挥免疫作用要受t 辅助细胞的帮助。 2 1 2 免疫运行机制及功能 ( 1 ) 免疫运行机制 生物免疫系统的运行机制可归纳为以下几种晔】： 1 ) 免疫应答( i m m u l l er e s p o l l s e ) ：指免疫细胞进入机体后，识别抗原、激活、分化 与增殖，以及产生免疫效应以清除抗原的过程，该过程是由多细胞系统参与并完成的。 免疫系统会通过抗体对抗原的识别，不断地进化出新的抗体，最终生成合适的抗体来消 灭抗原，动态地适应不断变化的外界环境。 2 ) 免疫记忆( i m m _ i l n em e m o r y ) ：生物免疫系统具有两种类型的免疫应答：初次免 疫应答和再次免疫应答，如图2 2 所示。当抗原第一次侵入生物体时引发初次免疫应答， 在此过程中，免疫系统通过学习抗原，利用克隆选择机制产生记忆细胞。当遇到相同类 型的抗原再次入侵时，再次免疫应答被触发，通过唤醒记忆细胞，在更短的周期内产生 大量的抗体以消灭抗原。因此，通过克隆复制可以产生抗击己知抗原的记忆细胞，以增 强免疫记忆能力。 3 ) 免疫调节( i m m u n er e g u l 撕o n ) ：在免疫应答的过程中，免疫系统内部的各免疫 细胞之间、抗原与抗体、抗体与抗体之间形成一个相互作用的动态平衡网络体系，当有 外界抗原入侵时，通过免疫系统的调节，可达到新的免疫平衡。即使在无抗原入侵时， 通过抗体间的相互促进与抑制反应，也能自我调节适当数量的必要抗体，使免疫应答维 持免疫平衡。 西南交通大学硕士研究生学位论文第6 页 再次应答 1 0 011 0 7 时间 的抗原 图2 2 免疫应答 ( 2 ) 生物免疫系统的功能 在正常的情况下，免疫系统的功能使机体内环境得以维持稳定，具有保护性的作用； 在异常情况下，免疫系统的功能有可能导致某些病理过程的产生和发展。机体免疫系统 在对“自己 或非己 物质识别和应答的过程中，主要发挥以下三种功能【2 5 】： 1 ) 免疫防御( i m m u n ed e f e n c e ) - 是指免疫系统通过正常的免疫应答，阻止和清除 入侵病原体及其毒素的功能，即抗感染免疫作用。如果免疫应答表现的过于强烈，则在 清除抗原的同时，也会造成组织的损伤，即发生超敏反应( 变态反应) 。如免疫应答过低 或缺少，机体则可能会发生免疫缺陷病。 2 ) 免疫自稳( i m m u n eh o m e o s t a s i s ) ：是指机体识别和清除自身衰老和损伤的细胞、 对自身正常成分产生免疫耐受、并通过免疫调节达到维持机体内环境稳定的功能。机体 免疫系统存在着极为复杂而有效的调解网络，借此来实现免疫系统功能的相对稳定性， 这种稳定性功能失调时，易导致某些生理平衡的紊乱，从而导致自身免疫病的发生。 3 ) 免疫监视( i m m u n es u r v e i l l a n c e ) ：免疫系统具有识别、杀伤并及时清除体内突变 细胞，防止恶性肿瘤发生的功能，称为免疫监视。免疫监视是免疫系统最基本的功能之 一。免疫监视功能低下则会导致肿瘤的发生或持续的感染。由于各种体内外因素的影响， 正常个体的组织细胞不断的发生畸变和突变，机体免疫系统可识别此类异常细胞并将其 清除。 2 2 人工免疫系统 2 2 1人工免疫系统的定义 人工免疫系统从字面意思理解可以有两层含义：一层是医学研究人员利用计算机技 术、数学等方法和手段建立的人工系统，其目的是为了更好的研究免疫系统本身的机理； 西南交通大学硕士研究生学位论文第7 页 另一层就是工程技术上的含义。本文中的人工免疫系统指后一层含义。对工程技术界来 讲，人工免疫系统是新近才发展起来的领域，引起人们对研究人工免疫系统产生极大兴 趣的原因不是免疫系统本身的功能，而是从中提取、发现免疫系统的有效机制作为一种 解决工程和科学问题的手段。 目前关于人工免疫系统的定义，已经有多种表述，以下列举的是关于a i s 的几种定 义。 ( 1 ) d ec a s t r o 为人工免疫系统下的第一个定义认为：“人工免疫系统是遵循可信的生 物学范例人类免疫系统原理的数据处理、分类、表示和推理策略系统”【2 6 1 。 ( 2 ) t i m m i s 为人工免疫系统给出的第一个定义则认为：“人工免疫系统是基于自然免 疫系统方法的计算系统”【2 7 】。 ( 3 ) d a s g u p t a 给出的定义是：“人工免疫系统是由生物免疫系统启发而来的智能策略 所组成，主要用于信息处理和问题解决 【2 8 1 。 ( 4 ) d ec a s t r o 后来为人工免疫系统给出了第二个定义：“人工免疫系统是受生物免疫 系统启发而来的用于求解问题的适应性系统”1 2 9 。 ( 5 ) t i m m i s 后来也为人工免疫系统给出了第二个定义，即：“人工免疫系统是一种由 理论生物学启发而来的计算范式，借鉴了一些免疫系统的功能、原理和模型并用于复杂 问题的解决”【3 0 】。 ( 6 ) 莫宏伟给出的人工免疫系统的定义为：“人工免疫系统是基于免疫系统机制和理 论免疫学而发展的各种人工范例的特称，【3 l 】。 从上述几种定义中，d ec a s t r o 给出的第一个定义仅仅从数据处理的角度对a i s 进行 了定义，t i m m i s 给出的第一种定义也仅将a i s 简单的定义为计算机系统，都不够全面； 后面的三个定义则着眼于生物隐喻机制的应用，强调了a i s 的免疫学的机理，并且说明 了a i s 旨在解决复杂的问题，因而更为贴切；最后一个定义涵盖免疫启发的算法与模型， 免疫启发的软硬件系统及免疫系统建模与仿真等多种基于免疫机制的系统与方法【3 2 1 。从 以上关于a i s 的定义可以看出，a i s 的定义是逐渐完善起来的，这也表明了人们对a i s 的认识在不断的深入，a i s 的相关研究正在不断的发展。 2 2 2 人工免疫系统与其他智能计算方法的关系 生物世界为计算问题求解提供了很多的灵感和源泉。人工免疫系统作为一种智能计 算方法，它与人工神经网络( a r t i f i c i a ln e u t r a ln e t w o r k ，a 卜n ) 、进化计算及群集智能( 包 括蚁群优化方法a n tc o l o n yo p t i m i z a t i o n ，a c o 和粒子群优化方法p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) 一样，都属于基于生物隐喻的仿生计算方法，且都来源于自然界中 的生物信息处理机制的启发，并被用于构造能够适应环境变化的智能信息处理系统，乃 是现代信息科学与生命科学相互交叉渗透的研究领域。 西南交通大学硕士研究生学位论文第8 页 自然启发的计算 l 物理、化学启发的计算|生物启发的计算社会启发的计算 匝匝匝匝框 图2 3 免疫计算与其他计算智能的关系 免疫计算可以与其他智能计算方法互相借鉴和融合，免疫计算与其他计算智能的关 系如图2 3 所示。 2 3 本章小结 本章首先介绍了生物免疫系统的一些基本概念及常用术语，并给出了生物免疫系统 的运行机制、功能，详细阐述了生物免疫系统的工作原理。这些内容是人工免疫算法的 的生物学原理，为本文的研究奠定了基础。接着，本章就人工免疫系统的定义、特点及 与其他智能计算方法的关系进行了详细的介绍。 西南交通大学硕士研究生学位论文第9 页 曼皇曼舅鼍曼曼鼍曼曼皇曼曼鼍曼曼鼍曼曼曼曼曼曼曼曼曼曼曼舅! 曼曼曼! 曼曼曼曼鼍曼m m i 一m m m m m 一一m l l lm m ! 第3 章人工免疫算法 认大致可以分为基于群体的免疫算法( p o p u l a t i o n - b a s e d ) 和基于网络的免疫算法 ( n e t w o r k - b a s e d ) 。前者构成的系统中的各元素之间没有直接的联系，系统组成元素直 接和系统环境相互作用，它们之间若要联系只能通过间接的方式。而在由后者组成的系 统中，恰恰相反，部分甚至是全体的系统元素都能够相互作用。本文主要对基于群体的 免疫算法进行探讨。 3 1 免疫算法基本概念 抗原( a n t i g e n ) ：算法中的抗原通常指目标函数。 抗体( a n t i b o d y ) ：算法中抗体通常指目标函数的优化解。 抗体间的亲和力：用于表明抗体之间的相似度。 抗原和抗体的亲和力：用于表明抗体对抗原的识别程度。 克隆选择：应答抗原能力强的免疫细胞被确定性的选择进行应答。 细胞克隆：被选择进行应答的免疫细胞依据其应答抗原能力的强弱，繁殖一定数目 的克隆细胞，免疫细胞繁殖克隆的数目与其亲和力成正比。 记忆细胞：由特定抗体组成的抗体群，用于保持种群的多样性，以及求解过程中的 最优解。 亲和成熟：免疫系统通过抗体的基因重复进行亲和突变来获得大量识别抗原能力比 母体强的抗体，这些识别能力较强的抗体能有效缠住入侵抗原，这种现象称为亲和成熟。 疫苗( v a c c i n e ) ：是指根据进化环境或待求解问题的先验知识，所得到的最佳个体 的编码。 疫苗注射：是指抗体获得最佳个体编码的过程。 疫苗抽取：是指根据已有的先验知识，提取最佳个体编码的过程。 3 2 免疫算法基本框架 从不同的角度对生物免疫系统的原理和机制进行模拟可以形成不同的人工免疫算 法，因此，可以建立一般性的免疫算法基本框架。 在用认解决具体的问题时，首先需要将问题的有关元素、概念和处理过程与生物 免疫系统的有关概念及免疫原理对应起来，定义免疫元素的数学表达，然后再设计相应 的l 。 如图3 1 所示，一般地，n 大致由以下几个步骤【3 3 】组成： ( 1 ) 定义抗原：将需要解决的问题抽象成符合免疫系统处理的抗原形式，抗原识别 西南交通大学硕士研究生学位论文第10 页 则对应为问题的求解。 ( 2 ) 定义抗体：将需要解决问题的解区域中的一个点或者说一个解决方案对应为人 工免疫算法的一个抗体。 ( 3 ) 产生初始抗体群体：将抗体的群体定义为问题的解，抗体与抗原之间的亲和力 对应问题解的评估：亲和力越高，说明解的质量就越好。类似遗传算法，首先产生初始 抗体群体，对应问题的一个随机解。 ( 4 ) 计算亲和力：计算抗原与抗体之间的亲和力。 ( 5 ) 克隆选择：与抗原有较大亲和力的抗体则优先得到繁殖，抑制浓度过高的抗体 ( 避免局部最优解) ，淘汰低亲和力的抗体。为获得多样性( 追求最优解) ，抗体在克隆 时要经历变异( 例如高频变异等) 。在克隆选择中，抗体促进和克隆删除对应优化解的促 进与非优化解的删除等。 ( 6 ) 评估新的抗体群体：若不能满足终止条件则转向第( 3 ) 步，重新开始；若满足终 止条件，则当前的抗体群体则为问题的最佳解。 图3 1 免疫算法的基本架构 3 3 免疫算法综述 ( 1 ) 否定选择算法 否定免疫算法基于生物免疫系统的特异性，借鉴生物免疫系统中胸腺t 细胞生成时 的“否定选择( n e g a t i v es e l e c t i o n ) 过程。f o r r e s t 研究了一种用于检测数据变化的否定 选择算法【3 4 1 ，用于解决计算机安全领域的问题。该算法通过系统对异常变化的成功检测 西南交通大学硕士研究生学位论文第11 页 而使免疫系统发挥作用，而检测成功的关键是系统能够辨别自己和非己的信息。随机产 生检测器，删除那些检测到自己的检测器，以使那些检测到非己的检测器保留下来。 否定选择算法的具体步骤为： 1 1 定义一个自体字符串集合s ，例如，s 可以是一个程序，数据文件( 任何软件) 或一般的行为模式。 2 1 随机产生一个检测器集合r ，其中每一个字符串都不能与集合s 中的字符串相匹 配。该算法中的匹配不是完全匹配，而是部分匹配，只要有连续r 位相同就称为匹配， 此r 为一个可选择的参数。 3 ) 通过与r 集的匹配不断检测s 的变化，一旦发生任何匹配，就说明s 集合发生 了变化，即有外来元素的侵入。 否定选择算法的基本框架如下： p r o c e d u r e 否定选择算法 b e g i n 随机生成大量的候选检测器( 即免疫细胞) ； w h i l e 一个给定大小的检测器集合没有生成d o b e g i n 计算每一个自体元素和一个候选检测器之间的亲和力； i f 这个候选检测器识别出了自体集合中的任何一个元素 删除检测器； e l s e 将该检测器放入集合； e n d ； e n d ； 1 9 9 6 年，d h a e s e l e e r l 3 5 1 提出了两个和输入规模相关的异常检测器生成算法，尝试选 择差距较大的检测器来获得更好的检测效果，并讨论了一些关键参数的选择。2 0 0 5 年， 张海英3 叼提出一种改进的阴性选择免疫算法，让检测失败率能自适应自体规模的变化。 改进后的算法具有更强的处理能力和更低的检测失败率。文【3 7 1 中推出了一种否定选择算 法，基于免疫系统中的自己和非己识别的原理来进行变化检测。 ( 2 ) 肯定选择算法 肯定选择算法与否定选择算法非常类似，其作用则刚好相反。对否定选择算法来说， 与自体匹配的免疫细胞必须清除，而在肯定选择算法中则刚好被保留。 s e i d e n 和c e l a d a ( 1 9 9 2 ) 提出了种细胞自动机模型【3 8 1 来实现计算机对免疫系统的模 拟，基本上这个工作的目的是模拟免疫应答，期间展示了肯定选择算法的应用情况。 肯定选择算法的具体步骤如下： 西南交通大学硕士研究生学位论文第12 页 1 ) 初始化：产生一个t 细胞候选集合p 。假设所有的分子都用长度为珀勺二进制串 表示，则可能产生2 7 个不同的细胞； 2 ) 亲和力计算：通过集合s ，计算p 中所有元素与自体s 的亲和力； 3 ) 可用集合的产生：如果p 中某个元素与s 中某个元素的亲和力大于或等于一个 给定的阈值口，即这个t 细胞能识别这个自体，则它肯定被系统选用，放入a ；否则删 除它。 肯定选择算法的基本框架： p r o c e d u r e 肯定选择算法 b e g i n 随机生成大量的候选检测器； w h i l e 一个给定大小的检测器集合没有生成d o b e g i n 计算每一个自体元素和一个候选检测器之间的亲和力； i f 这个候选检测器识别出了自体集合中的任何一个元素 将该检测器放入集合； e l s e 删除检测器； e n d ； e n d ； 肯定和否定选择算法都是参考“自己”和“非己的。特别适合于未知环境的变化 下故障诊断和计算机安全检测等情况。 ( 3 ) 克隆选择算法 克隆选择算法是一种基于克隆选择理论设计的i a 。c a s t r o 最早提出了用于优化和学 习的克隆选择算法c l o n a l g 3 9 1 。克隆选择原理被用来解释免疫系统是怎么与抗原作战 的。当外部细菌或病毒侵入机体后，b 细胞开始大量克隆并消灭入侵者，那些能够识别 抗原的细胞根据识别的程度通过无性繁殖达到增生的目的：与抗原具有越高的亲和力， 该细胞就能产生更多的后代。在细胞分裂的过程中，个体细胞还经历了一个变异的过程， 其结果使它们与抗原具有更高的亲和力：父代细胞与抗原具有越高的亲和力，则它们就 经历越小的变异。 算法分六步完成，每执行完六步，生成新一代的免疫细胞： 1 1 生成候选方案的一个集合( p ) ( 初始群体) ，它由记忆细胞( m ) 的子集合加上 剩余群体( p r ) ( p = p r + m ) ； 2 ) 选择1 1 个具有较高亲和力的个体； 3 ) 克隆这n 个最好的个体，组成一个临时的克隆群体( c ) 。与抗原亲和力越高， 西南交通大学硕士研究生学位论文第13 页 ! n no i 皇曼! 鼍 个体在克隆时的规模也就越大； 4 ) 把克隆群体提交到高频变异，根据亲和力的大小决定变异。产生一个成熟的抗体 群体( c 木) ： 5 1 对c 木进行再选择，组成记忆细胞集合m 。p 中的一些成员可以被c 幸中的其它一 些改进的成员替换掉； 6 1 生成d 个新的抗体取代p 中d 个低亲和力的抗体，保持多样性。 克隆选择算法的基本架构如下： p r o c e d u r e 克隆选择算法 b e g i n 随机生成一个属性串( 免疫细胞) 的群体； w h i l e 收敛标准没有满足d 0 b e g i n w h i l en o t 所有抗原搜索完毕d o 宰初始化木 b e g i n 选择那些与抗原具有更高亲和力的细胞；宰选择宰 生成免疫细胞的副本：越高亲和力的细胞具有越多的副本；产再生木 根据它们的亲和力进行变异：亲和力越高变异越小；产变异幸 e n d ； e n d ； e n d ； 在克隆选择算法m 】表现出的重要特征中，高频变异( h y p e r m u t a t i o n ) 、受体编辑 ( r e c e p t o re d i t i n g ) 是其重要的组成部分，它们是实现多样性的基本保障。 入入交换位 原串巨匹巨臣巨匝囹原串 8 异 叵叵互田三团卫卫新串 0 一异 区匹叵巨叵叵圈新串 ( a ) 单点逆反变异( b ) 多点逆反变异 图3 2 整数形态空间变异 高频变异机制的目的是为了使免疫应答能够快速地成熟。本文只介绍整数形态空间 下变异的机制。 整数形态空间可以被看成是字母表大小缩小了的