（模式识别与智能系统专业论文）遗传算法中致死染色体的利用方法研究.pdf

摘要 遗传算法中致死染色体的利用方法研究 学科名称： 研究生： 导师姓名： 职称： 答辩时间： 搓墓迟别皇蟹能丕统 蕴垂盈 缢 壶1 盘屯 圭! l i ：12 摘要 遗传算法( g e n e t i c a l g m i t h m ) 因其全局搜索性和鲁棒性，在解决大规模组台优化阿题等领域得 到了广搓应用。实际中，很多的优化问题是带有约束条件的，遗传算法求解有约束优化坷题是对目标 函数在整个遗传空间中搜索满足约束条件的可行解。不满足约束条件的染色体被称为致死染色体。 在遗传算法的种群进化过程中，由于交叉变异操作，致死染色体的产生经常发生，特别是对于约 束比较强的优化问题，致死染色体的产生率比较大。当种群中致死染色体数量比较多时，算法的搜索 性能将会恶化，甚至使算法不能运行。如果致死染色体的产生有一定的规律，可咀通过设计算法来避 免致死染色体的产生，然而在大多数情况下，找到避免致死染色体产生的方法是比较困难的。目前， 在遗传算法中一般采取将致死染色体从种群中剔酴的方法。 由于经过若干代的进化产生的致死染色体中包含了一些优秀的基因，如果对致死染色体加以利 用将会改善和提高算法的搜索性能，本文根据人工免疫算法原理，结合染色体的进化信息和问题的特 征信息提取疫苗和接种疫苗，提出一种基于免疫算子的致死染色体复活方法。在双岛模型中的“活岛” 和“死岛”之问，将致死染色体和复活的致死染色体进行迁移，实现致死染色体的利用。在免疫算子 中，根据致死染色体的特征信息，优秀染色体的特征信息和问题本身的特征信息的不同，分别设计了 三种不同的免疫方法。将算法应用于经典的沪l 背包河嚣和多重选择背包问题。通过数值实验结果表 啊了算法的有效性。该方法可以应用于求解约束优化问题的遗传算法，有效改善遗传算法的应用性能 和搜索性能。 关键词：遗传算法致死染色体免疫算子约束优化问题 本研究得到陕西省白然基金的资助( 项目编号：0 5 j k 2 6 9 ) 。 a b s t r a c t am e t h o d0 fu s i n gl e t h a lc h r o m o s o m e0 fg e n 盯l c a l g o r i t h m s p e c i a l t y ：p a i - r e r nr e c o g n i t i o na n d i n t e l l i g e n ts y s t e m s t u d e n t 8n a m e ：z h a n gy a - l o n g s u p e r v i s o r sn a m e ：m a x u a n ( s i g n a t u r e ) ：丛乒造卜 ( s i g n a t u r e ) ：幽坠 a b s t r a c t o a n e t i c a l g n 妇i s w i d e l y a p p l i e d t o t h e l a r g e - s e a l e c o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e m s f o r i t s g l o b a ls e a r c hp e r f o r m a n c ea n dr o b u s tp e r f o r m a n c e i np r a c t i c a l ，m a n yo p t i m i z a t i o np r o b l e m sa r cu s e dt o s o l v et h ec o n s t r a i n e do p t i m i z a t i o np r o b l e m s ，g e n e t i c a l g o r i t h mt os o l v ec o n s t r a i n e do p t i m i z a t i o np r o b l e mi s s e a r c h i n g t h e f e a s i b l es a l i s c i e d t h ec o n s t r a i n c o n d i t i o n i n t h e g l o b a l g e n e t i c t y p e s p a c e 。t h ec h r o m o s o m e u i l s a t i s f l e dc o n s t r a i n c o n d i t i o ni sc a l l e dl e t h a lc h r o m o s o m e w i t ht h ep o p u l a t i o no fg e n e t i ca l g o r i t h me v o l v i n g , d u et 0c j f 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 r , l e t h a lc h r o m o s o m e so c c i i ii nah i g hr a t e e s p e c i a l l yt 0t h ec o m b i n a t o r i a lo p t i m i z a t i o np m b l e r u sw i t hr i g o r o u s c o n s t r a i n t h en u m b e ro f l e t h a lc h r o m o s o m e sb e c o m ev e r yl a r g ei np o p u l a t i o n t h em o i a gt h en u m b e ro f l e t h a l c h r o m o s o m e sa l ei np o p u l a t i o n t h ew o r s et h es e a r c h i n gp e r f o r m a n c ei s ，t h ea l g o r i t h mw i l ls t o po ns o m l 。= o c c a s i o n s i f t h e p r o d u c e o f t h e l e t h a lc h r o m o s o m e o b e ys o m e o r d e r , l e t h a l c h r o m o s o m e s w i l lb ea v o i d e d v i a a l g o r i t h md e s i g n i n g b u tf o rm o s to fi n s t a n c e , i t sd i f f i c u l tt od e s i g na na l g o r i t h mt oa v o i dt h ep r o d u c eo f l e t h a l c h r o l n o s o r j c s t b e g e n e r a l m e t h o d f o r l e t h a l 吐m l o s o m i s t o e l i m i n a t e i t f r o m i t s p o p u l a t i o n 。 d u r i n gt h ee v o l v i n gp r o c e t 镕s o m ee x c e l l e n tg e n e sa r ec o n t a i n e di nt h el e t h a lc h r o m o s o m e i ft h el e t h a l c h r o m o s o m e j sr e u s e d i n s t e a d o f b e i n ge l i m i n a t e d t h es e a r c h p e r f o r m a n c eo f t h e a l g o r i t h m w i l l b e i m p r o v e d t h i sp a p e rp r o p o s eam e t h o do fr e v i v i n gt h el e t h a lc h r o m o s o m e sa n dr e u s ct h e mb a s e do nt h ea r t i f i c i a l i m m u n et h e o r y , w h i c hm a r r i a g et h ee v o l u f i o n a li n f o r m a t i o no ft h ec h r o m o s o m ea n dt h ec h a r a c t e r i s t i c i n f o r m a t i o no ft h ep r o b l e m , o p u r a t ev a c c i n ea n dv a c c i n a t i n g , t h el e t h a lc h r o m o s o m ei sr e u s e dt h r o g h m o v i n gt h el e t h a la n dr e v i v e dc h r o m 0 6 , o m e sb e t w e a ：nt h et w oi s l a n d s i nt h ei m m u n eo p e r a t o r , a c c o r d i n gt o t h ec h a r a c t e r i s t i ci n f o r m a t i o no ft h el e t h a lc h r o m o s o m e ，e x c e l l e n tc h r o m o m ea n dt h ep r o b l e m , t h r e e d i f f e r e n t i m m u n e m e t h o d s m d e s i g n e d a p p i i n g t h e a l g o r i t h m t o t h ec o n s f r a l n e d o p t i m i z a t i o n p r o b l e ms u c h 0 - 1k n a p s a c kp r o b l e ma n dm u l t i p l ec h o o s ek n a p s a c kp r o b l e m ，t h en u m e r i c a le x p e r i m e n tm s o l t ss h o wt h e v a l i d i t yo ft h ep r o p o s e da l g o r i t h m mm e t h o dp r o p o s e di t h i sp a p e rc a nb ea p p l i e dt og af o rs o l v i n g c o n s t r a i n e do p t i m i z a t i o np r o b l e m , t oi m p r o v et h ea p p l i c a t i o np e r f o r m a n c ea n dt h es e a r c h i n gp e r f o r m a n c eo f g a k e yw o r k s ：g e n e t i ca l g o r i t h m ，l e t h a lc h r o m o s o m e ，i m m u n eo p e r a t o r , c o n s f f a i n e do p t i m i z a t i o np r o b l e m 1 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处由本人承担一切相关责任 论文作者签名：撮垂垫姗7 年3 月7 7 r 日 学位论文使用授权声明 本人缓垂丛在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编人有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 论文作者签名：拯坠盈导师签名 卅年；月7 7 日 1 绪论 i 绪论 1 1 课题背景及意义 遗传算法( g e n e t i c a l g o r i t h m ) 是将待求解问题的可行解编码表示成一个染色体，由若 干个染色体构成一个种群，通过对种群的染色体交叉，变异等遗传算子实现遗传空间的搜 索，然后将搜索到的晟优染色体解码还原成问题的解。因其全局搜索性和鲁棒性，在 解决大规模组合优化问题等领域得到了广泛应用。 组合优化问题可分为无约束条件和有约束条件的优化问题，对无约束的组合优化问 题6 a 可以自由地在解空间进行搜索。实际中，很多的优化问题是带有约束条件的，遗 传算法求解有约束优化问题是对目标函数在整个解空间中搜索满足约束条件的可行解。 不满足约束条件的染色体被称为致死染色体。 在有约束优化问题中，致死染色体的产生有两种情况，一是在生成初始种群时产生 致死染色体，而且约束条件越苛刻产生的致死染色体越多。二是在种群进化过程中，由 于交叉变异操作，产生致死染色体，特别是对于约束强的优化问题，交叉和变异操作引 起的染色体致死情况越多。当种群中致死染色体数量比较多时，遗传算法的搜索性能将 会恶化，严重的使世代进化迭代不能进行。 如果致死染色体的产生有一定的规律，可以把握规律来避免致死染色体的产生，然而 在大多数情况下，找到避免致死染色体产生的方法是比较困难的。目前，在遗传算法中一 般采取将致死染色体从种群中剔除的方法。 剔除致死染色体是处理问题简单的方法。但是经过若干代的进化，新产生的致死染 色体中有可能包含了一些优秀的基因位或基因片断，或者说，包含了有用的进化信息， 如果将其从种群剔除相当于抛弃了一定量的进化成果。所以，如果不将致死的染色体从 种群中剔出，通过一定的方法提取其中的优秀基因片断加以利用。就会在进化过程q 1 最 大限度得利用进化信息，从而改善和提高算法的搜索性能。 1 2 研究现状 关于遗传算法致死染色体问题的研究，国内外文献尚不多见其中文献 3 研究了致 死染色体数量对遗传算法性能的影响，指出了致死俄染色体的产生使遗传算法的搜索性能 大大降低，有时甚至使遗传进化无法进行，但没有给出具体的解决方法。文献 4 提出了 一种在岛模型中用交叉变异遗传算子随机复活致死染色体的方法。即把种群中的染色体分 为“活岛”和“死岛”分别容纳非致死染色体和致死染色体，对“死岛”中的染色体进行 强行交叉和变异的遗传操作来复活染色体的方法，但由于其随机性比较大以及没有利用染 色体和问题的特征信息，效率不够高。 西安理i 大擘硕士学位论文 1 3 论文主要研究内容 一、分析有约束组合优化问题遗传算法中。致死染色体产生的原因和特点以及对算法 性能的影响。 二、分析人工免疫算法的特点，以及免疫算法与遗传算法的联系和共性。 三、提出将免疫算子应用于致死染色复活体利用的方法。 四、以o - 1 背包问题和多重选择背包验证提出算法的有效性。 1 4 论文结构 论文整体为六章。第一章绪论。第二章简要介绍遗传算法原理和致死染色体对遗传 算法的影响。第三章给出人工免疫算法的原理思想以及与遗传算法的联系。第四章提出 一种基于免疫算法的遗传算法致死染色体利用方法，对免疫算子进行了详细的介绍，第五 章通过数值实例验证所提出算法的有效性。第六章总结。 2 2 致死染色体问题 2 致死染色体问题 2 1 遗传算法简介 遗传算法( 0 a ) 是近年来新兴的一种仿生型优化算法，它具有并行搜索、群体寻优 的特点，被广泛用于解决各种具有n p 难度的问题和各种组合优化问题。遗传算法的研究 历史比较短，2 0 世纪6 0 年代末到7 0 年代初，主要由美国m i c h i g a n 大学的j o h nh o l l a n d 与其同事、学生们研究形成了一种比较完整的理论和方法，从试图解释自然系统中生物的 复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过2 0 多年的发 展，取得了丰硕的应用成果和理论进展，特别是近年来世界范围掀起了进化计算热潮，以 及后来的人工生命研究兴起，使遗传算法得到了广泛的关注。从1 9 8 5 年在美国卡耐基梅 隆大学召开的第一届国际遗传算法会议( i n t e r n a t i o n a lc o n f e r a n c co l lg e n e t i ca l g o r i t h m s ： i c g a 8 5 ) ，到1 9 7 7 年5 月i e e e 的t r a n s a c t i o n s o i l e v o l u t i o n a r y c o m p u t a t i o n 创刊，遗传 算法作为具有系统优化、适应和学习的计算和建模方法，对它的研究逐渐成熟。 遗传算法是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。 其思想源于自然进化的优胜劣汰，种群在进化过程中通过选择、交叉和变异来获得更 优秀的个体。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是 对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的 染色体有更多的繁殖机会。在遗传算法中，通过随机方式生成若干个所求解问题的数 字编码，即染色体，这里每一个染色体都对应问题的一个解，这若干个染色体的集合称 为种群。遗传算法从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个 体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足 期望的终止条件为止。 遗传算法的基本结构可以表示为如图2 一l 的形式。算法过程的语言描述如下； b e g i n t | _ - 0 初始化p ( t ) 评价p ( t ) w h il e ( 终止条件不满足) d 0 b e g i n 重组p ( t ) 以产生c ( t ) 评价c ( t ) 从p ( t ) 和c ( t ) 中选择p ( t + 1 ) t t + l 西安理i 大学项士学位论文 图2 - 1 遗传算法流程 f i g u r e2 - 1t h ep r o c e s so ft h eg e n e t i ca l g u r i t h m 遗传算法进化的终止条件有以下几种情况： l 、完成了预先给定的进化代数则终止； 2 、种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有 改进时可以终止； 3 、搜索到的最优个体达到了优化指标时终止。 模式定理和积本块假设是遗传算法的基本理论。 l 、模式定理；在遗传算法的几个基本操作( 选择、交叉和变异) 的作用下，具有 低阶、短定义距并且平均适应度高于群体平均适应度的模式在子代中将得以指数级增 长。 2 、积木块( b u i l d i n gb l o c k ) 假设：低阶、短距、平均适应度高的基因块，通过选 4 2 致死染色体问题 择、交叉和变异等遗传操作数的作用，能够互相拼接在一起，形成高阶、长距、平均 适应度高的模式，可晟终生成全局最优解。 模式定理保证遗传算法的收敛方向指向最优解，而积木块假设指出遗传算法具备 找到全局最优解的能力。模式定理保证了优秀模式的样本成指数增长，从而满足了求 最优解的条件。即遗传算法存在找到全局最优解的可能性：而积木块假设指出，遗传 算法具备寻找全局最优解的能力，即积木块在遗传操作数的作用下，最终生成全局最 优解。 2 2 遗传算法的特点 遗传算法是建立在自然选择和群体遗传学机理基础上的迭代、进化、具有广泛实 用性的搜索方法。它是一种方向性的优化算法，并不是简单的随机搜索，而是通过对 染色体的评价和对基因的作用，来利用有效的信息指导搜索，并优化种群。它结合了 生物进化中的适者生存和随机信息交换两种机制，与传统的优化算法相比，遗传算法 的主要本质特征在于种群策略和简单的遗传算子。遗传算法主要有以下几个特点。 一、以表示可行解的编码( 染色体) 为运算、搜索的对象。 传统的优化算法往往直接利用优化变量的本身进行进化运算操作，但是遗传算法不是 直接以原优化变量的值，而是以优化变量的某种形式的遗传编码为运算对象。这种对优化 变量的编码处理方式使得在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿 自然界中生物机制和遗传变异原理，也使得我们可以方便地应用遗传、进化等操作算子。 另外。对一些非数值概念或很难用数值概念而只能用代码的优化问题( 这类问题成为非数 值优化问题) ，遗传算法的这种处理方式显示其独特的优越性。 二、从问题解的种群开始搜索，而不是从单个解开始。 这是遗传算法与传统算法的主要区别。传统算法是从单个初始值迭代求出最优解。单 个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时甚至搜索过程陷于局部解 而停滞不前。遗传算法从种群开始搜索，覆盖面大，利于全局择优。 三、 求解时特定问题的信息少，容易形成通用的算法程序，稳健性强。 由于遗传算法使用适应度这一信息进行搜索，并不需要问题可导连续等与问题直接相 关的信息。遗传算法只需要适应度和个体编码等通用信息，因此其应用范围广泛。 四、选择、交叉和变异都是随机操作，而不是确定的精确规则。 很多传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的 转移方法和转移关系，这种确定性限制了算法的应用范围。而遗传算法用一种概率的方式， 增加了其搜索过程的灵活性。当然交义概率和变异概率等参数也会影响算法的搜索效果和 搜索效率，所以如果选择算法的交叉变异参数在其应用中是一个比较重要的问题。 西安理i 大擘硕士学位论文 五、具有隐含的并行性。 遗传算法的本质是对模式所进行的系列运算。一个个体从模式角度分析是隐含有多 种不同的模式个体，所以算法对一定种群规模的个体进行运算，实质上却处理了大于种群 规模的模式，而且是包含在处理过程内部的一种隐含并行性。通过这种隐含并行性，使得 我们可以快速地搜索出一些较好的模式。 六、 对解决离散问题的优势。 遗传算法对离散优化问题比传统优化算法具有优势。它能有效地处理大量离散参数， 可以解决传统优化方法无法解决的优化问题，大大扩大了它的适用范围。 2 j 遗传算法在优化问题上的应用 在管理科学、运筹学和工程设计中，优化问题处于非常重要的地位。许多工业工程的 组合优化问题的复杂程度属于n p - h a r d 问题，当输入较大时，导致组合“爆炸”，以至于 难于采用传统优化方法进行求解。近年来由于遗传算法作为新兴优化方法具有良好的潜 质，该算法受到普遍地关注。遗传算法具有简单、易操作、需求底、并行和全局等特点， 在工程优化中取得了成功应用。 图2 2 不可行解与致死染色体 f i g u r e2 - 2u n f e a s i b i l i t ya n s w e r s l e t h a lc h l - o m o s o m e 优化问题通常是具有多个变量且需要服从等式或不等式约束的最小化或最大化函数 问题。有约束优化问题的一般形式如下： m a x ，o ) ( 或m i l l ， ) ) ( 2 1 ) s 1 g ，o ) s o , i - 1 ，2 ，m i ( 2 2 ) h ( x ) 一0 ，f - m 1 + 1 ，m ( - m 1 + m 2 ) ( 2 3 ) j x( 2 4 ) 其中，函，9 2 c g ，k 。，k 是在r ”上定义的实值函数，x 是r 1 的子集，x 是h 维实 向量，其元素为z 。，屯，。上述问题的解必须为既能满足约束同时又最小化函数，的变 6 2 致死染色体问题 量而，而，x 。函数，通常称作目标函数。约束g 。o ) j0 称作不等式约束，约束h ；“) 一0 称作等式约束。集合x 通常可能包括变量的下界和上界，称作约束域。如图2 2 所示， 满足所有约束的向量x 工称作问题的可行解，这种解的集合构成可行区域。不满足其中 任意一条约束的向量，x 称作问题的不可行解，在遗传算法中这种不可行解对应的遗传 编码称为致死染色体。 遗传算法是以遗传编码( 染色体) 为运算对象，每个染色体对应一个问题的解，所以 编码空间与解空间是一种一一映射关系。如图2 2 。不可行解对应的编码染色体为致死染 色体。 2 4 致死染色体的产生及对算法的影响 遗传算法在求解有约束组合优化问题时，由于约束条件的存在。遗传编码对应的解 有可能不满足约束条件而产生致死染色体，致死染色体在以下两种情况下产生，一是在 生成初始种群时产生致死染色体，而且约束条件越苛刻产生的致死染色体越多。二是在 种群进化过程中，由于交叉变异操作，产生致死染色体，特别是对于约束强的优化问题， 交叉和变异操作引起的染色体致死情况越多。 咀0 一l 背包问题为例说明致死染色体产生的情况。 ，本文对文献 5 中的o _ 1 背包问题( v = 5 5 ，1 0 ，4 7 ，5 ，4 ，5 0 ，8 ，6 1 ，8 5 ，8 7 ，w = 9 5 ，4 ，6 0 ，3 2 ，2 3 ，7 2 ，8 0 ，6 2 ，6 5 ，4 6 ) 进行了实验。给定不同的约束强度b 一口了w ，在随 机生成的1 0 0 个染色体中致死染色体的产生数量如表2 1 所示。可以看出，在约束强度 变得比较大时，致死染色体的生成数量非常多。 表21 约柬强度与致死染色体数量 t a b2 - 1c o n s t r a i ni n t e n s i t y t h en u m b e ro ft h el e t h a lc h r o l n o s o m e n0 9o 70 50 40 3o 2 【限制重量 4 8 5 3 7 7 2 6 9 2 1 51 6 l1 0 7 数量 0o 1 8 2 4 8 91 0 0 表22 世代种群中的非致死染色体数量 t a b2 - 2t h en u m b e ro fn o n l e t h a lc h r o m o s o m ei ng e n e r a t i o np o p u l a t i o ng r o u p 进化代数 0l24681 01 2 数量 1 0 08 2 5 43 33 81 81 16 选取1 0 0 个非致死染色体作为初始种群，取交叉率和变异率分别为0 9 和0 0 1 ， a = o 5 ，在种群中剔除致死染色体，各代种群中非致死染色体的数量变化如表2 2 所示。 西安理工大学硕士学位论文 由于在进化过程中致死染色体的产生，种群中非致死染色体逐渐减少，在第1 2 代时种群 中仅有6 个非致死染色体。 种群中非致死染色体太少算法性能将严重劣化，甚至会使算法不能运行为了使 种群保持一定的规模，一般采取将致死染色体剔除后向种群中补充新生染色体的方法。 所以，当每一代进化产生的致死染色体的数量比较大时，在种群中需要补充大量的新生 染色体，这将使算法趋于随机搜索。 解决致死染色体现有的方法一般有咀下几种； l 、避免产生的方法。 避免致死染色体的产生要求致死染色体的产生有一定的规律，可以通过设计算法来 避免致死染色体的产生，然而在大多数情况下，因为致死染色体的产生没有明显的规律， 找到避免致死染色体产生的方法比较困难。 2 、抛弃方法。 抛弃方法是指在种群的进化过程中把产生的致死染色体从种群中剔除。抛弃方法是 处理问题最简单但也是效率最低的方法，因为在种群的进化过程中产生的致死染色体有 可能是由优秀的染色体经过交叉变异而成，致死的原因是因为其中某些基因不够优秀的 原因，而大部分基因由于已经经过很多代的进化已经是很优秀的基因，如果将其抛弃其 实是抛弃了以前很多代进化而来的优秀基因成果。是对进化资源的抛弃。 3 、惩罚的方法。 一 惩罚方法的基本恩想从传统优化中借鉴而来。这种方法通过设计罚函数来将约束问 题转换为无约束问题。任何对约束的违反都要在目标函数中添加惩罚项。关于设计罚函 数没有一般的指导性原则，构造一个有效的罚函数依赖于给定的具体问题。 4 、修补复活的方法。 修补复活的方法以使染色体复活为目的，对于许多组合优化问题，创建修补复活过 程相对容易，但是不是对进化资源利用的研究。对遗传算法搜索性能的改善有一定限制。 基于以上所述，对于求解约束优化问题的遗传算法，致死染色体问题是一个值得研 究的问题。 8 3 人i 免疫算法 3 免疫算法与遗传算法 3 1 免疫算法简介 生物和医学科学证实，人的免疫系统是一个与人脑一样复杂的巨型系统，拥有1 0 ” 个免疫细胞，遍布全身各个角落。当外部病原体或细菌侵入机体时，免疫细胞能够识别“自 体”和“异体”，迅速清除和消灭异物，确保机体的安全。所以人体因为某种细菌感染而 致病然后痊愈后，对该细菌抗原就会产生不同程度的免疫力。换言之，是指对感染因子的 再次感染有抵抗力，这是机体在初次感染后对该传染因子产生了免疫应答的结果。医学上 免疫是机体接触抗原性异物的一种生理反应。免疫系统有能力产生很多种抗体，免疫系统 的控制机制可完成这一调节功能，即只产生所需数量的抗体。根据生理特点，如果任一细 胞系中的细胞由于抗原的刺激而被激活并开始繁殖，其它能识别这种基因类型的细胞系也 被激活并开始繁殖，这样，如果这一过程连续地进行，就构成了对自身的免疫，并且通过 所有淋巴细胞的作用实现了调节机制。 生物免疫系统的这种能力，具有多样性、耐受性、大规模并行分布处理，自组织、自 学习、自适应、免疫记忆和鲁棒性等特点，近年来受到国内外众多研究者的关注。2 0 0 2 年6 月i e e et r a n s 卟e 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 次之多。 免疫算法( i m m u n e a l g o r i t h m ) 是基于生物免疫系统基本机制，模仿人体的免疫机理 的一种计算方法。根据模仿的免疫机理的不同，免疫算法一般有三种情况：一种是模仿免 疫系统抗体和抗原识别、结合抗体产生过程而抽象出来的一般免疫算法。基于这种免疫系 统中最基本的免疫机制的算法目前应用较多：第二种是基于免疫系统中其他特殊机制抽象 的算法，比如基于克隆选择原理的克隆选择算法等；第三种是与遗传算法等计算智能融合 产生的算法，目前主要是免疫遗传算法。 免疫算法大致可以分类为基于群体的免疫算法( 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 ) 。前者构成的系统中的元素之间没有直接的联系。系统组成元素 直接和系统环境相互作用，他们之间若要联系只能通过间接的方式，而在由后者构成的系 统中，恰恰相反，部分甚至是全体的系统元素都能够相互作用。 免疫算法主要模拟生物免疫系统中有关抗原处理的核心思想。用免疫算法解决具体问 题时，首先需要将问题的有关描述与免疫系统有关概念及免疫原理对应起来定义免疫元素 数学表达，然后再设计相应的免疫算法。一般地，免疫算法大致由以下几个步骤组成： s t e p1 、识别抗原：将需要解决的问题抽象成符合免疫系统处理的抗原形式，抗原识 别则对应问题的求解。 s t e p2 、产生初始抗体群体：将抗体的群体定义为问题的解，抗体与抗原之间的亲和 力对应问题解的评估：亲和力越高说明解越优秀。类似遗传算法，首先产生初始抗体群体， 西安理工大学硕士擘住论文 对应问题的一个随机解集合。 s t e p3 、计算亲和力：计算抗原与抗体之间的亲和力。 s t e p4 、抗体促进和抑制：与抗原有最大亲和力的抗体加给记忆细胞。由于记忆细胞 数目有限，新产生的与抗原具有更高亲和力的抗体替换较低亲和力的抗体。高亲和力抗体 优先得到繁殖，高密度抗体受到抑制。 s t e p5 、评价新的抗体群体：若不能满足终止条件，则转向s t e p 3 ，重新开始；若满足 终止条件，则当前的抗体群体则为问题的最佳解。 免疫算法的基本结构如图3 - l 。 图3 - 1 免疫算法流程 f i g u m3 - 1i m m u n ea l g o r i t h mp r o c e s s 如果将免疫算法用于求解优化问题，那么抗原、抗体、抗原和抗体之间的亲和性分别 对应于优化问题的目标函数、优化解、解与目标函数的匹配程度。 3 2 免疫算法与遗传算法的关系 3 人工免疫算法 免疫算法与遗传算法在生物学上的区别是：遗传算法的生物学机理是基于达尔文的物 种宏观进化思想，而免疫系统的算法是在个体的基础上发展的；但物种宏观进化对个体免 疫系统的进化是有重要影响的。免疫系统随着物种的进化一方面慢速进化，另一满面为了 适应病原体环境而快速进化。也就是说，生物进化是在有机体之间进行的自然选择，免疫 系统个体发育进化是在一个有机体内进行的自然选择。自然选择和个体发育卣目变化对于 生物为了生存而进行的无休止的斗争至关重要。正是二者之间的这种千丝万缕的联系反映 在计算智能反面，使二者发展的算法既有相似性，又有各自的特点，且可以相互促进。 遗传算法可用于研究不同的关于免疫系统如何进化的假设。在这种情况下在遗传算 法中，每个个体对应一个生物个体( 更确切地说，生物个体的免疫系统基因) ，适应度对 应个体抵制病原体的存活率，变异和交叉对应遗传变化( 下一代相对父代的变化) 。 免疫算法方法所用的遗传结构与遗传算法所用的类似，采用重组、变异等算子操作解 决抗体优化等问题。 免疫系统个体亲和力成熟过程使人联想到遗传算法，二者有许多不同之处。基于免疫 系统的计算方法也可以看作遗传算法的补充。二者的区别可以归纳如下： 一、免疫算法起源于宿主( h o s t ) 和宿原( p a r a s i t e ) 之间的内部竞争，其相互作用 的环境既包括外部也包括内部环境；而遗传算法起源于个体和自私基因之间的外部竞争。 二、免疫算法假设免疫元素相互作用，郎每一个免疫细胞等个体之间可以相互作用， 而遗传算法不考虑个体之间的相互作用，而考虑种群之间的宏观变化。 三、免疫算法中，基因可以由个体自己选择，而在遗传算法中基因由环境选择。 四、免疫算法中基因组合是为了获得多样性，一般不用交叉算子因为免疫算法中 基因是在同一代个体之间进行进化；而遗传算法后代个体基因通常是上一代个体交叉的结 果，交叉用于混合重组基因。 五，免疫算法与遗传算法的一个主要区剐是利用问题的特征信息制作疫苗。 3 3 免疫遗传算法 免疫遗传算法可以看做一种新型融合算法，也是一种改进的遗传算法，一种新型的计 算智能方法，是具有免疫功能的遗传算法。与免疫算法一样，把待求解的问题对应为抗原， 问题的解对应为抗体，在许多方面表现出超越遗传算法和免疫算法的优点，目前应用较为 广泛，比如t s p 问题、神经网络设计、信号分析、色谱分析等。这些算法既保留了遗传算 法的搜索特性，克服了遗传算法由于交叉而带来的局部搜索解空问上效率不高的缺点，又 在很大程度上避免未成熟收敛。 免疫遗传算法与免疫算法在形式p 看，就是在免疫算法中加入了遗传因子，与遗传算 法相比较，增加了抗原识别、记忆功能和调节功能，没有附加复杂的操作，没有降低遗传 算法的鲁棒性，算法蓑顾了搜索速度、全局搜索能力和局部搜索能力。免疫遗传算法一般 1 1 西安理i 大擘_ 项士学位论文 形式只是要表明免疫机理对进化算法的作用，许多具体算法要根据具体问题具体设计，但 基本思想大致一致。 免疫遗传算法的一般形式如图3 - 2 。 图3 - 2 免疫遗传算法流程 f i g u r e3 - 2i m m l l n ea n dg e n e t i c ：a l g o r i t h mp r o c e s s 论文是研究遗传算法本身的致死染色体问题，提出了一种基于免疫算法的遗传算法中 致死染色体的利用方法。以此解决遗传算法在进化过程充分利用进化资源的问题，以提高 遗传算法解决有约束优化问题的进化性能为目的，和免疫遗传算法不同。免疫遗传算法是 在免疫算法中加入遗传因子，而论文所作的工作是借助免疫算法的免疫机理，在遗传算法 中进行免疫操作，以实现致死染色体的利用主要是提取疫苗和接种疫苗的方法研究。 4 基于免疫算法的致死染色体利用 4 基于免疫算法的致死染色体利用 根据第2 章所述，遗传算法用于有约束的组合优化问题时，由于约束条件的存在，在 生成初始种群和算法的进化过程中，会根据约束条件的强弱产生不用数量的致死染色体， 如果将其抛弃其实质是抛弃了一定量的进化成果，特别是在种群的进化过程中抛弃的致死 染色体，相当抛弃了其中包含的优秀基因片段。如果用重新生成个体来补充种群的方法来 维持算法的继续进化，便算法加大了随机搜索的成分，这对算法的进化速度和收敛点有一 定的限制。 据此文章提出一种基于免疫算法的致死染色体的利用方法，通过设计免疫算子对致死 的染色体接种疫苗，在双岛模型的算法结构中实现免疫操作以复活致死的染色体，同时保 留致死染色体的优秀基因部分，以最大限度的利用进化资源为目的从而改善算法的进化 速度和提高收敛点。 下面首先介绍双岛模型算法结构以及算法步骤，然后把免疫机理引入到双岛模型处理 致死染色体的方法中，再介绍根据特征信息的不同设计的三种不同免疫算子在双岛模型中 的应用。 4 1 双岛模型 4 1 1 岛模型的来源 岛模型来源于文献【4 1 ，是由日本学者甜孟春等早在1 9 9 6 年提出的一种解决致死染 色体问题的遗传算法模型。文献 4 】所描述的岛模型是把致死染色体集中到一个集合( 死 岛) 中，强行对致死染色体进行遗传算子的交叉变异操作，随机地复活致死染色体，再把 复活的染色体提取到标准的遗传算法中加以利用。由于对致死染色体交叉和变异操作随机 性比较大复活率不高，以及没有利用染色体本身和问题的特征信息，所以效率不够高。如 果引入免疫处理可咀利用问题特征信息，可以改变致死染色体利用效率，从而改变算法的 搜索性能。为此论文设计了基于免疫复活的双岛模型来解决致死染色体的利用问题。 4 1 2 双岛模型算法结构 双岛模型的计算模式首先是基于遗传算法的基本框架只是在生成初始种群后将染 色体集合分为两个部分，为了便于描述，一个称之为“活岛”，容纳种群中满足约束条件 的染色体；另一个称之为“死岛”，容纳不满足约束条件的致死染色体。“活岛”中染色 体的进化采用交叉变异等遗传算子，“死岛”中致死染色体的复活采用免疫算子。对经过 遗传算子产生的致死染色体和经过免痤算子复活的染色体进行迁移，即把遗传操作的致 西安理工大学硕士学位论文 死染色体放入“死岛”，把免疫算子复活的染色体放入“活岛”。 双岛模型的计算模式其实是有两条计算线路的并行计算，其中一条是以“活岛”为 主线的标准遗传算法的流程，另一条是以“死岛4 为处理对象的免疫操作过程。算法的 控制是遗传算法进化一代的同时，免疫算子对“死岛”进行一轮免疫处理，然后交换染 色体，即把“活岛”经过遗传操作致死的个体迁移到死岛，再把死岛经过免疫操作复活 的个体迁移到活岛。然后再进行下一次的迭代，直至满足算法的终止条件。 双岛模型的算法流程如图4 - 1 所示。 4 1 3 算法步骤 图4 - 1 双岛模型流程 f i g u r e4 1t w oi s l a n dp r o c e s s 在双岛模型的致死染色体复活与利用方法中，“活岛”中染色体的进化采用遗传算子， 其过程与一般遗传算法相同，“死岛”中致死染色体的复活采用免疫算子。算法的主要步 骤如下： s t e p1 生成初始种群，将种群中的非致死染色体和致死染色体分别放入“活岛”和 “死岛”： 4 基于免疫算法的致死染色体利用 s t e pz 对死岛中的致死染色体免疫处理； 2 1 从“死岛”中选出一个致死染色体； 2 2 根据特征信息提取疫苗； ( 根据特征信息的不同，提取疫苗和接种疫苗有三种方法，如4 ，2 节所述) ； 2 3 对致死染色体接种疫苗； 2 4 重复2 1 2 4 ，直到遍历全部致死染色体； s t e p3 免疫选择。在死岛中选出经过s t e p2 复活的染色体，然后迁移到“活岛”， 准备参与遗传进化； s t e p4 对“活岛”中的染色体施加交叉变异算子，产生子代染色体，使种群向前进 化一代； s t e p5 迁移，把s t e p 4 中新产生的致死染色体迁移到“死岛”： s t e p6 重复s t e p 2 砖t c p 5 ，直到满足遗传算法的终止条件。 4 2 免疫算子 如第三章所述，根掘模仿的免疫机理的不同，免疫算法一般有三种情况：一种是模仿 免疫系统抗体和抗原识别、结合抗体产生过程而抽象出来的般免疫算法。基于这种免疫 系统中最基本的免疫机制的算法目前麻用较多：第二种是基于免疫系统中其他特殊机制抽 象的算法，比如基于克隆选择原理的克隆选择算法等；第三种是与遗传算法等计算智能融 合产生的算法。 无论是从哪一种免疫机理抽象出来的免疫算法模型，其主要模拟的是生物免疫系统 中有关抗原处理的核心思想。用免疫算法解决具体问题时，首先需要将问题的有关描述 与免疫系统有关概念及免疫原理对应起来定义免疫元素数学表达然后再设计相应的免疫 算法。 论文所要傲