（计算机软件与理论专业论文）用于组合优化的人工免疫算法设计与分析.pdf

摘要 摘要 克隆选择算法是人工免疫系统领域中的重要算法之一。作为克隆选择算法中 重要的算子，元动力学算子很少受到关注。另一方面，进化非选择算法是基于生 物免疫进化机制和免疫非选择机制而提出的一种新的算法，可应用于组合优化和 异常检测等问题。但是，迄今为止，尚未有相关文献专门研究用于组合优化问题 的进化非选择算法的时间复杂度。 本文主要针对人工免疫系统中的这两个算法进行研究，具体工作包括以下几 个方面。 ( 1 ) 从实验角度分析和讨论了不同元动力学策略对于克隆选择算法性能的 影响。传统的元动力学策略是对二进制染色体中的每一位，以相同的概率生成0 或者l 。然而，对于有些问题，这种元动力学策略实际上并不能真的增加种群的 多样性。例如，该问题的解与0 或者1 的个数有关，而与0 或者l 在二进制染色 体中的位置没有关系的时候。因此，本文提出了三种新的元动力学策略。针对上 面所提到的这类问题，这三种元动力学可以很明显的起到均匀采样的作用。实验 结果表明，本文提出的这三种元动力学策略在这一类问题上具有较好的性能。 ( 2 ) 基于一个典型的组合优化问题，对比分析了采用不同匹配阈值的进化 非选择算法在该问题上的平均时间复杂度。理论分析和实验结果表明，有合适匹 配阈值的进化非选择算法的性能优于传统进化算法的性能。由此可知，非选择算 子对于提升进化类算法的性能有重要作用。 ( 3 ) 一方面，有合适匹配阈值的进化非选择算法的性能优于传统进化算法 的性能。另一方面，当匹配阈值不合适时，进化非选择算法的性能未必优于传统 进化算法。为此，本文进一步分析和讨论了，匹配阈值在一定范围内变化时，进 化非选择算法的性能会有怎样的变化。理论结果和实验结果表明，合适的匹配阈 值在常数范围内变化时，进化非选择算法的性能仍然优于传统进化算法；而当不 合适的匹配阂值在常数范围内变化时，进化非选择算法的性能未必优于传统进化 算法的性能。 总的来说，本文首先提出了三种新的元动力学策略，分析了元动力学算子对 克隆选择算法性能的影响。然后，分析了进化非选择算法在一个组合优化问题上 的平均时间复杂度，以及匹配阈值对进化非选择算法性能的影响。本文的研究成 果不仅对用于组合优化问题的人工免疫算法设计具有重要意义，而且对人工免疫 算法的理论分析和应用研究都具有参考价值。 中国科学技术大学硕士学位论文 关键词：人工免疫系统克隆选择算法进化非选择算法平均时间复杂度 i i a b s t r a c t a b s t r a c t c l o n a ls e l e c t i o na l g o r i t h m s ( c s a s ) a r eak i n d o fi m p o r t a n ta l g o r i t h m si n a r t i f i c i a li m m u n ec o m m u n i t y a sa ni m p o r t a n to p e r a t o ro fc s a s ，t h ei n f l u e n c eo ft h e m e t a d y n a m i c ss t r a t e g yo nt h ep e r f o r m a n c eo fc s a sh a sn o tb e e np a i dm u c ha t t e n t i o n b a s e do ne v o l u t i o n a r ya l g o r i t h m s ( e a s ) a n d n e g a t i v e s e l e c t i o na l g o r i t h m s ， e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m s ( e n s a s ) h a v eb e e np r o p o s e d ，a n di tc a n b eu s e df o rc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m sa n da n o m a l yd e t e c t i o np r o b l e m s h o w e v e r , t h ea v e r a g et i m ec o m p l e x i t yo fe n s a sf o rc o m b i n a t i o n a lo p t i m i z a t i o n p r o b l e m sh a sn e v e rb e e ns t u d i e db e f o r e i nt h i sp a p e r , t h e s et w oa l g o r i t h m sa r es t u d i e d ，a n dt h ew o r k i n c l u d e s ， ( 1 ) b a s e do ne x p e r i m e n t s ，t h ei n f l u e n c eo fm e t a d y n a m i c so nt h ep e r f o r m a n c eo f c s a sa r es t u d i e da n dd i s c u s s e d i nt h eb i n a r ys p a c e ，t h et r a d i t i o n a lm e t a d y n a m i c s u s u a l l ya d o p t sa ne q u a lp r o b a b i l i t yt og e n e r a t e0a n d1f o re a c hb i to ft h ec h r o m o s o m e h o w e v e r , f o rs o m ep r o b l e m s ，s u c ham e t a d y n a m i c sc o u l dn o tr e a l l yi n c r e a s et h e p o p u l a t i o nd i v e r s i t y i nt h i sp a p e r , f o u rd i f f e r e n tm e t a d y n a m i c ss t r a t e g i e si n c l u d i n g t h et r a d i t i o n a lm e t a d y n a m i c ss t r a t e g ya n dt h r e en o v e lm e t a d y n a m i c ss t r a t e g i e sa r e t e s t e d b yf o u rc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m s t h ee x p e r i m e n t a lr e s u l t s d e m o n s t r a t et h e s e t h r e en o v e lm e t a d y n a m i c sc o u l di m p r o v et h ep e r f o r m a n c eo fc s a s f o rt h e s ef o u rp r o b l e m s ( 2 ) t h ea v e r a g et i m ec o m p l e x i t yo fe n s a so no n ec o m b i n a t i o n a lo p t i m i z a t i o n p r o b l e mi sa n a l y z e d t h et h e o r e t i c a lr e s u l t sd e m o n s t r a t et h a t ，f o rt h et w om a x f u n c t i o n , t h ee n s a sw i t ha l la p p r o p r i a t em a t c h i n gt h r e s h o l dc o u l dp e r f o r mb e t t e r t h a nt h et r a d i t i o n a l e a s o m es i m u l a t i o ne x p e r i m e n t so nt h ec o m b i n a t i o n a l p r o b l e ma r ea l s od o n e ，a n dt h ee x p e r i m e n t a lr e s u l t sa r ec o n s i s t e n tw i t ht h e o r e t i c a l r e s u l t s ( 3 ) f u r t h e r m o r e ，w h e nt h et h r e s h o l dc h a n g e s ，t h ea v e r a g et i m ec o m p l e x i t yo f e n s ai sa l s o a n a l y z e d t h et h e o r e t i c a lr e s u l t sa n de x p e r i m e n t a lr e s u l t sb e i t h d e m o n s t r a t et h a t ，w h e nt h et h r e s h o l d c h a n g e si nc o n s t a n t ，t h ea v e r a g et i m e c o m p l e x i t yo fe n s a i sn o tc h a n g e d 1 1 1a l l ，t h r e en o v e lm e t a d y n a m i c sa r ep r o p o s e di nt h i sp a p e ga n dt h ei n f l u e n c eo f m e t a d y n a m i c so nt h ep e r f o r m a n c eo fc s ai sa n a l y z e d t h e nt h ea v e r a g et i m e c o m p l e x i t yo fe n s ao nac o m b i n a t i o n a lo p t i m i z a t i o np r o b l e mi sa l l a y e d a l s o ，t h e i i i a b s t r a c t i n f l u e n c eo ft h r e s h o l do nt h ep e r f o r m a n c eo fe n s ai sa n a l y z e d t h er e s u l t so ft h i s p a p e ra r en o to n l yi m p o r t a n tf o rd e s i g no fa r t i f i c i a l i m m u n ea l g o r i t h m sf o r c o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m ，b u ta l s of o rt h et h e o r e t i c a l a n a l y s e s a n d a p p l i c a t i o no f a r t i f i c i a li m m u n ea l g o r i t h m s k e yw o r d s ：a r t i f i c i a li m m u n es y s t e m ，c l o n a ls e l e c t i o na l g o r i t h m s ，e v o l u t i o n a r y n e g a t i v es e l e c t i o na l g o r i t h m s ，a v e r a g et i m ec o m p l e x i t y i v 插图目录 图1 1 图1 2 图2 1 图2 2 图2 。3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图2 1 2 图2 1 3 图2 1 4 图3 1 图3 2 图3 3 图3 4 图3 5 图4 1 图4 2 图4 3 图4 4 插图目录 克隆选择算法一般流程 2 2 进化非选择算法一般流程 1 8 1 9 4 本文中使用的克隆选择算法的框架8 传统的元动力学策略9 第二个元动力学策略1 0 第三个元动力学策略1 l t w om a x 函数1 2 t w om a x 问题上的实验结果1 3 a l m o s tp o s i t i v e 函数1 4 a l m o s tp o s i t i v e 上的实验结果1 5 n - a l m o s tp o s i t i r e 函数1 6 na l m o s tp o s i t i v e 函数上的实验结果的1 7 d u f 3 的基本模块18 d u f 3 问题上的实验结果1 9 m d s - 2 。m d s - 3 和m d s - 4 的概率数组p r 0 i 0 0 一2 0 一个节点覆盖问题上的实验结果2 2 本文中分析所用到的( 年d e n s a 2 7 传统的( 斛肋e a 一2 8 t w om a x 函数一2 8 t w om a x 函数上的实验结果比较3 5 不同匹配阈值的e n s a 在t w om a x 问题上的实验结果3 7 匹配阈值为( n 2 一c ) ( c 为常数) 的e n s a 在t w om a x 函数上的实验结果比较4 5 匹配阈值为c ( f 为常数) 的e n s a 在t w om a x 问题上的实验结果4 6 匹配阈值为( 3 0 ( c 为常数) 的e n s a 在t w om a x 问题上的实验结果4 8 匹配阈值为( n 4 - c ( c 为常数) 的e n s a 在t w om a x 问题上的实验结果4 9 v i i 表格目录 表格目录 表2 1t w om a x 问题的实验结果。括号中数字表示标准差1 3 表2 2a l m o s tp o s i t i v e 问题的实验结果。括号中数字表示标准差1 4 表2 3na l m o s tp o s i t i v e 问题的实验结果。括号中数字表示标准差1 6 表2 4d u f 3 问题的实验结果。括号中数字表示标准差1 8 表2 5 节点覆盖问题的实验结果。括号中数字表示标准差2 l 表3 1 ( 肝肋e a 和( 胆川5 ) e n s a 在t w om a x 函数上的平均时间复杂度2 9 表3 2e n s a 和e a 在t w om a x 函数上的实验结果。括号里的数字是标准差3 4 表3 3 匹配阈值为2 和3 的e n s a 在t w om a x 函数上的实验结果。括号里的数字是标 准差3 6 表3 4 匹配阈值为( n 2 2 ) 和( n 2 一1 ) 的e n s a 在t w om a x 函数上的实验结果。括号 里的数字是标准差3 7 表4 1 当匹配阈值为( n 2 1 ) ，( n 2 2 ) 和( n 2 3 ) 时，e n s a 在t w om a x 函数上的 实验结果。括号里的数字是标准差4 4 表4 2 当匹配阂值为( n 2 4 ) ，( n 2 5 ) 和( n 2 6 ) 时，e n s a 在t w om a x 函数上的 实验结果。括号里的数字是标准差4 4 表4 3当匹配阈值分别为l ，2 ，3 的时候，e n s a 在t w om a x 函数上的实验结果。括号 里的数字是标准差4 5 表4 4当匹配阈值为4 ，5 ，6 的时候，e n s a 在t w om a x 函数上的实验结果。括号里的 数字是标准善4 5 表4 5 当匹配阂值为n 3 ，n 3 一l 和n 3 2 的时候，e n s a 在t w om a x 函数上的实验 结果。括号里的数字是标准差一4 7 表4 6 当匹配阈值为n 4 ，n 4 一l 和n 4 2 的时候，e n s a 在t w om a x 函数上的实验 结果。括号里的数字是标准差4 8 v i i i 中国科学技术大学学位论文原创，性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除己特别加以标注和致谢的地方外，论文中不包含任何他人己经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作了明确 的说明。 作者签名： 签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 口公开口保密( 年) 作者签名： 签字日期： 导师签名： 签字日期： 翌幺! 丝 竺鱼：堑12 第1 章绪论 第1 章绪论 人工免疫系统是基于生物免疫系统的工作机制和理论，用于解决各种形式的 计算问题的计算模型，方法和系统 1 】。当前，大多数的人工免疫系统主要集中 于几个免疫学机制，如克隆选择、非选择和免疫网络等。 对人工免疫算法的算子的研究以及对人工免疫算法的时间复杂度的分析，有 助于加深对人工免疫算法的理解。特别的，在组合优化问题上，研究人工免疫算 法，不仅有助于对用于组合优化问题的人工免疫算法设计具有重要意义，而且对 人工免疫算法的理论分析和应用研究都具有参考价值。 在本文中，首先研究和讨论的是克隆选择算法中的元动力学算子对于克隆选 择算法的性能的影响。其次，本文分析了进化非选择算法在一个组合优化问题上 的平均时间复杂度。最后，本文分析和讨论了进化非选择算法中的匹配阈值在该 组合优化问上对算法平均时间复杂度的影响。 本章首先介绍了克隆选择算法的基本流程，接着对克隆选择算法的研究现状 进行概述。然后，本章介绍了进化非选择算法以及它的相关研究情况。最后，介 绍了本文的主要研究内容。 1 1克隆选择算法概述 克隆选择算法最早是由d ec a s t r o 基于克隆选择原理提出的，并被应用于求 解优化问题和模式识别问题【2 】。本节首先简要介绍生物系统中的克隆选择机理， 然后重点介绍克隆选择算法的基本流程和研究现状。 1 1 1 克隆选择的生物机理 克隆免疫学说是b u r n e t 在1 9 5 9 年提出的 1 】。它的基本思想是，在免疫反应 过程中，那些能够识别抗原的细胞能进行大量增殖，并且这些细胞具有较高的存 活率。在免疫反应过程中，能够识别抗原的免疫细胞因为被激活而发生“超变异”， 从而产生大量相似的抗体。 1 1 2 克隆选择算法的流程 一般来说，克隆选择算法的过程可以分为如下五步【2 。 第一步：随机产生候选解，组成记忆细胞集m ，剩下的个体组成剩余群体p 。 第l 章绪论 第二步：基于个体的亲和度，确定群体中的c 个最佳个体。 第三步：克隆这c 个抗体，产生一个暂时的克隆群体。其中，一个抗体的亲 和度越高，那么它的克隆规模越大。 第四步：对克隆群体执行高变异算子，形成成熟的抗体群。其中，一个抗体 的亲和度越高，那么它的变异率越低。 第五步：从成熟的抗体群中选择抗体改进记忆集m 。在选择算子的作用下， 成熟抗体中的剩余个体替换集合p 中具有最低亲和度的抗体。 第六步：随机产生一部分个体来替换群体p 具有最低亲和度的抗体。这一策 略被称为元动力学策略，用来保持群体尸的多样性。 慰虢鼢辣貅一百 ，_ 。_ 一 。一 元勿鸲罅子l 图1 1 克隆选择算法一般流程 2 1 1 3 克隆选择算法的研究现状 克隆选择算法已经应用于很多领域，取得了一定的成果。当前克隆选择算法 主要是用来解决各种优化问题，例如全局优化 2 4 】，多目标优化【5 ，6 】，模式识 别【2 】，和现实世界中的优化问题 7 1 0 。 在克隆选择算法中，一个重要的算子是高变异算子。最近，o l i v e r t o 和他的同 2 匿兰；，尊一等， 第1 章绪论 事【ll 】研究了采用基于排序的变异算子( r a n k b a s e dm u t a t i o n ) 的进化算法 ( e v o l u t i o n a r ya l g o r i t h m s ：e a s ) 的时间复杂度，而且他们使用的基于排序的变 异算子实际上就是高变异算子的一种形式。因此，从这篇文章可知，高变异算子 在某些问题上确实比传统的变异算子有优势。 在克隆选择算法中，还有一个重要的算子是元动力算子。在文献【2 】中，d e c a s t r o 对元动力学算子给出了简单的经验上的使用方法。他建议，由元动力学算 子产生的新个体可以占整个种群的5 2 0 。但是，到目前为止，还没有关于元 动力学算子如何产生新个体的策略的专门研究。本文将就元动力学策略进行讨 论，提出了三种新的元动力学策略，并进行了实验验证。 1 2 进化非选择算法 进化非选择算法( e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m s ：e n s a s ) 是借 鉴生物系统中的免疫进化机制与免疫非选择机制而提出的算法，最初主要用于异 常检测【1 2 】。本节首先简要介绍了生物系统中的非选择机制，然后重点介绍进化 非选择算法的基本流程和研究现状。 1 2 1用于组合优化的进化非选择算法流程 进化非选择算法( e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i h t m s ：e n s a s ) 就是 包含有进化算子与非选择算子的算法。因为进化非选择算法既具有进化算法的自 适应和自学习能力，又能结合非选择算法的特性，因此它综合了两者的优势。进 化非选择算法用于组合优化类问题时的一般流程如图1 2 。其中进化算子操作可 以为重组、变异或两者的组合。 一般来说，进化非选择算法的算法流程如下： 第一步：随机产生个个体来组成初始化种群。开始时，把自我集置空值。 第二步：评估种群中每个个体的亲和度。如果满足终止条件，则e n s a 终止。 第三步：进化算子操作，对种群中的每个个体执行进化算子操作。 第三步：更新自我集，按照自我集更新策略更新自我集。 第五步：非选择算子操作，根据匹配规则，删除种群中满足和自我集中个体 相匹配的个体。 第六步：元动力学算子操作，随机产生新的个体，把它们加入到种群中，并 且以此保持种群的规模。 第七步：返回第三步。 3 第1 章绪论 图1 2 进化非选择算法一般流程 1 3 ，1 4 当前，己经有一些进化非选择算法用于组合优化问题的研究。文献【1 5 通过 在一些陷进函数上的实验比较，分析了进化非选择算法在函数优化问题中的性 能。对于设计的一些具有多个局部最优的陷进函数，与进化算法( e v o l u t i o n a r y a l g o r i t h m ：e a ) 相比，有非选择作用的进化非选择算法能够更好地跳出局部最 优解。文献【1 6 】提出了适用于移动机器人路径规划的进化非选择算法。该算法 1 6 】 主要通过非选择的作用，通过把差的个体加入到自我集中，以此来避免进化过程 中产生差的个体，达到加快算法收敛速度的目的。同时该算法也通过多样性控制 机制来防止种群“早熟收敛”。 1 2 2 进化非选择算法研究现状 当前己经有了一些关于进化非选择算法的理论工作。在文献【1 7 】中，分析了 一个简化过的用于异常检测的进化非选择算法的收敛性。许和他的同事【1 8 】分析 了进化非选择算法对异常检测的平均时间复杂度。但是，到目前为止，还没有关 于进化非选择算法在组合优化问题上的平均时间复杂度分析。而且，当前也没有 文献专门研究匹配闽值对进化非选择算法平均时间复杂度的影响。 当前分析进化非选择算法的理论工具主要是借鉴进化算法的平均时间复杂 度分析方法。概括来说，进化算法的平均时间复杂度的分析方法可以分成如下三 种。 1 概率方法。该方法由s t e f a nd r o s t e 等提出，并且他们利用该方法计算出 4 第1 章绪论 了进化算法在一些问题上的平均时间复杂度。 2 马尔可夫模型。h e 和y a o 通过利用马儿可夫模型得到了进化算法在很多 问题上的首次找到解的平均时间复杂度。 3 漂移分析。h e 和y a o 利用漂移分析模型计算出了进化算法在一类组合优 化问题上的平均时间复杂度。 1 3本论文的主要研究内容及组织安排 1 3 1 本文主要内容 在本文中，首先主要研究和讨论的是克隆选择算法中的元动力学算子。本 文提出了三种元动力学策略，并在四个组合优化问题上，检测这三种元动力学策 略的差别。由于传统的元动力学策略就是对二进制染色体中的每一位有相同的概 率生成0 或者l 。这种元动力学策略实际上服从二项分布。然而，对于有些问题， 事实上，该元动力学策略在该问题的全搜索空间中并没有真的起到均匀采样的作 用。例如，该问题的解与0 或者1 的个数有关，而与0 或者l 在二进制染色体中 的位置没有关系的时候。在这类问题上的实验结果表明，与传统的元动力学策 略相比，新提出的这三种元动力学策略会提高克隆选择算法的性能。 其次，本文分析了基于非选择算法的进化非选择算法在一个组合优化问题 上的平均时间复杂度。基于一个经典的组合优化问题，我们对比分析了，带有不 同的匹配阂值的进化非选择算法在该问题上的平均时间复杂度。理论结果表明， 有合适匹配阈值的进化非选择算法的性能优于传统的进化算法，也就是说，非选 择算子对算法的性能有重要的影响。另外，文中也进行了实验验证，实验结果也 和理论结果一致。因此，理论分析和实验结果这两方面都证明了，进化非选择算 法可以用于组合优化问题，并且可以取得很好的性能。而且，这些结果表明，非 选择算子对于提升进化类算法性能有重要作用 另外，本文还分析和讨论了进化非选择算法中的匹配阈值对于在该组合优化 问上的平均时间复杂度的影响。在这个组合优化问题上，匹配阈值在一定范围内 时，对算法的时间复杂度的影响不大。理论结果表明，合适的匹配阂值在常数范 围内变化时，进化非选择算法的性能仍然优于传统的进化算法；而不合适的匹配 闽值在常数范围内变化时，进化非选择算法的性能未必优于传统的进化算法。同 时，模拟实验结果也验证了理论结果。 5 第l 章绪论 1 3 2 本文的组织安排 本文其余各章的内容安排如下。 第二章从实验角度，讨论了不同元动力学策略对于克隆选择算法的性能的影 响。因此，本章提出了三种元动力学策略，并在四个组合优化问题上做了模拟实 验。实验结果也表明了，与传统元动力学策略相比，我们所提出的三种元动力学 策略可以很好的改进克隆选择算法在这一类问题上的性能。 第三章从理论分析和实验角度，针对进化非选择算法是否适用在组合优化问 题上作出了讨论。基于一个经典的组合优化问题，我们对比分析了，带有不同的 匹配阈值的进化非选择算法在该问题上的平均时间复杂度。结果表明，非选择算 子对于提升进化类算法有重要作用。 在第四章中，我们针对第三章中的匹配阈值问题作了进一步讨论。在第三章 中，有合适的匹配阈值的进化非选择算法的性能优于传统的进化算法。而当匹配 阈值不合适时，进化非选择算法的性能和传统的进化算法类似。于是，我们在这 一章中讨论和分析了，匹配阈值在一定常数范围内变化时，进化非选择算法的性 能会有怎样的变化。 第五章总结了全文工作，并提出了一些以后的工作方向。 6 第2 章克隆选择算法中元动力学算子的研究 第2 章克隆选择算法中元动力学算子的研究 在自然计算领域，人工免疫系统( a i s ) 【1 9 2 2 1 是个相对新的研究领域。 在人工免疫系统中，克隆选择算法( c s a s ) 作为一个兴起的算法，在近些年受 到了很多关注。克隆选择算法可以用于求解全局优化【2 4 】，多目标优化【5 ，6 1 ， 模式识别【2 】，和现实世界中的各种优化问题，例如蛋白质结构预测问题【8 】，文 本目标检测【1o 】，电磁优化问题【7 ，图像处理【9 ，压变换器【2 3 和机器人控制问 题 2 4 等问题。 对于克隆选择算法来说，元动力策略 2 】可以用来增加种群的多样性。作为 克隆选择算法中一个重要的算子，但是，元动力策略对克隆选择算法性能的影响 并没有受到太多关注。 事实上，元动力学策略是一种随机采样方法。通常来说，在二进制空间，对 于传统的元动力学策略，染色体中的每一个比特位以相同的概率被设置为0 和l 。 然而，对于一些问题来说，这种元动力学策略不能真正增加种群的多样性。因此， 为了研究不同元动力学策略对于克隆选择算法性能的影响，本章用实验测试比较 了四种不同的元动力学策略，包括传统的元动力学策略和其他三种本章提出的元 动力学策略的求解性能。实验结果表明，元动力学算子对克隆选择算法的性能有 很大的影响。 本章其余部分包括以下内容。第2 1 节介绍了些相关工作，主要是一个克 隆选择算法的简单描述，以及该算法用到的有关算子。第2 2 节给出了四种不同 的元动力学策略，其中包括传统的元动力学策略和其他三种新的元动力学策略。 在第2 3 节，在四个欺骗函数上进行了一些模拟实验，以此来比较没有元动力学 策略的克隆选择算法和其他四个包含有不同元动力学策略的克隆选择算法的求 解性能。在第2 4 节，给出了一些讨论。特别地，通过在一个节点覆盖问题上的 实验，研究了本章中元动力学策略的局限性。在第2 5 节，给出了本章的小结。 2 1 相关工作 克隆选择算法的变种有很多【2 ，3 ，7 9 】。基于d ec a s t r o 等在文献【2 】中提出的 克隆选择算法，本章中所采用的克隆选择算法的框架在图2 1 中给出。 应当注意的是，文献【2 】中的克隆选择算法包含了记忆集。但是，正如图2 1 所示，为了突出不同元动力学策略的影响，本章采用的是简化的，不包含记忆集 的克隆选择算法。 7 第2 章克隆选择算法中元动力学算子的研究 初始化：随机产生 价个体来组成初始种群以，k = 0 。 评估：评估每个个体的亲和度。 如满足终止条件，算法结束。 克隆选择和增殖：从种群以中，选择最好的c 个个体。克隆这些个体， 以此组成一个中间种群占。+ f 。其中，亲和度越高，克隆比例越高。 高变异：对中间种群 + c 中的每一个个体执行变异操作，并由此生成另 一个中间种群岛+ 吖。一般来说，亲和度越高，变异概率越低。 评估：评估中间种群岛。中所有个体的亲和度。 选择：从( 文+ 巳+ 吖) 中选择个个体来产生下一个种群毛+ 。，其中 ( 吼+ + 盯) 中的最好个体以概率l 保留下来，而其他( 一1 ) 个个体被选择 的概率跟它们的亲和度成比例。 元动力学算子操作：替换瓯+ 。中部分亲和度最低的个体，替换的比例为 只。 k = k + l 。如果终止条件满足，算法结束。否则，回到第2 步。 图2 1 本文使用的克隆选择算法的基本流程 尽管在不同的应用中 2 1 0 ，2 3 - 2 5 ，克隆选择算法有多种多样的克隆选择和 增殖算子，但基本的规则却是一样的。换句话说，一个个体的亲和度越高，那么 它的克隆数目就会越多【2 】。在本章中，克隆算子的定义如下。 ( 1 ) 所有的个个体按照亲和度从高到低降序排列。 ( 2 ) 第一个个体克隆次；第二个个体克隆( n - 1 ) 次，以此类推。 因此，所有个体的克隆数目为 c ：1 - n ( n + 1 ) 。 2 7。 尽管在不同克隆选择算法中【2 1 0 ，2 3 2 5 ，存在很多不同的高变异算子，但 是这些算子都遵守同样的基本原则。也就是说，一个个体的亲和度越高，那么它 的变异概率就越低【2 】。在本章中，为了方便，在模拟实验中采用了文章【2 6 】的高 变异算子。因此，首先把气+ c 中的所有个体按亲和度的高低升序排序，然后第i 个个体的变异概率尸通过下面的公式( 2 1 ) 计算得至1 j 2 6 。 只= 研“一玉i 幸( i - 1 ) ，i = 1 ，2 ，c 。 ( 2 1 ) 其中，r = 型并且钟佃= 土。 在克隆选择算法中，为了保持种群的多样性，经常会采用元动力学算子，即 用随机产生的一些新个体去替换乞n 个有最小亲和度的个体 2 】。在本章中，设 定弓= 1 0 。 通常，元动力学算子对染色体中每一个比特生成0 或者1 的概率是相等的。 目前，在克隆选择算法中广泛的使用就是这种元动力学算子。但是，对于某些问 题来说，实际上这种算子不能提高种群的多样性。值得指出的是，不同元动力学 8 l 2 3 4 5 6 7 第2 章克隆选择算法中元动力学算子的研究 策略对于克隆选择算法的性能的影响并没有受到太多关注。因此，本章将对元动 力学策略进行了一些研宄。 2 2 元动力学策略 本节主要介绍了四种不同的元动力学策略。第一种是传统的元动力学策略， 其余三种是本章提出的元动力学策略。 在介绍具体的元动力学策略之前，先给出一些符号表示。 ( 1 ) x = ( 毛) ，s ， 0 , i ，表示一个个体，其中表示问题规模。 ( 2 ) x = 五，屯，) ，表示种群，其中表示种群大小。 ( 3 ) p r 0 埘】是一个数组，其中p r i ( 0 i 玎) 表示新产生的个体共有i 位为l 的概率为p r i 。 其次，四种不同的策略的伪代码分别在图2 2 到图2 4 中给出。这些策略分 别被命名为m d s 1 ，m d s 2 ，m d s 3 和m d s 4 。 传统的元动力学策略：m d s 1 l f o r 卢lt ob n 2 p r o b a b i l i t y = 0 5 3 f o r j = lt o7 4 i f ( r a n d o m ( 0 ，1 ) p r o b a b i l i t y ) 5 x j j 】= l 6e l s e 7 x , f j 】_ 0 8 9 1 0 用这些新产生的个体替换具有最低亲和度的那些个体 图2 2 传统的元动力学策略 图2 2 给出了克隆选择算法中传统的元动力算子，即m d s 1 。在各种克隆选 择算法中，最经常使用的就是m d s 1 ，如【2 】中的元动力学策略。通常来说，很 多进化算法生成初始种群中的个体时也采用这种策略 2 7 ，2 8 1 。 m d s 1 对二进制染色体中的每一位都是以相同的概率即0 5 来产生0 或者。 ，、1 因此，对于m d s l 来说，p r i = f ! l ( 去) “，0 j ，。 l z 在本章中，所用的初始种群采用m d s 一1 来生成。 图2 3 中给出了m d s 2 。从图2 3 中可以看出，对每个新生成的个体 而= ( 而矗) ，1 i 乞n ，它的每一位5 ，( 1 - ，门) 都以相同的概率置为1 ，并且这个 概率是随机产生的。 对于m d s 2 来说，当由m d s 2 产生个体的数目足够大的时候， 9 第2 章 克隆选择算法中元动力学算子的研究 p 玎妇。三，o f 疗。 仃 第二个元动力学策略：m d s 2 1 f o ri2lt o 只 2 p r o b a b i l i t y = u n i f o r m r a n d o m ( 0 ，1 ) 3 f o r j = lt on 4 i f ( r a n d o m ( o ，1 ) p r o b a b i l i t y ) 5 “，】= l 6e l s e 7 【刀= 0 8 ) 9 1 0 用这些新产生的个体替换最低亲和度的个体 图2 3 第二个元动力学策略 在图2 4 中给出是m d s 3 。用m d s 3 可以产生不同数目的1 ，并且产生 不同数目的l 的概率是不相等的。在m d s 3 中，首先用公式( 2 2 ) 产生一 个辅助的临时数组t e m p 0 朋】。 t e m p i = 1 5 一l 三一0 5 1 ，o i n 。 ( 2 2 ) 刀 然后，数组p r i ( 0 i 刀) 可以通过公式( 2 3 ) 产生。 p r i 】- 塑趔：! ：! 二! 型竺二型。 t e m p j 1 5 一i j n 一0 5 l j = oj * o ( 2 3 ) 从公式( 2 3 ) 可以得出，在m d s 3 中，新产生的个体有总共n 2 个l 的 概率是最大的。 从图2 4 中可以观察到，首先基于概率数组p r o 埘】，一个随机数字广从 0 ，n 】 中通过赌轮法选择得到。然后，从 1 ，玎】中随机选出来，个整数组成集合尺。最后， 对于将要产生的个体，如果，r ( 0 j 刀) ，s ，= 1 ；否则s ，= 0 。 对于m d s 4 来说，除了概率数组p r o 埘】不同外，其他的都和m d s 一3 一样。 因此，对于m d s 4 来说，下面仅需给出概率数组p r 0 n 】的产生公式。 在m d s 一4 中，一个辅助的临时数组t e m p n + 1 用来帮助设定p r i ( o ，厅) ， 并且数组t e m p n + 1 基于下面的公式( 2 4 ) 产生。 t e m p i 】= l ( 1 一二) + l ，0 i 刀 ( 2 4 ) 那么，对于概率数组p r o n 】来说，可以通过下面的公式( 2 5 ) 产生。 p r 【壮# 盟：娑 ( 2 5 ) 丢伧m p 【力丢打钞，；0，= o 1 0 第2 章克隆选择算法中元动力学算子的研究 第三个元动力学策略：m d s 3 l f o r 卢lt o 只n 2 p r o b a b i l i t y = u n i f o r m r a n d o m ( 0 ，1 ) 3i fp r o b a b i l i t y p r 0 】 r = 0 e l s e i f p r o b a b i l i t y l ip r 【j 】，p r 【j 】l ( o 1 3 用这些新产生的个体替换最低亲和度的个体 图z 4 第三个元动力学策略 在下面的2 3 小节中，基于这四种元动力学策略，五种不同的克隆选择算法 在四个不同的组合优化问题上进行了实验测试。其中这五个克隆算作算法包括没 有元动力学算子的克隆选择算法和其他四种分别包含元动力学策略m d s 1 ， m d s 2 ，m d s 3 和m d s 4 的克隆选择算法。 这五种克隆选择算法除了元动力学算子外，其他算子都一样。 c s a 1 ：它不包含元动力学算子。 c s a 2 ：它采用了元动力学策略m d s 1 。 c s a 3 ：它采用了元动力学策略m d s 2 。 c s a 4 ：它采用了元动力学策略m d s 3 。 c s a 5 ：它采用了元动力学策略m d s 4 。 2 3 实验结果及分析 本节在不同问题上用实验来比较五种不同的克隆选择算法的性能，其中这五 种克隆算作算法分别是没有元动力学算子的克隆选择算法和其他四种分别包含 原动力学策略m d s 1 ，m d s 2 ，m d s 一3 和m d s 一4 的克隆选择算法。 在所有试验中，对不同的克隆