（计算机应用技术专业论文）基于人工免疫系统的函数优化问题研究.pdf

武汉理工大学硕士学位论文 中文摘要 许多实际工程问题可以抽象为相应的函数优化问题。目前已经有很多启发 式算法用于解决函数优化问题。与传统算法相比较，启发式算法的优点在于其 有较好的全局搜索能力，避免过早收敛于局部最优解。而传统的遗传算法就是 一种比较经典的解决函数优化的算法。免疫系统是一个分布式、自组织和具有 动态平衡能力的自适应复杂系统。人工免疫系统是与生物免疫系统相对应的工 程概念，人们从免疫系统中提取、发现有用机制用来解决工程和科学问题。研 究如何根据免疫优化理论以及模拟生物免疫优化行为来设计新的有效优化算法 是非常很有意义的科研课题。克隆选择是人工免疫系统中非常重要的一个原理。 由克隆选择原理启发而得出的免疫算法，能够很好地解决函数优化问题。 本文的工作主要有以下几个方面： ( 1 ) 介绍了生物免疫原理，目前常用的免疫优化算法。总结了免疫算法与遗 传算法的特点与区别。介绍了e c o 平台，在本文中使用e c j 平台来实现遗传算 法并进行数值实验。 ( 2 ) 根据人工免疫系统中的克隆选择原理的框架，实现了一种基于克隆选择 的算法来解决无约束的数值函数优化问题。实现的免疫算法与现有克隆选择算 法的主要区别有以下两方面，编码方式和变异方式。编码方式采用实数编码； 变异方式采用一种高斯变异，个体在可行域上朝着适应值最好的点搜索，减少 了完全随机变异的不确定性。 ( 3 ) 为了测试该算法的性能，选择了几个目标函数进行优化，包括单峰函数 和多峰函数。然后将实验结果与基于e c o 的遗传算法进行比较。数值实验的结 果表明，该免疫算法能够寻找到函数的最优值，而且收敛速度很快，在收敛速 度和优化结果上都要优于遗传算法。 ( 4 ) 通过数值试验研究了免疫算法中比较关键的两个参数，种群大小和参数 卢对该免疫算法的性能影响。 关键字：遗传算法，人工免疫系统，免疫算法，克隆选择，函数优化 武汉理工大学硕士学位论文 a b s t r a c t m a n yp r a c t i c a le n g i n e e r i n gp r o b l e m s c a l lb ea b s t r a c t e dt oc o r r e s p o n d i n gf u n c t i o n o p t i m i z a t i o np r o b l e m s u n t i ln o wt h e r e a r em a n yh e u r i s t i c a l g o r i t h m s t os o l v e f u n c t i o no p t i m i z a t i o np r o b l e m s c o m p a r e dt oc o n v e n t i o n a la l g o r i t h m s ，t h em e r i to f h e u r i s t i ca l g o r i t h m si st h e i rb e t t e rg l o b a ls e a r c ha b i l i t y , w h i c ha v o i d sc o n v e r g i n gt o l o c a lo p t i m i z a t i o ne a r l y a n dt r a d i t i o n a lg e n e t i ca l g o r i t h mi sac l a s s i c a la l g o r i t h m f o rf u n c t i o no p t i m i z a t i o np r o b l e m s i m m u n es y s t e mi sad i s t r i b u t e ds e l f - a d a p t e d c o m p l e xs y s t e m a r t i f i c i a li m m u n es y s t e mi s a l li d e a c o r r e s p o n d i n gt ob i o l o g y l m m l l n es y s t e m p e o p l ef i n du s e f u ls t r a t e g yt os o l v ee n g i n e e r i n ga n ds c i e n t i f i c p r o b l e m s h o w t od e s i g ne f f e c t i v ea l g o r i t h mf o ro p t i m i z a t i o nb y s i m u l a t i n gb i o l o g y i m m u n e a c t i v i t y i sa m e a n i n g f u ls u b j e c t c i o n a l s e l e c t i o n p r i n c i p l e i s v e r y i m p o r t a n ti na r t i f i c i a li m m u n es y s t e m i n s p i r e db yt h ec l o n a ls e l e c t i o np r i n c i p l e ， t h ei l n m l m e a l g o r i t h m c a l ls o l v ef u n c t i o n o p t i m i z a t i o nw e l l t h ew o r kw ed oi nt h i st h e s i si sa sf o l l o w e d ： ( 1 ) t h ep r i n c i p l eo fb i o l o g yi m m u u es y s t e ma n dt h ec o m m o ni m m u n ea l g o r i t h m f o ro p t i m i z a t i o na tp r e s e n ta r ei n t r o d u c e d t h ec h a r a c t e r sa n dt h ed i f f e r e n c e so ft h e i m m u n ea l g o r i t h ma n dg e n e t i ca l g o r i t h ma r es u m m a r i z e d e c lw h i c hw eu s et o i m p l e m e n tg a a n dd on u m e r i c a l e x p e r i m e n t i si n t r o d u c e di nt h i st h e s i s ( 2 ) ac l o n a l s e l e c t i o n a l g o r i t h m b a s e do nc l o n es e l e c t i o n p r i n c i p l e t os o l v e n u m e r i c a lf u n c t i o no p t i m i z a t i o ni s p r o p o s e d t h e r ea r em a i n l yt w od i f f e r e n c e s b e t w e e nt h ea l g o r i t h ma n dt h ep r e s e n tc l o n a ls e l e c t i o na l g o r i t h m ，t h ew a yo f c o d i n g a n dm u t a t i o n r e a ln u m b e rc o d i n gi s a d o p t e d ak i n do fg a u s s i a nm u t a t i o ni s a d o p t e d ，w h i c h m a k et h ei n d i v i d u a l ss e a r c h e dt o w a r d st h eb e s tf i t n e s s n e a l g o r i t h mh a sn of i x e dm u t a t i o np r o b a b i l i t ya n dc a nf i n d b e s ts o l u t i o n sw i t h o u t c o n t r o l l i n g s oi tc 姐q u i c k e nt h es p e e do f c o n v e r g e n c e ( 3 ) i no r d e rt ot e s tt h ep e r f o r m a n c eo ft h ea l g o r i t h m ，s e v e r a lo b j e c tf u n c t i o n sa r e o p t i m i z e di n c l u d i n gs i n g l e - m o d a la n dm u l t i m o d a lf u n c t i o n a n dw ec o m p a r et h e r e s u l t so ft h ei m m u n ea l g o r i t h mt ot h a to fag e n e t i ca l g o r i t h m t h en u m e r i c a l e x p e r i m e n tr e s u l t sd e m o n s t r a t et h ei m m u n ea l g o r i t h mc a nf i n dt h eb e s ts o l u t i o n s 武汉理工大学硕士学位论文 w i t hf a s tc u n v e r g c n c es p e e d , w h i c hh a v eb e s tr e s u l t st h a nt h eg e n e t i c a l g o r i t h m ( 4 ) t h r o u g hn u m e r i c a le x p e r i m e n t , w cd i d ar e s e a r c ho nt h et w oi m p o r t a n t p a r a m e t e r so f t h ei m m u n e a l g o r i t h mp r o p o s e d i nt h i st h e s i s a n dw cs t u d i e dh o wt h e t w o p a r a m e t e r sa f f e c tt h ep e r f o r m a n c e o ft h ea l g o r i t h m k e y w o r d s ：g e n e t i ca l g o r i t h m ，a r t i f i c i 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 ，f u n c t i o no p t i m i z a t i o n i i 此页若属实，请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名： 至盘f ! t l i 型墨当目1 5 - r a 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：盟导师签名 注：请将此声明装订在论文的目录前。 州厂 武汉理工大学硕士学位论文 第1 章引言 1 1 人工免疫系统及其研究概述 1 1 1 问题的提出 对于很多实际问题进行数学建模后，可以将其抽象为一个数值函数的优化 问题。由于问题种类的繁多，影响因素的复杂，这些数学函数会显示出不同的 数学特征。如有些函数是连续的，丽有些函数是离散的；有些函数是凸函数， 有些函数是凹函数：有些函数是单峰值的，有些函数是多峰值的。更经常遇到 的函数是这些不同数学特征的组合。除了在函数是连续、可求导、低阶的简单 情况下可解析地求出其最优解外，大部分情况下需要通过数值计算的方法来进 行近似优化计算。尽管人们对这个问题进行了多年的研究，而至今仍尚无一种 既能处理各种不同的复杂函数，又具有良好求解结果的数值计算方法。特别是 问题的规模比较大时，优化计算时的搜索空间也急剧扩大，人们逐渐意识到要 严格地求出其最优解既不可能，也不现实。所以需要研究出一种能够在可接受 的时间和可接受的精度范围内求出数值函数近似最优解的方法或通用算法。 函数优化问题是一个典型的数值优化问题。求解数值优化问题的方法很多， 2 0 世纪8 0 年代初禁忌算法、模拟退火算法、遗传算法和人工神经网络这些启 发式算法o a c u r i s t i ca l g o r i t h m ) 的兴起，给数值优化问题增添了一些新的解决方 案。启发式算法是相对最优算法提出的，一个问题的最优算法求得该问题每个 实例的最优解，而启发式算法则可以认为是一种基于直观或经验构造的算法， 在可接受的花费下给出待解决优化问题的每个实例的一个可行解，该可行解与 最优解的偏移程度不一定事先可以预计。启发式算法可以在我们能接受的花费 下找出一个近似解。从工程实际的角度来看，在一定误差范围内的近似解都是 可以接受的。由于启发式算法的速度快，直观易行等特点，得到了很快的发展。 免疫系统( i m m u i l es y s t e m ) 是一个分布式、自组织和具有动态平衡能力的 自适应复杂系统。免疫系统对外界入侵的抗原( a n t i g e n ) ，可产生相应的抗体 ( a n t i b o d y ) 抗体上有特定的物质，可以结合、粘附或消除入侵的微生物( 即 武汉理工大学硕士学位论文 抗原) ，以维持免疫平衡。 近年来生物免疫系统的许多特性引起了人们注意，众多学者开始模仿免疫 系统的作用机制用于其它领域的研究，这些受免疫系统启发而建立的人工系统 称为人工免疫系统。对于人工免疫系统，主要有几种定义：s t a r l a b 明的定义为： “a i s 是一种数据处理、归类、表示和推理策略，该模型依据一种似是而非的 生物范式，即人体免疫系统”。d a s g u p t a 给出的定义为：“a i s 由生物免疫系统 启发而来的智能策略所组成，主要用于信息处理和问题求解”【9 l ot m a m i s 给出 的定义为：“a i s 是一种由理论生物学启发而来的计算范式，它借鉴了一些免疫 系统的功能、原理和模型并用于复杂问题的解决”1 5 】 基于免疫系统的免疫算法属于一种启发式算法。因为自然界中生物体的免 疫系统具备很高的智能级，免疫行为可以很好地保持多样性能够很好地防 止“早熟”现象。因此，研究如何根据免疫优化理论以及模拟生物免疫优化行 为来设计新的有效优化算法是非常有意义和前途的科研课题。 1 1 2 研究现状 目前人工免疫系统研究主要集中在这三个方面：a i s 网络模型，免疫算法， 免疫多样性。 ( 1 ) a l s 网络模型。目前有很多的a i s 网络模型，最著名最早提出的是1 9 7 3 年j e m e 提出的独特性网络模型( 1 d i o t y p i cn e t w o r k ) 【蚓。独特型网络能很好解 释免疫初次反应，二次反应、免疫记忆。该模型作为一种非线性动力学系统， 被广泛用于自适应控制，机器学习和故障诊断等领域。f a r m e r 在1 9 8 6 年的工 作建立的一种模型反映了j e m e 提出的独特型网络的本质特征，并确定它具有 记忆机制印j 。1 9 8 9 年p v r e l s o n 在前人的研究基础上，从抗体形态空间理论的角 度出发，在论文中给出了独特型网络的概率模型【蚓。1 9 9 5 年i s h i g u r o 提出了互 联耦合免疫网络模型( m u t u a lc o u p l e di i r m u r l cn e t w o r k ) ，即免疫系统是通过多 个完成某一特定任务的局部网络之间相互通信形成的大规模免疫网络。并提出 了一种分级递阶式免疫网络，用于六足行走机器人的速度控制【2 6 1 。1 9 9 7 年t a n g 从免疫系统中b 细胞和t 细胞之间相互作用的机制出发，提出了多值免疫网络 模型p 6j ，用于字符识别，该模型具有分类少、记忆模式新和容量大等优点。d c - c a s t r o 提出一种名叫a i n c t 的免疫网络【2 l ，他研究了免疫系统的一些基本问题， 武汉理工大学硕士学位论文 目的是研究未标识数据集合的聚类和过滤问题，表明免疫系统具有强大的计算 能力，可利用免疫概念发展强大的数据处理计算工具。该网络利用统计推论技 术实现，作者用两个数据测试集合测试其性能，并与人工神经网络进行了比较。 ( 2 ) 免疫算法。免疫算法主要是借鉴免疫原理来优化和学习的算法。目前提 出的算法有：f o r r e s t 于1 9 9 4 年提出的否定选择算法( n e g a t i v es e l e c t i o n a l g o r i t h m ) 1 5 l 。该算法模拟免疫系统中的“自我”和“非我”，定义一组“自 我集”和“监视集”，通过按概率检测系统异常，能够实现故障检测。该算法被 用于网络安全监测。1 9 9 5 年h u n t 和c o o k e 提出一种基于b 细胞网络的学习算 法结构【划。该算法以免疫系统中的b 细胞为原型，通过b 细胞网络的模式匹配 和记忆更新，可以完成复杂的模式学习和自组织记忆。该算法的基本思想被广 泛应用于模式识别和函数优化。1 9 9 6 年i s h i d a 等人借鉴免疫系统的局部记忆学 说和免疫网络学说，提出免疫a g e a t 算法【矧。该算法包括多样性产生、自忍耐 建立、记忆非我三种操作，适合用于计算机病毒库进化、网络防御和自适应控 制等领域。1 9 9 7 年c h u n 等人将免疫理论和遗传算法相结合，提出一种免疫遗 传算法( h n r u n n eg e n e t i cm g o r i t l 皿) p j 。该算法通过在遗传算法过程中添加个体 浓度控制机制，控制了高适应度的超级个体在群体中的扩散速度，从而有助于 解决遗传算法的早熟问题，具有较强的全局优化能力。2 0 0 0 年d e c a s t r o 提出 一种克隆选择算法c l o n a l g ( c l o n i n gs e l e c t i o na l g o r i t h m ) l 。该算法以b 细胞的克隆选择理论为基础，将抗原对应成求解的问题，抗体对应成问题的结 果，通过模拟b 细胞的克隆变异过程完成全局最优解的搜索，该算法适用于求 解复杂函数优化问题。 ( 3 ) 免疫多样性。主要研究成果有：1 9 9 6 年p e r e l s o n 等人提出了形状空间 理论【埔j ，通过用二进制编码表示抗体和抗原，用码位互补表示抗体对抗原的识 别。h i g h t o w e r 等人以形状空间理论为基础，对抗体基因库的形成机理做出了 进一步的研究i 圳。1 9 9 8 年o p e r a 用二进制抗体模型研究了免疫系统多样性原理 和进化意义l “l 。 人工免疫系统研究手段和内容及应用涉及多个领域，包括医学免疫学、计 算机科学技术、计算智能、人工智能、模式识别、智能系统、控制理论与控制 工程等，是比较典型的交叉学科，发展出的人工免疫系统形式也是多种多样的。 目前关于人工免疫系统的研究成果主要涉及机器人学、自动控制、计算机安全、 异常和故障诊断、模式识别、机器学习、分子生物学、图像处理、联想记忆、 武汉理工大学硕士学位论文 群体智能、搜索和优化、数据分析等许多领域。 1 2 本文主要内容 1 2 1 本文的研究内容 本文的研究内容主要是人工免疫系统领域中的免疫算法。本文根据人工免 疫系统的克隆选择原理，借鉴c l o n a l g 1 】算法，设计了一种免疫算法，将该 免疫算法用来解决无约束的数值函数优化问题。该算法的主要框架是基于抗体 细胞的克隆选择过程，在算法中个体变异过程中使用了遗传策略中的高斯变异 算子，编码方式采用浮点数编码。并且将该算法与标准遗传算法的特点作了比 较。 本文中提出的免疫算法采用j a v a 语言实现。为了测试该算法的性能，选择 了几个目标函数进行优化，其中包括单峰函数和多峰函数。将实验结果与基于 e c l l 5 6 平台计算的标准遗传算法的结果进行了对比，并从收敛速度，优化结果 上进行了统计分析。 最后然后通过数值试验，研究并且讨论了免疫算法具体实现过程中几个关 键参数对该算法性能的影响。 1 2 2 本文的组织 全文总共分六章。文章的组织如下，第一章主要介绍人工免疫系统的研究 现状和本文的研究内容。在第二章，我们将会对免疫系统的运行机制及其生物 学基础，以及目前常见的免疫优化算法的特点做一个综合的介绍。第三章描述 了人工免疫系统中的克隆选择原理以及它在优化中的应用，然后介绍了本文的 主要工作，将函数优化与克隆选择过程对应起来，具体实现一种基于克隆选择 原理的免疫算法。第四章介绍了目前函数优化中比较常用的遗传算法以及本文 的数值实验中遗传算法采用的e o 平台，接着将免疫算法与遗传算法做了比较， 总结了两种算法的区别和特点。第五章通过数值实验，我们将免疫算法和遗传 算法的优化结果和收敛代数进行了统计和讨论：研究了免疫算法中的两个重要 参数对该算法的影响。第六章主要是对前面工作的结论和对下一步工作的展望。 武汉理工大学硕士学位论文 第2 章基于免疫系统的函数优化 2 1 生物免疫系统 生物免疫系统是一种高度进化的智能系统，具有学习、识别和记忆等诸多 特征，能提供给科学和工程领域各种富有成效的技术和方法。 生物免疫系统由免疫器官、免疫组织以及多种淋巴细胞组成，淋巴细胞主 要包括t 细胞和b 细胞两种，它们分布于整个身体，在免疫中起主要作用，b 细胞可以分泌抗体，辅助t 细胞刺激或抑制b 细胞抗体的分泌。当病原体侵入 机体后，被一些b 细胞识别，这些b 细胞在t 细胞的作用下分裂，进而变成浆 细胞，分泌抗体来消灭抗原，发生免疫应答。 2 1 1 免疫运行机制 生物免疫系统的主要运行机制可归纳为以下几种【3 l ： ( 1 ) 免疫应答( i l n n l u n cr e s p o n s e ) ：指免疫细胞识别抗原、激活、分化与增 殖，以及产生免疫效应以清除抗原的过程。免疫系统会通过抗体对抗原的识别， 不断地进化出新的抗体，最终生成合适的抗体来消灭抗原，动态地适应外界环 境的变化。 ( 2 ) 免疫记忆( i m m u n em e m o r y ) ：生物免疫系统具有两种类型的免疫应答： 初次免疫应答和二次免疫应答。当抗原第一次侵入生物体时引发初次免疫应答， 在这个过程中，免疫系统通过学习抗原，利用克隆选择机制产生记忆细胞。当 相同类型的抗原再次入侵时，二次免疫应答被触发，通过唤醒记忆细胞，在更 短的时间周期内产生大量的抗体消灭抗原。据此，通过克隆复制可产生抗击已 知抗原的记忆细胞，增强免疫记忆能力。 ( 3 ) 免疫调节( 1 l d j n u n cr e g u l a t i o n ) ：在免疫应答过程中，免疫系统内部各 免疫细胞之间、抗原与抗体、抗体与抗体之间形成一个相互作用的动态平衡网 络体系，当有外界抗原入侵时，通过免疫系统的调节，可达到新的免疫平衡。 即使在无抗原入侵时，通过抗体间的相互促进与抑制反应，也能自我调节适当 数量的必要抗体使免疫应答维持免疫平衡。 武汉理工大学硕士学位论文 2 1 2 免疫原理 从信息处理的角度来看，免疫系统具备强大的识别学习和记忆的能力及分 布式、自组织和多样性等特性，这些显著的特征不断吸引着研究人员从免疫系 统中抽取有用的原理，开发相应的a i s 模型和算法用于信息处理和问题求解。 下面对免疫系统中的几个重要的免疫原理进行描述： 1 _ 克隆选择( c l o n es e l e c t i o n ) 1 9 5 7 年，奥地利免疫学家b u r n e t 提出了细胞克隆选择学说【”】，较好的解 释了免疫识别等免疫现象。该学说认为：胚胎期由于细胞的分化，体内已形成 许多淋巴细胞系，每一淋巴克隆细胞表面有一种特定的抗体受体，抗原进入体 内选择具有相应受体的淋巴细胞系并与其表面的抗原受体发生特异性结合，导 致该克隆的淋巴细胞活化、繁殖、分化，从而引起特异性免疫应答。克隆选择 理论描述了获得性免疫的基本特征，并且只有成功识别抗原的免疫细胞才能得 以繁殖。经历变异后的免疫细胞分化为抗体和记忆细胞两种。其过程见图2 1 。 参 分 记七一 l 图2 - 1 克隆选择原理图 2 抗体多样性 抗体的多样性是免疫识别的基础。抗体是具有活性的免疫球蛋白。它由四 条肽链组成，肽链是氨基酸联结成的序列。在肽链上有氨基酸数量和排列比较 稳定的恒定区，又称c 区；还有氨基酸的排列因抗体不同而不同的可变区，又 冷一 府冷 o o 酞 龟 电 h i j i l 灶r1柚等0 以 兮岔卜厶 武汉理工大学硕士学位论文 称v 区。在可变区中，有几处氨基酸排列次序比可变区其他部分更加容易改变， 它们被称作高变区，体现抗体的特异性和多样性。抗体本身具有“抗体决定簇”， 它能够被机体本身产生的其他抗体所识别并引起反应，这样，抗体便具有识别 抗原又被其它抗体识别的双重性。抗体与抗原决定簇结合的部位就是高变区。 细胞上的这些抗体能够与一定性质的抗原结合，从而改变抗原的化学结构，达 到破坏抗原的效果。如图2 2 所示。 抗体 图2 2 抗体中v 区示意图 3 浓度控制 浓度控制是免疫系统赖以保持抗体种类多样性的重要措篪。在抗原入侵肌 体，产生免疫反应的过程中，t 细胞起着控制和调节抗体浓度的作用。高亲和 度的同种抗体在抗原刺激下迅速繁衍，当浓度不断增高，并达到一定值时，该 类抗体的产生就将受到t 细胞的抑制。t 细胞的这种机制能够避免单种免疫细 胞模式垄断整个免疫细胞群体，为免疫系统的整体优化提供保证。 p e r e l s o n 研究配体( 1 i g a n d ) 和受体( r e c e p t o r ) l 盲q 交连的规律，得到了配体浓度 的方程式【”j 。再通过假设受体和配体各自的能量守恒，得出了配体受体关系。 当自由配体浓度较低时，受体的激活程度随抗体或配体浓度增加而增加；过了 激活状态后，当自由配体浓度继续增加时，受体的激活程度反而下降一受体 处于抑制状态。另外，免疫过程完成后机体内抗体浓度不会过高，否则，正常 体细胞会受到损害。 武汉理工大学硕士学位论文 由此可见，浓度控制是免疫优化中一个相当重要的特点。 4 独特型网络 j c r n e 在生物免疫学对抗体分子独特型认识的基础上，首次提出了独特型网 络模型的概念，并列出了该模型的微分方程表达式。 独特型网络模型理论认为免疫系统是由各种抗体通过相互作用构成的一个 整体，即网络，其中每个抗体作为免疫网络中的单个节点，都具有双重身份和 作用：一方面，抗体具有特殊受体，能够与抗原发生特异性结合；另一方面， 任何抗体本身也具有特异性结构，能够与其他抗体的受体发生特异性结合，因 而可以扮演抗原角色。网络中的抗体在周围环境的影响和牵制下，实行网络中 各种抗体浓度的自组织动态调整。 免疫网络理论对免疫细胞活动、抗体生成、免疫耐受、自我与非我识别、 免疫记忆和免疫系统的进化过程等做出了系统的假设，并且将免疫系统视为由 免疫细胞或者分子组成的调节网络，免疫细胞以抗体间的相互反应和不同类免 疫细胞间的相互通信为基础，抗原识别是有抗原相互作用所形成的免疫网络完 成的。 独特型网络模型可以较好的解释各种抗体自组织和记忆现象，为保持抗体 模式的多样性提供了一种方法，在许多人工免疫系统中被采用。 该原理见图2 3 。 促进拭件生成 图2 3 独特型免疫网络示意图 8 武汉理工大学硕士学位论文 一般的，人工免疫系统中的信息处理机理主要包括以下几方面： 识别自己与非己：免疫系统的阴性选择原理【1 5 1 表明，免疫系统能够识 别体内分子与外来分子。 学习与优化：免疫网络和克隆选择理论揭示了免疫应答过程的机理， 表明抗体的产生是免疫系统的学习过程【3 l ，也是一个优化过程。 联想记忆：免疫系统消灭抗原后，产生记忆细胞，当与该抗原相似的 抗原再次入侵机体时，免疫系统能产生更快速、更强烈的二次应答， 免疫记忆是一种联想记忆【1 8 1 。 自适应网络：免疫网络学说【4 5 】表明，免疫系统中的b 细胞通过识别与 被识别组成一个网络，对抗原的识别是网络中的b 细胞相互作用的结 果，免疫网络与神经网络一样，是一个能够学习和记忆的自适应网络。 并行的分布系统：免疫系统中的淋巴细胞分布于全身，根据周围的环 境自适应地确定自身的行为，整个免疫系统是一个没有控制中心的并 行的分布自治系统。 复杂系统：免疫系统本质上是一个具有“突现智能”的复杂系统。 2 2 生物免疫系统与优化计算 生物免疫系统有如下的优点【1 3 】： 免疫系统通过进化地处理具有不同特征的抗原来产生抗体，其抗体的 多样性遗传机理，使其具有很好的优化搜索能力； 免疫系统通过对抗体的相互抑制与促进反应，自我调节必要的抗体生 成，有效地解决了迭代搜索的局部收敛问题： 免疫系统具有可寻址的自组织记忆功能，并且能动态维护，具有能忘却 很少使用信息的进化学习能力，能够很快适应外界环境的改变( 不同优 化计算问题) ： 免疫系统的耐受诱导与维持机理，允许抗原被相同抗体识别，因而具 有强大的抗噪声能力； 免疫系统通过其组织细胞与分子分散到生物体内的各个部分，构成了 一个天然的没有中央处理器的分布式处理系统，可以用来解决大型和 复杂的优化计算问题。 武汉理工大学硕士学位论文 免疫系统的以上特点，为高效率地解决工程优化问题奠定了基础。 如果把算法对应为整个免疫系统，把外来入侵的抗原对应为求解问题的目 标函数，把免疫系统产生的抗体对应为问题的解，则实际问题的求解过程与生 物免疫机制是十分类似的。 2 3 免疫优化算法 2 3 1 常见免疫优化算法 不同研究人员出于不同的研究目的，开发了许多免疫算法。免疫算法模拟 了生物体的免疫系统。免疫算法从体细胞理论和网络理论等得到启发，实现了 类似于免疫系统的自我调节功能和生成不同抗体的功能。比较常见的免疫优化 算法有如下几种： 1 免疫a g e n t s 算法 基于多样性、自体耐受和免疫记忆的免疫特性，l s h i d a 从免疫系统提取出 信息处理技术，发展了一种基于a g e n t s 的免疫算法，该算法分为3 个步骤：产 生多样性，建立自体耐受，记忆非自体。该算法是一种基于a g e n t 结构方法， 其中a g e n t 群体和它们之间的通信反映了反映与环境的交互作用。在产生多样 性阶段，用类似遗传算法方式对识别器进行遗传编码。在建立自体耐受阶段， 从基于a g e n t 结构中移除对自体模型特异的识别器。在非自体记忆阶段，调整 网络参数。 免疫算法被用于噪声的自适应控制l ，该算法还可用于模型调整和决策制 定【2 9 l 。 2 b 细胞网络算法( b c e l l a l g o r i t h m ) 以独特型网络理论和克隆选择理论为基础，h u n t 等人模拟生物免疫系统的 自学习、自组织机理提出一种人工免疫网络模型b 细胞网络模型【3 03 1 l 及其 算法。该模型由骨髓、b 细胞网络、抗原、抗体组成。b 细胞网络由一组b 细 胞实现，这些细胞互相连接，通过相互作用，实现抗体模式自组织记忆。抗原 对应于最优模式，骨髓用于产生新的抗体模式，用于补充死亡的抗体或b 细胞。 算法主要步骤如下：1 调用抗原群体；2 初始化b 细胞网络；3 循环，直到 武汉理工大学硕士学位论文 满足条件：3 1 从抗原群体中随机选择一个抗原；3 2 从b 细胞网络中随机选择 一点插入抗原；3 3 选择此点b 细胞领域内某个百分比数的所有b 细胞；对 以上选中的b 细胞，计算每个b 细胞与抗原的免疫相应程度，若没有细胞产生 免疫响应，则由骨髓产生一个细胞连入网络。根据免疫响应程度进行排序；3 4 清除5 免疫响应最差的b 细胞。3 5 由骨髓随机产生2 5 新b 细胞，选择其中 5 最好的细胞连入网络。 该算法在机器学习和优化计算中应用较广，其缺点是计算量大。 3 免疫遗传算法( i m m u n eg e n e t i c a l g o r i t h m ) 借鉴免疫系统中抗体的浓度控制原理，文 3 7 1 提出一种免疫遗传算法。为 了克服遗传算法容易出现早熟现象的缺陷，免疫遗传算法在简单遗传算法的基 础上增加了抗体浓度概率激素、抗体的促进与抑制、抗体散布性计算三个模块 来提高解的多样性。其中：抗体浓度是指与某一抗体相同或相近的抗体被看作 同一抗体；抗体的选择概率取决于其适应度概率和浓度概率，高适应度概率和 低浓度概率的抗体的选择率相对较高，因此该抗体受到促进；反之低适应度概 率和尚浓度概率的抗体的选择率相对较低，因此改抗体受到抑制：抗体的散布 性是指每一代抗体群都应具有较好的分布特性。通过抗体的散布性计算来衡量 新一代抗体群是否已达到要求。一旦抗体的散布性满足要求，则可停止新抗体 的产生。算法过程以基本的遗传算法为框架，中间加入了免疫算子。 该方法因为将免疫系统中抗体多样性维持机制引入了遗传算法，使得免疫 遗传算法比标准遗传算法更近了一步。 4 克隆选择算法( c l o n a ls e l e d i o n a l g o r i t h m ) 克隆选择是免疫优化的重要方式，在人工免疫系统中被广为应用。d c c 弱t r o 提出一种克隆选择算法( c l o n a l g ) 。算法模拟免疫细胞克隆选择原理。 被选择的细胞受制于亲和力成熟过程，该过程改善对抗原的亲和力。 算法主要步骤如下：1 产生候选方案的集合s ( p ) ，该集合为记忆细胞子集( m ) 和剩余群体( p r ) 的总和( p = p r + m ) ；2 基于亲和度度量确定群体p 中的n 个最佳 个体p n ：3 对群体中的这n 个最佳个体进行克隆( 复制) ，生成临时克隆群体c 克隆规模是抗原亲和度度量的单调递增函数；4 对克隆生成的群体施加变异操 作，变异概率反比于抗体的亲和度，从而生成一个成熟的抗体群体( c ) ；5 从c 武汉理工大学硕士学位论文 中重新选择改进个体组成记忆集合，p 集合的一些成员可以由c 的其他改进成 员加以替换；6 将群体中的d 个低亲和度的抗体予以替换，从而维持抗体的多 样性。 文【1 】中应用该算法进行二进制字符识别，证明其学习和知识获取的潜能。 同时也将该算法应用到多峰函数优化任务以及著名的旅行商( t s p ) 问题。 2 3 2 免疫优化算法特点 综合上述基于人工免疫系统的优化算法，可以总结出免疫算法有如下一些 特征： 免疫优化算法是建立在编码上的随机优化算法。各种优化问题的解首 先必须转化成相应的编码串，然后对编码串进行处理。 免疫优化算法属于并行优化算法，其操作的对象均是一个种群。 免疫优化算法是以反复的进化过程为特征，通过随机搜索，并不断强 化优势个体，完成群体进化，最终获得最优个体。个体的筛选不根据 优化函数，因而对函数形态没有特殊要求。 保持模式多样性是免疫优化算法中非常重要的特征。 武汉理工大学硕士学位论文 第3 章基于克隆原理的免疫算法 3 1 克隆选择原理特点 克隆选择原理最先由j e m e 提出，后由b u r n e t 予以完整阐述。其大致内容为： 当淋巴细胞实现对抗原的识别( 即抗体抗原的亲和度超过一定阈值) 后，b 细胞 被激活并增殖复制产生b 细胞克隆，随后克隆细胞经历变异过程，产生对抗原具 有特异性的抗体。克隆选择理论描述了获得性免疫的基本特性，并且声明只有 成功识别抗原的免疫细胞才得以增殖。经历变异后的免疫细胞分化为效应细胞 ( 抗体l 和记忆细胞两种。 克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖，随后通过遗 传变异分化为多样性效应细胞( 如抗体细胞) 和记忆细胞。克隆选择对应着一个 亲合度成熟( a t t m i t ym a t u r a t i o n ) 的过程，即对抗原亲合度较低的个体在克隆选择 机制的作用下，经历增殖复制和变异操作后，其亲合度逐步提高而“成熟”的 过程。因此亲合度成熟本质上是一个达尔文式的选择和变异的过程，克隆选择 原理是通过采用变异等算子和相应的群体控制机制实现的。 免疫系统在成长的过程中也是自适应的，呈现出一种变异机制，在对抗体 特异编码的基因中产生极高频率点变异。这种高频变异的机制与为改进抗原结 合而进行的选择，共同导致细胞与抗原具有亲和力匹配。 3 2 基于克隆选择的函数优化 3 2 1 问题描述 一般的地，最优化问题由目标函数和约束条件两部分构成： m i l l i m i z c f ( x ) - f 瓴，恐，而) s u b j e c tz - “l ，j 2 ，x 。) e s c x 满足所有约束条件的解空间s 称为可行域，可行域中的解称为可行解。在 可行域中使目标函数最小的解为最优解。对于最大化问题，可将目标函数乘以 武汉理工大学硕士学位论文 ( 一1 ) ，转化为最小化问题求解【4 7 1 。 从人工免疫系统观点来看，数值函数优化即在给定范围内发现最优值的问 题，等同于抗体群体进化来识别单个抗原。抗原对应于要求解的问题，最好的 抗体对应于问题解的最优值，函数值对应于抗体和抗原的亲和度。通过这样的 一种对应方式，可以设计出针对函数优化的免疫算法。 3 2 2 克隆选择在优化中的应用 基于克隆选择的函数优化最初由f u k u d a 提出【3 2 1 。该算法由如下步骤构成： ( 1 ) 抗原识别，即：导入待优化函数。 ( 2 ) 利用记忆细胞产生抗体，抗体用二进制编码表示。 ( 3 1 计算抗体与抗原的亲和度。 ( 4 ) 亲和度较高的抗体按亲和度比例克隆增生，其中浓度特别高的抗体增生 程度将被抑制，以维持抗体多样性。 部分亲和度较高的抗体加入记忆细胞群体，其它的被淘汰。 ( 6 ) 产生新的抗体替换部分亲和度过低的抗体。 2 0 0 0 年d ec a s t r o 等人对克隆选择原理进一步研究与浓缩，提出一种比较 简单的克隆选择算法( c l o n a i g ) i 。该算法包括一组抗原，一组抗体，一组记 忆细胞，其基本操作是抗体细胞的高变异克隆繁殖、以及对最优模式的选择记 忆。该算法在模式识别、组合优化和多峰值函数优化中得到了验证。能够很好 的保持群体多样性从而求得多种优化解。但是，从论文无法提取出具体的试验 结果数据，因此，难以评估该算法的潜在性能，也无法和其他的算法做具体比 较。 2 0 0 2 年c a r l o s 等人提出一种以克隆选择为核心的人工免疫系统，用来解决 多目标函数优化问题。文 3 8 1 将该算法与三种比较有名的多目标函数优化方法 比较，仿真结果显示，基于克隆选择的方法能够搜索和保存更多的p a r e t o 解。 t m a m i s 提出一种bc e l l 舢g o 酬i l m ( b o q 用于解决函数优化问题f 柏1 。并将结 果与一种混合遗传算法( h g a ) 做比较。结果显示在寻找到最优值上面，b c a 要优于h g a 。 免疫算法作为一种比较新的优化算法逐渐引起了人们的注意，不过由于它 起步比较晚，其应用研究的广度和深度还有待进一步加强。上面提出的几种基 武汉理工大学硕士学位论文 于克隆选择原理的算法说明了，我们能够以该原理为出发点，从中提取出有用 的算法用于解决各种优化问题。 3 3 一种基于克隆原理的免疫算法实现 3 3 1 算法框架 本文提出的一种免疫算法i a ( i m m u n e a l g o r i t h m ) ，主要算法框架是依据克 隆选择过程，结合了c l o n a i x 3 算法框架，在算法中个体变异中采用了遗传策 略中的高斯变异算子，编码方式采用浮点数编码。 免疫算法i a ( 1 m m l l n c ：a l g o r i t h m ) 的步骤如下： 初始化：在取值范围内，随机生成一个抗体群a b 。，种群大小为。 循环：对于群体中的每个抗体d o ： ( 1 ) 适应值( f i t n e s s ) 计算：计算出每个抗体和抗原的亲和度，也就是目标 函数的适应值。 ( 2 ) 选择：选择和抗原亲和度( 目标函数的适应值) 最高的n 个抗体a b , 。 ( 3 ) 复制：对于选择出来的抗体a b 进行复制，组成一个更大的抗体群c ， c 的大小为 ( 4 ) 变异：根据每个抗体的适应值，对抗体群中c 中的个体采用高斯变异。 得到新的抗体群c 。变异方式根据公式3 - l ： ( 5 ) 替代更新：取c 中的前n 个抗体组成一个抗体群一6 ，随机产生d 个新 的抗体，将原来a b 中亲和度最低的d 个个体替换。形成了新一代的抗体群。 w h i l e ( 小于代数i t e r a t i o n 或者符合收敛条件) 该算法流程图如图3 2 。 步骤( 4 ) 中的根据适应值的高斯变异