（计算机应用技术专业论文）基于克隆算法的模糊规则提取及其应用研究.pdf

摘要 对于一个分类问题，分类之前我们必须首先对被分类事物进行特征提取，再 根据特征来实现其分类。而无论用哪种手段哪种方法提取的特征值一般情况下都 是没有明确界限的、模糊的，这就为我们的问题解决带来了一定的困难。而模糊 逻辑则正是一种建立在自然语言基础上并模拟人类的模糊思维来描述和解决该类 问题的有力工具，其核心是依据学习样本特征所建立的模糊规则集合。传统上模 糊规则的提取都是通过专家经验人工提取的，这是一个相当繁琐的工作，对于分 类问题，所提取的规则不仅在分类能力上要达到最优，同时在各分类规则之间的 关系上也要达到最优，这就是人工提取规则的困难所在。目前用于解决分类问题 的模糊规则的提取方法还比较少，本文则结合人工免疫系统的克隆选择原理，采 用克隆算法，提取通过多精度模糊分割产生的大量模糊i f t h e n 规则中的少数精 华规则，从而建立了模糊分类所需要的有效规则集合。由该方法所提取的模糊规 则具有分类准确率高，规则数目较少，识别时间短的特点。为了检验该方法的性 能，我们还将该方法用于车型分类的研究，其结果是令人满意的。 本文所采用的克隆算法包含两个最为重要的过程，一个是高频变异，另一个 是受体编辑，高频变异负责局部寻优的微观调控，而受体编辑则进行宏观控制保 证全局寻优的实现，二者保持抗体种群的多样性，在功能上互相补充，使抗体和 抗原的亲和力快速成熟。另外，在我们将该规则提取方法应用与车型分类问题的 研究中，还对该具体问题涉及到的特征提取进行了研究，通过小波分解提取了车 辆感应信号关于小波能量、均值、方差的四个特征，在一定程度上保证了车型识 别的准确率。 关键词：模糊规则；克隆算法；高频变异；受体编辑；车型分类：小波分解 a b s t r a c t f o rac l a s s i f i c a t i o np r o b l e m ，w em u s te x t r a c tt h ef e a t u r e so ft h ec l a s s i f i e do b j e c t s f i r s t ，t h e n ，c o m p l e t et h i s t a s ka c c o r d i n gt ot h ef e a t u r e s w h a t e v e rm e a s u r ea n d t e c h n i q u ew e r eu s e dt oe x t r a c tf e a t u r e s ，t h ef e a t u r ev a l u e sg a i n e da l lh a v en oc l e a r b o u n d a r y ，a n dt h e ya r ef u z z y ，t h a tb r i n gu sal o to fd i f f i c u l t yf o rt h ep r o b l e mr e s o l v i n g h o w e v e r ，f u z z yl o g i ct h a ti sb a s e do nn a t u r el a n g u a g ea n di m i t a t e st h ef u z z yt h o u g h t o fh u m a ni sj u s tap o w e rt o o lt oc h a r a c t e ra n dr e s o l v et h u sp r o b l e m s ，a n di t sc o r ei s f u z z yi f - t h e nr u l e sc o n s t r u c t e db yt h es t u d yp a t t e r nf e a t u r e s c 0 n v e n t i o n a l l y ，f u z z y r u l e sa r ee x t r a c t e df r o me x p e r t sa n dt h a ti sav e r yf u s s yw o r k f o rac l a s s i f i c a t i o nt a s k ， t h ee x t r a c t e dr u l e sn o to n l ya r eo p t i m i z e di nc l a s s i f i c a t i o np o w e r ，b u ta l s ot h er e l a t i o n a m o n gt h er u l e s ，s o ，f e a t u r e se x t r a c t e da r t i f i c i a l l yi sd i f f i c u l t a tp r e s e n t ，m e a s u r e a b o u tr u l ee x t r a c t e da u t o m a t i c a l l yi sf e w t h i sp a p e rt h ee l i t er u l e sw e r ee x t r a c t e d f r o mam a s so ff u z z yr u l e sp r o d u c e db ym u l t i p l ef u z z yp a r t i t i o nb yc l o n es e l e c t i o n a l g o r i t h mp r o p o s e da c c o r d i n gt oc l o n es e l e c t i o nt h e o r yo fa r t i f i c i a li m m u n es y s t e m ， t h u sap o o lo fe f f e c t i v er u l e sa r ef u n d ，t h a th a v el e s s e r r u l en u m b e ra n dv e r yh i g h c l a s s i f i c a t i o nc o r r e c t n e s s ，a n dv e r ys h o r ti d e n t i f i c a t i o nt i m e t h ee l i t er u l e sw e r eu s e d i nr e a l t i m ev e h i c l ec l a s s i f i c a t i o nf o re x a m i n i n gi t sp e r f o r m a n c e ，a n dh a sm o r ee x a c t c l a s s i f i c a t i o nc a p a b i l i t yb yt h ec o m p u t e rs i m u l a t i o n ，i ti ss a t i s f i e d t h ec l o n es e l e c t i o n a l g o r i t h m i n c l u d e st w om o s t i m p o r t a n tp r o c e s s ， h y p e r m u t a t i o na n dr e c e p t o re d i t i n g h y p e r - m u t a t i o nm e c h f a n i s ma l l o wt h ei m m u n e s y s t e mt oe x p l o r el o c a la r e a sb ym a k i n gs m a l ls t e p st o w a r d sa na n t i b o d yw i t hh i g h e r a f f i n i t y ，l e a d i n gt oal o c a lo p t i m a ，r e c e p t o re d i t i n go f f e r st h ea b i l i t yt oe s c a p ef r o m l o c a lo p t i m ao na n a f f i n i t yl a n d s c a p ea n dr e a c h t h eg l o b a lo p t i m u m t h i st w o m e c h a n i cc a nk e e pt h ed i v e r s i t yo fa n t i b o d yp o p u l a t i o n ，a n dl e a dt oaf a s tm a t u r a t i o n o fa n t i b o d y - - a n t i g e na f f i n i t y ，a sar e s u l tt h ea l g o r i t h mc o n v e r g e n c et o ao p t i m a l s o l u t i o nm o r eq u i c k l ya n dm o r es t a b l e ，t h a ti st h ec a u s et h a tt h ea l g o r i t h mw a ss e l e c t e d i nt h i sp a p e r i na d d i t i o n ，a n o t h e rp i v o t a lp r o b l e m ，f e a t u r ee x t r a c t i o n ，w a ss t u d i e di n v e h i c l ec l a s s i f i c a t i o nw h e nt h em e a s u r ep r o p o s e di nt h i sp a p e rw a sa p p l i e dt ot h i s i s s u e i nt h i sp a p e r ，w ee x t r a c t e df o u rw a v e l e tf e a t u r e sa b o u tt h ev e h i c l ei n d u c t i v e s i g n a li n c l u d i n gw a v e l e te n e r g y ，a v e r a g ev a l u ea n d d i v i a t i o n t h e s ef e a t u r e so v e r c o m e t h ei n f l u e n c eo fv e h i c l es p e e di nv e h i c l ei d e n t i f i c a t i o nd y n a m i c a l l y ，a n de n s u r et h e a c c u r a c yo ft h ev e h i c l ec l a s s i f i c a t i o n k e y w o r d s ：f u z z yr u l e s ；c l o n a ls e l e c t i o na l g o r i t h m ；h y p e r - m u t a t i o n ；r e c e p t o r e d i t i n g ；v e h i c l ec l a s s i f i c a t i o n ；w a v e l e td e c o m p o s i t i o n i 长沙理工大学 学位论文原创- i 生声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 去拂娟 日期：埘年4 月；o 曰 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 五妫4 3 日期：诃年鲆月；d 日 导师签名： 叶前日期：柳j ，年于月f f + 日 1 1 研究背景 第一章绪论 在我们的现实生活中总是存在着大量具有不确定性和不精确性的事物，当然， 这里的不确定是一个相对的概念，即在某种条件或范围内是确定的和精确的，而 在另一种条件或范围内就是不确定和不精确的，我们称此为一个模糊的概念。比 如说“小型车”，何所谓“小”呢? 这就是一个模糊的概念。正是由于现实生活 中事物模糊性的普遍存在，所以常常使我们对事物的分类造成极大的困难。然而 由美国著名自动控制理论专家l a z a d e h 子2 0 世纪6 0 年代引入的模糊逻辑则正 是一个用来表示并解决模糊的和不确定( 相对的) 知识的有力工具。模糊逻辑是 对模糊的、自然语言的表达和描述并进行操作和利用，它允许在模糊系统中纳入 常识和自学习规则，并意味着一个学习模块能够用一个模糊规则集合来解释其行 为。这样，模糊系统对于使用者来说就是透明的，它更易于为我们所理解和应用， 这与人工神经网络形成了直接的对比，因此模糊逻辑的理论和方法近年来不断得 到完善和发展，并日益受到人们的重视。正是由于模糊逻辑是建立在自然语言基 础上并模拟人类的模糊思维来描述与人类模糊思维方式、方法相关的宏观过程， 因此在模糊逻辑系统中其核心就是模糊推理规则的建立。但是在大多数情况下这 些规则都是来自人类专家的人工提取，所以一直以来模糊规则的提取都是一个相 当繁琐的问题。另外，对于分类问题，关于模糊规则实际上还不仅仅是一个简单 的提取问题，这正是由于事物模糊性的存在而使各类彼此之间存在内在的必然联 系，因此对于判定各类的规则也必然存在着内在的的联系，这样对于规则还存在 着一个优化的问题，而这些优化规则又不仅仅是其本身在分类能力上达到最优， 而是还要在所提取的优化规则间的关系上也要实现一个优化。 1 2 模糊规则自动提取方法概述及问题提出 从早期大量的有关模糊理论和模糊技术的文献中可以看出，对于模糊规则的 提取方法并没有其理论依据，基本上是人为决定的。最早的模糊规则提取一般是 由专家根据经验而得到的，往往不够准确，尤其是对于两个或以上的输入，人工 设定模糊规则就显得很困难，甚至是不可能的。近几年来，一些专家学者提出了 从输入一输出数据中产生模糊规则的若干方法，例如，r o s k o 提出的空间聚类方法 i l l ，l i n 用b p 网络辩识模糊规则和调整隶属度函数的方法【：i ，以及i s h i b u s h i 等建 立的一个带有模糊权和模糊阈值的多层前馈神经网络吲，在这些思想方法的引导 下，国内外一些控制理论及计算机科学领域的专家学者又提出了各种力求全局最 优的模糊规则的提取方法，并在隶属函数的参数调整方面也做了大量的研究工作。 如【4 】提出了一种基于径向基函数神经网络( r b f ) 的模糊规则提取的新方法，在 【5 】中刚使用模糊联想记忆方法来实现分类，在【6 】中提出利用决策树方法来提取规 则。虽然有不少专家学者提出了关于模糊i f t h e n 规则自动产生的方法i m ii m ，其中大 部分采用的是人工神经网络的方法1 1 0 p 1 1 2 ，但由于人工神经网络存在网络规模和网 络结构较为复杂以及学习收敛性等问题，因而对于模糊规则的自动提取效果并不 十分理想。随着生命科学与工程科学的相互交叉、相互渗透和相互促进，一系列 的进化计算方法得以形成。其中最具影响力的进化计算方法之一就是遗传算法 一i l l s ，遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于 并行处理以及应用范围广等显著特点，奠定了它作为2 1 世纪关键智能计算之一的 地位。正是遗传算法上述的诸多优点，最近又形成了许多将遗传算法用于产生模 糊i f t h e n 规则1 1 6 卜f 2 1 】的方法。另外，许多专家学者在模糊系统和神经网络的结合 方面也做了大量工作，如 2 2 1 中，综合了模糊系统和神经网络的优点，一方面考虑 了专家的经验，另一方面利用样本集进行学习，来自动提取模糊规则和优化隶属 度函数。尽管提出了上述产生模糊i f t h e n 规则的一系列方法( 包括采用遗传算 法产生模糊规则的方法) ，其主要是用于解决控制问题1 2 a 1 1 2 4 ，而用于解决分类问 题的方法却比较少。目前，关于模糊推理规则的自动产生方法中，比较有代表性 的是i s h i b u c h i 等人在 2 5 】中提出的一个新的产生模糊i f - - t h e n 规则的方法，该方 法由两个阶段组成：首先，将一个模式空间分割成几个模糊子空间；其次，确定 每个模糊子空间的模糊i f t h e n 规则。 在 2 5 1 中，模式空间的模糊分割采用的是简单的模糊网格分割形式，见图1 1 。 区这这趟 图1 1 模式空间的模糊分割 在该例中，一个二维模式空间被分割成5 2 = 2 5 个模糊子空间。由该图我们可 以看出，基于模糊i f t h e n 规则的模糊分类系统的执行效果有赖于如何选择模糊 2 分割。如果一个模糊分割过于“模糊”，那么该系统的分类能力可能会非常差，这 时可能会出现多类样本同时落入同一个模糊子空间，从而造成该模糊子空间较差 的分类能力而在进行分类识别时产生错误的分类结果。而如果一个模糊分割过于 精确，那么就会产生过多的模糊子空间，这样由于许多模糊子空间缺乏训练样本 而无法产生模糊i f t h e n 规则；另外由于分割过细，也可能出现原本一个模糊子 空间就能确定的类此时却由几个模糊子空间来同时确定，从而造成规则的冗余。 所以选择一个恰当的模糊分割就显得尤为重要。然丽有时候只确定一个合理的模 糊分割仍然是不够的，让我们考虑下面的一个两分类问题，见图1 2 。 图1 2 一个分类问题 这里黑点表示模式类1 ，圈表示模式类2 。 对于该分类问题，模式空间的左半部分需要一个精确的模糊分割，但是对于 右半部分则需要一个较为“模糊”的模糊分割。因此，基于一个简单的模糊网格 的模糊分割对于图1 2 这样的分类问题就显得比较困难。为了解决这样的困难，在 f 2 5 忡提出了分布式模糊i f - - t h e n 规则的概念，将相应于几种的模糊分割所对应的 模糊i f t h e n 规则同时应用于模糊推理，即多个模糊规则表同时用于一个模糊分 类系统，见图1 3 。 输入 样本 一，输出 类别 图1 3 一个基于多模糊规则表的模糊分类系统 3 由图1 3 可以看出，对于一个二维模式空间，相应于5 个模糊规则表共产生 2 2 + 3 2 + 4 2 + 5 2 + 6 2 = 9 0 个模糊i f t h e n 规则构成了一个模糊分类系统。在该分类 系统中，由于同时用到了相应于粗糙模糊分割和精确模糊分割的模糊i f t h e n 规 则，因而解决了前面所提到的在选择恰当模糊分割时所遇到的困难，提高了分类 精度。然而该方法存在着一个缺陷，就是采用该方法会使模糊i f t h e n 规则的数 量变得非常巨大，尤其是对于高维模式空间的分类问题。显然，由该方法得到的 模糊i f t h e n 规则并不都是有效规则，即使有效规则其有效程度也不尽相同。如 果去掉那些不必要的模糊i f t h e n 规则，选择出相关的规则并在这些规则中提取 少量但更为有效的模糊i f t h e n 规则，那么这与未进行无效规则的剔除和有效规 则的提取之前相比，该方法将会大大减少模糊i f t h e n 规则的数量而又几乎不影 响模糊系统的分类能力，甚至具有更强的分类能力。 而对于一个具有少量模糊i f t h e n 规则的紧凑的模糊分类系统应该具有以下 特点： 不需要大量存储( 较少的规则个数) ； 具有较高的分类能力； 对新样本的推理具有较高的速度； 每个模糊i f t h e n 规则都可以由用户检验。 最后一条表明了获取新知识的可能性。当少量有效的模糊i f t h e n 规则选定 后，用户通过仔细检查所选择的规则，就可以从中获得新的信息知识。相反，如 果一个模糊分类系统中包含了成千上百条模糊i f t h e n 规则，那么要检查所有的 规则也并非易事1 1 3 免疫理论的新发展 实际上在上一节的最后我们就提出了一个用于分类问题的多模糊分割规则优 化问题。说到优化问题，最值得我们关注的也是一直倍受国内外专家学者普遍关 注的就是生物信息系统的计算能力1 2 6 卜1 3 ”。随着生命科学与工程科学的相互交叉渗 透和促进，一系列进化计算方法得以形成，其中最具影响力的要属遗传算法。而 除此以外，目前特别值得一提的也是近年来受到国内外众多学者的高度重视的就 是免疫计算。 科学家已经证实，人体的免疫系统是一个具有高度分布性的自适应学习系统， 具有完善的机制来抵御外来病原体或细菌侵入。研究还表明，生物免疫系统具有 良好的多样性、耐受性、大规模并行分布处理、自组织、自学习、自适应、免疫 记忆和鲁棒性等特点1 3 2 1 3 3 ，并且免疫系统的这些特点对于许多领域的问题研究与解 决起到了深刻的启发作用，从而导致了计算机免疫学产生及发展。 关于免疫理论的新发展，澳大利亚学者b u r n e t 于1 9 5 8 年率先提出了克隆选择 4 原理，并于1 9 6 0 年因此而获得诺贝尔将。1 9 7 8 年他本人又对该原理予以完整阐述 1 3 2 1a 1 9 9 9 年，h u n t 进一步发展了克隆选择理论，并提出了高频变异学说。克隆选 择原理是免疫系统用来说明抗原刺激所产生的免疫应答基本特征的算法理论，其 基本思想就是只有那些能够识别抗原的细胞才进行分裂扩增，同时被免疫系统选 择和加以保留作为记忆细胞。随着同种抗原的不断侵袭，被保留的抗体不断发生 分裂，在分裂的过程中产生变异，我们称之为高频变异。变异后的优秀( 与抗原有 较高的匹配能力，高亲和力) 抗体继续被选择保留，以各抵抗下次的抗原侵袭。这 样，经过若干次抗原的侵袭后，抗体的和抗原之间的亲和力越来越高，达到亲和 力成熟，从而对该种抗原具有较高的消灭能力。除此以外，免疫系统还具有受体 编辑的能力，即重新产生新的该类抗原的抗体，他们也不断的发生高频变异达到 亲和力成熟。但是受体编辑避免了高频变异陷入局部最优的可能，从而在宏观上 控制了全局寻优的过程，高频变异则从微观局部进行寻优调控。 因此免疫学的克隆选择原理是以贪婪搜索为特征，同过累积的盲目变异和受 体编辑方法来保持抗体的多样性。克隆算法正是基于壳隆选择原理的这些优良特 性而提出的，它与遗传算法相比引入了受体编辑机制以及更加合理的变异机制因 而更易于理解和便于操作。本文正是基于克隆算法优良的寻优能力从相应于多个 模糊分割的模糊i f t h e n 规则中去掉不必要的规则，提取出一个具有高效分类能 力的紧凑的模糊规则集，从而实现其分类功能的。 1 4 本文方法概述 综上所述，本论文提出了一种解决分类问题的基于克隆算法的模糊i f t h e n 规则提取( 优化) 方法，该方法中模糊i f - - t h e n 规则的选择的实现是通过克隆算 法对由两个目标构成的组合优化问题的优化求解而实现的，该组合优化目标分别 是：1 、最大化模糊规则集中规则的分类能力，包括规则能正确分类的样本个数及 其确定度1 3 4 1 3 5 1 ；2 、在保证正确分类率的情况下，最小化规则集中模糊i f - - t h e n 规 则的数目。我们将一系列模糊i f t h e n 规则编码为一个数字串，作为克隆算法中 的抗体，每个抗体的亲和力计算函数即由上述的两目标组合优化问题确定。通过 克隆算法我们对由规则作为基因组成的抗体进行克隆、高频变异和受体编辑等操 作从而得到满足目标函数的最优解，也即提取出具有较高分类能力的优质分类规 则，实现我们的目标。 1 5 论文的结构安排 本论文主要研究用于解决分类问题的模糊i f - - t h e n 规则的提取及其相关问题。 论文章节安排和各章的主要内容表述如下： 5 第二章介绍克隆选择原理和算法，本章首先从生物免疫系统的角度出发对克 隆选择原理进行了详细的阐述，然后结合计算机应用，重点把握克隆选择原理中 的克隆、选择、高频变异、受体编辑、克隆扩增等过程给出了克隆算法的过程： 第三章和第四章为本论文的核心部分，第四章详细介绍了本文提出的基于克 隆算法的模糊i f - - t h e n 规则提取的过程，同时还分析了对算法造成影响的可变参 数的选取： 第四章本章作者将本文所提出的基于克隆算法的模糊i f - - t h e n 规则提取方法 具体应用于车型分类，通过对该应用的各项仿真试验检验，从各方面说明了本文 所提方法的性能，论证了该方法的分类准确性，收敛速度及寻优能力。 论文最后对全文进行了总结。 6 2 1 引言 第二章克隆选择原理及克隆算法 免疫系统的免疫应答过程分为三个阶段：抗原识别；免疫细胞活化；免疫效 应1 3 6 1 。免疫系统的克隆选择原理，如图2 1 所示，反映了自适应免疫系统受到抗 ，参耄：三瑟 争克隆舭、： - ? 6 ，。夸。 联i 。蚤 原刺激时发生的免疫应答的基本特征，即特异性1 3 7 】、记忆性i ”l 和识别“自己”和“非 己” s 9 1 4 0 。克隆选择原理的基本思想就是只有那些能够识别抗原的细胞才能进行分 裂扩增，并被免疫系统选择和加以保留作为记忆细胞；而那些不能识别抗原的细 胞则不被选择，也不进行克隆扩增。在克隆选择过程中，所选择的细胞服从亲和 力成熟过程h 1 f 4 z j ，即随着抗体分子与同种抗原的多次遭遇，抗体与抗原的平均亲和 力不断提高，从而具有更高的消灭抗原的能力的过程。在亲和力成熟过程中有两 个机制起着特别重要的作用，那就是高频变异和受体编辑1 4 1 h “】。对于亲和力成熟 过程，前者微观调控，后者宏观控制，不断的保持抗体的多样性，从而有利于最 佳抗体的出现。克隆算法，正是基于免疫学中的克隆选择原理而提出的种人工 免疫算法，该方法对具有较高亲和力的抗体( 可行解) 进行克隆，以贪婪搜索为 特征，通过累积的盲目变异以及受体编辑方法保持抗体的多样性，从而更有利于 产生复杂优化问题的最优解。 2 2 克隆选择原理 在免疫学中，凡能刺激生物机体，由生物机体的自适应免疫系统识别并能与 之发生特异性结合产生特异性免疫应答的物质，我们称之为抗原。而生物体中这 种会辨认抗原并能与之结合引发特异免疫反应的物质就是抗体。抗体是种特殊 的蛋白质分子，主要黏附于b 细胞( b 淋巴细胞) 表面，而且不同的b 细胞携带 的抗体种类也不相同。抗体和抗原发生特异性结合，即抗原和抗体的匹配是具有 针对性的，只有那些能识别抗原的抗体才会与其发生结合。盛行于2 0 世纪4 0 年 代的教导说( i n s t r u c t i o nh y p o t h e s i s ) 认为带有不同抗体的b 细胞最初并不是分别带 有不同抗体的，只是在它们与抗原分子接触之后，在抗原分子的影响下才分化出 与抗原分子的抗原决定基互补的抗体。但现已证实，b 淋巴细胞不需要任何抗原 的作用，就已分化为多种带有不同抗体的细胞了。当一种抗原侵入生物机体后， 在无数种淋巴细胞中，只有表面本来就带有和这种抗原互补的抗体的少数b 细胞 才能与其结合。而且这种b 细胞一旦和抗原结合，就会在介导细胞，如辅助t 细胞的= 次信号作用下被激活并具有分裂能力，并且连续分裂产生大量带有该种 抗体的b 淋巴细胞群。由于这群b 淋巴细胞同源，它们都携带有同一种抗体，所 有我们称该过程为细胞克隆( c l o n e ) 。这些b 淋巴细胞最终停止分裂成为成熟( 不 再分裂) 的细胞，这时的b 细胞分裂为两类细胞，即长寿浆细胞和长寿免疫记忆 b 细胞，如图1 所示。其中浆细胞是最活跃的抗体分泌器，可以分泌大量的抗体。 但是，这时的抗体与抗原的结合力( 或称抗体和抗原的亲和力) 比较低。记忆细 胞不能分泌抗体，它们通过血液、淋巴、组织在生物体的全身循环，并且当再有 同类抗原入侵时，随即迅速开始分裂为大量的淋巴细胞，这些b 细胞重新分裂成 熟产生具有更高亲和力的抗体。当生物体受到同一种抗原的多次感染，生物体的 免疫系统会发生多次免疫应答后，b 细胞所携带的相应抗体和该种抗原的亲和力 也在不断提高，从而不断提高机体的免疫能力，更有力的消灭该种抗原。以上即 为克隆选择原理。 b 细胞与抗原结合而发生分裂，这时细胞以极高的频率发生有丝分裂，并且 其中部分抗体在分裂过程中发生变异，我们称之为细胞的高频变异，这是克隆扩 增期间产生的重要变异形式。高频变异对于受体多样性的产生及局部最优抗体的 产生起着重要作用。除此之外，在克隆选择过程中b 淋巴细胞还会经历受体编辑 过程，即去除携带抗体亲和力较低的b 淋巴细胞，并通过v ( d ) j i t t l ( 可以造成基因 突变) 再结合生成全新的抗体，避免免疫应答陷入高频变异造成局部最优停滞， 从而增加获得全局最优抗体的机会。因此克隆选择中的高频变异和受体编辑对于 抗体指令系统的多样性和免疫应答的快速成熟是非常重要的两个过程。因此克隆 选择原理主要具有以下几个特征蛳”t j ： 携带能够识别抗原的抗体的b 细胞在抗原的肃j 激下发生分裂增殖； 由于细胞在高速分裂过程中发生随机变异，因而抗体表现为不同的形式，并 且随着对于同一种抗体免疫应答的重复，抗体的亲和力不断提高，服从亲和力成 熟过程； 不断的去除分化后的淋巴细胞中亲和力较低的个体，并加入重新合成的细胞， 实现受体编辑，提高抗体多样性。 2 2 1 免疫学习和免疫记忆 免疫系统学习主要目的是为了提高那些能够识别某种特定抗原的淋巴细胞的 相对种群大小及其与抗原之间的平均亲和力。因此当我们根据克隆选择原理来解 决实际问题( 抗原) 时，并不是要对每个候选抗体( 解) 都进行大量的克隆，而 是根据抗体种群中抗体和抗原之间的亲和力大小来对抗体进行克隆。抗体种群中 亲和力越高的抗体其克隆的抗体个数相对于亲和力低的抗体来说就越多，并且还 需要丢弃删除一些低亲和力的抗体，同时保留一部分亲和力较高的抗体作为记忆 抗体群。这样处理问题的目的是根据克隆选择原理以最小的代价来解决问题，因 此我们的任务就是寻找出数量最少质量最高的解。 在一般的免疫系统进化过程中，认为一个生命有机体在其一生中会不断遭遇 到同一种特定的抗原的感染。为了更加详细的说明白适应免疫系统的学习机制， 我们假设一个抗原a g 在0 时刻进入有机体，并且在生物体中它发现了几个能够识 别抗原a g 的特异抗体，经过定潜伏期后，这种抗体的浓度开始升高，并且上升 到一定的水平。但需要注意的是，此时该种抗体的含量仍然较低，因此维持时间 短，在与抗原a g 相结合，对其进彳亍_ 消灭后其浓度又迅速下降，这种现象称为初次 免疫应答( p r i m a r yr e s p o n s e ) 。在最初遭遇抗原的初次自适应免疫应答中，只有 少量能识别该抗原的b 细胞发生科隆，所以产生的抗体种群并不是很大，且与抗 原相结合的抗体的平均亲和力较低。在初次应答中除了一部分抗体来消灭抗原外， 还有另外一部分亲和力较高的抗体保留下来作为免疫记忆细胞，它这些记忆细胞 通过血液、淋巴、组织在生物体的全身循环，当该有机体再次遭遇同类抗体的感 染时，由于对于第一次感染的记忆细胞的存在，免疫系统随即以较初次免疫应答 更快的速度进行再次免疫应答( s e c o n d a r yr e s p o n s e ) ( 或称回忆应答) ，这时抗体出 现的潜伏期较初次应答明显缩短，产生抗体的平均亲和力较初次免疫应答也更高、 种群规模也更大来消灭同种抗原，同时再次保留其中部分亲和力较高( 高于初次 免疫应答产生的记忆抗体的亲和力) 的抗体作为下次免疫应答的记忆抗体。由此 可见，再次免疫应答与初次免疫应答相比其效果明显提高了，见图2 2 。 这样，在与同一种抗原的多次遭遇之后，就能够产生亲和力不断提高的抗体。 因此每次的免疫应答并不是总是从零开始，这样的学习机制确保了免疫应答 的速度和准确性在几次感染之后会变得越来越好。由此可见，免疫系统采用的加 强学习机制m ，这使系统能够不断提高其执行任务的能力。 摭 体 浓 废 图2 2 初次及再次应答抗体产生的一般规律 另一方面，关于免疫记忆的一个重要特点就是它具有联想性；对于能够识别 特定类型抗原a g l 的b 细胞，它不仅对抗原a g l 提供较快较有效的再次应答，还能 对任何与a g l ；f h 似结构的抗原! t l l a g l + a 9 2 提供再次应答。该现象称为免疫交叉反 映，或者称为交叉反映免疫应答m n w 。这是因为两种抗原的决定基具有相似的+ 结 构。在其他人工智能领域中，如神经网络m ，称之为概括能力。联想记忆的一些 特点在人工免疫系统中特别重要，它可以通过一个不完整的或遭到破坏的样本信 息来恢复该样本。对于含噪数据，甚至对于缺乏记忆成分的情况通常具有很强的 鲁棒性。 2 2 2 亲和力成熟 随着抗体分子与同种抗原的多次遭遇，记忆应答中的抗体与较早的初始应答 中的抗体相比一般具有更高的平均亲和力。这个现象( 仅限于t 辅助细胞下的应 答) 被称为免疫应答的亲和力成熟。由此可见免疫应答的亲和力成熟要求成熟应 答中的抗体分子的抗原结合点在结构上与在初次应答中抗体分子的抗原结合点不 同。在克隆选择过程中，所选择的细胞就服从亲和力成熟过程。在t 细胞辅助的 免疫应答中，亲和力成熟过程主要是由两种重要机制构成的，即高频变异和受体 编辑，以实现由抗原激活的抗体指令系统多样化。对于亲和力成熟过程，前者微 观调控，后者宏观控制，不断的保持抗体的多样性，满足免疫应答亲和力成熟的 要求，从而有利于最佳抗体的实现。 在抗体的高频变异中采用的是随机的点变异机制，这样的变异有时会导致较 高亲和力抗体的出现，于是这些高亲和力的抗体被选择进入记忆细胞群。而受体 编辑则可以将抗体种群中亲和力较低的抗体去除并通过v ( d ) j ( 可以造成基因突 变) 重新合并形成全新的受体，加入抗体种群。受体编辑为免疫应答的亲和力成 熟提供了一种从亲和力风景的局部跳出，避免寻优局部停滞的能力，从而弥补了 高频变异容易陷入局部最优的缺陷，见图2 3 。在图2 3 中，x 轴表示抗体 1 0 以 黔w m 一铷 抗原结合点 图2 3 高频变异和受体编辑 所有可能的抗原结合点结构，其中结构相似的抗原结合点彼此临近，形成一个局 部区域。y 轴表示抗体和抗原的亲和力。假设在初始免疫应答中选择了一个特定抗 体4 6 ，于是随机的点变异可以使免疫系统以较小的步伐探索4 6 ，周围的布局区域 并朝着使抗体亲和力升高的抗原结合点方向迈进，从而到达一个局部最优彳舛。由 于在高频变异后只有亲和力高的抗体得以保留，而亲和力较低的抗体则被丢弃， 因此高频变异搜索只能朝着亲和力升高的上山方向进行，而不能进行下山搜索。 这样正如前面所说高频变异常常会造成寻优的局部停滞。而受体编辑则可以使抗 体以较大的步伐跨越亲和力风景，并落在另一个局部区域的某一抗原结合点a b ：， 通过高频变异搜索达到该局域的最优a b ：。但有时候，受体编辑也可能使抗体落在 一个非常有希望达到全局最优的局域位置a b ，根据高频变异的微调作用达到全局 顶峰a b ，。所以高频变异在局部区域内起到微调的作用，非常有利于局部区域探索， 寻找局部最优。而受体编辑则在全局寻优中发挥宏观控制的作用，弥补了高频变 异的不足。 除了高频变异和受体编辑之外，骨髓还会产生一小部分新的淋巴细胞加入淋 巴细胞群以保持抗体的多样性。按照【7 3 1 ，每代中至少有5 8 受刺激的淋巴 细胞被新生淋巴细胞替换，并且可以产生和受体编辑相同的效果，即可以对抗原 结合点进行更广阔的全局寻优。 对于高频变异还有一点需要补充的是高频变异的规则。对于免疫应答的快速 成熟，就必须要有一个迅速积累的变异，但实际上其中大部分的变异都会导致更 差或者根本无效的抗体。即使一个细胞刚刚发生了有效变异，但是如果在下次免 疫应答时该细胞继续以相同的变异率变异时，不利变异的积累可能导致有利的变 异的丢失，那么同样可以导致无效抗体的产生。然而选择机制为此提供了一种方 法，即在高频变异过程中，根据抗体的亲和力来决定其变异率。亲和力相对较低 的抗体以较高的变异率发生变异，亲和力较高的抗体则以较低的变异率发生变异。 a紫lllillllll| 持徉亲刊刀 因此随着抗体亲和力的逐步成熟，其变异率也逐步趋向于停止，变异率和抗体亲 和力成反比关系。高频变异可能会导致抗体的进一步成熟，但是如果他们的亲和 力以及克隆规模如果没有得到改善，那么这些抗体通常会死亡。 2 3 克隆算法 在讨论了克隆选择原理和亲和力成熟过程之后，接下来我们对于克隆算法的 讨论就变得很容易了。对于克隆算法的我们需要考虑的相关免疫问题主要有：1 ) 保留一个特异的记忆集；2 ) 选择并克隆最受刺激的抗体；3 ) 未受抗原刺激的抗 体死亡；4 ) 亲和力成熟；5 ) 对克隆的抗体重新选择，并保持抗体的多样性。实 际上克隆算法可以用于模式识别以及问题优化等任务。但由于本论文主要采用了 克隆算法在优化问题方面的功能，因此这里只重点讨论克隆算法在该方面的应用。 关于克隆算法在模式识别方面的应用流程见 5 4 ，下面我们首先介绍该算法中的用 到的符号表示 b 2 3 1 算法中的符号说明 在克隆算法中基本由两个指令系统( 群体) 串构成：一组是抗原a g ( a n t i g e n ) ， 一组是抗体a b ( a n t i b o d y ) 。其中抗体群a b 可以根据克隆算法的应用任务( 模式 识别、优化) 而分解为几个子群。下面对克隆算法中用到的符号进行说明，其中， 黑体字符( 如a g 、a b ) 表示矩阵，黑体斜体字符( 如a b ，) 表示向量，s 相应于形 态空间中的坐标轴，括号中的下标表示集的矢( 如a b 佃 ) 。 a b ：可用的抗体a b 指令系统，可将其分解为几个不同的子集( a b e s “， a b = a b r v a b 伽 ，rq - m = n ) 。 ? a b 。) ：记忆抗体指令系统( a b 。 e s ”，研s ) 。 a b ，l ：剩余的抗体指令系统( a b ， s “，r = 一所) 。 a be ：来自a b 的对于抗原a g ，的n 个亲和力最高的抗体( a b 厶) s ，ns n ) 。 a b 似：重新产生的d 个抗体，用来替换a bf ，) 中d 个低亲和力的抗体 ( a b d ) s 4 “，der ) 。 a g m ：m 个需要识别的抗原构成的群体( a g s ”“) 。 fj ：包括所有关于抗原a g j 的抗体亲和力向量( f ，辨：) 。 c ：由a b 厶 产生的。个克隆抗体群( c7 s “) 。c 在高频变异过程后表示 为c 广。 a bf ：从c ，+ 中选出进入记忆抗体群的候选抗体。 2 3 2 克隆算法的优化过程 按照前面介绍的克隆选择原理，在克隆算法中表现出的重要特征中，高频变 异( h y p e r m u t a t i o n ) 和受体编辑( r e c e p t o re d i t t i n g ) 是其最重要的组成部分，他们 是实现抗体指令系统多样性的保障。根据克隆选择原理，克隆算法只对具有高抗 原亲和力的抗体进行克隆扩增，在高频变异中引入盲目( 随机) 的变异机制，并 只选择其中亲和力得到改善的成熟后代。该机制说明该算法执行的是一个贪婪的 搜索，对其中每一个抗体都进行局部优化( 探索其周围的空间，并朝着抗体优化 的方向前进) ，得到一系列局部极值。受体编辑机制正如前面提到的受体编辑过 程，则提供了一种消除局部极值的能力从而进行更大范围的搜索。除了高频变异 和受体编辑之外，从骨髓新产生的那部分细胞被加入淋巴细胞，以维持群体的多 样性。其效果同受体编辑一样，从而有可能找到更好的抗体。这些特点使得克隆 算法更加适合解决目标优化任务，尤其是多峰值目标优化问题。克隆算法用于目 标优化的操作如下： s t e p1 随机产生条长度为的初始抗体，构成初始抗体种群a b s t e p2 建立目标函数，( ) ，即引入抗原。 由于在目标优化问题中，只有一个目标函数，( ) 需要优化( 最呔化或最小化) ， 即在抗原种群a g 中只包含一个抗原，因此整个抗体种群a b 就构成了该抗原的记 忆抗体群a b 。将其放入抗体指令系统a b = a b 卅l ，这样对于一个特定的抗体 可以计算得到一个相应于目标函数( 抗原) 的亲和力，因此抗体种群a b 中的每个 抗体a b 表示输入空间的一个元素。 s t e p3 确定抗体种群a b 中所有个抗体关于抗原( 目标函数) 的亲和力 f 。 s t e p4 从a b 中选择，1 个亲和力最高的抗体构成一个新的关于抗原的高亲 和力抗体集合a b 。 。 一， s t e p5 对于s t e p4 所选择的抗体种群a b 中的抗体分别进行复制。 由s t e p4 选择的各抗体的克隆个数与其相应于抗原的亲和力成正比，即对于n 个所选抗体，与抗原亲和力越高的抗体其克隆的个数越多，从而产生一个克隆抗 体指令系统c 。 s t e p6 克隆抗体种群c 发生变异。 该克隆抗体指令系统c 在分裂的过程中会发生随机点变异，且其中的每个抗 体发生变异的概率与其抗原亲和力成反比，即克隆抗体指令系统c 中的抗体，与 抗原亲和力越高的抗体变异率越低，产生一个变异的克隆抗体种群c 。 s t e p7 确定变异克隆抗体种群c 中每个抗体关于