（计算数学专业论文）免疫蚁群算法及其应用.pdf

摘要 免疫蚁群算法及其应用 摘要 人工免疫算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用不 足，往往做大量无为的冗余迭代，求解效率低。蚁群算法具有分布式并行全局搜索能 力，但初始解随机，易早熟且求解速度慢。本文提出免疫算法和蚁群算法的混合算 法免疫蚁群算法，采用接种疫苗机制获得初始解，通过交叉变异等操作加快其收敛速 度，并用基于浓度的选择机制防止早熟。将该算法用于求解旅行商问题和函数优化问 题进行计算机仿真，结果证明该算法是一种收敛速度和计算精度较好的一种算法。 关键词：入工免疫算法，蚁群算法，旅行商问题，两数优化问题。 i a b s t r a c t 免疫蚁群算法及其应用 a b s tr a c t a r t i f i c i a li m m u n ea l g o r i t h mh a st h ea b i l i t yo fd o i n gag l o b a ls e a r c h i n gq u i c k l ya n d s t o c h a s t i c a l l y b u ti t c a n tm a k eu s eo fe n o u g ho u t p u ti n f o r m a t i o n ，a n dh e n c ed oa l a r g er e d u n d a n c yr e p e a ts e a r c h i n gf o rt h eo p t i m a ls o l u t i o n ，w h i c hr e d u c e st h ee f f i c i e n c y o fa l g o r i t h m a n tc o l o n ya l g o r i t h mc o n v e r g e so nt h eo p t i m a lp a t ht h r o u g hp h e r o m o n e a c c u m u l a t i o na nr e n e w a l ，a n dh a st h ea b i f i t yo fp a r a l l e lp r o c e s s i n ga n dg l o b a ls e a r c h i n g b u ti t si n i t i a ls o l u t i o ni ss t o c h a s t i c ，c o n v e r g e n c es p e e di ss l o wa n di ti se a s yp r e c o c i o u s i nt h i sp a p e rw ep r o p o s eah y b r i da l g o r i t h mb a s e do na r t i f i c i a li m m u n ea l g o r i t h ma n d a n tc o l o n ya l g o r i t h m i ta d o p t sa r t i f i c i a li m m u n ea l g o r i t h mt og i v ep h e r o m o n et o d i s t r i b u t ea n dm a k e su s eo fa n tc o l o n ya l g o r i t h mt og i v et h eo p t i m a ls o l u t i o n t h e c o m p u t e rs i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi sb e t t e rt h a nt h ep r e - v i o u st w oa l g o r i t h m so nt h ec o n v e r g e n c es p e e da n da b i f i t yo fs e a r c h i n gf o ra p p r o x i m a t e g l o b a lo p t i m a ls o l u t i o nf o rs o l v i n gt r a v e l i n gs a l e s m a np r o b l e ma n df u n c t i o no p t i m i z a t i o n p r o b l e m s k e y w o r d s ：a r t i f i c i a li m m u n ea l g o r i t h m ，a n tc o l o n ya l g o r i t h m ，t r a v e l i n gs a l e s m a n p r o b l e m ，f 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 i i 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 李堕芷纱叩年厂月2 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：j 盟 聊年月2 日 硕士学位论文免疫蚁群算法及其应用 1 1研究背景 第一章引言 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简称t s p ) 是求一次遍访指定城市并返 回出发城市的最短旅行路线问题。t s p 问题作为经典的组合优化问题，已经被证明是 一个n p 难题 1 。另一方面，现实中的许多工程问题，如网络布线、物流配送、电路板 钻孔等 2 ，都可以抽象成为t s p 问题。可以说t s p 是一个既有理论价值又有广泛的工 程应用价值的组合优化问题。因此人们不断的寻找能够有效地解决t s p 问题的各种方 法。近几年，智能算法应用- 于t s p i ；- j 题的求解已经取得了一些成果 3 4 】。2 0 世纪9 0 年 代初，意大利学者m d o r i g o ，v m a n i e z z o 和a c o l o r n i 首先将蚁群算法用于求解t s p i ； 题 并取得了较好的效果。 人工智能经历了2 0 世纪8 0 年代整整1 0 年的繁荣后，由于方法论上始终没有突破经 典计算思想的樊篱，再次面临着寒冬季节的考验。在这种背景下，社会性动物( 如蚁 群、蜂群、鸟群等) 的自组织( s e l f - o r g a n i z a t i o n ) 行为引起了人们的广泛关注，许多 学者对这种行为进行数学建模并用于计算机对其进行仿真，这就产生了所谓的“群体 智能 ( s w a r mi n t e l l i g e n c e ，简称s i ) 【5 卜【1 0 。社会性动物的妙处在于：个体的行 为都很简单，但当他们一起协同工作时，却能够“突现”出非常复杂( 智能) 的行为 特征。例如，单只蚂蚁的能力极其有限，但当这些简单的蚂蚁组成蚁群时，却能完成 像筑巢、觅食、迁徙、清扫蚁巢等复杂行为；一群行为显得盲目的蜂群能造出精美的 蜂窝；鸟群在没有集中控制的情况下能够同步飞行等。这些自组织行为中，又以蚁群 在觅食过程中总能找到一条从蚁巢到食物源的最短路径最为引人注目。受其启发，意 大利学者m d o r i g o ，v m a n i e z z oa n da c o l o r n i 于2 0 世纪9 0 年代初提出的一种新型的智能 优化算法- 蚁群优化( a n tc o l o n yo p t i m i z a t i o n ，简称a c o ) 1 1 。它通过信息素的积累 和更新来寻求最优解，主要特点是模拟自然界中蚂蚁的群体行为。目前国内外研究者 用蚁群算法研究了旅行商问题，指派问题，调度问题等，取得了一系列较好的实验结 1 第1 章引言 硕士学位论文 果。蚁群算法具有分布式并行搜索能力，较强的鲁棒性和易于与其他算法结合等优 点，但同时也存在着一些不足之处：( 1 ) 与其他算法相比该算法需要较长的搜索时 间；( 2 ) 该算法容易早熟，即搜索进行一定程度后，所有个体所发现的解完全一致， 不能对解空间进行进一步搜索；( 3 ) 初始解和初始信息素随机。 近几年，人们提出了多种方法来解决蚁群算法的这三个缺点，其中蚁群算法与其 他算法混合产生新的混合算法是一个研究方向，例如禁忌算法与蚁群算法混合 1 2 】 遗传算法与蚁群算法混合 1 3 1 4 ，粒子群算法与蚁群算法混合 1 5 等。这些算法应用 于t s p 问题或函数优化问题的求解取得了较好效果。 人工免疫系统( a t i f i c i a li m m u n es y s t e m ，简称a i s ) 是模访生物免疫系统的免疫应 答、免疫调节等机理，构造出的一类高性能、自组织、鲁棒性好的人工智能系统。目 前，人工免疫系统的研究已经受到学者们越来越广泛的关注，人工免疫算法也在实际 工程应用中得到了推广。人工免疫成为继神经网络、模糊逻辑和进化计算后人工智能 领域又一研究热点 1 6 】一 i s 。免疫系统是一种复杂的分布式信息处理学习系统，这种 系统具有免疫防护、免疫耐受、免疫记忆、免疫监视功能，这些功能和特点给予研究 人员较多的灵感，促成许多学者建立了基于免疫机理的智能方法，解决大量的非线性 科学问题。本文将人工免疫算法与蚁群算法混合产生新的算法免疫蚁群算法( a r t i f i c i a l i m m u n ea n tc o l o n ya l g o r i t h m ，简称a i a c a ) ，并将该算法应用于t s p i h - 题和函数优化 问题的求解，计算机仿真结果证明该算法是一种收敛速度和计算精度都较好的一种算 法。 1 2本文的主要内容 由于人工免疫算法涉及到人工免疫算法及蚁群算法，所以首先要了解关于人工免 疫算法及蚁群算法的基本知识。故本文做如下安排：第二章为预备知识，这一章将首 先的介绍一下蚁群算法的基本思想及基本理论，然后介绍关于人工免疫算法的知识。 第三章首先给出人工免疫算法的基本思想，然后给出人工免疫算法的基本步骤。第四 2 硕士学位论文 免疫蚁群算法及其应用 章为人工免疫算法在求解t s p 阀题中的应用，4 1 为t s p 阎题的模型，4 2 为人工免疫算 法求解t s p 闯题时的基本算子，4 。3 为计算机仿真结果。第五章为工免疫算法在求解函 数优化问题中的应用。 3 第2 章预备知识硕士学位论文 2 1基本蚁群算法 第二章预备知识 蚁群优化算法是一种受自然界生物行为启发而产生“自然”算法。产生于对蚁群 行为的研究。蚁群中的蚂蚁以“信息素”( p h e r o m o n e ) 为媒介，间接异步的相互联 系。这是蚁群优化算法的最大特点。蚂蚁在行动过程中( 寻找食物或寻找回巢的路 径) 中，会在他们经过的地方留下一些化学物资，称之为“信息素 。这些物资能被 同一蚁群中后来的蚂蚁感受到并作为一种信号影响后者的行动。具体表现在后到的蚂 蚁选择有这些物资的路径的可能性比选择没有这些物资的路径的可能性大得多。后到 者留下的信息素会对原有的信息素进行加强，并循环下去。这样，经过蚂蚁越多的路 径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被其他蚂蚁选 中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路为止。 通过图2 1 简单的了解蚂蚁的运动过程。假设一个蚂蚁外出寻找食物，蚂蚁 从n e s t 点出发，行走速度相同，食品在f o o d 点，蚂蚁可能行走的路线如图2 1 。由于无 法预知道路中间的情况，蚂蚁出发时会随机选择n e s t b f o o d 或n e s t c f o o d 中的一条。 假设初始每条路线上分别分配一只蚂蚁，每单位时间走一步。当行走7 个单位时间 后，为图2 1 中上半部分的情形，已经有一个蚂蚁到达f o o d 点。当行走1 4 个单位时间 后，走n e s t b - f o o d 的蚂蚁已经回到a 点，而行走n e s t c f o o d 的蚂蚁到达f o o d 点。如果 蚂蚁每经过一点都留下大小为1 的信息素，这时n e s t b f o o d 路线的第一点聚集2 点， 而n e s t c f o o d 路线的第一点聚集1 点。在行走2 8 个单位时间后，这两点的信息素变化分 别为4 和2 ，比值为2 ：1 ，n e s t c f o o d 路线的蚂蚁返回n e s t 点。 如果按比值的比例，一群决定n e s t b f o o d 路线派两个蚂蚁，而n e s t c f o o d 路线 上派一个蚂蚁。在每个蚂蚁再各行走2 8 个单位时间后，n e s t b f o o d 和n e s t c f o o d 路线 的第一个点各累计1 2 和4 ，比值为3 ：1 。如果再按比值分配蚂蚁数量，贝u n e s t b f o o d 路 线分配三只蚂蚁，而n e s t c f o o d 路线分配一只蚂蚁。按原有的模式重复2 8 个单位时 4 硕士学位论文免疫蚁群算法及其应用 图2 1 ：蚂蚁寻物过程的简化图 间，n e s t b f o o d 和n e s t c f o o d 路线的第一点信息素各积累2 4 和6 ，比值为4 ：1 。如此重复 下去，可以发现n e s t b f o o d 和n e s t c f o o d 路线的第一点信息素的比值会越来越大，最 后的极限是所有的蚂蚁只选择n e s t b f o o d 路线。 为了更好的描述蚁群算法，下面所有的符号和算法设计以t s p 为基础，其它应用 可以据此进行改进。令戤= ( x i ，z 妇，z h ) 为礼为搜索空间中第i 只蚂蚁的位置。 假设i 舅= ( z 1 ，巧，z 。) 表示第i 只蚂蚁可以去的所有位置的集合。等式( 2 1 ) 给 出了第z 只蚂蚁向第歹个位置移动的概率函数，并且位置z i 与位置之间的信息素的值 越大、先验值仇f 的值越大选择路径i 一歹的概率越大，其中仇j 为下l 这里士是由位 。 。 j 一o iu 王一正i 置忍移动到位置z j 的耗费，通常由目标函数决定，它可以是两点间的距离或花费的费 用。等式中的o t ，p 是两个系数，分别为残留信息素和转移耗费的相对重要程度。 心咱( t ) ：乒继蚁 ( 2 1 ) h ( 亡) 口( 亡) p 1 - - 1 下一个位置可以根据足。2 ，( ) 的最大值来选择或是用轮盘赌来随机的选择下一个位 5 第2 章预备知识 硕士学位论文 置 1 9 】。当一个蚂蚁走完了所选的路径，则按式( 2 2 ) 更新信息素值。在每一次循环 结束后，每条路径上的信息数值都按( 2 3 ) 式进行更新，其中如是全局信息素挥发系 数，0 p g 1 。 6 + 1 ) = ( 1 一p ) ) + p 死j ( ) ；0 p 1 丁( 亡+ 1 ) = ( 1 一鳓) 7 _ ( 亡) ( 2 2 ) ( 2 3 ) 硕士学位论文 免疫蚁群算法及其应用 2 2基本人工免疫算法 2 2 1一般免疫算法的理论思想 生物免疫系统( b i o l o g i c a li m m u n es y s t e m ) 是一种高度并行的、分布式的自适 应系统，它是脊椎动物体内能够识别和排除抗原性异物，保护机体免受损害以及维持 机体内部环境稳定的极为复杂的生物学系统 1 7 2 0 。在免疫系统中，外来的细菌、 病毒( d a n g e r o u sf o r e i g nb a c t e r i a ，v i r u s e s ，e t c ) 等“非己物质称为抗原，负责识别 和清除抗原的是抗体。抗体与抗原的匹配程度用亲合力( a f f i n i t y ) 表示。当亲合力超 过某一闭值时，即表示抗体与抗原匹配成功，免疫应答( i m m u n er e s p o n s e ) 过程被 启动。此时，与外来抗原匹配的免疫细胞( b 细胞) 被激活( a c t i v a t i o n ) 并大量增生 ( p r o l i f e r a t i o n ) ，分泌出抗体，这些抗体与抗原结合将抗原消灭。那些能够参与免疫 应答的细胞，会被记忆下来而长期保存在免疫系统中，当相同或相似的抗原再次入侵 机体时( p r e v i o u s l y ) ，免疫系统会产生所谓的“二次应答”，能更快、更准确、更有 效地消除抗原。所以，生物免疫系统具有学习、记忆及联想( a s s o c i a t i v er e t r i e v a l ) 的 功能。 从信息处理的观点看( f r o ma ni n f o r m a t i o n - p r o c e s s i n gp e r s p e c t i v e ) ，免疫系统是 与遗传系统、神经系统并存的人体三大信息系统之一，它具有如下的功能：模式识别 能力，并行信息处理能力，学习能力，记忆与联想能力，自适应能力，自组织自调 整能力以及抗体的多样性保持能力。正是因为免疫系统所具有的这些优良特性，引 发了工程领域内众多研究人员对免疫系统极大的研究兴趣。研究者们根据问题的需 要，从生物免疫系统中抽取若干个特性，建立了很多人工免疫系统( a r t i f i c i a li m m u n e s y s t e m a i s ) 和人工免疫算法( a r t i f i c i a li m m u n ea l g o r i t h m - a i a ) ，以解决复杂的工 程实际问题。目前，在a i s 和a i a 中，主要采用了三种生物学免疫原理，即：免疫网络 理论，反向选择机制以及克隆选择原理 2 1 。 7 第2 章预备知识 硕士学位论文 免疫系统是高等脊椎动物体内能够识别和排除抗原性异物，保护机体免受损害及 维持内环境稳定的极为复杂的生物学系统。抗原性异物即是所谓“非己”物质，称为 抗原，不管是曾经遇到过的“非己物质，还是未曾遇到过的“非己 物质，免疫系 统均能识别并将其清除，很少错把“非己当作“自己，或把“自己 当作“非 己”。在免疫系统中，负责识别和清除抗原的是抗体，免疫系统的强大的识别能力， 即来源于抗体的多样性。阐明免疫系统抗体多样性产生机理的，是奥地利免疫学家伯 内特( n k b u r n e t ) 于1 9 5 7 年提出的细胞克隆选择学说。这个学说认为免疫系统在胚 胎期由于遗传和免疫细胞在增殖中发生基因突变，形成了免疫细胞的多样性。这些 细胞不断增殖形成无性繁殖系。细胞的无性繁殖系称作克隆。有机体内免疫细胞的 多样性能达到这种程度，以至于当每一种抗原侵入机体都能在机体内选择出能识别 和消灭相应抗原的免疫细胞，使之激活、分化和增殖，进行免疫应答以最终清除抗 原 17 2 1 】 2 2 】。 当病原体被清除后，免疫系统中就只存在抗体而不存在抗原了，或者抗原存在 但浓度很低，这种( 或多种) 与病原体匹配并参与清除抗原的抗体在免疫系统中 大量存在，浓度较高，免疫系统这时处于一种失衡状态，它如何回复到平衡状态 呢? n k j e r n e 等人提出的独特型( i d i o t y p i c ) 网络学说 2 3 回答了这个问题。这个学 说主要基于这样的概念，即淋巴细胞并不是彼此孤立的，相反，不同种类的淋巴细胞 间通过抗体的相互作用而交换信息并相互作用，共同完成免疫系统的功能。这一免疫 网络学说认为，抗体不但具有与抗原的抗原决定基( e p i t o p e ) 相结合的抗体结合部位 ( p a r a t o p e ) ，而且具有自己的特定的抗原决定基( i d i o t o p e ) 。具有这种特定的抗原 决定基的抗体作为一种特殊的抗原与别的抗体相结合，亦即被抗原激励的抗体反过来 可以激励别的抗体。当某种抗体的浓度达到一个给定阈值时，它就起到了某种抗原的 作用而对别的能与之相匹配的抗体产生激励作用，同时，它也被别的抗体抑制，从而 导致其浓度的下降，直到免疫系统回复到平衡状态。这就产生了所谓的免疫网络。 免疫识别是免疫系统的主要功能，识别的本质是区分“自我”和“非我”。免疫 8 硕士学位论文免疫蚁群算法及其应用 识别具有两个层次上的涵义。一层涵义的识别是对入侵抗原的识别，主要是通过淋巴 细胞上的抗原识别受体与抗原的结合来实现的，二者结合的强度称为亲合度。另一层 涵义的识别发生在胸腺中t 细胞成熟的过程，是生物免疫系统免疫耐受行为的根源所 在。免疫系统对外界入侵抗原的识别依靠t 细胞表面的受体进行检测，而在t 细胞的产 生过程中，受体通过伪随机基因重组过程来形成。基因重组形成的未成熟t 细胞在胸腺 中首先要经历一个审查环节，只有那些不能与生物体自身蛋白细胞组织( 自我) 发生 免疫应答的t 细胞才可以离开胸腺，执行免疫应答的任务；而那些对自身蛋白产生免疫 应答的未成熟t 细胞则被就地破坏掉，从而防止对生物体自身造成错误攻击。也就是 说，经历阴性选择后的存留下来的成熟t 细胞都对抗原具有亲和力，可形成免疫识别； 而对自体蛋白质不具备亲和力，可形成免疫耐受。t 细胞成熟过程中经历的选择过程称 为阴性选择( n e g a t i v es e l e c t i o n ) ，亦称反向选择 2 4 ，基于阴性选择的个体识别方法 称为免疫系统的自我一非自我识别原理，它也是免疫识别的一种主要方式。 2 2 2 人工免疫算法 近年来，国内外已提出并发展了一些免疫算法 2 5 2 6 2 7 ，不同免疫算法的分析 和比较主要从以下两方面进行研究：1 ) 自然免疫系统的免疫学理论和方法；2 ) 计算 机算法的分析量度。 主要免疫学说有反向选择原理、进化学说、克隆选择理论、疫苗学说和免疫网络 理论等。根据这些不同的免疫学说提出以下5 种不同的免疫算法： 1 、反向选择算法 免疫系统中的t 细胞在胸腺中发育，与自身蛋白质发生反应的未成熟t 细胞被破坏 掉，所以成熟的t 细胞具有忍耐自身的性质，不对自身蛋白质发生反应，只对外来蛋白 质产生反应，以此来识别自己与非己，这就是所谓的反向选择原理。 f o r r e s t 2 8 基于反向选择原理提出了反向选择算法用来异常检测，算法主要包括 两个步骤：首先，产生一个检测器集合，其中每一个检测器与被保护的数据不匹配；其 9 第2 章预备知识硕士学位论文 次，不断地将集合中的每一个检测器与被保护数据相比较，如果检测器与被保护数据 相匹配，则判定数据发生了变化。f o r r e s t 用概率分析的方法估计了算法的可靠性与检 测集合大小的关系。该算法的显著特点是异常检测时不需要先验知识，具有很强的鲁 棒性，其缺点为当被保护的数据变长时，集合中检测器的数量按指数率增加，产生检 测器的代价过大。针对这一缺点，h e l m a n 2 9 提出一种更有效的检测器产生算法，使 得集合中检测器的数量随着数据的长度按线性增长。p a t r i k 3 0 对反向选择算法进行了 理论分析。 2 、免疫遗传算法 c h u n 3 1 等提出了一种免疫算法，实质上是改进的遗传算法。根据体细胞和免疫 网络理论改进了遗传算法的选择操作，从而保持了群体的多样性，提高算法的全局寻 优性能。通过在算法中加入免疫记忆功能，提高了算法的收敛速度。算法中把抗原看 作目标函数，抗体看作问题的可行解，抗体与抗原的亲和力看作可行解的适应度。算 法中引入了抗体浓度的概念，并用信息嫡来描述，表示群体中相似可行解的多少。算 法根据抗体与抗原的亲和力和抗体的浓度进行选择操作，亲和力高且浓度小的抗体选 择概率大，这样就抑制了群体中浓度高的抗体，保持了群体的多样性。c h u n 3 2 将免 疫算法与进化策略、遗传算法相比较，指出免疫算法的特点与优点。 3 、克隆选择算法 c a s t r o 3 3 提出基于免疫系统的克隆选择理论提出克隆选择算法，该算法是模拟免 疫系统学习过程的进化算法。 免疫应答产生抗体是免疫系统的学习过程，抗原被一些与之匹配的b 细胞识别， 这些b 细胞分裂，产生的子b 细胞在母细胞的基础上发生变化。以寻求与抗原匹配更好 的b 细胞。与抗原匹配更好的子b 细胞再分裂。如此循环往复，最终找到与抗原完全匹 配的b 细胞，b 细胞变成浆细胞产生抗体，这一过程就是克隆选择过程。克隆选择算法 模拟这一过程进行优化。 c a s t r o 3 4 进一步将免疫网络理论和克隆选择算法相结合，提出了人工免疫网络学 】0 硕士学位论文免疫蚁群算法及其应用 习算法用于知识发现，冗余数据挖掘，自动分类，并对算法的参数灵敏度特性进行了 分析。 4 、基于疫苗的免疫算法 焦李成 3 5 等提出基于免疫系统的理论提出基于疫苗的免疫算法。该算法是在遗传 算法中加入免疫算子，以提高算法的收敛速度和防止群体退化。免疫算子包括接种疫 苗和免疫选择两个部分，前者为了提高适应度，后者为了防止种群退化。理论分析表 明这种免疫算法是收敛的，对7 5 城市t s p 问题的仿真验证了该算法的有效性。 5 、基于免疫网络的免疫算法 n a r u a k i 3 6 3 7 提出基于主要组织相溶性复合体( m h c ) 和免疫网络理论提出一 种自适应优化的免疫算法，用于解决多艾真体中每个艾真体的工作域分配问题。算法 主要分两步：( 1 ) m h c 区别自己和非己，消除智能体中的竞争状态；( 2 ) 用免疫网 络产生智能体的自适应行为。n t s p 问题的仿真表明，该算法具有自适应能力，并比 遗传算法具有更高的搜索效率。 除了以上主要免疫学习算法外，h u n t 3 8 提出了一种包括骨髓、b 细胞网络、抗原 和抗体的免疫学习算法；i s h i d a 3 9 提出了基于智能体结构的免疫算法 根据蚁群算法的缺点本文主要采用以下基本免疫算子： 接种疫苗设个体x ，给其接种疫苗是指按照先验知识来修改x 的某些基因位上的 基因或其分量，使所得个体以较大的概率具有更高的适应度。这一操作应该满足如下 两点：第一，若个体y 的每一基因位上的信息都与最佳个体不同，则对任一个体x ，x 转 移为y 的概率为0 ；第二，若个体x 的每个基因为上的信息都与最佳个体相同，即x 已经 是最佳个体，则x 以概率1 转移为x 。设有群体c = ( z 1 ，z 2 ，z n 。) ，e c 接种疫苗是指 在c 中按比例q 随机抽取佗口= a n 个个体而进行的操作。疫苗来源于问题的先验知识，它 所包含的信息量及其准确性对算法的性能起着重要的作用。 免疫选择这一操作一般分两步完成。第一步是免疫检测，即对接种了疫苗的个 体进行检测，若其适应度仍不如父代，说明在交叉、变异的过程中出现了严重的退化 1 】 第2 章预备知识 硕士学位论文 现象。这时，该个体将被父代中所对应的个体所取代；第二步是退火选择，即在目前 的子代群体e k = ( x 1 ，z 2 ，z n 。) 中以概率 墨型 p ( 卜彝n o ( 2 4 ) 选择个体甄进入新的父代群体，其中厂( ) 为个体x t 的适应度， 死) 是趋近于。的温度控 制序列。需要指出的是，免疫选择仅指免疫检测而没有退火选择。 浓度选择抗体浓度表示群体中相似可行解的多少。算法根据抗体与抗原的亲和 力和抗体的浓度进行选择操作，亲和力高且浓度小的抗体选择概率大，这样就抑制了 群体中浓度高的抗体，保持了群体的多样性。 抗体x 。的浓度计算公式： 1 2 nn d ( x i ) = i f ( z t ) 一f ( x j ) l + i x t - x j l ( 2 5 ) j = lj = a 以此为基础x 。被选择的概率为： p ( x i ) ：粤：竺竺 ( 2 6 ) p !r 12 讧- 1 , d ( z t ) 刍n ( i m t ) 一，( 即) l + i 戤一句i ) 硕士学位论文 免疫蚁群算法及其应用 第三章免疫蚁群算法 3 1免疫蚁群算法的基本思想 将免疫算法和蚁群算法相结合，把用蚁群算法解决的问题看作抗原，通过所提取 的疫苗给信息素赋初值，再由蚁群算法产生抗体给参数赋值，并应用于具体问题的求 解，将得到的结果作为当前抗体的适应度值，然后通过免疫算法的接种疫苗，交叉， 变异，亲和度选择等操作，将适应度好的抗体保留，淘汰适应度差的抗体，经多次迭 代，最终得到抗体，也就得到了对具体问题来说较优的蚁群算法的参数组合。算法中 采用基于亲和度的选择更新，从而有效的防止了“早熟的问题，将搜索过程引向全 局最优；采用提取疫苗机制给信息素赋初值，避免了初始解的随机性；并采用接种疫 苗机制、交叉和变异等操作来加快其收敛速度。 3 2免疫蚁群算法的基本步骤 步骤i 初始化城市间的距离信息并确定参数值，例如蚂蚁( 抗体) 数目 ( i a n t c o u n t ) ，变异概率( p _ m u t a t i o n ) 等。 步骤2 根据待求问题或求解过程中的些特征信息，先验知识等提取疫苗v 。根 据提取的疫苗初始化城市间的信息素值，并根据城市间的距离初始化先验值。 步骤3 用蚁群算法产生i a n t c o u n t 只蚂蚁( 抗体) a 。 步骤名每只蚂蚁走完了所选路径时都用等式( 2 2 ) 更新局部信息素值。 步骤5 当所有蚂蚁都走完所选路径时用等式( 2 3 ) 更新全局信息素值。 步骤6 ，对a 中蚂蚁( 抗体) 进行交叉、变异操作生成蚂蚁( 抗体) 群b 。 步骤7 对b 中蚂蚁( 抗体) 进行接种疫苗操作生成蚂蚁( 抗体) 群c 。 1 3 第3 章免疫蚁群算法 硕士学位论文 1 4 步骤占对b u c 进行免疫选择保留适应度较好的蚂蚁( 抗体) 淘汰适应度差的蚂 蚁( 抗体) 产生i a n t c o u n t 只蚂蚁( 抗体) d 。 步骤9 浓度选择：再随机产生m 只蚂蚁( 抗体) e ，e du e 用等式( 2 5 ) 计算 其浓度，用等式( 2 6 ) 计算每只蚂蚁的选择概率，再由轮盘赌产生i a n t c o u n t 只 蚂蚁f 。 步骤_ f d 判断是否满足算法的终止条件，如满足则算法停止转步骤1 1 ；否则返回 步骤3 。 步骤f j 输出最好解。 硕士学位论文 免疫蚁群算法及其应用 第四章免疫蚁群算法在求解t s p 问题中的应用 4 1t s p i h 题模型 t s p 问题是一个典型的n p 难问题。t s p 问题可以描述为一个商人欲到竹个城市推销 商品，每个城市都遍历且仅遍历一次并返回到出发城市所能行走的最短路径问题。假 设这礼个城市的坐标为局，马，r ，城市i 与城市歹之间的路径长度为d ( 只，弓) ，且旅行 商人从城市只，出发。则一个整数排列x = 只。，只。，只。) 即为该t s p 问题的一个可 行解( 其中只，) 固定为出发城市，i 2 ，i 3 ，如为1 ，2 ，n 除去i 1 后的所有整数的一个排 列) 。由此目标函数可以表示为： n 一1 r a i nf ( x ) = r a i n ( ( d ( 吃，只，+ ，) + d ( 只。，只。) ) ) j = l n ( 4 1 ) n 、7 = r a i n ( d ( p i ，r ) ) 式中，厂( x ) 表示当遍历路径为x 时的路径。 4 2免疫蚁群算法解t s pi h - j 题时的基本算子 4 2 1 提取疫苗算子 就t s p 问题本身的特点而言，在最终的解决方案中，即最佳路径必然在很大程度上 包括了相邻城市间距离最短的路径。这个特点是t s p 问题自身的一种属性，也是在解 决问题时可以利用的一种特征信息和知识，故而能够作为从问题中抽取疫苗的一种途 径。 不是一般性，设在某一具体问题中，所有与城市a 距离最近的城市为如，并且二 者未能前后连接，而是分别处于某一路径的两段：a 一1 一a a 件1 和a j 一1 - a j a j + 1 ， 如图4 1 中实线所示。则当前的遍历路径为 7 r = a o ，k 一1 ，a i ，a i + 1 ，b 一1 ，a j ，a j + 1 ，a n ) 1 5 第4 章免疫蚁群算法在求解t s p 问题中的应用 硕士学位论文 其对应的路径长度为 图4 1 ：t s p 问题的疫苗作用机理示意图 d 丌= a k + 锄+ a k + 哟一1 + + a k ( 4 2 ) k = l k = i + l k = j + l 在免疫概率只发生条件下，对城市a 而言，免疫算子将把其邻近城市如排列为它 的下一个目标城市，而使原先的遍历路径调整为 7 r c = 山，a 一1 ，a ，如，a + 1 ，如一1 ，a j + 1 ，4 ) 则相应的路径长度变化为 d 几= n 七+ f 1 + z 2 + a k + 1 3 + a k ( 4 3 ) k - - 1 k - - i + 1 k = j + l 比较式( 4 2 ) 和式( 4 3 ) ，因为如是所有城市中( 即全局中) 与城市a 距离最近 的点，在由a 一如一a i + 1 所构成的三角形中c 1 一定为最短边或次短边( 此时f 2 一定为最 短边。因为若口i 0 ，并且的值越大，算法的收敛速度越慢。 通过上面的讨论我们就可以得到高斯核p d f g i ( x ) ，我们就把它作为信息素的概率 分布密度函数。 5 2 2 提取疫苗算子 在这里采取动态疫苗提取策略，假设武= ( z 1 ，z n ) 是f ( x ) 在某次迭代中的最优 解，那么就令疫苗v = ( v l ，v n ) = ( x l ，z n ) 。 5 2 3 接种疫苗算子 从抗体群中按一定概率选择一个抗体x = ( x l ，z 之) 并且随机选择一个疫苗 一个疫苗吻。