（信号与信息处理专业论文）改进免疫遗传算法在函数优化中的应用研究.pdf

父c ：乱 苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文口 论文作者签名：塾：堇兰塑 日 导师签名： 期：少j 口，f g 日期：7 1 0 1 0 f i 矿 7 摘要 研究 的一个实现，模 问题的分解、处 域得到了成功的 挖掘、故障诊断 等。但i a 存在收敛速度较慢的缺点。 遗传算法是一种借鉴生物界自然选择和遗传机制的高度并行、随机、自适应的 全局优化概率搜索算法。但遗传算法的理论和方法尚未成熟，算法自身的一些不足 也有待于进一步地改进和完善。 鉴于两种算法都有其不完善处，而函数优化是对算法进行性能评价的常用方 法。本课题将两种算法相结合并进行改进，给出改进的免疫遗传算法，来求解函数 优化问题。改进方法如下：期望繁殖率评价、矢量矩浓度计算、免疫记忆算子、逼 近方法定位的交叉操作以及动态变异概率的变异算子，分析三种算法的运行机制， 对亲合力、浓度、免疫记忆、交叉和变异操作进行深入细致的研究，并在m a t l a b 环境中使用改进算法来求解函数优化问题。选择一些典型的低维和高维复杂函数进 行仿真测试，通过与基本遗传算法和一般免疫算法的比较，仿真实验结果表明本文 的改进免疫遗传算法不仅能有效地避免“早熟 现象，提高算法的收敛速度，而且 所求得的解都可以达到或逼近最优解。 最后，通过对研究工作的总结，指出本文改进算法的优点与不足，为算法的进 一步研究提供一定的参考。 关键词：免疫遗传算法；函数优化；免疫记忆；矢量矩 作者：孙梦娴 指导教师：陈小平 t h er e s e a r c ho f i m p r o v e di m m u n e g e n e t i c a l g o r i t h mf o rf u n c t i o no p t i m i z a t i o n a b s t r a c t i m m u n ea l g o r i t h m ( i a ) i sar e a l i z a t i o no fn a t u r a li m m u n es y s t e mi ne v o l u t i o n a r y c o m p u t a t i o n , s i m u l a t i n gt h ek n o w l e d g ep r o c e s s i n gs y s t e mo fi m m u n es y s t e ma b o u t l e a r n i n g ，m e m o r ya n df o r g e t t i n g ，s ot h a tt h e r ei sah i g h e ri n t e l l i g e n c ea n dr o b u s t n e s si n d e c o m p o s i n g ，h a n d l i n ga n ds o l v i n gd i s t r i b u t e dc o m p l e xp r o b l e m s i m m u n ea l g o r i t h mh a s b e e ns u c c e s s f u li nm a n yf i e l d s ，s u c h 勰v i r u sr e m o v a la n di n v a s i v em o n i t o r i n g f u n c t i o n o p t i m i z a t i o n ，t s pp r o b l e m ，d a t aa n a l y s i sa n dm i n i n g ，f a u l td i a g n o s i s h o w e v e r ，i ah a st h e d i s a d v a n t a g eo fs l o wc o n v e r g e n c e g e n e t i ca l g o r i t h m ( g a ) i sah i g h l y p a r a l l e l ，r a n d o ma n da d a p t i v es e a r c h i n g p r o b a b i l i s t i cm e t h o db a s e do nb i o s p h e r en a t u r a ls e l e c t i o na n dg e n e t i cm e c h a n i s m b u tt h e t h e o r ya n dm e t h o do fg e n e t i ca l g o r i t h mi sn o tm a t u r e s o m ei n s u f f i c i e n c i e so fa l g o r i t h m a l s or e m a i n st ob ef u r t h e ri m p r o v e da n dp e r f e c t e d i nv i e wo ft h ea b o v e - m e n t i o n e df a c t sa n df u n c t i o no p t i m i z a t i o na sa c o m m o nm e t h o d f o re v a l u a t i o no fa l g o f i t h mp e r f o r m a n c e ，i m m u n eg e n e t i ca l g o r i t h m ( i g a ) i sp r e s e n t e da n d i m p r o v e dt os o l v ef 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 p r o p o s ean e wa p p r o a c h ：a s s e s s m e n to f e x p e c t e dr e p r o d u c t i o nr a t e ，c a l c u l a t ec o n c e n t r a t i o no ft h ev e c t o rd i s t a n c e ，i m m u n em e m o r y ， a p p r o x i m a t i o nm e t h o do ft h ec r o s s o v e ra n dm u t a t i v ep r o b a b i l i t yo fm u t a t i o no p e r a t o r ， a n a l y z et h r e ea l g o r i t h m s o p e r a t i o n a lm e c h a n i s m ，r e s e a r c ht h ea f f i n i t y ，c o n c e n t r a t i o n , i m m u n em e m o r y ，c r o s s o v e ra n dm u t a t i o nt o ，a n du s i n gi m p r o v e da l g o r i t h mt os o l v et h 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 mi n m a t l a b c o m p a r e dw i t hg e n e t i ca l g o r i t h ma n d i m m u n ea l g o r i t h m ，s i m u l a t i o nt e s t ss e l e c ts o m et y p i c a ll o wa n dh i g hd i m e n s i o n a lc o m p l e x f u n c t i o n st oi n d i c a t et h a tt h ei m p r o v e di m m u n ea l g o r i t h mc a ne f f e c t i v e l ya v o i dt h e ”p r e m a t u r e ”p r o b l e m ，i m p r o v et h ec o n v e r g e n c es p e e da n do b t a i nt h eo p t i m a ls o l u t i o n f i n a l l y ，t h r o u g hc o n c l u d i n gt h er e s e a r c hw o r k ，t h ea d v a n t a g e sa n dt h ew e a k n e s s e sh a v e b e e nc l e a r ，w h i c hp r o v i d ec e r t a i nr e f e r e n c ef o rf u r t h e rr e s e a r c ho fl g a k e y w o r d s ：i m m u n eg e n e t i ca l g o r i t h m ；f u n c t i o no p t i m i z a t i o n ；i m m u n em e m o r ys t r a t e g y ； v e c t o rd i s t a n c e ； i i w r i t t e nb y ： s u p e r v i s e db y ： s u nm e n g x i a n c h e nx i a o p i n g 1 3 1 免疫算法的基本类型3 1 3 2 免疫算法设计4 1 4 课题的提出及研究的意义4 1 5 本文的主要工作及内容安排4 第二章遗传算法和兔疫算法的基本理论7 2 1 基本遗传算法7 2 1 1 基本遗传算法描述7 2 1 2 基本遗传算法的运算流程8 2 2 一般免疫算法1 0 2 2 1 一般免疫算法描述1 0 2 2 2 一般免疫算法的运算流程1 l 2 3 3 收敛性分析1 3 2 3 免疫遗传算法1 4 2 3 1 免疫与遗传算法的不同特点1 6 2 3 2 算法实现1 7 第三章免疫遗传算法操作算子的分析及改进1 9 3 1 编码方式1 9 3 1 1 二进制编码1 9 3 1 2 实数编码2 0 3 2 亲合力计算2 1 3 2 1 抗体浓度2 1 3 2 2 适应度函数2 5 3 3 免疫记忆3 0 3 4 选择算子，j 3 1 3 5 交叉算子3 2 j j ，2 3 3 6 变异算子3 4 3 7 控制参数3 5 第四章改进免疫遗传算法在函数优化中的应用3 6 4 1 函数优化问题的描述3 6 4 2m a t l a b 遗传工具箱3 7 4 3 测试函数3 9 4 4 矢量矩免疫遗传算法的描述与参数设置4 2 4 4 1 矢量矩免疫遗传算法的描述4 2 4 4 2 矢量矩免疫遗传算法的操作流程4 3 4 4 3 矢量矩免疫遗传算法的参数设置4 4 4 4 4 对比算法的描述与参数设置4 6 4 5 实验数据及分析4 6 4 5 1 低维函数的实验结果与分析4 7 4 5 2 高维函数的实验结果与分析5 0 4 5 3 记忆子群规模研究5 3 第五章总结。5 5 参考文献5 7 攻读学位期间公开发表的论文6 1 附录v d i a 源程序。6 2 j 琴【谢6 5 改进免疫遗传算法在函数优化中的应用研究引言 第一章引言 1 1 概述 免疫系统是高等脊椎动物体内抵御病原体如细菌、病毒等入侵，保护机体免受 损害的极为复杂的生物学系统。在自然免疫系统中，存在着大量的淋巴细胞克隆( 抗 体) ，以致于几乎每种病原体( 抗原) 入侵生物机体时，免疫系统一般都能选择出_ 种 或数种能识别该种抗原的抗体使之活化、增殖，去抵御入侵的病原体。当病原体被 清除后，这种能与病原体匹配的抗体在免疫系统中大量存在，浓度增大，自然免疫 系统通过抑制细胞对这种高浓度的抗体进行抑制，降低该种抗体的浓度，使免疫系 统回复到一个新的平衡状态，以免生物机体产生自身免疫疾病。 免疫算法( i m m u n ea l g o r i t h m ) 是自然免疫系统在进化计算中的一个实现，模 拟了免疫系统学习、记忆、遗忘的知识处理机制，使其对分布式复杂问题的分解、 处理和求解表现出较高的智能性和鲁棒性。免疫算法己在很多领域得到了成功的应 用，特别是在计算机科学领域，如计算机安全【1 1 、函数优化、智能控制2 1 、数据分 析和数据挖掘【3 1 、故障诊断f 4 1 等。但从存在收敛速度较慢的缺点。 在遗传及免疫算法的诸多应用中，函数优化是最显而易见的应用，也是经典的 应用【5 】。函数优化问题是许多领域中普遍存在的问题，也一直是人们探索的若干重 要问题之一。很多复杂的问题，如神经网络的训练、系统模型参数的辨识等，可以 转化为函数优化问题来求解。函数优化的本质就是从所有可能的方案中选择出最合 理，能达到最优目标的方案。它通常可归结为求最小值问题，对于最大值问题可以 通过对函数取反，将其转化为最小值问题。对于函数优化问题，传统的求解方法有 最速下降法、牛顿法、拉格朗日乘数法、罚函数法等等。对于这些确定的搜索优化 方法来说，函数可微通常是求解问题的前提，而且随着函数维数的增长，求解的难 度大幅度增长。因此传统的优化方法并不适合于求解不可微函数以及高维函数的优 化问题。一种模仿生物自然进化过程的、被称作为演化算法的随机优化技术在解这 类优化难题中显示出了优于传统优化算法的性能。 自从美国密歇根大学j o h nh h o l l a n d 教授予1 9 7 5 年提出遗传算法( g e n e t i c a l g o r i t h m ，g a ) 6 j p g 来，遗传算法一直是人工智能的一个研究热点，取得了很多研究 成果，人们利用g a 解决了很多复杂的问题。但g a 的一个显著的缺点是其保持解群 1 引言 改进免瘦遗传算法在函数优化中的厘用研究 _ 一- _ - _ 。_ - _ _ _ - - _ _ _ _ - _ _ _ _ _ _ - _ _ _ _ _ - - _ - _ _ - _ _ - _ _ _ _ - i - _ - _ _ _ _ _ _ i _ - _ - _ _ - - _ _ _ _ _ _ _ _ _ 。_ _ _ _ _ _ _ - 。- _ 。_ 。i 。_ 。_ _ _ _ _ _ - _ _ - _ - - 一 多样性的能力不足，易于在成熟前陷入收效，从而易使算法收敛于局部最优。免疫 算法相较于遗传算法引入了抗体浓度( c o n - c e n t r a t i o no fa n t i b o d y ) 这一概念。g a 中个 体的选择概率由适应度决定，队中选择概率既与适应度有关也与浓度有关，有效地 增强了算法的多样性，较好地克服了遗传算法易陷入局部最优的缺点。 1 2 人工免疫系统的发展历史 1 9 7 4 年，诺贝尔奖获得者、免疫学家j e r n e 提出了免疫网络理论而引起关注。 1 9 8 6 年，f a r m e r 发表了一篇题为免疫系统、适应与机器学习的论文，拉开了人 工免疫系统的研究序幕。这篇文章提出了一个基于j e m e 的网络假说的动态免疫系统 模型。该文关于免疫系统与机器学习的研究工作是具有创造性和开拓性的。 2 0 世纪9 0 年代初，b e r s i n i 利用免疫系统思想解决控制问题【7 8 】。i s h i d a 于1 9 9 0 年 利用免疫系统解决故障诊断问题【9 】，将几个简单的免疫机制应于传感器网络故障诊 断领域。f o r r e s t 在1 9 9 4 年将免疫系统机制用于计算机安全和病毒检测【1 0 1 。在f o r r e s t 开展其研究工作同时，英国学者h u n t 等研究人员也在研究免疫系统学习的本质以及 免疫网络思想如何用于建立机器学习算法，并成功应用免疫思想分类d n a 序列【1 1 1 以及 抵押欺诈检测【1 2 q 3 1 。此后，越来越多的人尝试开发基于免疫系统机制的智能计算方 法。 1 9 9 6 年1 2 月，在日本举行了基于免疫系统的国际专题讨论会，首次提出了计算 机科学领域的人工免疫系统的概念。1 9 9 7 年和1 9 9 8 年i e e es y s t e m ，m a na n d c y b e m e t i c s 际会议组织了相关专题讨论，并成立了人工免疫系统及应用分会。目 前，世界著名的进化计算以及计算智能会议如c e c 、g e c c o 、w c c i 等近些年也都 开设了人工免疫系统专题。越来越多的国际、国内会议开始覆盖这一主题。 2 0 世纪9 0 年代初，国内焦李成、曹先彬、王煦法等一批学者提出了多种形式的 免疫算法 1 扣1 5 】。 早期的人工免疫系统都是采用多学科合作的方法开发的，关注所抽取启发的免 疫学理论。近些年，人工免疫系统在形式上越来越多样，在方法上越来越新颖，在 应用范围上越来越广泛，它们的设计方法已经与早期研究有很大差别。但是在理论 上没有突破，与生物学即免疫系统机制和免疫学理论渐行渐远，设计都是面向工 程，而较少在深入理解关键的免疫系统生物学上进行开发设计。 2 改进免疫遗传算法在函数优化中的应用研究 引言 人工免疫系统内容是多样化的，以至于目前人们还无法统一描述人工免疫系统 以及建立相应的理论模型。所以目前人工免疫系统处于面向问题的研究阶段。人工 免疫系统近些年之所以能够迅速发展，除了免疫系统启发因素外，计算机和电子技 术的发展也使人们能够在技术层面更容易实现和验证包括算法在内的各种方法，为 解决日趋复杂多样的工程问题提供新的思路和方法。 1 3 免疫算法 1 3 1 免疫算法的基本类型 免疫算法没有统一的模式，即使在生物学基础上也不是统一的。它与遗传算法 等传统自然计算或计算智能方法的差别在于，遗传算法、人工神经网络等方法是基 于单一的生物学理论而发展的，比如进化论、人脑的神经网络结构。而免疫算法的 生物学基础是多样的，比如免疫网络、克隆选择理论、阴性选择等，基于这些免疫 学理论或机制已经开发出多种形式的算法模型。它是人工免疫系统的主要研究内 容，也是免疫计算的主要形式。 免疫算法是面向问题的方法，因此从人工免疫系统发展以来，已经有许多用于 不同领域的算法开发出来【1 0 1 ，许多学者利用免疫系统的某一方面机制或原理设计 新算法，或者改进现有技术。所依据的原理基本是传统的免疫学理论，因此免疫算 法从启发源角度可以大致可以分成三类：免疫网络模型( 分为连续和离散两种形 式) 、克隆选择、阴性选择。代表性的有一般免疫算法【2 1 1 、早期的骨髓模型【2 2 1 、d e c a s t r o 提出的克隆选择算法【2 3 1 、f o r r e s t 提出的阴性选择算法 2 4 1 、d ec a s t r o 提出的人工 免疫网络算法( a i n e t ) 等【2 5 1 。此外，文献【2 6 】中提出了b 细胞算法，文献 1 4 最早提 出了基于疫苗概念的免疫算法。文献 2 7 2 8 】分别对免疫算法进行了深入的研究。 上述免疫算法可进一步分为两类：基于群体的模型和基于网络的模型。 基于群体的模型是是受到免疫细胞在释放进入淋巴系统之前早期变化的过程启 发的。采用特殊的算法( 阴性、阳性、克隆) 去选择一组自己或者非自己的识别器 或分类器。如克隆选择算法、阴性选择算法等。 基于网络的免疫计算模型是受到免疫网络理论启发的计算方法。免疫网络是生 物和社会系统中的许多动力学网络模型之一，从卡夫曼自催化网络、遗传控制网络 到神经网络的动力学模型，再到生态食物网、社会和技术网络。多数现有数学网络 3 引言改进免疫遗传算法在函数优化中的应用研究 理论局限于静态的、同质的、结构的、封闭的网络，简单且易处理。但这些并不是 实际的生物网络模型特征。因此免疫网络计算模型面临的挑战在于开发动态的、异 质的、无结构的、开放网络模型。一般免疫算法本质上是基于网络的算法。 1 3 2 免疫算法设计 免疫算法的设计和应用有一般规律，免疫算法解决问题的过程如下： 1 确定应用领域 2 确定免疫实体 包括四个部分：表示法、亲合力度量、免疫机制应用、算法循环。 3 获得问题解 表1 1 给出最基本的免疫学概念与一般免疫算法的对应隐喻关系【2 9 1 。 表1 1 免疫学与免疫算法的对应关系 免疫系统一般免疫算法 抗原优化问题或进化群体中最优解 抗体优化问题的可行解 记忆细胞进化群体中较好的解 自己抗体优化问题的可行解 1 4 课题的提出及研究的意义 从上面的介绍可以看出，免疫算法已经成为一个研究的热点课题，国内外都非 常重视免疫算法理论和应用的研究，并取得了令人瞩目的进展，提出了多种形式的 免疫算法。但免疫算法没有统一的模式，即使在生物学基础上也不是统一的，其理 论和方法都尚未成熟，所以目前免疫算法处于面向问题的研究阶段。将免疫算法与 其他优化算法相结合得到免疫混合算法，可以改进单一算法自身的一些不足。本文 源于此目的，结合进化算法的经典应用领域函数优化，审视各种改进方法，研 究它们的优点与不足之处，进而对单一免疫算法作出较为合理的改进。 本课题的主要任务是通过对各种免疫混合算法的深入分析，结合典型的多维或 高维复杂函数，重点研究混合算法对免疫算法性能的影响，给出改进方法。本课题 对免疫算法的进一步改进研究有一定的参考意义。 1 5 本文的主要工作及内容安排 本课题以免疫遗传算法的改进方法为主要研究内容，针对亲合力、浓度、免疫 4 改进免疫遗传算法在函数优化中的应用研究引言 记忆、交叉和变异操作进行深入细致的研究，给出改进方法：期望繁殖率评价、矢 量矩浓度计算、免疫记忆算子、逼近方法定位的交叉操作以及动态变异概率的变异 算子。主要完成了以下几个方面的工作： 1 引入期望繁殖率的概念，分析浓度计算及适应度函数对算法的影响，采用计 算简单的矢量矩方法，并通过仿真测试验证； 2 分析记忆算子对算法的影响，给出本文的免疫记忆策略，验证参数选择对算 法的影响； 3 分析各控制参数对算法的影响，确定本文采用的各种算法的控制参数； 4 综合各算子的特点对免疫遗传算法进行改进，即期望繁殖率评价、矢量矩浓 度计算、免疫记忆算子和逼近方法定位的交叉操作的免疫遗传算法，并选择5 个典型 的复杂多维多峰函数和4 个高维函数( 分别取3 0 维、1 0 0 维和1 0 0 0 维) 进行仿真测 试，通过与基本遗传算法、一般免疫算法比较，实验结果表明本文的改进算法能有 效地避免“早熟 现象，提高了收敛速度、收敛概率，而且所求得的解都可以达到 或逼近最优解，提高了单一免疫和遗传算法的性能。 论文章节安排如下： 第一章引言 简要介绍免疫和遗传算法的概念特点、发展历史和研究进展；提出本文的研究 动机和主要工作。 第二章遗传算法和免疫算法的基本原理 介绍了遗传算法和免疫算法的基本原理，阐述了基本遗传算法、一般免疫算法 的实现方法。对比两种方法的不同之处，分析免疫遗传算法的实现方法。 第三章免疫遗传算法操作算子的分析及改进 分析算法各操作算子，编码方法、亲合力计算( 包括抗体浓度和适应度) 、免疫 记忆、选择操作、交叉操作、变异操作、参数选取等方面对算法性能的影响，给出 了本文的改进方法：期望繁殖率评价、矢量矩计算浓度、免疫记忆算子、逼近方法 定位的交叉操作以及动态变异概率的变异算子。 第四章改进免疫遗传算法在函数优化中的应用 介绍了函数优化问题、r a t l a b 遗传算法工具箱的结构和功能，选择了9 个典型 的具有相当复杂度的多维或高维函数，利用m a t l a b 遗传算法工具箱的对具体的测试 引言改进免疫遗传算法在函数优化中的应用研究 函数分别采用不同的方法进行优化，给出具体的实验结果并对比分析。 第五章总结与展望 总结本文的研究工作，指出改进算法的优点与不足，为算法的进一步研究提供 有益的建议。 6 第二章 收敛性， 并分析了这两种算法的优缺点，从而引出了综合两种算法优点的改进算法免疫 遗传算法，并介绍免疫遗传算法的实现流程。 2 1 基本遗传算法 2 1 1 基本遗传算法描述 基本遗传算法以群体中的所有个体为对象，只使用选择、交叉和变异三种基本 遗传算子，其遗传进化操作过程简单，它是其他一些遗传算法的基础，为各种遗传 算法提供了一个基本框架。模式定理和积木块假设是解释遗传算法有效性的理论依 据，理论分析与实际应用都表明基本的遗传算法不能处处收敛于全局最优解，因此 基本遗传算法有待进一步改进。 遗传算法提供了一个求解复杂系统优化问题的通用框架，不依赖问题的领域和 种类。遗传算法以适应度函数为依据，通过对群体中的个体施加遗传操作，实现群 体内个体结构重组的迭代处理过程。g o l d b e r g 总结的简单遗传算法( s i m p l eg e n e t i c a l g o r i t h m s ，s g a ) 是一种最基本的遗传算法。只包括选择、交叉和变异三种基本遗 传算子。其数学模型可表示为： s g a = ( c ，e ，p o ，n ，f ，甲，丁) 式中：c 个体的编码方法； e 个体适应度评价函数； r 初始种群； 种群大小； 选择算子； r 交叉算子； y 变异算子； 丁遗传运算终止条件。 对一个需要进行优化计算的实际应用问题，通常按下述步骤来构造求最优解的 遗传算法： 7 第二章 改进免疫遗传算法在函数优化中的应用研冗 1 确定决策变量及其各种约束条件，即确定个体的表现型和问题的解空间； 2 建立优化模型，即确定目标函数的类型( 求最大值还是最小值? ) 及其数学描 述形式或量化方法； 3 确定表示可行解的染色体编码方法，即确定个体的基因型和遗传算法的搜索 空间； 4 确定解码方法，即确定由个体基因型到个体表现型的转换对应关系； 5 确定个体适应度的量化评价方法，即确定由目标函数到个体适应度的转换规 则； 6 设计遗传算子，即确定出选择、交叉、变异等算子的具体操作方法； 7 确定遗传算法的运行参数，即确定遗传算法r ，已，r 等参数。 其中可行解的编码方法、适应度函数和遗传算子的设计是构造遗传算法时需要 考虑的主要问题。对不同的优化问题需要使用不同的编码方法和不同的遗传操作算 子，这与所求解的具体问题密切相关。 2 1 2 基本遗传算法的运算流程 遗传进化操作简单、易懂，是其它一些遗传算法的雏形和基础，它不仅给各种 遗传算法提供了一个基本框架，同时也具有一定的应用价值。g a 的流程图如图2 1 所示。 1 编码和产生初始群体 根据问题选择相应的编码方法，并随机产生一个确定长度的爪染色体组成的 初始群体： p o p ，( r ) ，t = 1 ，f = 1 , 2 ，3 ，n ( 2 1 ) 2 计算适应度值 对群体p o p ( t ) 中的每一个染色体p o p i ( t ) 计算它的适应度： ，= f i t n e s s ( p o p ，( ，) ) ( 2 2 ) 3 判断算法收敛准则是否满足。若满足，输出搜索结果；否则，继续执行以下 步骤； 4 选择操作 根据各个个体的适应度值计算选择概率： 8 第二章 ( 2 3 ) 遗传到下一 ( 2 4 ) 用某一较小的概率使染色体的基因发生变异，形成新的群体m u t p o p ( t + 1 ) ；该 新的群体即为完成一次遗传操作后的子代记为p o p ( t ) = m u t p o p ( t + 1 ) ，同时它又作 为下一次遗传操作的父代，返回2 。 图2 1 标准遗传算法流程图 算法终止条件中，最简单的终止条件是规定最大遗传( 迭代) 代数，当其运行 到最大的进化代数后就停止运行，并将当前群体中的最佳个体作为所求问题的最优 解输出；另一种判断的方法，利用某种判定准则判定出群体已经进化成熟，且不再 9 第二章 改进免疫遗传算法在函数优化中的应用研究 有进化趋势时终止算法运行，如群体中所有个体适应度的方差或连续几代个体平均 适应度的差异小于某一极小的阈值或最优值满足所需的精度等来终止算法运行。 基本遗传算法存在一些问题，如过早收敛、局部搜索能力较弱从而导致求解效 率低，求解精度不高等。r u d o l p h t 3 0 1 用齐次马尔可夫链证明了带选择、交叉、变异的 标准遗传算法并不收敛于全局最优解。在实际的应用过程中，必须对g a 进行适当的 改进，才能使遗传算法具有良好的收敛性能。 2 2 一般免疫算法 一般免疫算法模仿了免疫系统中抗体和抗原识别、结合及抗体产生的过程，并 利用免疫系统的多样性和记忆机理抽象得到【3 1 3 3 1 。目前，一般免疫算法大多采用类 似于遗传算法的搜索策略，借用了遗传算法的选择、交叉和变异算子( 有的只用变 异算子) ，但在群体搜索策略和记忆单元设置等方面又与遗传算法有所不刚划。从搜 索策略上来讲，遗传算法采用适应度函数来指导搜索过程，一般免疫算法则采用亲 合度和浓度进行度量；同时，一般免疫算法与遗传算法的群体控制策略也有所不 同：遗传算法没有记忆单元，而一般免疫算法则利用记忆机制加强局部搜索或者抑 制早熟收敛，从而使算法快速收敛到全局最优解。 2 2 1 一般免疫算法描述 一般免疫算法是基于生物免疫系统的基本机制开发形成的免疫算法，其基本要 素和流程等可描述如下： 朋( ，g ，a ，b ，f ，s ，m ，q ，彳，f ) 式中：搜索空间( 形态空间) ( 抗体) ； g 表示空间( 抗体抗原表示方法) ； 彳抗体集合； 召抗原集合； 广亲合力函数； s 相似度函数； m 记忆机制； q 免疫算子( 变异，重组等) ； 1 0 改进免疫遗传算法在函数优 f 选择百 化中的应用研究 第二章 分比； f 终止条件。 在使用免疫算法解决问题时，般各个步骤有对应形式：抗原对应要解决问题 数据输入如目标、约束；抗体对应优化问题的最优解；亲合力对应解的评估、结合 强度的评估：记忆细胞分化对应保留优化解；抗体促进和抑制对应优化解促进，非 优化解的删除等；抗体产生对应优化解的出现等。对应内容因解决问题对象不同而 内容各异。 2 2 2 一般免疫算法的运算流程 为了叙述算法方便，定义b 为输入抗原；彳为包含有r 1 个抗体的集合；m e a 为 个记忆单元；彳，为抗原、抗体之间的亲合力向量函数；s 为抗体抗体之间的相似 度矩阵；f 为选择成熟分子的比率；仃凼为相对自然死亡或衰减的阈值。一般免疫算 法的流程图如图2 2 所示。 一般免疫算法通常可以分为以下6 个步骤【3 5 】： ( 1 ) 抗原识别： 输入待解问题抗原，一般将目标函数和各种约束作为算法的抗原8 ( 2 ) 产生初始抗体群体a ( ，) 在解空间中用随机的方法产生。对抗体编码，并且遵循完备性、健全性、和非 冗余性要求。 ( 3 ) 计算亲合力 群体未变，分别计算抗原和抗体之间的亲合力及抗体之间的相似度。抗体和抗 体相似度的度量一般采用解空间中的距离 s 驴= 1 1 口f 一口i i , i = 1 ，2 ，刀 ( 2 5 ) 彳，= l ia ，l ，彳，2 ，a l i ( 2 6 ) ( 4 ) 记忆细胞分化 更新记忆单元选择f 与抗原的亲合性高的抗体加入到记忆单元中。由于记忆单 元数目有限，清除那些与抗原亲合力低于盯出以及较大密度的记忆单元( 抗体的自然 死亡) 。 l l 第二章改进免疫遗传算法在函数优化中的应用研究 定义抗体记忆矩阵与抗原的平均亲合力为 打 a a f ( m ) = 彤 j 暑l 因此 ( 2 7 ) a a f ( m ( t + 1 ) ) a a f ( m ( t ) ) ( 2 8 ) 式( 2 8 ) 表示抗体平均亲合力大于等于上一代抗体平均亲合力。 抗原识别 产生初始抗体群 计算亲合力 记忆细胞分化 抗体促进和抑制 新抗体产生 ly !i!一 输出搜索结果 图2 2 一般免疫算法流程图 ( 5 ) 抗体促进和抑制 高亲合力抗体受到促进，高浓度抗体受到抑制。群体分化产生新抗体。一般来 讲，与抗原亲合力高的抗体和低密度的抗体生存几率较大，但是，为了有利于优化 过程的进行，某些与抗原有较高亲合力的抗体也必须受到抑制，从而体现了抗体克 隆控制机制的多样性。可以再随机产生新的抗体，也可以通过变异和交叉产生进入 下一代的抗体，并将m i 1 入新抗体群落，去除那些亲合力低的记忆单元 ( 6 ) 新抗体产生 1 2 改进免疫遗传算法在函数优化中的应用研究第二覃 利用遗传算法的选择、交叉及变异算子产生新的抗体 彳( ，) 一qja ( t + 1 ) 在以上步骤中，步骤( 3 ) 至步骤( 6 ) 需要迭代执行，直到满足终止条件为止。终 止条件一般设置为最大迭次数或求解精度或者二者的结合。 在应用中，根据具体问题，研究人员对上述免疫算法进行不同的改进或变化， 比如与遗传算法结合，利用遗传算子产生多样性抗体等，以符合解决具体问题需 要，从而发展出多种形式的免疫算法，但基本上都遵循这六个步骤。 注意免疫细胞识别抗原的不完全匹配性，即免疫细胞识别抗原的过程就是与抗 原匹配并结合的过程，这种匹配不要求二者的完全匹配，只要这种匹配所导致的亲 合力大于某一固定的阈值即可。基于不完全匹配性，一种免疫细胞可以识别多种不 同的抗原。形态空间理论可以对识别多样性作出合理解释。 一般免疫算法是在人工免疫系统发展早期阶段形成的一种免疫算法。由于仅仅 只是对免疫系统的一些基本机制做了比较简单的应用，一般免疫算法的实现较为容 易，这也使得该算法求解复杂问题的能力受到限制。 2 3 3 收敛性分析 定义2 1 设e 是时刻后时群体中的最优抗体，f 是待求问题的抗原，当且仅当 j i m 尸( 疋= f ) = 1 成立，称免疫算法是全局收敛【3 q 的。 定义2 2 a 是一个玎x ，z 的方阵。 ( i ) 若对所有的f ，口l ，0 ，记为a o ，称a 为非负的( n o n n e g a t i v e ) ； ( 2 ) 若a 是非负的，且对所有的f ，a q = 1 ，则a 是随机的( s t o c h a s t i c ) ； ( 3 ) 若a 是非负的，且对a 中的行和列经过置换能得到i 吴；i 形式( c ，丁是方阵) ， 则a 是可约的( r e d u c i b l e ) 。 定理2 1 设尸是一个可约随机矩阵，尸= l ；i ，其中c 是正的，z 阶随机矩阵， 第二章改进免瘦遗传算法在函数优化中的_ 匝用研冤 尺，丁。，则p 。= 。l i m 。p 。= ! 骢l 篓c 。一，t 曼i = ：3 尼殍o ，则，2 2 1 骢陧m c ti _ l 二。u j l j - oj 。 定理2 2 免疫算法是依概率l 收敛的。 证：算法中的交叉操作是以概率p ，对选择的一对b 细胞上的两个基因位进行交 叉。变异操作是对b 细胞的每个基因位以概率p 朋相互独立的进行变异。则算法步骤 ( 1 6 ) 的刀步状态转移可用状态转移阵尸= ( 既) 表示，且岛【o ，1 】，p f = l 。根据 定义( 2 1 ) 和( 2 2 ) ，状态转移阵p 是随机的。 通过置换将转移矩阵p 的各状态排列如下：第一个状态为全局最优解；第二个状 态为全局次优解，第n 状态为全局最差解。则算法步骤6 对b 细胞的更新操作可 视为：对任意状态f ，依p f + p 盯专p 。和p 。= 0 ，w f 对转移矩阵更新，生成新 j = i + l 的转移阵尸。 p ： 1o p 2 1p 2 2 见1 p 2 埘 o o p m p 2 2 丁：i l 以： = 医 i 三 ；r ，丁。；c - c ，是一阶正的随机矩阵， 根据定义2 2 ，状态转移阵尸是可约的。 根据定理2 ，尸“= ! 骢尸“= 曼二羽= 二三 。尸的第一状态的极限概率为 1 ，即p t = 女l i m 。p ( e = f ) = 1 ，可知免疫算法是全局收敛的。 这里需要说明的是，如果把免疫算子从免疫算法中略去，可以证明该算法不再 保证收敛到全局最优解。 2 3 免疫遗传算法 遗传算法是具有很强全局搜索能力的随机化搜索算法，特别适合求解问题的近 墼鲎叁壅望堡簦鲨垄里望垡些主塑窒旦翌窒兰三皇 似优化解。但g a 本身存在许多不足，尤其在解群分布不均匀时易于出现未成熟收 敛。目前对基本遗传算法有很多种改进的方法，避免未成熟收敛，提高群体多样性 是主要改进方法之一。 免疫系统抗体的超变异是微进化的一种方式，实际上一些动物的生存能力也存 在短时间内可观察到的快速变异现象。超变异是进化的一种特殊现象，免疫系统的 超变异现象是符合进化规律的。这种生物学上的相似性使人们可以将免疫进化机制 应用于算法设计中，产生与遗传算法类似的免疫进化算法。 免疫算法所用的遗传结构与遗传算法的遗传结构类似，选用选择、交叉和变异 等算子解决抗体优化等问题。基于免疫原理的计算方法也可以看做是遗传算法的补 充。 从免疫系统的特征上分析，免疫系统通过细胞的分裂和分化作用，产生大量的 抗体来抵制各种抗原，这对应于遗传算法中个体的多样性；免疫系统具有维持免疫 平衡的机制，通过对抗体的抑制和促进作用，能自我调节产生适当数量的必要抗 体，这对应于遗传算法中个体之间适应度的有益选择，利用这一功能可以提高遗传 算法的局部搜索能力；免疫系统产生抗体的部分细胞会作为记忆细胞而被保留下 来，对今后入侵的同类抗原，相应的记忆细胞会迅速激发而产生大量抗体。如果免 疫算法利用这种抗原识别记忆功能，则可以加快搜索速度，提高算法的总体搜索能 力。免疫遗传算法与免疫算法在形式上看，就是在免疫算法中加入了遗传算子；与 遗传算法相比，增加了抗原识别、记忆功能和调节功能，没有附加复杂的操作，没 有降低遗传算法的鲁棒性，算法兼顾了搜索速度、全局搜索能力和局部搜索能力。 免疫遗传算法一般形式只是要表明免疫机制对进化算法的作用，许多具体算法要根 据具体问题来设计，但其基本思想是一致的，具体操作上非常灵活。 遗传算法所面临的几个问题： ( 1 ) 如何使问题空间解集合中所有的候补解都能用g a 空间的染色体来描述。 ( 2 ) 如何使g a 空间的染色体能与空间解集合中所有的候补解一一对应。 ( 3 ) 如何使用前一代的性质能有效地遗传到下一代。 ( 4 ) 如何控制遗传算法的收敛方向。 ( 5 ) 如何使遗传算法具有记忆功能。 ( 6 ) 如何使遗传算法直接与问题空间的目的函数和制约条件相对应。 第二章改进免疫遗传算法在函数优化中的应用研冗 为了解决上述问题，研究者提出了具有免疫功能的免疫遗传算法。免疫遗传算 法具有下述功能：克服通常遗传算法收敛方向无法控制的缺陷，把目标函数和制约 条件作为抗原，这就能保证所生成的抗体直接与问题相关联，收敛方向能得到控 制，生成的抗体能有效地排除抗原即求得了问题的最优解。对于抗原亲合力高的抗 体进行记忆，能促进快速求解，即当遇到同类抗原时可以快速生成与之对应的抗 体。 免疫遗传算法可以看做是一种改进的、具有免疫功能的