（计算数学专业论文）混合免疫算法及其应用研究.pdf

摘要 摘要 免疫算法( i m m u n e a l g o r i t h m ) 是将生物免疫系统的概念及 理论移植于传统的遗传算法而形成的一类进化算法，其构造简 单，在一定条件下具有全局收敛性，在最优化问题、计算机安全 等众多领域得到了广泛的应用。由于使用随机搜索技术，在保证 算法全局收敛性的同时，其局部寻优的性能往往受到损害，且收 敛速度也不理想。传统的优化方法充分利用了目标问题的信息， 局部寻优能力较强，收敛速度较快，但又会陷入局部最优的陷阱。 可以说，免疫算法提供了全局性的点搜索方法，而传统优化方法 则提供了局部性的面搜索方法，两类方法各有利弊。将这两类方 法有机结合起来，迭代当中先将免疫算法的变异操作作用于前一 代的解，再用传统优化方法搜索该解附近的局部最优解，就可以 点面结合进行搜索，使得这两种方法互为补充。这种算法称为混 合免疫算法( h y b r i di m m u n ea l g o r i t h m ，i i i a ) 。本文针对t s p 问题，将标准免疫算法与改良圈算法、贪婪算法、拟贪婪算法结 合，构造了一种混合免疫算法。使用m a f l a b 实现该算法并对随 机生成的数据进行验证，与单纯使用免疫算法或传统优化方法比 较，可见混合免疫算法的表现令人满意。 关键词：免疫算法( i a )混合免疫算法( i l i a ) t s p 问题 贪婪算法拟贪婪算法改良圈算法 a b s t r a ( 丁 h y b r i di m m u n ea l g o r i t h ma n di t sa p p l i c a t i o ni ns o l v i n gt s p p r o b l e m w a n g l i a l l i d i r e c t e db yx i 赡z h i d o n g d e p t o f m a t h ，n o r t h w e s tu n i v e r s i t y ，x i a 7 1 0 0 6 9 i m m u n ea l g o r i t h m0 a ) i s & n e w l yc o n s t r u c t e de v o i n f i o na l g o r i t h m ( e a ) b y t r a n s p l a n t i n gt h ec o n c e p t sa n dt h e o r yo fb i o l o g i c a li m m u n es y s t e mi n t og e n e t i ca l g o r i t h m i a i se a s yt oc o n s t m c 【，h a sg l o b a lc o n v e r g e n c e 。i th a sb e e nw i d e l ya p p l i e di nm a n y a r e a ss u c ha so p t i m i z a t i o n , c o m p u t e rs e c u r i t y b yu s i n gr a n d o ms e a r c h i n gm e t h o d ，1 a g u a r a n t e e si t sg l o b a lc o n v e r g e n c e ，b u ta tt h e 鞠l n ct i m e ，地a b i l i t yo ff i n d i n gl o c a lo p t i m a l i sa f f e c t e d a n dt h ec o n v e r g e n c es p e e do fni sn o ts a t i s f i e d t r a d i t i o n a lo p t i m i z a t i o n m e t h o d su s em u c hm o r e ：i n f o r m a t i u no ft h et a r g e tp r o b l e m , s ot h e i rc o n v e r g e n c es p e e di s m u c hb e t t e r , a n dt h ea b i l i t yo ff i n d i n gl o c a lo p t i m a li sb e t t e r i as u p p l i e su sag l o b a lp o i n t s e a r c h i n gt e c h n i q u e ，a n dt r a d i t i o n a lo p t i m i z a t i o nm e t h o d ss u p p l yu s al o c a ls u r f a c e s e a r c h i n gt e c h n i q u e b yc o m b i n i n gt h e s et w ot y p e so fm e t h o d s ，w eg e ts oc a l l e dh y b r i d i m m u n ea l g o r i t h m 阻1 a ) i th a sg l o b a ls u r f a c es e a r c h i n ga b i l i t y i nt h i st h e s i s ，r e s e a r c h o ni a e s p e c i a l l yh i a , i sr e v i e w e da tf i r s t , a n da l lh 1 ai sc o n s t r u c t e dt os o l v et s pp r o b l e m b yc o m b i n i n gg r e e d ya l g o r i t h m ，s e m i - g r e e d ya l g o r i t h m , a n da m e n d m e n t - c i r c l ea l g o r i t h m 谢山1 a r e a l i z i n gt h i sa l g o r i t h mw i t hm a t l a b a n ds o l v i n gr a n d o m l yg e n e r a t e dt s p e x a m p l e sb yi t t h en s u l tg a i n e di sq u i t es a t i s f i e dc o m p a r e dw i l hi aa n do t h e rt r a d i t i o n a l o p t i m i z a t i u nm e t h o d s k e y w o r d s ：i u l i n u n ea l g o r i t h m ，h y b r i di m m u n ea l g o r i t h m ，t s pp r o b l e m ， g r e e d y a l g o f i t h m ，s e m i - g r e e d y a l g o r i t h m ，a m e n d m e n t - c i r c l e a l g o r i t h m h i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属于西北大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版。本入允许论文被查阅和 借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时，本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作 者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名： 圣基麴指导教师签名： 堋y 年月牛日年 月 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 本论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西 北大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：王海莉 3 口心年占月牟日 免疫算法与混台免疫算法 第一章免疫算法与混合免疫算法 免疫算法( 1 m m u n ca l g o r i t h m ) 是将生物免疫系统的概念与理论移植于遗传算法而形成 的一类新的进化算法。自然免疫系统提供了一个自下而上进化策略的范例，从而成为人工 智能的一个模仿对象，这就构成了免疫算法的生物学基础。 1 1 免疫算法的生物学基础 免疫算法的生物学基础是自然免疫系统 1 1 。从信息系统的角度来看，免疫系统( i m m u n e s y s t e m ，i s ) 可以视为阀题学习解决系统。当外来抗原侵入机体时。免疫系统需要对其做 出反应，产生适当的抗体来对抗该抗原。这里的抗原相当于待求解问题( 目标问题) ，抗体 相当于产生的解。最初，备选解的质量是相当低劣的，但经过多代的选择、进化过程，最 终可以得到优秀的解。 以下介绍自然免疫系统。 免疫系统是由具有免疫功能的器官、组织、细胞和分子组成的解剖和生理网络组成的。 生物体的免疫系统分为先天性免疫系统和适应性免疫系统，前者与生俱来，可以识别侵入 体内的各种微生物；后者是后天形成的，也称获得性免疫，是由免疫系统中淋巴细胞受病 原体( 抗原) 的刺激、诱导后而形成的。淋巴细胞主要有b 细胞和t 细胞 1 】。 圜1 1 自然免疫系统示意圈 第一章免疫算法与混合免疫算法 免疫算法是通过对适应性免疫系统的模仿产生的。 在适应性免疫系统中，主要由两种免疫机制：体液免疫( h u m o r a lr e s p o n s e ) 和细胞免 疫( c e l l u l a rr e s p o n s e ) 。在体液免疫中，用于取代抗原( a n t i g e n a g ) 的抗体( a n t i b o d y _ a b ) 由b 细胞产生，b 细胞同时又由抗原和t 细胞催化产生；在细胞免疫中，k 型t 细胞包 围细菌或被病毒感染的细胞，将其杀死，这些k 型t 细胞又由抗原和其它的t 细胞催化 产生。t 细胞在这两种免疫机制中都起到主要作用。 圈1 1 反映了细胞免疫和体液免疫之间的关系，以及抗原( a g ) 、抗体( a b ) 、b 细 胞( b ) 、辅助t 细胞( t h ) 和抑制t 细胞( 砧) 之间的反应，体现了免疫反馈机制原理。 由图1 1 可见，抗原进入机体并经周围细胞消化后，将信息传递给t 细胞，即t h 细胞和 t s 细胞，b 细胞用于抑制t h 细胞的产生，然后共同刺激b 细胞，经过一段时间后，b 细胞产生抗体以清除抗原。当抗原较多时，机体内的t h 细胞也较多，而t s 细胞较少，从 而产生的b 细胞会多些。随着抗原的减少，体内弧细胞增多，它抑制了t h 细胞的产生， 则b 细胞也随之减少。经过一段时间后，免疫反馈系统便趋于平衡。 与生物进化原理相似，免疫系统中也存在着进化现象【2 】。免疫系统中有大量带有独 特受体( 形状) 的b 细胞，所有可能受体的集合称为形状空间。b 细胞对与之形状互补 的抗原具有较强的抗性，可以产生抗体将其消灭。当抗原侵入生物体时，与入侵抗原形状 互补程度大的b 细胞和入侵抗原之间亲和力高，从而更易结合。b 细胞群体通过如下进 化过程产生抗体以消灭抗原【3 】： 1 ) 选出与入侵抗原亲和力高的b 细胞。 2 ) 在辅助t 细胞的作用下，被选中的b 细胞分裂增生，产生大量子b 细胞。这一 过程称为克隆扩增( c l o n a le x p a n s i o n ) 。子b 细胞受体形状在母细胞的基础上发生微小变异， 即发生超突变( h y p e r m u t a t i o n ) 。b 细胞通过克隆扩增在其小邻域内产生大量子b 细胞，以 在局部范围内搜索亲和力更高的b 细胞。 3 ) 一些亲和力低的予b 细胞删除其受体并生成新受体，即受体修饰( r e c e p t o r e d i t i n g ) 。受体修饰使得子b 细胞在形状空间中可能突变为离母b 细胞较远的点，这样可 以在全局范围内搜索亲和力更高的b 细胞。亲和力更低的部分子b 细胞死亡，由骨髓产 生部分新b 细胞以维持b 细胞群体的多样性。 4 ) 经过若干代的选择、克隆扩增、受体修饰和骨髓产生新b 细胞的过程，最终产 生了亲和力很高的b 细胞，产生大量有效的抗体以消灭抗原。 第一章免疫算法与棍台免疫算法 1 2 遗传算法简介 遗传算法( g e n e t i ca l g o d t h m ，g a ) 属于进化算法( e v o l u t i o na l g o r i t h m ，e a ) ，最初 由美国m i c h i g a n 大学的h o l l a n d 教授提出基本概念，首篇论文于1 9 7 5 年发表f 4 】，现已获得 了广泛的实际应用。 一般进化算法【5 】的基本思想是：从问题可行解集的一个子集即初始种群( p o p u l a t i o n ) 开始，按照适者生存和优胜劣汰的原理，逐代进化产生越来越好的可行解予集，或者说种 群。若其中的进化过程为基因的交叉( c r o m o v e r ) 和变异( m u t a t i o n ) ，则称之为遗传算法。 这里，种群由经过基因( g e n e ) 编码( e o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组成， 而个体就是带有染色体( c h r o m o s o m e ) 特征的实体。染色体是遗传物质的主要载体，其内 部表现为某种基因组合，决定个体的的外部表现。 应用g a 解决具体问题时，首先要根据问题的特点，选择适当的基因编码方式，建立 适当的亲和力函数。这里所谓的基因编码方式，也就是数据结构，即如何表达问题的可行 解( 个体) 。而亲和力函数则用以描述可行解( 个体) 的品质好坏，也称为适应度函数。 适应度越高，个体的品质越好。寻找适应度最高的个体的过程也就是解题的过程。其次， 要构造适当的交叉算子和变异算子。g a 不同于实际的生物进化过程，生物学中的交叉和 变异在这里没有明确的对应物。所谓交叉算予，就是从已有的两个可行解出发，构造两个 新的可行解的过程：所谓变异算子，就是从已有的一个可行解出发，构造个与之具有一 定相似性的新的可行解的过程。交叉算子和变异算子均需要有一定的控制参数。再次， g a 解题的过程是一个迭代的过程，因此需要确定一个迭代终止的条件。个简单的方法 是事先指定最大迭代代数g ，当迭代过程进行g 代之后即自动终止。但对g 的选择不可 避免的存在随意性。种群的规模，即种群中包含个体的数量，n ，也需要事先指定。同样， 这也具有某种随意性。最后，确定个体的选择机制，即如何从当前种群中选择一些个体用 于构造下一代种群。通常来说，这是要规定一组选择概率。 选择概率的确定可以有多种 不同的方式，即可以根据个体适应度的排序确定，也可以根据个体适应度的数值确定。 g a 计算的基本步骤为： s t e p l ：产生初始种群： s t e p 2 ：当迭代终止条件不满足时： 计算当前种群个体的适应度； 第一章免在算法与混合免疫算法 根据适应度选择个体： s t e p 3 ：复制被选中的个体： s t e p 4 ：执行交叉操作和变异操作； s t e p 5 ：个体替换，将所得到的新个体集合视为当前种群； s t e p 6 ：若满足中止条件，将当前种群中的最优个体作为问题的近似解 否则，转到s t e p 2 。 遗传算法提供了一种求解复杂系统优化问题的通用框架，不依赖于问题的具体特点， 有很强的鲁棒性，所以被广泛应用于很多学科，如函数优化、组合优化、生产调度问题、 自动控制、机器人智能控制、图像处理与模式识别等。 遗传算法本身尚存在一些不足之处。从理论上分析，在保留上一代最佳个体的前提下， 遗传算法是全局收敛的，但在用g a 处理实际复杂问题时，往往出现未成熟收敛现象，只 能得到局部最优解；g a 的局部搜索能力较差；g a 的参数设置复杂，随意性强；g a 对初 始条件较为敏感，缺乏必要的稳定性。尽管针对g a 的改进工作很多【6 】【7 】，但大多是经验 的方法，算法的改进依赖于个人技巧，难以建立统一的指导性的数学模型。 1 3 免疫进化算法 模仿生物免疫系统的进化原理，可以构造免疫进化算法。与自然免疫系统不同的是， 在免疫进化算法当中，直接将可行解作为个体，而目标函数值也直接作为个体的适应度( 对 最大化问题如此：对最小化问题，将目标函数值的倒数作为个体的适应度) 。 本节介绍目前应用较多的两种免疫进化算法：自适应免疫进化算法【8 】和基于抗体浓度 调节的免疫进化算法【9 】。 1 自适应免疫进化算法 简单模拟生物免疫系统的适应性免疫应答过程，可得到自适应免疫进化算法。这里， 需要设定一组控制参数，包括n ，种群规模；g ，最大迭代次数：口，选择概率：芦，淘 汰概率：y ，记忆概率；，扩展半径；r 。突变半径。 自适应免疫进化算法的基本步骤为： s t e p l ：产生初始种群。随机产生甩个个体组成初始种群a 。初始化迭代次数计数 嚣k = 0 。 s t e p 2 ：当迭代次数小于g 时，计算当前种群4 中每个个体的适应度，从中选择适 4 第一章免疫算法与混台免疫算法 应度最高的【n a l 个个体组成群体嘎。自适应调节算法控制参数。 s t e p 3 ：扩展操作。对群体甄中的每一个个体构造其半径为，的小邻域，在其中随 机产生若干新个体，组成群体c 。 s t e p 4 ：计算群体q 中每个个体的适应度。 s t e p 5 ：突变操作。对群体c k 中适应度最低的n 一 h a 】个个体，分别构造半径为r 的 大邻域，在其中随机产生一个个体。用新产生的这露一f 尼口】个个体和群体q 中适 应度最高的 n a l 个个体组成群体巩。 s t e p 6 ：计算群体巩中每个个体的适应度。 s t e p 7 ：替换操作。将群体皿中适应度最低的【撑，】个个体淘汰，用随机产生的个体 替代。如此形成群体b 。 s t e p 8 ：计算群体b 中每个个体的适应度。 s t e p 9 ：最优个体保留。将群体也中适应度最低的m r 】个个体替换为4 中适应度最 高的【 】个个体。令k = k + l ，转s t e p 2 。 在适应性免疫应答中，b 细胞与抗原的亲和力越高，其分裂产生的子b 细胞越多。模 拟这一现象，用正比选择法确定群体巩中每个个体扩展产生新个体的数量。设毋中有小个 个体，分别为时。v ：，t ，其适应度分别为五，2 ，无。在每一次扩展操作时，令第f 个 个体产生新个体的概率为： p 。，f 荟 江坛朋 累积概率为 吼= p ， i = 1 令a 0 。在【o ，1 上产生一个均匀分布的随机数1 ，。若吼一。s w 弓吼，则对y ，进行扩展操 作，产生一个新个体。如此重复n 次，即可得到 个新个体。由于优秀个体被选中进行扩展 操作的概率较大，因此产生的新个体数较多，对其邻域的搜索也就越细。 用自适应免疫算法进行优化计算，如果扩展半径和突变半径较大，可保持群体多样性， 但群体收敛缓慢：如果扩展半径和突变半径较小，算法可快速收敛，但群体多样性减小很 快，算法容易陷入局部最优。因此，算法快速收敛和保持群体多样性具有矛盾性。 5 第一章免疫算法与混台免疫算法 当群体多样性较小时，个体均集中在可行解集合的较小范围内，算法接近局部或全局 最优。此时将扩展半径和突变半径增大，可以使个体在解空间更广阔的范围内变异，增大 群体的多样性，避免陷入局部最优。与此同时，减小选择概率，使群体玩中被选中的较 优个体产生更多新个体，这样扩展半径的增大就不至于减弱算法的局部搜索能力。而当群 体多样性较大时，群体正在进化中，与前述情形相反，扩展和突变半径应较小，选择概率 则应大一些。 因此，如果算法参数根据群体的多样性自动调节，则算法不仅能快速收敛，而且能保 持群体多样性以避免陷入局部最优解。 为可操作性起见，定义群体间的多样度为群体中全体个体间的平均距离，并以此调节 算法控制参数。假设第k 时代中群体风包含m 个个体咭，v ：，：，则这些个体间的平均 距离为 d 忙- = 芒x d o ：，时) ， m ( m 一1 ) 白盘“ 群体巩的多样度定义为 d ( ) 。p 婶肛。，孑耻d 。， i , e s e 其中d 。为给定常数。第k 代时的算法参数按下式进行调节： 口仆) 一+ r d ( ”， ，一，o + 坼( 1 一d ) ， r - r + ( 1 一d ) ， 其中：口”、r “、r 分别为第k 代的选择概率、扩展半径和突变半径；口0 、r o 、r 分别为相应参数的最小值；吼、仉、分别为相应参数的调节范围。 2 基于浓度调节的免疫进化算法 生物免疫系统当中还存在一种特殊的浓度调节机制。简单的说，在克隆扩增过程当中， 高浓度的b 细胞会受到一定程度的抑制作用，而低浓度的b 细胞则会受到促进。浓度调节 机制有利于维持免疫细胞群体的多样性，避免早熟现象，利于在全局范围内进行最优个体 的搜索。 将生物免疫系统的浓度调节机制引入免疫进化算法，则得到基于浓度调节豹免疫进化 算法。 第一章免疫算法与混合免疫算法 假设第k 时代中群体巩包含m 个个体v ：，y ：，v ：，则定义其中第i 个个体到其他个体 的距离为 d p 沪善毗v 定义该个体处的浓度为 p 以) 2 丽1 。 对自适应免疫进化算法中的扩展操作加以调整，可以将生物免疫系统的浓度调节机制 引入免疫进化算法。具体方式为：首先计算群体喀中每个个体的浓度值p ) ，i 。l 2 ，历。 再计算每个个体被选择进行扩展操作的概率，) 。善盟。算法的其它部分与自适应免 善p 钟 疫进化算法相同，这里不再赘述。 在自适应免疫进化算法和基于浓度调节的免疫进化算法当中，均需要用到个体之间的 距离。对于个体对应于多维欧氏空间中点的情形，取欧氏距离作为个体之间距离即可：对 于离散优化问题，个体之间不存在类似的距离概念，这时可以变通地采用个体适应度之间 的距离替代个体之间的距离。 对算法的终止条件作了一个简单的处理，即指定最大迭代次数，当迭代次数达到最大 迭代次数时终止。应该说这是一个比较无奈的选择，原因与遗传算法相同。 免疫进化算法与遗传算法形式上非常相似【1 0 】。均属于并行随机优化方法，在初始解的 产生，编码，个体评价等方面的操作基本一致，也都进行选择操作和变异操作。但是这两 类方法的生物学原型不同，遗传算法是对生物有性繁殖方式的模拟，而免疫进化算法则是 对生物免疫系统无性繁殖方式的模拟，使用的术语也就有所差别。 这里介绍的免疫进化算法只是一个基本的框架，需要针对目标问题的具体特点，定义 个体的数据结构，距离，适应度函数，扩展操作及突变操作等，才能付诸实用。 1 4 免疫进化算法的应用 免疫进化算法虽然诞生时间不长，但已经在很多领域得以应用。 第一章免疫算法与混合免疫算法 传统函数优化方法在用于求解复杂问题时，为克服计算量过大的问题，常常会限制列 搜索空间全面仔细地搜索，因此往往只能得到局部最优解或次优解。作为进化算法的一种， 免疫进化算法在搜索全局最优解方面的鲁棒性使其在解决这类优化问题方面潜力巨大。特 别是对于具有非线性、非凸性的复杂优化问题，免疫算法的作用尤为明显1 1 0 。 同时，在组合优化领域。免疫算法也发挥了日益重要的作用。如文献【1 1 】中即将免疫算 法用于图的染色问题。这是由于组合优化以及相近的排列优化问题均属于离散优化问题， 可行解的数量随问题规模增长非常快，靠穷举法搜索的计算量过于庞大，而这类问题又没 有函数优化问题中极值点的必要性条件等可供借鉴。本文的第三章也将免疫算法应用于排 列优化中的t s p 问题，收到了满意的效果。 在人工智能的些新领域当中，免疫算法的作用也日益明显。例如，j u h eg r e e n s m i t h 等将免疫算法用于有限文档分类问题 1 2 1 ，j o nt i m m i s 和t h o m a sk n i g h t 则将免疫算法用于 数据挖掘问题 1 3 ，h u n tj e 和c o o k ed e 将免疫算法用于学习系统 1 4 。 计算机安全是免疫算法另一个重要的应用领域。计算机系统本身如同一个生物体，通 过互联网等渠道与外部沟通的同时，也将自身暴露于形形色色的外来攻击面前。如何防范 外来攻击( 病毒防治、黑客入侵检测等) ，保护自身安全，就成为计算机安全的重要课题。 这一问题与生物体所面对的免疫防护问题是一致的。因此，计算机安全成为免疫算法天然 的应用对象，锝到了研究者的高度重视 1 5 。 1 5 混合免疫算法 尽管免疫算法已经在众多领域发挥作用，但与遗传算法类似，其随机搜索机制在保证 算法全局收敛性的同时，也导致算法收敛速度较慢，且局部寻优能力不强。这是免疫算法 这样构造简单较少考虑目标问题具体特点，信息利用不充分的算法的共同的缺点，也是 无法避免的代价。 传统的优化方法，如最速下降法、牛顿法、共轭梯度法等，对目标问题的具体特点考 虑较多，充分利用目标问题的信息，因此局部寻优能力较强，收敛速度也比较快。对于性 质较好的问题，这类优化方法方便，快捷，有效；但对于局部最优解大量存在的复杂问题， 传统优化方法往往难以避免陷入局部最优解的问题。 将以随机搜索为特点，具有全局搜索能力的新优化方法与传统优化方法相结合，构造 混合优化方法，可以对这两类方法取长补短，优势互补，形成更为有效的优化方法。 第一章免疫算法与混台免疫算法 目前，将遗传算法与传统优化方法相结合而构造的混合遗传算法( t t y b r i dg e n e t i c a l g o r i t h m ，h g a ) 已经得到了众多研究者的关注【1 6 】【1 7 】。 同样，将免疫算法与传统局部优化方法相结合，可以构造出混合免疫算法( h y b r i d i m m u n e a l g o r i t h m ，h i a ) 。 具体来说，首先针对目标问题，选择适当的局部优化方法，构造局部优化算子。例如， 在函数优化问题当中，可以使用最速下降法、牛顿法或共轭梯度法等经典算法作为局部优 化算子。其次，在原有的免疫算法当中在每一次迭代过程当中，进行变异操作之后，将 局部优化算子作用于所得个体，搜索该个体附近的局部最优个体，用这些局部最优个体形 成中间代种群。这时再结合人工免疫系统的记忆机制将中间代种群与记忆单元当中存储 的较优个体合并，重建记忆单元，同时形成下一代种群。 由于免疫算法发展相对较晚，目前的研究重点还处在开拓其应用领域方面，对混合免 疫算法的研究尚不多见。如文献【1 1 】。 9 免疫算法的收敛性分析 第二章免疫算法的收敛性分析 2 1 免疫算法的收敛性 本节讨论两类免疫算法，即自适应免疫算法和基于浓度调节的免疫算法的收敛性。 1 自适应免疫算法的收敛性 利用概率分析方法 1 8 1 ，可以证明免疫算法依概率收敛到全局最优解。 考虑优化问题 m a x f ：s _ r ( 2 1 ) 其中f 为评价两数，s 为搜索空间。设e 为s 上的波莱尔域，其l e b e s g u e s 测度珊( ) 满 足m ( s ) 一1 ，故p ( s ，玩，小) 构成一个概率空间。 参考文献【1 8 】，对免疫算法的收敛性定义如下： 定义2 1 设第k 代群体中最优个体的评价值为 ，全局最优个体的评价值为，+ ，若 随机序列 噍。f 一 ) 依概率收敛于0 ，则称自适应免疫算法收敛于全局最大值，。 定理2 1 设优化问题( 2 1 ) 满足： 1 全局最大值，。1 警，o ) 存在； 2 v 。，0 ，设m 一 工e s l f ( 上) 苫f 一暑) ，则m ( 皿) 0 。 则自适应免疫算法收敛于函数优化问题( 2 1 ) 的全局最大值，。 证明考虑对群体珥中评价值最低的l 个个体进行替换操作，其中任一个体石被替换 为s 中的随机元素善。对于v f 0 ，有时s ，故 p ( x 。e m ，) 一m ( m 。) m ( s ) = m ( 丝) ) 0 ( 2 2 ) , - g t r 。令埘( f t ) 一d ，则个体j 经替换操作后进入m 。的概率为6 。因此，n 中评价值最 低的l 个个体经替换操作未产生进入 f 的个体的概率为 只。= ( 1 一d ) ( 2 3 ) 在前k 代中共进行k 次替换操作，因此在前k 代替换操作中未产生皿中个体的概率为 1 0 免疫算法的收敛性分析 ) 。i ：l 。( 1 - 6 ) “ ( 2 4 ) 由于在前k 代中可能存在通过扩展或突变操作而进入m 。但没有被替换的个体，并被最 优个体保留策略所保留，放 p ( 畋 b ) s 只。 ) ( 2 5 ) 由于6 ，0 ，由式( 2 4 ) 有 熙气 ) 。恕( 1 一d 严1 0 由式( 2 5 ) 和( 2 6 ) 有 熙p 佩，) 。腮o ) 1 0 故算法收敛。 条件1 ) 是理所当然的。对于不满足条件2 ) 的评价函数 困难的。因此，对，的假设条件是合理的【1 9 】。 2 基于浓度调节的免疫算法的收敛性 ( 2 6 ) ( 2 7 ) 用任何优化方法求解都将是 定义2 2 设e 是时刻k 时群体中的最优抗体，f + 是待求问题的抗原，称免疫算法是依 概率全局收敛的，当且仅当靶j 限一f ) z 1 成立。 定义2 t 【1 9 】设4 为n x l 的方阵。 1 ) 若对所有的i ，0 ，则称a 为非负的( a o a n e g a t i v e ) ，记为a - 0 ； 2 ) 若a 是非负的，且对所有的i ， 再。l 则称4 为随机的。0 c h 鼬廿c ) 3 ) 若a 是非负的，且对a 中的行和列经过置换能得到医；】形式( c ，r 是 方阵) ，则称a 是可约的( r e d u c i b l e ) 。 定理2 2 【2 0 】设p 是一个可约随机矩阵，p = 医：】，其中c 是正的m 阶随机矩阵， r ，t _ 0 ，则 -。一：i?!-t=一lim【，出；，。c。k。?t一。12。【三： 呻 一_ 、- 矸r 一 t ll 膏” 定理2 3 基于浓度调节的免疫算法依概率全局收敛。 免疫算法的收敛性分析 证明算法中的交叉操作是以概率肌对选择的一对b 细胞上的诱个基因位进行交叉。 变异操作是对b 细胞的每个基因位以概率p m 相互独立的进行变异。则算法步骤( 1 - 6 ) 的 n 步状态转移可用状态转移矩阵p 一( 既) 表示，且 o ，1 ，既；1 。根据定义l 和定义2 ， 状态转移阵p 是随机的。 通过置换将转移矩阵p 的各状态排列如下：第一个状态为全局最优解；第二个状态为 全局次优解；第n 个状态为全局最差解。则算法步骤( 7 ) 对b 细胞的更新操作可视为： 对任意状态i ，依几+ 芝p o - p u 和p p 。o ，w ，f 对转移矩阵更新，生成新的转移矩阵 p 盘 1o o p 2 lp 2 2 0 p np 2 一p 。 。医 这里，r 一。p p 刮2 1 ，r ，f ：ii ! 三】冠r ，。，c 叫是一阶正的随机矩阵，根据定义，状 根据触z p 一酽。雕】i 【二”一状态槲， 即p l 一熙限一f ) 一1 ，由定义2 2 知基于浓度调节的免疫算法是全局收敛的。 2 2 混合免疫算法的收敛性 混合免疫算法是将免疫算法与传统局部优化方法相结合产生的算法，其每一次迭代过 程均包括两个阶段：变异操作与局部寻优操作。由前一节可知，免疫算法的全局收敛性源 自于两个因素，即变异操作的随机性确保产生包含于集合m - 工s i ， ) z f + 一8 中的概 率严格大于零，以及最优个体保留策略确保最优解一经产生即永久保留而不致遭到破坏丢 失。局部寻优操作的单向性使得该操作也不会破坏已经产生的最优解。因此，当免疫算法 全局收敛时，相应的混合免疫算法必然全局收敛。 免疫算法的收敛性分析 应该指出，免疫算法以及混合免疫算法的全局收敛性更多地只是具有理论上的意义。 在实际问题当中，对于可以接受的f ，m 。的测度往往是非常小的，要通过随机方法产生足 够好的近似解，需要的计算量之大是无法容忍的。实际计算当中，往往需退而求其次，选 择其他指标作为迭代终止的标准。下文中将就t s p 问题的情形进行说明。 混合免疫算法在t s p 问题中的应用 第三章混合免疫算法在t s p 问题中的应用 旅行商问题是图论当中著名的n p c 难题之一，具有重要的实际意义。目前对这一问题 尚无有效算法，甚至有效算法的有无也是悬而未决的问题。本章将免疫算法用于求解t s p 问题，并与贪婪法和改良圈算法相结合，构造一类混合免疫算法。数值计算结果表明，混 合免疫算法优于标准的免疫算法和单一的改良圈算法。 3 1t s p 问题和免疫算法 旅行商问题( t s p ) ，也称货郎问题，有两种提法f 2 1 】。一种是货郎到各树去卖货，再回 到出发处，每村都要串到( 不限制次数) ，为其设计一种路线，使得所经旅行距离最短。其数 学模型是在加权图g ，e ) 上求一个生成回路c ，使得 w ( c ) = 罗w ( e ) am i r i 各个生成回路的权 。 鬣 这个c 叫做理想回路。另一种提法是限制货郎到且仅到每村一次。这时，其数学模型 为在加权图上求一个h a m i l t o n 圈c ，使得 w ( q = w ( c ) ，m i n 各个h 硼i l t o 阍的权 。 露 从算法理论上讲，这两种提法的难度是相当的。已经证明的是，t s p 问题属于n p c 问 题，此类河题日前尚无有效算法，也不知道是否存在有效算法，但一般认为难度很大。已 有的研究主要集中于两个方面：确定最优路径长度上下界的启发式规则( h e u r i s t i c a l g o r i t h m s ) ；逐次修正已有可行解以使路径总长度缩短的改良算法。任何一个行经所有城市 恰次的环路均构成t s p 问题的一个可行解，其路径长度不小于最优路径的总长度。因此 确定了最优解路径总长度的上界。启发式规则可以构造可行解，但对可行解的质量没有任 何保证。改良算法中最为常用的是所谓改良圈算法f 2 1 】。 t s p 问题很值得关注。一方面，t s p 问题是n p c 中有代表性的问题，与其他n p c 问 题具有等价性，若在髑p 的求解当中取得突破，则大量n p c 问题的求解方法就可以迎刃而 解。同时，t s p 问题具有广泛的应用背景。例如，在印刷电路板的加工当中，需要在平面 混台免疫算法在t s p 问题中的应用 部件对大量节点进行焊接操作，焊枪运动的路线设计就是一个t s p 问题【2 2 】。与一般t s p 问题不同的是，焊枪在移动时可以在任意两个焊点之间沿直线运动，这里的图g 为完全图， 在节点数为n 时，h a m i l t o n 圈存在并且有o 一1 ) ! 2 个，各边的权值满足三角不等式，因此， 最优路线存在并且一定是一个h a m i l t o n 圈。t s p 问题甚至还应用于晶体的结构分析 2 3 1 。 本文考虑以下特殊类型的t s p 问题：图g 为完全图；任意边的权重恰为其两个端点的 欧几里德距离；欲求理想h a m i l t o n 圈。对于一般的t s p 问题，可以先用d i j k s t r a 算法 2 1 】 求得任意两点之间的最短距离。再使用本文的方法求解。这里不做详述。 设t s p 问题中的节点( 以下称为城市) 用数字1 到一编号，城市i 和j 间的直线距离记 为d ，不失一般性，总可以将出发点选在城市以。这样，数字1 到n 一1 的任何一个全排列 ( c l ，c 2 ，c 。) 就对应完全图g 的一个h a m i l t o n 圈c - 这个h a m i l t o n 圈的总距离为 瞄 d i s ( c ) ；d 帖+ z d ，啊。+ d w ， 在使用免疫算法求解髑p 问题时，可以将数字1 到n 一1 的任何一个全排列c 均看作一 个抗体，而1 d s ( c ) 则作为抗体c 的适应度。由于t s p 问题属于排列优化问题，本文考虑 采用两种特殊的变异方式，即基因突变方式与基因重组方式，从已有抗体产生新的抗体。 前者是将抗体中任意选定的一定长度片段( 这一长度称为突变半径) 中任意选定的一定数 目( 这一数目成为突变强度) 的城市的次序任意重新排列，保持其他次序不变；后者则是 将抗体中任意截取的任意长度的片段任意地平移至任意选定的新位置。有些作者在此采用 了随机多点对换变异 2 4 】。 3 2 解t s p 问题的基本免疫算法 首先考虑用基本免疫算法( f u n d a m e n t a li m m u n e a l g o r i t h m ，筒记为f i a ) 解t s p 问题。 这里，基本免疫算法计算的步骤为： s t e p1 读入城市的坐标数据哪及控制参数n ，g 。 s t e p2 计算城市的数目开，边数耵。 s t e p3 计算城市间的距离矩阵d 。 s t e p 4 随机生成初始抗体种群 c ? ，q ，c ：) ，计算各抗体的适应度之倒数 】5 掘合免疫算法在t s p 问题中的应用 d s ( q ) ，= l 2 ，n ，将抗体按照适应度排序。初始化迭代次数计数器g 。 s t e p 5 计算各抗体的选择概率p 及累积选择概率印。 s t e p6 根据累积选择概率c p ，以轮盘赌方式选择个抗体，以随机突变或基凼 重组方式产生中间代抗体种群，并计算中间代抗体的适应度的倒数。 s t e p 7 将父代种群与中间代种群合并，按适应度择优挑选j v 个抗体组成下一代 种群( 按适应度从大到小排列) 。 s t e p8 给迭代次数计数器g 加l 。 s t e p 9 如果g 大于g ，停止迭代，转第】o 步，否则转第5 步。 s t e p1 0 将当前种群中的第一个抗体作为问题的最优解，计算结束。 步骤5 当中，抗体的选择概率与其适应度成正比。步骤6 当中，随机突变操作的两个 控制参数按如下方式选取：在前g 2 次迭代中，突变半径，取为甩3 ，突变强度k 取为2 ； 在后g 2 次迭代中，突变半径，取为2 n 3 ，突变强度k 取为4 。 使用数学软件m a t l a b 编程实现上述基本算法。选择文献【5 】中的数据试算( 称为 t s p 2 0 问题) ，以为2 0 ，将种群大小取为2 0 0 ，迭代次数g 取为2 0 0 ，计算2 0 次，有1 9 次 求得了该问题的最优解，另有1 次得到优解。将取为3 0 0 ，g 取为3 0 0 ，仍计算2 0 次，每 次均取得最优解。 用计算机随机产生一组坐标数据，包含3 0 个点( 称为t s p 3 0 问题) ，仍用上述算法计 算，种群大小分别为3 0 0 ，迭代次数为3 0 0 。用f i a 计算2 0 次，2 次得到最优解，成功率 为o 1 。图3 1 和图3 2 为t s p 2 0 和t s p 3 0 问题的最优解。 1 6 渴台免疫算法在t s p 问题中的应用 在计算t s p 2 0 和t s p 3 0 问题的迥异表现值得研究。通过观察迭代过程中最短路径长= 度 的演化过程可以看出( 见图3 3 和图34 ) 。f i a 计算过程中，在最初一段时间，路径最短长 度减小速度很快，以后改善幅度逐渐减小，赢至趋向最优解的长度。收敛的速度与问题的 规模有关。同样取g 和为3 0 0 ，对t s p 2 0 问题，g 明显偏大，浪费了计算量；对t s p 3 0 问题，则有些冒险，算法常在收敛前已经终止。这表明，f i a 算法表现对控制参数的取值 敏感，缺乏鲁棒性质。 圈i 3 用f l 解髓p 外代鼍短路径长度的靛化 g ) 一一一一一一一 l 4 5 世舶 出 嚣祷 蛹 曩 擎 筠 2 0 1 。l - , _ 1 一 一i o5 01 0 0 姥矗警数 挪2 翮o 姥代敬数 混合免疫算法在t s p 问题中的应用 ，。一! 竺里! 竺! ! ! ! ! 竺堡苎塑! 璺苎慝粤堕些一 8 ( 1l 7 0 i 。， l ”卜裔一 这里的计算步骤当中，下一代种群仅由父代种群与中间代种群择优组成，没有添加随 机产生的抗体以维持种群的多样性。因此，算法的全局收敛性可能受到影响，计算结粜的 好坏可能依赖于初始种群的选择。这样处理的原因将在下文中阐明。 3 3t s p 问题的特点与近似算法 尽管免疫算法求解t s p 问题的效果不错，但收敛速度仍然是一个问题。为r 更为育效 地求解t s p 问题，分析t s p 问题最优解的特点是必要的。通过观察t s p 问题的最优解和 优解，不难看出，在理想h a m i l t o n 圈或较优的h a m i l t o n 圈上，若边e 被选中，则该边的两 个端点c j 和c 往往互为相对接近的“邻居”。 为了更为清晰地看到这一点，以如下方式为各边打分：对所有的城市q ，将其他的即一1 个城市按照与c i 的距离排序得到这些城市对c i 的近邻排序名次：以c i 和c ，为端点的边得分 为e 对c ，的近邻排序名次数与c ，对t 的近邻排序名次数之和。例如，若勺是c ，的第3 近邻， c ；是c 的第5 近邻，