（计算数学专业论文）关于免疫遗传算法的研究.pdf

捅要 遗传算法是一种具有“生成+ 检测”迭代过程的搜索算法。群体搜索和群体中个体 之间信息相互交换是通过交叉和变异算子来实现的，算法在迭代搜索的过程中，交叉算 子和变异算子都是在一定概率的条件下，随机地实现的。因此，交叉算子和变异算子在 为群体中的个体提供进化机会的同时，也无可避免地产生了退化的可能。另一方面，每 一个待求的实际问题都会有自身一些显而易见的、基本的知识或特征信息。但是遗传算 法的交叉算子和变异算子却相对固定，在问题求解的过程中，可变的灵活程度较小。也 就是忽视了问题的特征信息在问题求解时的辅助作用，特别是在求解一些复杂问题时， 这种“忽视”所带来的损失往往是很明显的。 生物免疫系统具有免疫记忆、抗原识别和保持抗体的多样性等特性，本文研究根据 这些特性而提出的一种改进遗传算法一免疫遗传算法，该算法将生物免疫系统中的免疫 思想引入到遗传算法中，即利用先验知识构造免疫算子，通过接种疫苗和免疫选择，既 保留了群体中的最优个体又保证了个体的多样性，从而避免了进化搜索的过早收敛，提 高算法的收敛速度。同时设计了一种改进的免疫遗传算法，即将免疫算子引入传统的遗 传算法，并采用适时的动态疫苗接种，同时给出了一种停机准则。在对算法阐述过程中， 给出了免疫疫苗的选取策略和免疫算子的构造方法。函数优化仿真实验结果表明，与传 统的遗传算法相比，改进的免疫遗传算法不仅是有效的，也是可行的。改进的算法不仅 可以较好地解决已有算法中出现的退化现象，而且使收敛速度有显著提高。 论文就改进的基于疫苗接种的免疫遗传算法进行了简单的收敛性分析，得出了改进 的免疫遗传算法是概率1 收敛的。 关键词 遗传算法，免疫遗传算法，免疫算子，免疫疫苗，疫苗接种 a b s t r a c t g e n e t i ca l g o r i t h mi s a ”g e n e r a t i o na n dd e t e c t i o n ”i t e r a t i v ep r o c e s so ft h es e a r c h a l g o r i t h m t h ea l g o r i t h mb yc r o s s o v e ra n dm u t a t i o no p e r a t o ra c h i e v e sg r o u ps e a r c ha n d g r o u pi n f o r m a t i o ne x c h a n g eb e t w e e ni n d i v i d u a l s ，i n o r d e rt oo p t i m i z et h eo p p o r t u n i t i e s p r o v i d e db ye a c hi n d i v i d u a l ，s o t h a tt h eg r o u p se n s u r et h a tt h ed i r e c t i o no fe v o l u t i o ni n s e l e c t i o nm e c h a n i s mo fs u r v i v a lo ft h ef i t t e s t h o w e v e r , i nt h es e a r c h i n gp r o c e s so fi t e r a t i v e a l g o r i t h m ，t h ec r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o ra r er a n d o m l yr e a l i z e du n d e rt h e c o n d i t i o n so fac e r t a i np r o b a b i l i t yo fo c c u r r e n c e t h e r e f o r e ，t h e yh a v ep r o v i d e dt h e o p p o r t u n i t i e so fi n d i v i d u a le v o l u t i o nf o rt h eg r o u p ，a n da l s oi n e v i t a b l yr e s u l t e d i nt h e p o s s i b i l i t yo fd e g r a d a t i o n e a c hp r a c t i c a lq u e s t i o nr e q u e s t e dw i l l h a v ei t so w nb a s i ca n d o b v i o u sc h a r a c t e r i s t i c si n f o r m a t i o no rk n o w l e d g e h o w e v e r ，g e n e t i ca l g o r i t h m sc r o s s o v e r a n dm u t a t i o no p e r a t o ra r cr e l a t i v e l yf i x e d ，i ns o l v i n gp r o b l e m s ，l e s sf l e x i b l ea n dv a r i a b l e ， n a m e l y , t h e yi g n o r eas u p p o r t i n gr o l ei n t h ec h a r a c t e r i s t i c si n f o r m a t i o no ft h ep r o b l e m ， e s p e c i a l l yi ns o l v i n gs o m ec o m p l e xp r o b l e m s ，t h i s ”n e g l e c t ”i so f t e nb r o u g h ta b o u tl o s so f m o r ed i s t i n c t l y i nt h i sp a p e r , b a s e do nb i o l o g i c a li m m u n es y s t e m sa n t i g e nr e c o g n i t i o n ，m a i n t a i n i n gt h e d i v e r s i t yo fa n t i b o d i e sa n di m m u n em e m o r ya n do t h e rf e a t u r e s ，ap r o p o s e di m p r o v e dg e n e t i c a l g o r i t h m t h ei m m u n eg e n e t i ca l g o r i t h mi sp u tf o r w a r d ，t h ea l g o r i t h mw i l li n t r o d u c et h e t h i n k i n go fb i o l o g i c a ls y s t e m si m m u n et o t h eg e n e t i ca l g o r i t h m ，n a m e l yi nu s eo ff i r s t i m m u n ek n o w l e d g ei ts t r u c t u r e si n s p e c t i o no p e r a t o r b yv a c c i n a t i o na n di m m u n es e l e c t i o n ，i t n o to n l yr e t a i n st h eb e s ti n d i v i d u a lg r o u p sb u ta l s oe n s u r e st h ed i v e r s i t yo fi n d i v i d u a l s ，t h u s a v o i d i n gt h ep r e m a t u r ec o n v e r g e n c eo fe v o l u t i o n a r ys e a r c ha n di m p r o v i n gc o n v e r g e n c es p e e d m e a n t i m e ，a ni m p r o v e di m m u n eg e n e t i ca l g o r i t h mi sd e s i g n e d ，t h a ti s ，i n t r o d u c i n gi m m u n e o p e r a t o rt ot r a d i t i o n a lg e n e t i ca l g o r i t h m ，a n da d o p t i n gt i m e l yd y n a m i cv a c c i n a t i o na n dt h e s h u t d o w nc r i t e r i aa r eg i v e n i nt h ep r o c e s so fd e s c r i b i n ga l g o r i t h m ，t h es e l e c t i o ns t r a t e g yo f i m m u n ev a c c i n e sa n dt h ec o n s t r u c t e dm e t h o do fi m m u n eo p e r a t o ra r eg i v e n f u n c t i o n o p t i m i z a t i o ns i m u l a t i o nr e s u l t ss h o w t h a tw i t ht h et r a d i t i o n a lg e n e t i ca l g o r i t h m ，t h ei m p r o v e d i m m u n eg e n e t i ca l g o r i t h mi se f f e c t i v ea n df e a s i b l e i m p r o v e da l g o r i t h mc a nn o to n l ys o l v et h e a p p e a r e dt h ed e g r a d a t i o no ft h ep h e n o m e n o no ft h ea l g o r i t h m ，b u ta l s ot h ec o n v e r g e n c er a t e h a sm a r k e d l yi m p r o v e d i m p r o v e di m m u n eg e n e t i ca l g o r i t h m b a s e do nv a c c i n a t i o nc o n d u c t sas i m p l e c o n v e r g e n c ea n a l y s i sa n dc o m e st ot h ec o n v e r g e n c e o ft h ep r o b a b i l i t yo f1 1 i k e y w o r d s g e n e t i ca l g o r i t h m ，i m m u n eg e n e t i ca l g o r i t h m ，i m m u n eo p e r a t o r , v a c c i n e ，v a c c i n a t i o n i i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：二夸道靶指导教师签名： 年月1 7 日7 ，年月? 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：米蛾 7 年月7 e t 西北大学硕士学位论文 第一章绪论 1 1 遗传算法和免疫优化计算的发展及研究现状 进化计算是一类模拟生物进化过程与机制来求解问题的自适应、自组织人工智能技 术，是一种具有“生成+ 检测”的迭代过程的搜索算法，该算法以实现群体和群体中个 体之间信息交换的两大策略的交叉算子和变异算子为每个个体提供优化的机会，从而使 整个群体在优胜劣汰的选择机制下保证进化的趋势。其中最著名的方法有基于达尔文进 化论思想的遗传算法和生物免疫系统的免疫优化计算。 1 1 1 遗传算法的发展与研究现状 遗传算法起源于2 0 世纪6 0 年代，美国m i c h i g a n 大学的j o h nh o l l a n d 教授在对自然 和人工自适应系统的研究时提出的【1 1 。7 0 年代d ej o n g 在计算机上基于遗传算法的思想 进行了大量的纯数值优化计算实验【2 1 。8 0 年代由g o l d b e r g 在一系列研究工作的基础上对 其进行归纳总结，形成了遗传算法的基本框架【3 1 。8 0 年代末是遗传算法的发展高潮，一 直延续至今。 遗传算法使用群体搜索技术，它通过对当前群体施加一系列遗传操作，产生出新一 代的群体，并逐步使群体进化到接近或包含最优解的状态。遗传算法具有思想简单、易 于实现、并行、通用、稳健性、从多个点开始寻优、容易获得最优解等优点，因而被广 泛应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域【4 ，5 。文【8 ， 9 1 0 应用遗传算法求解旅行商问题、背包问题、布局优化等n p 难度的问题。文 1 1 】将 遗传算法应用到手写体汉字识别系统的优化中。文 1 2 】已成功地开发了一个基于遗传算 法的数据挖掘工具。文【1 3 提出并设计了一种单纯形法和g a ( g e n e t i ca l g o r i t h m ) 相结合 的启发式优化方法，来求解生产规划模型中的维数灾、局部解等问题。文 1 4 通过在传 统遗传算法中引入最优点变异算子和低适应度值高变异算子等非自然规则，建立超自然 g a 。 为了扩大g a 的应用领域和使之更加有效，人们对其执行策略做了大量的改进工作， 设计了很多算法，主要有以下几方面【1 5 】： a 混合遗传算法，如文献 1 6 ，1 7 - 2 0 】； b 遗传算法与局部优化方法的结合，如文献 2 1 ，2 2 】； c 并行遗传算法( p a r a l l e lg e n e t i ca l g o r i t h m ) ，如文献 2 3 】； d 共存演化遗传算法( c o o p e r a t i v ec o e v o l u t i o n a r yg a , c c g a ) 。 第一章绪论 1 1 2 免疫优化计算的发展及研究现状 传统的遗传算法是一种具有“生成+ 检测 迭代过程的搜索算法，因为有着其他传 统优化方法无法比拟的优点而被广泛应用，但是很多实践表明，在应用中，遗传算法有 许多缺陷，例如对于多峰值函数的优化，往往出现“早熟”现象，使得算法收敛于非最 优值。那么，将生物中的免疫概念引入到工程应用领域，研究免疫优化理论和生物免疫 优化行为，借助免疫的有关知识和理论，并将其与遗传算法有机的结合起来，建立新的 理论与算法来改进遗传算法以提高遗传算法的整体性能在理论上和实践上都有重要意 义。 在国内，焦李成、王磊等人通过模拟自我免疫机制设计了一种免疫遗传算法，不仅 证明了该算法的全局收敛性，而且将其应用于t s p 问题的优化求解【2 4 1 ，证明了该算法 的有效性，填补了国内免疫遗传算法研究的空白。其后，人们模拟免疫行为中的抗体记 忆、抗体的抑制、促进和抗原识别等免疫行为设计出免疫遗传算法，通过用于t s p 优化、 b p 网络的辅助设计和多峰值函数优化，表明i g a 提高了遗传算法的全局和局部搜索能 力，避免了遗传算法易出现早熟即不能很好地保持个体多样等问题f 2 5 ，2 6 瑚】。2 0 0 3 年，文 2 9 将免疫遗传学的基本思想引入到优化设计中，模拟生物体的实际免疫行为，设计出了 融合应答、免疫记忆、基因重组、新陈代谢、浓度控制、隔离小生境技术和混沌思想的 实用化的i g a 。2 0 0 5 年，文 3 0 引入鞍方法，通过对免疫算子的研究，得出了i g a 本身 的几乎处处强收敛性结论，并对i g a 进行了收敛速度估计。文【31 1 采用免疫算子和保优 策略提出了自适应i g a 文 3 2 】提出了基于相似矢量距为选择概率的i g a ，并给出了此类 概率选择的一般表示形式。2 0 0 7 年，文 3 3 】借鉴生物免疫概念与理论并结合并行计算的 思想提出了基于免疫的并行单亲遗传算法。2 0 0 8 年，文 3 4 提出了一种基于群划分和杂 交的i g a ，通过划分种群并对种群间的最优个体进行杂交来提高算法的速率和稳定性。 在国外，最早提出免疫系统的遗传建模方法的是美国的a p e r e l s o n 和s f o r r e s t 。c h u n 等基于免疫网络理论和体细胞理论提出了一种免疫算法。t a z a w a 等利用小生境技术提出 了一种遗传特性与免疫系统相结合的免疫遗传算法【3 s 。g a o 等提出一种基于免疫多样性 的选择算子【3 6 】。k a z u y u k i 等提出了免疫优化算法并将其应用于解决自适应调度问题【3 7 1 。 1 2 论文研究的背景和意义 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的自适应搜索算法。遗传 算法有以下特点：( 1 ) 直接对结构对象进行操作，不存在函数可导和连续的限定；( 2 ) 采 用概率化的寻优方法；( 3 ) 具有内在的隐并行性和良好的全局寻优能力；( 4 ) 较传统的搜 2 塑! ! 奎堂婴主兰垡丝茎 索算法使用方便、鲁棒性强；( 5 ) 能自动获取和指导优化的搜索空间，自适应地调整搜索 方向，不需要确定的规则。因此，得n - y 广泛的应用【4 ，5 刀。实际上g a 不会比其他的算 法有效，虽然对于某些问题，g a 与别的优化算法至多是一样有效的，但是其解决复杂 优化的潜力是传统的优化算法难以比拟的。遗传算法已成为计算智能研究中的热点，受 到许多学科的共同关注。但是遗传算法作为一种新的人工智能方法，无论是算法本身还 是在其具体实现上都存在着不足。 就其算法本身而言，由于自然进化和生命现象的“测不准”性，遗传算法不可避免 的存在概率算法的缺陷，即在对算法的实施过程中两个主要遗传算子一交叉算子和变异 算子都是在一定发生概率的条件下，随机地进行迭代搜索，因此交叉算子和变异算子在 为群体中的个体提供进化机会的同时，也不可避免的产生早熟、种群多样性减少等退化 现象。遗传算法在实践中的明显缺点是收敛速度慢和未成熟收敛【3 8 1 。另一方面，每一个 待求的实际问题都会有自身的、先验知识或者特征知识，但是在问题求解得过程中，遗 传算法的交叉算子和变异算子可变的灵活程度较小，这对于求解一些复杂问题所带来的 损失往往是比较明显的。缺乏有效的局部搜索机制和没有很好的利用问题先验知识，是 遗传算法在具体实现中的重要缺陷；从某种角度来讲，先验知识在一定程度上有助于实 现局部搜索；而且，传统的遗传算法只是严格而简单的模拟了达尔文进化，突出了基因 遗传对生物种群的重要性，而忽略了个体学习与种群整体进化的关系。因而，研究和改 进遗传算法，扩展其应用范围是其发展的一个重要而有意义的课题。 本文正是针对传统的遗传算法难以引进问题先验知识，提出了集免疫机制和进化机 制于一体的一种新的改进的遗传算法一免疫遗传算法。通过在遗传算法的基本框架里 引入免疫算子，有针对性的抑制由变异操作的盲目性而引起的退化现象。显然这一研究 课题不仅对发展遗传算法具有很大的新意，而且有一定的探索性。另一方面，免疫思想 的引入大大改善了遗传算法的性能，使其在优化计算中得到更广泛的应用，从而提高优 化计算的水平和效率。 1 3 论文的主要内容 本文共分四章，具体章节安排如下： 第一章主要阐述了本课题研究的背景、意义以及免疫遗传算法的发展及研究现状 和本文的组织结构。 第二章主要介绍了遗传算法的基本原理、特点，并分析了遗传算法所存在的缺陷， 且在遗传算法的基础上研究了免疫遗传算法的设计原理和特点。 第一章绪论 第三章主要介绍了一种改进的免疫遗传算法一基于动态疫苗接种的免疫遗传算 法。首先给出基本的基于疫苗接种的免疫遗传算法，然后提出了一种新的基于动态疫苗 接种的免疫遗传算法，并对算法的免疫算子( 疫苗提取、接种疫苗和免疫选择) 、基本 思想、流程和步骤进行了具体详尽的描述，最后用新的算法对多峰值函数进行了仿真试 验分析，并与s g a ( s i m p l eg e n e t i ca l g o r i t h m ) 的求解结果进行了比较，结果表明新的算 法不仅是可行的，而且是有效的。 第四章给出了与收敛性分析有关的马尔可夫链及其相关的性质，并对于新的基于 动态疫苗接种的免疫遗传算法的收敛性做了分析。 接着对所研究的内容进行了总结，得出了结论并给出了基于疫苗接种的免疫遗传算 法今后的研究方向。 最后是参考文献，作者在攻读硕士学位期间取得的科研成果和致谢。 4 西北大学硕士学位论文 第二章免疫遗传算法的原理和方法 2 1 引言 免疫遗传算法就是在遗传算法原有的理论框架里引入免疫思想，即利用生物免疫系 统的抗原识别、保持抗体的多样性和免疫记忆的特性而提出的一种改进的遗传算法。仿 真试验结果表明其可以很好的防止遗传算法出现“早熟”现象和未成熟收敛，提高优化 计算的效率。但就其实质而言，免疫遗传算法还是遗传算法，如何通过模拟生物实际免 疫行为来设计出合理的免疫优化算法，来改进传统遗传算法的优化效果是本章研究探讨 的目的。为此，先具体分析一下传统遗传算法的原理和缺陷。 2 2 遗传算法的原理和缺陷 遗传算法自2 0 世纪6 0 年代出现以来得到了广泛的应用，但是由于遗传算法自身存 在许多难以解决的问题，如控制参数的选择、早熟收敛、随机漫游等。这些问题的存在 给遗传算法的实际应用带来了极大的不便。因此，研究如何解决这些问题，提高优化效 率就显得十分必要。为此，需要从遗传算法的原理开始着手研究。 2 2 1 遗传算法的运算过程 g o l d b e r g ( 1 9 8 9 ) 等归纳总结出遗传算法的一般运算过程，其中编码形式采用二进制， 繁殖分为交叉与变异两个独立的步骤，具体如下【3 9 】： s t e p l ( 初始化) 确定种群规模，交叉概率只，变异概率己；设置终止进化准则； 随机生成个个体作为初始种群义( o ) ；置t ：= 0 。 s t e p 2 ( 个体评价) 计算或评价x ( t ) 中各个个体的适应度。 s t e p 3 ( 种群进化) 3 1 选择( 母体) 从x ( ，) 中运用选择算子选择出m 2 对母体( m ) 。 3 2 交叉对所选择的m 2 对母体，以概率p 执行交叉，形成m 个中间个体。 3 3 变异对m 个中间个体分别独立依概率己执行变异，形成m 个候选个体。 3 4 选择( 子代) 从上述所形成的m 个候选个体中依适应度选择出个个体组成新 一代种群x ( t + 1 ) 。 s t e p 4 ( 终止检验) 如已满足终止准则，则输出x ( r + 1 ) 中具有最大适应度的个体作 为最优解，终止计算，否则置f ：= t + 1 并转s t e p 3 。基本遗传算法的流程如图1 所示： 第二章免疫遗传算法的原理和方法 图1 基本遗传算法的流程图 2 2 2s g a 的构成要素【8 】 1 编码方法。s g a 用固定的二进制符号串来表示群体中的个体，其等位基因是由符 号集 o ，1 ) 所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。如： x = 1 0 0 111 0 0 1 0 0 0 1 0 11 0 1 就可以表示一个个体，该个体的染色体长度为n = 1 8 。 2 个体适应度评价。s g a 按与个体适应度成正比的概率来决定当前群体中每个个体 遗传到下一代群体中的机会多少。 3 遗传算子。s g a 使用三种遗传算子：选择运算、交叉运算和变异运算。 4 运行参数。以下4 个运算参数需提前设定： m ：群体大小，即群体中所含个体的数量，一般取为2 0 1 0 0 。 丁：遗传算法的终止进化代数，一般取为1 0 0 5 0 0 。 p ：交叉概率，一般取为0 4 o 9 9 。 巴：变异概率，一般取为0 0 0 0 1 0 1 。 注意：遗传算法的求解结果和求解效率与这四个参数有一定的关系，但目前还没有合理 设定这四个参数的理论依据，在我们实际的应用计算中，往往要经过多次试算和实验才 能确定这些参数的取值大小。 6 西北大学硕士学位论文 下面对三种遗传算子做具体的说明。 1 选择运算 选择运算是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代去 群体中的一种遗传运算。常用的方法比例选择，最优保存策略，确定式采样选择，无回 放随机选择，无回放余数随机选择，排序选择和随机联赛选择。 2 交叉运算 所谓交叉是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成 两个新的个体。交叉算子主要包括单点交叉，双点交叉与多点交叉，均匀交叉和算术交 叉。 3 变异运算 变异运算是指用个体染色体编码串中的某些基因位上的其他基因等位基因来替换 该基因位上的基因值来形成一个新的个体。变异算子包括基本位变异，均匀变异，边界 变异，非均匀变异和高斯变异。 2 2 3 遗传算法的特点和缺陷 遗传算法是一种鲁棒搜索算法，可用于复杂优化计算，与其他的传统优化算法相比 较主要有以下的几个特点f 3 】： 1 遗传算法的运算对象是决策变量的编码，而不是直接利用决策变量的实际值本 身来进行优化计算。 2 遗传算法直接以目标函数值作为搜索信息，而不需要目标函数的导数值等其他一 些辅助信息，就可以确定搜索进一步的搜索方向和搜索范围。 3 遗传算法同时使用多个搜索点的搜索信息，而不是从单个点开始搜索。 4 遗传算法使用概率搜索技术，而不是确定性的搜索方法，这样可以增加其搜索过 程的灵活性。 上述这些特点使得遗传算法和其它搜索方法相比有许多优越性，即使用简单，鲁棒 性强，良好的全局搜索性，易于并行化等，从而使其应用非常广泛。虽然s g a 的算法 体系在理论上已经较为完善，然而在单峰函数或单调函数，尤其是多峰函数的实际优化 应用中，s g a 就会出现收敛速度慢和“早熟现象。这是遗传算法本身的缺陷，由于自 然进化和生命现象的“测不准”性，遗传算法不可避免存在概率算法的缺陷。遗传算法 属于一种自适应概率搜索技术，在对算法的实施过程中选择、交叉、变异等运算都是在 一定概率发生的条件下进行的。s g a 的选择策略多采用个体繁殖机会同其适应值成正比 7 第二章免疫遗传算法的原理和方法 例的方法，这样就很容易导致超级个体问题和多个相似数字串问题。交叉率和变异率是 根据经验选取的固定值，交叉率太低时，由于群体规模进化过程中缺乏多样性而极易陷 入局部最优，导致群体过早收敛；当交叉率过高时，虽可保证群体的多样性，但当优化 到最优点附近时，会使个体难以接近最优点，导致群体收敛速度显著放慢。变异虽然可 以保持群体多样性，但经过多次迭代后群体会形成“近亲繁殖 ，不可避免地产生早熟、 种群多样性减少等“退化”现象。在实践中，仿真结果表明遗传算法最明显的特点是收 敛速度慢和未成熟收敛 3 9 , 4 0 。这些缺陷大大限制了遗传算法的应用范围。因此，研究如 何改进s g a ，采用合适的算法提高遗传算法的整体性能在理论和实践上有重要意义。 2 3 免疫遗传算法基本原理和特点 2 3 1 生物免疫学原理 免疫是指生物体维持自身生理活动平衡与稳定、自主抵御外界病毒与细菌侵入的生 命现象。生物的免疫系统由众多器官、细胞与分子相互作用构成，其主要的作用方式是 由t 细胞介导的细胞免疫，以及由b 细胞分泌抗体发挥免疫功能的体液免疫。生物免疫 功能包括洲：( 1 ) 免疫防御( 2 ) 免疫稳定细胞( 3 ) 免疫监视。免疫细胞识别抗原、活化、 分化与增值以及消除抗原的过程在免疫学中被称为免疫应答。免疫应答大体上分为三个 阶段，即感应阶段，增值、分化阶段和效应阶段。抗体是具活性的免疫球蛋白。免疫系 统具有以下特性：( 1 ) 识别多样性，其一，只要抗体和抗原之间有相当程度而不是完全 的匹配时，免疫系统即可对这样的抗原予以识别；其二，一种抗体可以识别多种不同的 抗原；其三，存在“细胞超变异”，可以应付入侵抗原的变种，从而进一步提高免疫识 别的多样性能力。( 2 ) 存在免疫记忆。当抗原初次侵入机体时，抗体产生慢，抗体数量 低，抗原清除就比较慢，但经过一段时间后，同一种抗原再次侵入机体时抗体增值快， 数量比初次应答高，抗原消灭快，这种现象称为免疫记忆。另外，通过疫苗接种的方法 能够增强机体内特定类免疫细胞以及相应记忆细胞的存在和数量，以达到人工免疫的手 段而加强生物体的免疫功能【3 9 1 。 2 3 2 免疫遗传算法基本原理和特点 为了克服遗传算法在实际工程优化计算中出现的早熟收敛问题，以提高遗传算法的 全局搜索能力，将免疫算予引入到标准遗传算法的框架里，构造出了一种新的改进遗传 算法一免疫遗传算法。为了克服遗传算法中交叉算子和变异算子操作的盲目性，在原有 遗传算法中引入免疫概念和方法，用局部特征信息以定的强度干预遗传算法的全局搜 8 西北大学硕士学位论文 索过程，来达到抑制或避免求解过程中的一些重复和无效的工作的目的。算法的核心是 合理提取疫苗，为了使群体适应度相对稳定地提高，算法在执行时，通过有针对性地抑 制群体进化过程中出现的一些退化现象来达到目的。 根据生物免疫学原理，我们发现遗传算法的求解过程与生物免疫系统的运行机制非 常相似。当抗原入侵时，通过细胞的增殖和分化作用，免疫系统可产生大量的抗体来抵 御。如果把遗传算法中求解优化问题的目标函数和约束条件看作“抗原”，而把优化问 题的解看作“抗体 ，那么遗传算法搜索优化问题最优解的求解过程就类似于生物免疫 系统产生大量抗体以排除抗原的过程。遗传算法种群中的大量个体就对应于生物免疫系 统中大量的抗体。生物免疫系统具有记忆特性可以对种群和个体进行识别。基于疫苗接 种的免疫遗传算法是模拟和反映生物机体免疫系统的上述特点，并结合工程优化应用而 提出的一种优化算法。它将已有的遗传算法看成是一个生物体，将算法中不可避免地出 现的退化现象就可以看成是外来的抗原。算法利用待求问题的特征信息，通过注射“疫 苗”来抑制上述退化现象的操作，从而在进化算法中起到“优胜劣汰”的作用，保持了 算法的每一步都沿着优化线路执行，从而达到免疫的目的。 与s g a 相比免疫遗传算法的特点是： 1 、具有抗体的多样性保持功能：可提高全局搜索能力，避免未成熟收敛； 2 、具有自我调节功能：可提高局部搜索能力； 3 、具有免疫记忆功能：可加快搜索速度，提高全局搜索能力，确保快速收敛于全局 最优解。 9 第三章改进的基于疫苗接种的免疫遗传算法设计 第三章改进的基于疫苗接种的免疫遗传算法设计 3 1 引言 遗传算法是一种具有“生成+ 检测 迭代过程的搜索算法。群体搜索和群体中个体 之间信息相互交换是通过交叉和变异算子来实现的，从而为每个个体提供优化的机会， 使整个群体在“优胜劣汰的选择机制下保证进化的方向。但是算法在迭代搜索的过程 中，交叉算子和变异算子都是在一定概率的条件下，随机地实现的。因此，交叉算子和 变异算子在为群体中的个体提供进化机会的同时，也无可避免地产生了退化的可能。同 时，每一个待求的实际问题都会有自身的一些知识或特征信息。但是在问题求解的过程 中，遗传算法的交叉算子和变异算子却相对固定。也就是忽视了问题的特征信息在问题 求解时的辅助作用，特别是在求解一些复杂问题时，这种“忽视”所带来的损失往往是 很明显的。 免疫是生物体维持自身生理活动稳定平衡、自主抵御外界病毒与细菌侵入的生命现 象。免疫系统对侵入机体的非己成分( 如细胞、病毒和各种病原体) 以及发生了突变的 自身细胞具有精确地识别、适度地应答和有效地排除的能力【4 2 1 。免疫系统有先天性免疫 系统和适应性免疫系统。先天性免疫系统是生物在种系发育和进化中逐渐建立起来的一 系列天然防御功能，其特点是与生俱有，能传给下一代，无特异性，对各种病原体都有 一定的防御功能，适应性免疫系统则是在个体生命过程中慢慢建立起来的，当免疫系统 与某种病原体产生“免疫初次响应”后，能记住该病原体，当再次遇到它时，会产生“免 疫再次响应 ，迅速而有效地消除该病原体。从生物处理信息的角度看，免疫系统具有 多样性，免疫自我调节，免疫记忆，分布式系统，动态适应，多时间尺度进化系统等特 性【4 3 。免疫行为可以很好的保持多样性，因而能够很好地防止算法陷入局部最优，有效 地提高寻优速度，改善寻优质量。因此，研究免疫优化理论以及模拟生物免疫行为而设 计新的有效算法具有重要的理论和实践意义。 3 2 基本的基于疫苗接种的免疫遗传算法 免疫系统作为一个动态进化系统与遗传算法所模仿的自然界生物种群进化的过程 有一定的相似之处，但也有自己特殊的演化规律，免疫系统的动态变化包括从亚分子事 件到细胞群体变化，以及需要无数代才能完成的免疫基因库的改变。在遗传算法的进化 框架上结合免疫系统的特殊处理机制发展起来了多种免疫遗传算法，主要有四种：1 ) 基于免疫自我调节机制的免疫遗传算法；2 ) 基于免疫响应的免疫遗传算法【4 4 ，4 5 。4 6 】； l o 西北大学硕士学位论文 3 ) 基于免疫抗体记忆的免疫遗传算法；4 ) 基于疫苗接种的免疫遗传算法。本文所探讨 的是基于疫苗接种的免疫遗传算法，首先介绍一下基本的基于疫苗接种的免疫遗传算 法。 疫苗接种是免疫记忆临床应用的一个重要方面，疫苗的预防免疫是在对流行病病 毒的充分了解的基础上，研制出疫苗来有针对性地防治流行病。将这一免疫概念用于遗 传算法，有效地利用求解问题的一些基本的、显而易见的特征信息或知识提取疫苗，使 问题求解更具有针对性。王磊，潘进和焦李成最早提出了基于疫苗接种的免疫遗传算法， 即在标准的遗传算法中，在保留原算法的优良特性的前提下，引入了一个新的算子一免 疫算子，有选择、有目的地利用待求问题中的一些特征信息或知识，提取“疫苗”来抑 制其优化过程中出现的退化现象，在进化选择过程中，通过“接种疫苗 和“免疫选择 来指导搜索过程，获得更好的优化性能【4 7 1 。这一算法的流程如图2 所示： 图2 基本的基于疫苗接种的遗传算法流程 第三章改进的基于疫苗接种的免疫遗传算法设计 3 3 改进的基于疫苗接种的免疫遗传算法设计 3 3 1 新算法设计的基本思想 本算法将生物免疫行为可以保持种群多样性这一特性应用到标准遗传算法中，通过 免疫接种，有选择，有目的地利用待求问题中一些特征或知识来抑制其优化过程中出现 的退化现象，保持种群的多样性，防止算法陷入局部最优，提高遗传算法整体的优化性 能。新算法的核心是合理提取疫苗，并适时地接种疫苗。与一般的免疫遗传算法【3 2 , 3 3 , 4 7 】 不同： 首先，在遗传操作中加入了免疫疫苗，即在个体经过交叉后将其中的适应度值最好 的个体的全部基因位作为疫苗提取，然后让这些个体独立地进行一定概率的变异。 其次，给出了算法可能陷入局部最优的条件。当判断出算法可能陷入局部最优时进 行疫苗接种，即每次先计算每个个体的适应度值f ( x ，) 和当前种群的平均适应度值 f ( x ) ，计算x ，和的均值偏差度i f ( x ，) 一，( x ) i ，当当前种群中四分之三的个体满足 i f ( x ，) 一，( ) j ( s 为一个正数) 时，即可认为算法可能陷入局部最优，此时才对当 前种群中一定数量的个体进行疫苗接种。 再次，采用动态疫苗接种。疫苗接种时并不是将待接种个体的全部基因用疫苗的全 部与之相对应的基因覆盖，而是采用动态疫苗接种方法，将疫苗接种和免疫选择结合在 一起进行：即一位一位的用疫苗相对应的基因对其进行强制改变，然后计算改变后的个 体适应度值，通过与其接种前的适应度值比较，将对其适应度值改变最大而且适应度值 有所提高的那一位基因用疫苗相对应的基因将其覆盖，其他的基因位保持不变。 动态疫苗接种伴随了免疫选择的过程，所以不仅可以提高个体的适应度值，提高种 群的多样性，而且可以防止陷入局部最优，加快算法整体的收敛速度。新算法为了保证 全局收敛，算法在选择前采用了杰出者保留策略，让全局最优个体不参加交叉，变异， 以保证最优个体的全部基因信息毫无破坏地被保留到下一代。 本章对于新算法提出了一种判断是否是最优解的终止准则，即自定义一个数m 和 最大迭代次数，如果算法连续m 次如上进行动态疫苗接种后，这m 次的种群平均适应度 值分别为互， ，如果互，e ，l 的偏差小于某个预先给定的正数卢，则可能已是 全局最优了，此时停止进化，终止计算，输出最优解，否则继续迭代直到达到最大迭代 数。其中加和p 可以根据用户对计算结果精度的不同要求而自行设定。修正的终止准则 可以避免计算过程中已获得最优解但没有达到最大迭代次数而还需要不断计算的问题。 1 2 西北大学硕士学位论文 3 3 2 新算法的免疫算子分析 人们受生物自然科学的启发而提出了免疫算子的概念。在实际问题中，问题的求解 总是和问题本身的特点及其条件联系在一起的。免疫遗传算法解决问题遵循这样的思 路。实际操作过程中，通过具体分析提取特征信息，对此特征信息进行处理，将其转化 为一种求解问题的方案，再将此方案以适当的形式转化成免疫算子。改进的免疫遗传算 法的核心是合理提取疫苗，在此基础上通过动态接种疫苗和免疫选择两个操作步骤来完 成的。疫苗提取是为了有效地保持疫苗提取最优，以便遗传算子在接种疫苗时能够充分 地发挥作用；动态接种疫苗是为了提高适应度，免疫选择则为了防止群体的退化。具体 描述如下： 1 ) 疫苗的提取 疫苗是指根据先验知识从待求问题中提取的一种基本的特征信息。免疫疫苗的提取 通常有两种，一种是在群体进化过程中从每代最佳的基因中提取有效信息，从而制作疫 苗；一种是视具体分析待求问题，搜索特征信息进而制作免疫疫苗。以下两个原因使第 二种方法受到限制，_ 是对待求问题大都难以形成较为成熟的先验知识，无法从分析问 题中提取出合适的特征信息，因此得不到有效地免疫疫苗。二是提取疫苗的代价太大， 超出了其在寻找全局最优解过程的比例。所以在改进的免疫遗传算法中采用第一种方 法，即将交叉后种群中的最优个体的全部基因位的有效信息作为疫苗v 。由于免疫系统 产生的抗体具有很强的针对性，所以适应度较高的抗体含有解决问题的特征信息。而改 进的算法每次迭代都保留了最佳个体，所以在提取最优个体基因疫苗时采用疫苗更新， 因为疫苗的优劣，生成抗体的好坏严重影响到免疫算子中动态接种疫苗作用的发挥，但 与算法的收敛性无关。 2 ) 动态接种疫苗 设个体为y ，接种疫苗是指对个体y 按照先前提取出来的先验知识来修改个体y 的 某些基因位上的基因或者它的分量，以提高其适应度。此操作必须满足以下两点：第一， 如果最佳个体的每一基因位上的信息都与个体z 不同，则对任一个体y ，一位一位的用疫 苗v 相对应的基因对其进行强制改变，然后计算改变后的个体适应度值，通过与其接种 前的适应度值比较，将对其适应度值改变最大而且适应度值有所提高的那一位基因用疫 苗相对应的基因将其覆盖，其他的基因位保持不变；第二，如果个体y 的每个基因位上 的信息都与最佳个体相同，即y 已经是最佳个体，则y 以概率l 转移为j ，。设第k 代的 第三章改进的基于疫苗接种的免疫遗传算法设计 群体为d = ( 盔。，d 2 ，d n k ) ，贝, u x v j d 。接种疫苗是指在d 。中按比例口( o 口1 ) 随机 抽取虬= a n 个个体而进行的操作。 3 ) 免疫选择 即对接种了疫苗的个体进行检测，这个过程是伴随着动态疫苗接种进行的。如果 接种了疫苗的个体适应度仍不如父代，则该个体将被父代中所对应的个体所取代；如果 其适应度优于父代，则它的子代将代替父代进入下一代种群。 3 3 3 新算法设计的具体执行步骤 s t e p l ：( 初始化种群和有关参数) p = 0 7 ：交叉概率 巴= 0 1 ： 变异概率 ： 种群规模 l： 二进制编码长度 t： 最大进化代数 r：迭代次数 d： 解空间的维数 m： 遗传操作中间个体数 m：连续迭代数 p ：检验是否全局最优的阀值 s：检验迭代是否陷入局部最优的阀值 随机生成个个体形成初始种群x ( o ) ；置，# 0 。 s t e p 2 ：( 个体评价) ( 保优) 计算x ( t ) 中各个个体的适应度值，找出最优个体在种群中 的位置，对其采用杰出者保留策略。 s t e p 3 采用轮盘赌选择策略从