（计算机应用技术专业论文）改进的克隆选择优化算法及其应用研究.pdf

摘要 生物免疫系统是一种高度并行的自适应信息学习系统，它能自适应地识别和 排除机体的抗原性异物，并且具有学习、记忆和自适应调节能力，能够保护机体 体内环境的稳定。近年来，人们逐渐意识到生物免疫机制对开发新的计算机智能 的启示意义，克隆选择算法( c s a ) 耳o 是受生物免疫系统启示而设计的新型算法。 它结合了先验知识和生物免疫系统的自适应能力两大特点，因而具有较强的鲁棒 性和信息处理能力，并且在对问题进行求解时不要求目标函数具有可导等高附加 信息，在搜索过程中能更快收敛到全局最优解，被人们认为是具有强大潜力的搜 索算法，现已经用于模式识别，异常和故障诊断，机器人控制，网络入侵检测， 函数优化等领域，表现出较卓越的性能和效率。 本文根据克隆选择原理，研究了克隆选择算法在多峰值函数优化和动态路径 优化中的应用。 本文的工作主要有以下几个方面： ( 1 ) 介绍了生物免疫系统的发展历史、系统功能和一些基本概念，简单介 绍了人工免疫系统的免疫机理、免疫优化机理以及常见的免疫优化算法；其次， 介绍了克隆选择算法的基本原理、基本特点以及克隆选择在优化中的应用。 ( 2 ) 论文通过分析经典的c l o n a l g 算法在多峰值函数优化中的不足，改 进克隆选择操作和变异操作，并且引入了免疫网络的抑制操作，提出了一种多峰 函数优化的改进的克隆选择算法，该算法并与c l o n a l g 算法和o p t 。a i n e t 算法 在多峰函数中的优化效果进行比较。 ( 3 ) 通过分析路网中交通状态实时变化的特点以及出行者选择最佳路径的 问题上存在多目标性的特点，建立了基于路段行程时间和路段长度的动态路径多 目标规划模型。然后，在分析了克隆算法的路径编码方式和变异操作的基础上， 设计了一种用于求解动态路径多目标模型的克隆选择算法。仿真结果表明，该算 法具有实时性的特点，能以启发式的变异操作较快的搜索出的基于出行者选择的 车辆行驶最佳路径，在车辆行驶过程中，可根据实时的交通状态，动态地调整行 驶路线。 关键词：人工免疫系统；免疫算法；克隆选择算法；函数优化；交通工程；动态 路径优化；行程时间 a bs t r a c t b i o l o g i c a li m m u n es y s t e mi s ah i g h l yp a r a l l e la d a p t i v ei n f o r m a t i o nl e a r n i n g s y s t e m ，w h i c hc a l li d e n t i f ya n dr e m o v et h ea n t i g e n i ce y ew i n k e r si n v a d i n gt h eb o d y t h i ss y s t e mc a nl e a r n , r e m e m b e ra n da d j u s ta d a p t i v e l yt ok e e pt h es t a b i l i z a t i o ni n s i d e t h eb o d y d u r i n gr e c e n ty e a r s ，p e o p l eb e g i nt or e a l i z et h er e v e l a t o r ys i g n i f i c a n c eo f t h eb i o l o g i c a li m m u n em e c h a n i s mt oi n t e l l i g e n ta l g o r i t h m c l o n es e l e c t i o na l g o r i t h m i st h i sk i n do fn e wa l g o r i t h mw h i c hi si n s p i r e db yt h eb i o l o g i c a li m m u n es y s t e m i t c a nb es a i dt h a t ，n o w a d a y st h es t u d yo fa r t i f i c i a li m m u n ea l g o r i t h mc o m b i n e st w o m a i nf e a t u r e s ，t h ep r i o r yk n o w l e d g ea n dt h ea d a p t i v ea b i l i t yo fi m m u n es y s t e m ， e n d o w i n gi tw i t hp o w e r f u la n dr o b u s ta b i l i t y , w h i c hc a nd e a lw i t hi n f o r m a t i o n i ti s c o n s i d e r e dt ob eav e r ys i g n i f i c a n ta n dm e a n i n g f u lr e s e a r c hd i r e c t i o n n o wt h i sk i n d o fa l g o r i t h mh a sb e e n u s e di n m a n yf i e l d s ，s u c h a s p a t t e r nr e c o g n i t i o n ， u n c o n v e n t i o n a l i t ya n dm a l f u n c t i o nd i a g n o s i s ，c o n t r o lo fr o b o t s ，i nb r e a kd e t e c t i o no f n e t w o r k ，f u n c t i o no p t i m i z a t i o na n de t c b yu s i n gt h ep r i o r i t yo ft h ea r t i f i c i a li m m u n e a l g o r i t h m o nt h ea n a l y s i so ft h ec l o n es e l e c t i o nm e c h a n i s m ，s t u d y i n gt h ea p p l i c a t i o no ft h e a l g o r i t h mw h i c hu s e di nm u l t i - m o d a lf u n c t i o na n dd y n a m i cr o u t i n go p t i m u mi nt h i s p a p e r t h em a i n w o r ka sf o l l o w s ： ( 1 ) t h eo r i g i n ，s y s t e m a t i cf u n c t i o na n d b a s i cc o n c e p t so ft h eb i o l o g i c a li m m u n e s y s t e m a r ei n t r o d u c e d ，i m m u n em e c h a n i s m ，o p t i m u mm e c h a n i s ma n dt h em a i n i m m u n eo p t i m i z a t i o na l g o r i t h mo fa r t i f i c i a li m m u n es y s t e ma r es i m p l yi n t r o d u c e d t h e n ，t h eb a s i cp r i n c i p l e ，f e a t u r e sa n dt h ea p p l i c a t i o no fc l o n es e l e c t i o na l g o r i t h ma r e a l s op r e s e n t e d ( 2 ) o nt h ea n a l y s i so ft h ei n s u f f i c i e n to ft h ec l a s s i cc l o n a l ga l g o r i t h m ，w i t h t h ei m p r o v e m e n to fo p e r a t i o no fc l o n es e l e c t i o n ，c l o n em u t a t i o na n dt h eo p e r a t i o no f a n t i b o d ys u p p r e s s i o ni si n t r o d u c e d ，aa d v a n c e dc l o n e s e l e c t i o na l g o r i t h mi sp r o p o s e d a n dt h er e s u l to ft h eo p t i m i z a t i o no ft h ea l g o r i t h mf o rm u l t i - m o d a lf u n c t i o nh a sb e e n c o m p a r e d 、i t hc l o n a l g a n do p t - a i n e t ( 3 ) o nt h ea n a l y s i so ft r a v e l e r ss e l e c t i o nf o rt h eo p t i m u mr o u t i n gr e p r e s e n t m u l t i o b j e c t i v ec h a r a c t e r i s t i c ，a n dt r a v e l e rc o u l da d j u s tt h ep r e v i o u sr o u t i n gb a s e d o n t r a f f i cs t a t u s ，am u l t i o b j e c t i v em o d e lo fd y n a m i cr o u t i n gb a s e do nl i n kt r a v e lt i m e a n dl i n kl e n g t hi sp r e s e n t e d t h e n , ac l o n es e l e c t i o na l g o r i t h ms o l v i n gt h em o d e li s p u tf o r w a r d ，w i t ha n a l y s i st h ee n c o d i n gm e t h o da n dt h eo p e r a t i o no fm u t a t i o n s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f i c i e n ta n dh a st h ec h a r a c t e r i s t i co f r e a l - t i m ep e r f o r m a n c e ，c o u l da l s op r o v i d et h e o p t i m u mr o u t i n go nt h eb a s i so f r e a l t i m et r a 伍ci n f o r m a t i o n 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 ；i m m u n ea l g o r i t h m ；c l o n es e l e c t i o n a 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 ；t r a f f i ce n g i n e e r i n g ；d y n a m i cr o u t i n g o p t i m i z a t i o n ；t r a v e lt i m e i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：彳留韶易泛日期：妒撼年f 月7 尹日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 髫积纵 翩躲履童 日期：妒睥f 月f 罗日 日期：。) 纤，月7p 日 1 1引言 第一章绪论 赖以支撑生物体复杂生命现象和高级智能行为的各种神奇法则一直是人类 悠然神往的奥秘和不竭的技术思想方法源泉，不断启迪着科学和工程技术向前发 展。目前，生物体四大信息处理系统中，神经系统( n e r v o u ss y s t e m s ) 和遗传系统 ( g e n e t i cs y s t e m s ) 经得到了深入研究，基于它们工作原理的各种人工模型及其 算法结构被广泛应用于工程实践，产生了巨大的科研经济效用。然而，对免疫系 统( i m m u n es y s t e m s ) 和内分泌系统( ( e n d o c r i n es y s t e m s ) 的研究和应用却相对滞 后。上世纪六七十年代以后，随着免疫学理论研究的不断发展，人们对生物免疫 系统的认识不断深入。 人工免疫系统研究的目的旨在通过深入探索生物免疫系统所蕴含的信息处 理机制，建立相应的工程模型和算法，开拓新型智能信息处理系统。可见，借鉴 免疫原理提出高效的学习和优化算法，是人工免疫理论研究的重要内容之，免 疫系统有许多优点可用于发展新型计算方法，免疫算法就是一种借鉴生物免疫系 统特性而形成的启发式搜索算法。 优化问题求解是人工智能的一个重要的应用领域，优化问题也一直是人们感 兴趣的问题之一。由于该问题的普遍性和重要性，几十年来得到了广泛和深入的 研究。直到现在，仍有许多学者在对优化问题作更为深入的研究工作。正是因为 这些持续的研究工作，才不断涌现出新的理论和方法，满足了科学与技术发展的 需要，也为人工免疫系统的发展提供了基础。基于免疫系统原理开发的各种模型 和算法已经引起人们的极大重视，其在科学研究和工程实践上将会有越来越多的 应用。 本文在已有成果的基础之上，对免疫系统中的克隆选择算法进行了研究，根 据多峰值函数优化和动态路径优化的特点对原有的算法进行了改进。把改进后的 算法用于多峰值函数优化问题，其收敛速度和多峰值搜索能力都优于原算法。把 改进后的算法应用于动态路径优化问题，也取得了满意的效果。 1 2 人工免疫系统( a ls ) 的发展历史及研究现状 1 2 1人工免疫系统的生物学基础 生物体是一个复杂的大系统，其信息处理功能是由时间和空间尺寸相异的三 个子系统完成的，即：脑神经系统、免疫系统和内分泌系统。人工智能对神经系 统的借鉴和模拟的成果很丰富，已经有比较成熟的方法和模型以资利用，相比较 而言，对免疫系统和内分泌系统的相应研究还处于初级阶段。 1 ) 生物免疫研究的发展历史 在生物学领域中，免疫学是一门相对年轻的学科，然而，人类对自然免疫的 认识可以追溯到3 0 0 年以前。早在1 7 世纪，我国医学家就创造性地发明了人痘 以预防天花。1 7 9 6 年英国医生e d w a r d3 e n n e r “牛痘”的发明，取代了人痘苗， 是公认的现代免疫学开端。法国免疫学家p a s t e u r 发明了减毒细菌疫苗，奠定了 经典免疫疫苗的基础。经过3 0 0 多年的发展，免疫学已经从微生物学的一章发展 成一门独立的学科，并派生出若干分支，例如，细胞免疫学、分子免疫学、神经 与内分泌免疫学生殖免疫学和行为免疫学等。表1 1 总结了免疫学历史上( 至 2 0 世纪9 0 年代初) 比较重要的思想、理论和研究成果【1 1 。事实上，人们对自然 免疫系统的认识还不是十分充分，只是在免疫系统理论上“建立一个合作系统的 综合性理论的基础和需要都己很明显”。就现有的免疫系统理论而言，为学术界 所接受，并为工程应用尤其是人工智能领域所借鉴的主要是b u m e t 的克隆选择学 说和j e m e 的免疫网络学说。 表1 1 自然免疫学的主要理论 主要目标时间代表人物思想、理论和研究成果 1 6 世纪起中国民间 “人痘”的发明和应用 1 7 9 6 1 8 7 0 j e n n e r“牛痘”的发明和应用 经验免疫k o c h 病理学 时期1 8 7 d 一1 8 9 0p a s t e u r 疫苗接种 b e s e d o v s k y神经内分泌免疫网络学说 m e r e h i n i k o f 噬菌作用 1 8 9 0 1 9 1 0y o nb e h n i n g & k i t a s a t o发现抗体 科学免疫 e h r l i c h 发现细胞受体 时期1 9 1 0 一1 9 3 0b o r d e r 免疫特性 l a n d s t e i n e t 半抗原 1 9 3 0 一1 9 5 0 b r e i n l h a u r o w i t z抗体合成 现代免疫学l i n u sp a u li n g抗原模型 时期1 9 5 0 _ 一1 9 8 0b u r n e r 克隆选择 n i e l sj e m e 免疫网络与协作理论 分子水平研究 1 9 8 0 1 9 9 0s u s u m ut o n e g a w a 受体的结构和多样性 2 )生物免疫系统及其功能 2 免疫系统( i m m u n es y s t e m ) 是保护肌体免受各种致病细菌侵袭，维护肌体健康 的重要生物系统，其功能是免疫( i m m u n i t y ) 。免疫是肌体的保护性生理反应，即： 通过识别“自己和“非己 ，排除抗原性“异物”( 病原生物及其产物、衰老 的自身细胞、突变产生的异常细胞) ，维持肌体内环境平衡。免疫分两种：特异 性免疫( s p e c i f i ci m m u n i t y ) 和非特异性免疫( n o n s p e c i f i ei m m u n i t y ) 【2 】。非特 异性免疫又称先天性免疫，是肌体在进化过程中逐渐建立起来的天然防御功能， 与生俱来，对各种病原微生物都有防御作用，没有特殊针对性，它是肌体防御外 来侵袭的第一防盗线，主要由皮肤、粘液等组织完成。特异性免疫又称获得性免 疫，是免疫系统通过对环境不断学习，后天积累的，针对特定致病因子的防御功 能。特异性免疫是肌体适应环境的体现，由免疫细胞完成，它是免疫学主要的研 究对象。 免疫系统包括免疫淋巴组织和免疫活性细胞。免疫淋巴组织按作用不同分为 中枢淋巴组织和周围淋巴组织。前者包括胸腺、腔上囊( 鸟类特有) ，人类和哺 乳类的相应组织是骨髓和肠道淋巴组织；后者包括脾脏、淋巴结和全身各处的弥 散淋巴组织。免疫活性细胞是指能接受抗原刺激，并能引起特异性免疫反应的细 胞。按发育成熟的部位及功能不同，免疫活性细胞分成t ( t h y m u s ) 细胞和b ( b u r s a ) 细胞两种。t 细胞全称为胸腺依赖性淋巴细胞，其主要功能是执行体液免疫。t 细胞由胸腺内的淋巴干细胞在胸腺素的影响下增殖分化而成，主要分布在淋巴结 的深皮质区和脾脏中央动脉的胸腺依赖区。t 细胞受抗原刺激时，首先转化成淋 巴细胞，然后分化成免疫效应细胞，参与免疫反应。t 细胞按功能不同，又可分 成杀伤性t 细胞、辅助性t 细胞和抑制性t 细胞。杀伤性t 细胞的主要功能是 识别并清除抗原；辅助性和抑制性t 细胞主要功能是进行免疫调节。b 细胞由腔 上囊组织中的淋巴干细胞分化而成，主要功能是执行细胞免疫。b 细胞主要分布 在淋巴结皮质区的淋巴小结、髓索及脾脏白髓的淋巴小结、脾索等非胸腺依赖区。 b 细胞受抗原刺激后，首先转化成浆母细胞，然后分化成浆细胞，分泌抗体参与 免疫反应。 抗体( a n t i b o d y ) 又称免疫球蛋白，其主要功能是识别、清除肌体内各种病原 性异物，即抗原a n t i g e n 。各种抗原分子都有其特异结构i d i o t y p e 抗原决定基， 又称e p i t o p e 表位，而每个抗体分子v 区也存在类似机构受体，或称p a r a t o p 对 位。抗体根据其受体与抗原决定基的分子排列相互匹配情况识别抗原。当两种分 子排列的匹配程度较高时，两者亲和度( a f f i n i t y ) 较大，亲和度大的抗体与抗 原之间会产生生物化学反应，通过相互结合形成绑定( b a n d i n g ) 结构，并促使 抗原逐步凋亡。 抗原侵入肌体后会刺激免疫系统发生一系列复杂的连锁反应，这个过程叫做 免疫应答( i m m u n er e s p o n s e ) ，或称免疫反应( i m m u n er e a c t i o n ) 。免疫反应分初 次反应和二次反应。未知抗原侵入肌体后，达到一定匹配程度( 亲和度) 的抗体被 激活，经过持续的“体液高变异( s o m a t i ch y p e m u t a t i o n ) 和“克隆选择( c l o n e s e l e c t i o n ) 逐渐产生与抗原高度亲和的抗体，并形成一定的浓度优势快速清除抗 原。随着抗原被消灭，抗体的数目大幅度下降，在各种效应因子的相互影响和作 用下，最后在一定数目上达到系统平衡。随后借助抗体间信息传递，不断产生一 定数目的同类抗体，长期滞留在免疫系统中，形成免疫记忆，这是初反应；当肌 体遭遇同类抗原的再次侵入，免疫系统产生二次反应。由于抗原的涌入，系统原 有的静态平衡被破坏，同时由于免疫记忆的存在，系统中高亲和度的抗体急剧增 加，从而能够保证快速有效地杀灭抗原。 3 )生物免疫系统的一些基本概念 ( 1 ) 免疫细胞 人体的免疫细胞由造血干细胞、淋巴细胞系、单核吞噬细胞系统组成，主要 是在骨髓和胸腺中发育成熟，它们在血液和淋巴液中循环，图1 1 所示为免疫系 统产生的细胞和分泌物的结构划分。免疫系统中某些免疫细胞负责固有免疫系统 中的一般防御，而其它则在自适应免疫系统中担负起了对付高度特异化病原体的 重任。在这里我们重点介绍免疫系统中起主要作用淋巴细胞系。 淋巴细胞系是具有特异免疫识别功能的细胞系，人和哺乳类动物的淋巴细胞 图1 1免疫系统产生的细胞和分泌物的结构划分 系是由形态相似、功能各异的不均一细胞群所组成。按其个体产生、表面分子和 功能的不同，可将淋巴细胞系分为t 细胞和b 细胞两个亚群，每个亚群又可分 为不同的亚类。另外还有一群单核细胞，其来源可能与淋巴细胞相关，但不具有 特异识别功能，称为天然杀伤细胞( n a t u r a lk i l l e rc e l l ，简称n k ) 可归类为第三群 淋巴细胞。成熟的t 细胞和b 细胞均为单核的小淋巴细胞。在光学显微镜下， 单纯从形态学是能加以区别的。 ( 2 ) b 细胞 4 b 细胞是免疫系统的本质部分，是b 淋巴细胞的简称。b 细胞首先证明是在 鸟类淋巴样器官法氏囊内发育成熟的，故称之为b 细胞，图1 2 所示为b 细胞的 简化图。哺乳动物的b 细胞，在胚胎早期存在于胚肝，胚胎晚期至出生后则在 骨髓内分化成熟。成熟的b 细胞定居于周围淋巴组织，如淋巴结、脾、扁桃体 等组织和器官当中。 b 细胞是体内唯一能够产生抗体( 免疫球蛋白分子) 的细胞。它的表面含有可 以识别特异性抗原的多种抗体分子，其多样性来自干百万种不同的b 细胞克隆。 每一个b 细胞克隆的特性是由其遗传性决定的，可产生一种能与相应抗原特异 相结合的免疫球蛋白分子。b 细胞能与t 细胞相互作用，并在后者的辅助下激活。 活化的b 细胞进入滤泡，在该处扩增，取代处于休眠状态的b 细胞形成生发中 b 细胞 b 细胞表面的抗体 图1 2b 细胞简化图 心，并进一步化为分泌抗体的浆细胞或成为长寿的记忆细胞。 b 细胞有三个主要的功能：产生抗体、提呈抗原和分泌细胞因子参与免疫调 节。 b 细胞在免疫应答和清除病原体过程中起主要的作用，在清除病原体过程中 受到刺激，分泌抗体结合抗原，但其发挥免疫作用要受t 辅助细胞的帮助。人 对抗原的亲和力对网络中其他b 细胞的亲和力 至 墨 b 细胞死亡，由骨髓产生 新的b 细胞，加入到网络 中 b 细胞进行克隆，克隆产生的 b 细胞通过高频变异产生具有 新抗原受体的b 细胞 图1 3b 细胞刺激水平示意图 体每天有大量的b 细胞产生和死亡，这也是免疫系统具有动态性的主要原因。 5 刺激水平不仅取决于b 细胞抗体与抗原结合的情况，而且取决于在免疫网络中 其他b 细胞的匹配情况。如果刺激超过一定阀值，b 细胞变大开始分裂，千百次 复制自己，以非常高的频率在基因中产生点变异，基因对抗体分子特异编码，这 种机制称为体细胞高频变异。相反如果刺激水平降低到一定阀值，b 细胞不再复 制，则到了一定时间会全部死亡。 b 细胞刺激水平也取决于它与免疫网络中其他b 细胞的亲和力。该网络是由 于b 细胞识别系统中其他b 细胞而形成。与一个b 细胞的有亲和力的“抗原邻 居”越多，它受到的来自系统中的刺激越多，反之越少。图1 3 所示为b 细胞刺 激水平的示意图。 骨髓产生或高频变异产生的新b 细胞存活与否取决于它们对抗原和网络中 其他b 细胞的亲和力。新细胞可能对抗原有更高的亲和力，会进行复制并比现 存的b 细胞存活时间更长。免疫网络加强有用的b 细胞并复制它。通过重复的 高频变异和选择过程，经过一段时间后免疫系统通过学习产生了对抗原更高的亲 和力。 ( 3 ) t 细胞 t 细胞是由一群功能不同的异质性淋巴细胞组成，由于它在胸腺内分化成熟 故称之为t 细胞。成熟后的t 细胞由胸腺迁出，移居于周围淋巴组织。它的主 要功能包括调节其他细胞的活动以及直接袭击宿主感染细胞。t 细胞是经其自身 分化为效应细胞后直接执行免疫功能的，故由t 细胞介导的免疫称为细胞介导 免疫。成熟的t 细胞也以两种状态存在于免疫系统中：静止期和活化期。t 细胞 按功能来分，可分为两类：毒性t 细胞和调节t 细胞。而调节t 细胞又分为辅 助性t 细胞和抑制性t 细胞。辅助性t 细胞与抗原结合时分泌蛋白质分子来刺 激b 细胞分子，因此它的本质作用是激活b 细胞。 毒性t 细胞能够清除微生物入侵者、病毒或者癌细胞。一旦被激活，并与它 们的配合物结合，就向入侵的细胞注入有毒的化学物质，并在细胞膜表面打孔使 其死亡。毒性t 细胞对于保持免疫应答非常重要，没有毒性t 细胞的活动，免 疫会失去控制，导致过敏反应和自身免疫性疾病。 ( 4 ) b 细胞与t 细胞之间的联系与区别 b 细胞是抗体的唯一产生者，但是当b 细胞识别到抗原的时候，只有在与抗 原的匹配程度超过某一阀值的时候，才有可能分化成浆细胞，否则没有达到阀值 的b 细胞就会凋亡。即使超过了阀值，b 细胞并不能马上分化成浆细胞，而需要 在t 细胞也同时检测到b 细胞提呈的抗原缩氨酸之后，由t 细胞分泌刺激物对 b 细胞进行刺激，b 细胞才会分化成浆细胞制造大量的抗体，没有t 细胞的协同 刺激，b 细胞就不能分化。 6 b 细胞和t 细胞表面都存在大量的抗原识别受体，这些受体通过对于特定的 抗原决定基高度特异来识别抗原。t 细胞表面的抗原识别受体称为t 细胞受体， b 细胞表面的抗原识别受体称为b 细胞识别受体，简称抗体。t 细胞受体与b 细胞受体的不同之处在于，b 细胞抗体与完整的抗原分子表面上的抗原决定基相 互作用，当b 细胞的抗体能够完全或者部分识别抗原表面的抗原决定基的时候， b 细胞就通过克隆扩增，进入到高频变异和受体编辑阶段，实现对抗原决定基的 高度特异识别。t 细胞只与细胞表面分子进行相互作用。t 细胞分泌能够杀死或 者促进其他细胞( 如b 细胞) 生长的化学物质，在免疫调节中起重要的作用，通过 识别细胞表面的异常分子，t 细胞必须判断是采取直接溶解该细胞，还是寻求与 其它细胞进行合作来清除该细胞。 不同淋巴细胞的特异性给免疫系统提供了更快的适应性应答能力和非自体 反应能力。t 辅助细胞的责任是自体耐受，b 细胞通过体细胞高频变异适应特异 病原体。虽然t 辅助细胞必须能够认识b 细胞提呈的缩氨酸，但两类淋巴细胞 都是必要的。t 辅助细胞一般执行非特异检测，对特异检测效率不高。b 细胞则 对检测特殊病原体更有效率。 ( 5 ) 抗原 在现代免疫学中，所谓抗原( a n t i g e n ，简称a g ) 是指凡是能够诱导免疫系统 发生免疫应答，并能与其产生的抗体或效应细胞在体内或体外发生特异性反应的 物质，图1 4 为抗原与抗体示意图，抗原表面被抗体识别的部分被称为抗原决定 基。根据现代免疫学抗原的概念，抗原必须具备两种特性，即免疫原性和抗原性。 图1 4 抗原与抗体 免疫原性 抗原的免疫原性是指抗原分子能诱导免疫应答的特性。免疫原性涉及抗原分 子与免疫细胞之间的相互作用，即抗原必须能够被抗原提呈细胞的加工、处理和 提呈作用，以及能被t 细胞和b 细胞的抗原识别受体所识别。因此抗原的免疫 原性与抗原分子的化学性质相关，更与机体的免疫应答特性相关。 抗原性 抗原的抗原性是指抗原分子能与免疫应答产物，即抗体或效应t 细胞发生特 7 异反应的特性，故称之为抗原的反应原性。它只涉及抗原分子与抗体分子或t 细胞的抗原受体分子之间的相互作用，即分子与分子间的的相互作用。只是抗原 分子表面的有限部位能与抗体分子结合，称此部位为抗原决定基。因此抗原的抗 原性主要决定于抗原分子的化学性质。如果抗原为蛋白质分子，其抗原性可决定 于其氨基酸序列或其空间构型。 ( 6 ) 抗体 抗体是b 细胞识别抗原后克隆扩增分化为浆细胞所产生的一种蛋白质分子， 也称为免疫球蛋白分子。抗体结合由外部入侵的感染微组织或者有毒物等抗原， 然后依靠自己或者借助免疫系统其他元素( 如t 细胞等) 帮助破坏这些抗原，消除 对人体的威胁。抗体由抗体决定基和独特型组成，抗体决定基是抗体上识别抗原 决定基的部分，而独特型是抗体上可供自身免疫细胞识别的抗原决定基。抗体是 具有两种截然不同的功能区的分子。一部分是保持相对静态状态的稳定区，称为 稳定区，简称c 区；而另一部分则是负责与不同的多种感染抗原结合的分子变 化区，称为可变区，简称v 区，图1 5 为抗体结构示意图。 基 图i 5 抗体结构示意图 可变区基本只关心抗原结合，稳定区与在宿主组织上的受体相互作用。两个 区域的不同导致多种抗体种群。c 区变化有限，v 区的变化使免疫系统在自适应 处理中具有一定的能力和速度。对免疫应答期间产生的抗体多样性的研究已经证 明v 区的体细胞变异随时间增加，正是可变区为免疫系统提供了大部分鲁棒性 和自适应能力。当一个外部抗原袭击身体时，抗原提呈细胞把外部分子分解到抗 原决定基层次，下一步是产生与抗原决定基结合的抗体。抗体由d n a 分子片段 随机重组产生。一旦抗原决定基层次发现匹配，一个特定信号就会发给b 细胞， 产生适合匹配的更多的抗体，用来中和外部抗原，消除入侵者和被感染细胞。 ( 7 ) 亲和力 免疫系统中的免疫识别是发生在分子水平的，并且这种识别是基于抗体决定 基和抗原决定基之间的形状互补。发生免疫识别的抗体决定基和抗原决定基在结 构上越互补，结合就越可能发生，结合的力度也就越紧密，这种结合的力度与强 度被称为抗体与抗原之间的亲和力。 抗体与抗原的结合就像一把钥匙开一把锁的关系。钥匙的形状与锁芯必须一 致。当然抗体与抗原在结构上不一定需要完全一致，但也必须在一定程度上匹配。 8 这样大致匹配具有较高亲和力的b 细胞，就可以通过体细胞高频变异和受体编 辑等途径实现亲和力的成熟，达到与抗原的高度匹配。 1 2 2 人工免疫系统理论的发展概况 迄今为止，人们根据应用对象不同，从不同的角度模拟生物免疫系统，提出 了不少有价值的a i s 网络模型。其中最为著名的是1 9 7 3 年，美国诺贝尔奖获得 者j e m e 提出了免疫网络理论而引起人们的关注 3 1 。1 9 8 6 年f a r m e r 等人基于免 疫网络学说给出了免疫系统的动态模型1 4 1 ，探讨了免疫系统与其它人工智能方法 的联系，开始了人工免疫系统的研究。1 9 8 9 年p e r e l s o n 在前人研究基础上，对 独特型网络进行了深入研究1 5 】。他从抗体形态空间理论的角度出发，开创了用二 进制编码描述抗体，研究免疫现象的方法。1 9 9 0 年f a r m e r 通过对免疫系统、神 经系统以及遗传系统的特点及其异同进行分析比较后，给出了基于联结主义的动 态系统模型基本特点的描述【6 1 。他们的研究工作为建立有效的基于免疫原理的计 算系统和智能系统开辟了新的道路。1 9 9 5 年h u n t 等人提出一种人工免疫系统 模型b 细胞网络，用于染色体的模式识别 7 - 9 1 。1 9 9 6 年p e r e l s o n 等人提出了形 状空间理论，他通过用二进制数编码表示抗体和抗原，用码位互补表示抗体对抗 原的识别，开创了用数学手段解释免疫系统多样性形成的研究 1 0 - 1 1 1 ；1 9 9 7 年， c h u n 等人将细胞理论和遗传算法相结合，提出了一种免疫遗传算法 1 2 - 1 3 1 ；随后， f u k u d a 提出基于克隆选择的函数优化。1 9 9 8 年，o p e r a 用二进制抗体模型研究 了免疫系统多样性原理和进化意义 1 4 - 1 5 l 。2 0 0 0 年，d ec a s t r o 等人对克隆选择机 理进一步浓缩和概括，提出了一种较为简介的克隆选择算法( c s a ) n 6 j - 【1 8 1 。该算 法以b 细胞的克隆选择理论为基础，用“抗原 表示优化解，用“b 细胞 表示 解的可能模式，通过b 细胞的高变异完成全局最优解的搜索。该算法结构新颖、 性能优良、能够保持模式的多样性，适合于求解复杂函数优化问题。2 0 0 1 年， t i m m s 等人在b 细胞网络理论和克隆选择原理的基础上，提出一种新的函数优 化方法【1 9 1 ；2 0 0 2 年，c a r l o s 等人以克隆选择为核心构造一种人工免疫系统，用 于求解多目标函数优化【2 0 1 。 目前，世界上绝大多数人工免疫系统研究成果出自美国、英国、日本。而巴 西c a m p i n a s 大学的d ec a s t r o 博士最早在其博士论文中总结了人工免疫系统，并 试图建立人工免疫系统的统一框架结构 2 1 1 。在人工免疫系统领域取得显著成绩 的主要有：利用免疫系统原理研究计算机安全的美国n e wm e x i c o 大学计算机科 学系的f o r r e s t 博士 2 2 1 ；研究基于免疫原理的计算机安全和异常检测及工业应用 的m i s s o u r i 大学计算机与数学系的d a s g u p t a 博士：研究数据分析的英国k e n t 大 学的t i m m i s 博士；研究计算机网络入侵的k i n g s 学院的k i m 博士：威尔士大学 9 e h u n t 和d e n s i ec o o k e 领导的i s y s 研究小组等。此外还有研究故障诊断的日本 n a r a 科学技术学院的i s h i d a 博士；研究机器人的n a g o y a 大学工程学院信息电子 部的i s h l g u i o 博士等。 国内对于免疫系统的研究较国外迟。1 9 9 8 年西安电子科技大学的王磊、焦李 成等在i c s p 9 8 上首先提出了一种免疫遗传算法并应用于一种典型的优化问题一 t s p 的求解中；2 0 0 0 年，东华大学的丁永生等在查阅大量文献的基础上发表了 有关人工免疫系统研究的综述文章一可以说，这是这方面国内科学界的第一篇较 为全面和实用的介绍文章。同年，王磊等提出了免疫规划算法 2 3 - 2 4 】。2 0 0 3 年， 哈尔滨工程大学的莫宏伟总结了国内外以及自己的研究成果【2 5 1 ，这是国内首次 对免疫系统较为详细的介绍。2 0 0 6 年，西安电子科技大学的焦李成等在全面总 结国内外人工免疫系统发展现状的基础上，着重根据自己在这一领域的研究成 果，对人工免疫系统理论及应用做了详细的总结，主要介绍了免疫算法、免疫克 隆选择算法、量子克隆计算、人工免疫网络等算法的构造及其工程领域的应用 犯6 1 ，也探讨了人工免疫系统进一步研究的方向。 1 3 基于人工免疫系统的优化算法 1 3 1 人工免疫系统与优化算法之间的关系 人工免疫系统由于它所具备的多种特性，使其在优化领域有着广泛的应用前 景，为研究新的优化算法及改进现有的优化算法提供了多种新的思路。 1 ) 免疫系统的动态进化性 免疫系统在与病原体之间相互竞争的同时，也在不断的进化。这一特性可用 于动态优化算法的求解过程，随着环境的变化，得到的优化解也是动态进化的， 而传统遗传算法一般是静态寻优，往往无法在线动态寻优，免疫系统的动态特性 以及与变化的不断适应过程，为动态优化提供了一种新的思路。 2 ) 免疫系统的多尺度进化特性 免疫系统实际上是一个在动态变化环境中通过自学习而不断完善的多时间 尺度进化系统。免疫系统的双时间尺度进化可分为d n a 分子生物进化的慢速学 习模式和用于免疫系统进化的快速学习模式两种。免疫系统的鲁棒性是在慢速学 习阶段，保证在外来攻击的大范围内获得满意的性能，免疫系统自适应性是在快 速学习阶段实现的。这对于单尺度优化算法提供了补充和扩展。 3 ) 免疫系统的搜索方式 免疫系统对于特殊的入侵抗原选择最适宜的抗体时，也经历了一种搜索“最 优抗体”的过程。免疫系统的搜索方式是将随机性和基于反馈的高度定向行为结 1 0 合起来。免疫系统在任何时候都有许多不同淋巴细胞，淋巴细胞上又存在大量的 抗原受体一抗体，可以捕获潜在的抗原，每一种受体都是通过父辈的遗传物质随 机组合形成。当一个抗原激活了一个特定的b 细胞并使其增殖，这是基于反馈 的高度定向行为，使生成的抗体越来越针对于这一特定抗原。而与此同时，免疫 系统内部仍存在大量的不同种类的抗体，准备识别新的抗原。免疫系统这种将随 机性与定向性相结合来进行搜索的特性，使得免疫系统在深度搜索和广度搜索之 间取得了平衡，这对于优化搜索方式也是一种启发。 4 ) 免疫系统抗体生存的周期性 免疫系统抗体群中，一般抗体的寿命很短，可能只有几天或几个星期，而记 忆细胞可以存活几十年，将这种免疫抗体生命周期引入优化算法。可以用于动态 环境中的种群个体的不同适应性的标度，在大范围内具有适应性的个体将具有较 长的寿命，而只能在小范围内适应的个体的寿命较短，这样种群个体具有不同的 生命周期，可以获得动态优化的效果。 1 3 2 免疫优化算法的研究现状 目前，优化领域中应用的免疫优化算法主要有以下几种：( 1 ) 基于克隆选择 原理的免疫优化算法，这种算法利用免疫系统克隆选择的机制来实现优秀抗体的 扩展和增生，并利用了免疫系统中的记忆机制保证了算法能够最终收敛到全局最 优解；( 2 ) 基于免疫系统的抗体浓度调节原理的免疫优化算法，这种算法利用抗 体多样性保持机制，改进传统的遗传算法，提高了算法的群体多样性，能有效地 抑制早熟现象，使免疫遗传算法具有较好的全局收敛性；( 3 ) 基于免疫响应的免 疫优化算法，这种算法引入了免疫记忆和抗体多样性等免疫特性；( 4 ) 基于免疫 疫苗接种的免疫优化算法，该算法引入疫苗接种的概念，能充分利用问题的先验 知识，改善算法的性能，在优化问题中获得了良好的效果；( 5 ) 基于免疫抗体记 忆的免疫优化算法，这种算法将随机搜索过程中的局部搜索和全局搜索采用不同 的促进和抑制策略，有效保证了算法的收敛速度。 人工免疫系统在函数优化、组合优化、调度问题、电网规划、神经网络优化 等许多的优化领域中得到了应用并取得了很好的效果 1 1 。由此可见，免疫算法本 身所具备的特性，决定了免疫算法对于各种优化问题的求解有着巨大的潜力，可 以预见免疫优化算法将会在优化领域中得到广泛的应用。 1 4 本文主要内容 1 、针对2 0 0 2 年d ec a s t r o 提出克隆选择算法( c l o n a l g ) 中克隆选择操作和变 异操作不足，提出改进的克隆选择操作和变异操作；首先分析经典c l o n a l g 存在的一些不足： ( 1 ) 在克隆选择操作中，该算法分两个过程，首先是从a b 中选择拧个最优 个体，然后是从c + 中选择刀个个体。对于第二个过程，该操作只是单纯的从变 异后的抗体群中选择n 个最优个体进入下一代。通过分析可以发现，如果变异的 步长较大，父代抗体经克隆、变异操作后有可能从一个较低的波峰跳到另一较高 的波峰，从而丢失了较低的波峰，这样就不利于多峰值函数优化。 ( 2 ) 在变异操作中，该算法采用与抗体适应度有关的高斯变异，而高斯变 异产生的随机数的范围较小，所以它跳出局部极值区域的速度较慢，甚至难以跳 出局部区域；。针对以上的不足，本文提出新的克隆选择操作和克隆变异操作对 其进行改进。 2 、对经典的静态最短路径算法如：d i j k s t r a 算法【2 7 1 、f l o y d 算法【2 8 1 、启发式算 法 2 9 1 以及动态最短路径搜索策略等进行分析研究，并在此基础上对算法的道路 网表达式、网络的存储结构、搜索策略等方面的优化进行研究，提出了一种新的 动态路径多目标优化方法。首先根据路段上交通状态动态变化的特点，