（教育技术学专业论文）基于免疫策略的基因表达式编程在函数挖掘中的应用.pdf

天津师范人学硕士学位论文 摘要 函数挖掘作为数据挖掘的一种，成为近十年来数据库界研究的又一热 点：由于基因表达式编程不需要太多领域知识和建立先验模型、染色体简单、线 性和紧凑、易于进行遗传操作，因此在处理函数挖掘问题中得到了广泛的青睐。 然而，函数挖掘的实践已经暴露出传统基因表达式编程( g e p ) 的缺陷：收敛 速度慢、易陷入局部最优等。在前人的工作基础上，本文针对g e p 存在的弊端， 借鉴免疫算法( i m m u n ea l g o r i t h m ，i a ) 抗体多样性和免疫记忆等优点，提出了一 种基于免疫策略的基因表达式编程算法( a r t i f i c i a li m m u n ei ng e n ee x p r e s s i o n p r o g r a m m i n g ，a i g e p ) 。 算法的核心在于保持种群的多样性，将免疫算法的免疫记忆机制用于g e p 算子中，通过引入优良记忆库实现精英保留策略，保证算法搜索的快速性及有效 性；通过引入差评记忆库实现评定及淘汰弱小的策略，以保证快速搜索和避免陷 入局部最优解。 a i g e p 算法有效地提高了算法的收敛速度，较好的保证了个体的多样性，避 免了传统基因表达式编程算法在进行函数挖掘出现的弊端。为验证a i g e p 算法的 正确性及有效性，将算法应用于函数挖掘。函数挖掘的仿真结果，进一步验证了 a i g e p 算法的性能，所挖掘的模型具有更高的拟合度和预测精度。 关键词：函数；数据挖掘；基因表达式编程；人工免疫算法 天津师范大学硕上学位论文 a b s t r a c t f u n c t i o nm i n i n g ，a sak i n do fd a t am i n i n g ，h a sa g a i nr e c e i v e dp l e n t yo fa t t e n t i o n s i nt h ed a t a b a s er e s e a r c hg r o u p ss i n c et h el a s tt e ny e a r s a m o n gv a r i o u sf u n c t i o n m i n i n gt e c h n o l o g i e s ，g e n ee x p r e s s i o np r o g r a m m i n g ( g e p ) h a sb e e nw i d e l ya p p l i e d i nc o m p l e xf u n c t i o np r o b l e m sb e c a u s ei tr e q u i r e sl i t t l ef i e l dk n o w l e d g ea n dn op r i o r m o d e la n ds i m p l i c i t y ，l i n e a r i t y ，c o m p a c ti nc h r o m o s o m e ，e a s yg e n e r i co p e r a t i o n h o w e v e r ，t h e s ep r a c t i c e sh a v ee x p o s e ds o m el i m i t a t i o n so ft r a d i t i o n a lg e p f o r i n s t a n c e ，s u c ha sl o wc o n v e r g e n c er a t e ，l o wf i t t i n gd e g r e ea n de a s i l yf a l l i n gi n t o l o c a l b e s t b a s e do ne x i s t i n gr e s e a r c ha n di nv i e wo ft h ed i s a d v a n t a g e so fg e n e e x p r e s s i o np r o g r a m m i n g ，t h i st h e s i sc o m b i n e sg e p w i t ha r t i f i c i a li m m b n e a l g o r i t h m s a n dp r o p o s e sa r t i f i c i a li m m u n ei ng e n ee x p r e s s i o np r o g r a m m i n g ( a i g e p ) t h ek e yt ot h i sa l g o r i t h ml i e si nm a i n t a i n i n gt h ed i v e r s i t yo fp o p u l a t i o n t h e m e c h a n i s mo fi m m u n o l o g i c a lm e m o r yw h i c hf i o mi m m u n ea l g o r i t h mi su s e di nt h e g e n e r i co p e r a t i o no fg e p u n d e rt h ea c t i o no fe x c e l l e n tm e m o r yc e l lt oa c t u a l i z e e l i t i s ts t r a t e g y ，t h es e a r c ho fa l g o r i t h mi se f f e c t i v e ；u n d e rt h ea c t i o no ft h ew e a k m e m o r yc e l lt oj u d g ea n de l i m i n a t et h ew e a ki n d i v i d u a lt h r o u g hs e l e c t i o n ，s ot h e s e a r c ho fa l g o r i t h mi sr a p i da n da v o i d sf a l l i n gi n t ol o c a lb e s t a i g e pa l g o r i t h mi n c r e a s ee f f e c t i v e l yt h er a t eo fc o n v e r g e n c e ，c o r k i n gm a i n t a i n t h ed i v e r s i t yo fi n d i v i d u a l a n da v o i d i n gs o m el i m i t a t i o n st h a tt r a d i t i o n a lg e pw a s u s e di nd a t ai i l i i l i n g i no r d e rt op r o v et h ee f f i c a c ya n dc o r r e c t n e s s ，t h ea l g o r i t h mi s u s e di nf u n c t i o nm i n i n g s i m u l a t i o nr e s u l t so ff u n c t i o nm i n i n gf u r t h e rs h o wt h e e f f i c i e n c yo ft h ea l g o r i t h m ，a n dt h em o d e lo fm i n i n gh a sm o r ef i t n e s sa n dp r e d i c t p r e c i s i o n k e yw o r d s ：f u n c t i o n ；d a t am i n i n g ；g e n ee x p r e s s i o np r o g r a m m i n g ( g e p ) ；i m m u n e a l g o r i t h m s i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得天鲞竖范大鲎或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 签名： 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论 文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、 汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期： 天津师范大学硕士学位论文 第1 章绪论 1 1引言 需要是发明之母。 人类在自然科学和社会科学中的各个领域进行着不断的观测，积累了大量数 据，特别是随着信息时代的到来，各种信息数据量更是呈指数级增长。但是，面 对海量数据，人们渴望能够去粗取精、去伪存真，发现数据中蕴含的相关事物的 内在联系和规律，以利用这些知识从本质上更好地认识客观世界，以帮助我们做 出决策，或进行某种科学预测。由此，随着计算机网络技术迅速发展和应用的普 及，数据挖掘应运而生。 数据挖掘就是从数据库中抽取隐含的、以前未知的、具有潜在应用价值的信 息的过程。数据挖掘引起了信息产业界的极大关注，其主要原因是它可以帮助用 户发现隐藏在大型数据库中的规律和模式。经过十几年的研究，获取的信息和知 识可以广泛用于各种应用，包括信息管理、生产控制、查询处理、市场分析、工 程设计和科学探索等。 函数挖掘是数据挖掘的重要分支，其目的是发现描述数据或趋势的函数，以 能够使用函数模型进行预测。函数是数学最基本的、最普遍的概念之一。纵观科 学发展史，各种物理学、化学、天文学中的自然规律和现象大都是科学家通过对 大量的实验数据进行深入的研究整理，最后归纳所发现的。例如牛顿三大定律、 万有引力定律、开普勒行星运行定律等。这些定律采用数学公式的形式表述了不 同因素间的函数关系。 1 2 - 1函数挖掘概述 1 2 函数挖掘及其研究现状 科研和工程中不仅需要对大量的数据定性分析，而且需要对它们进行定量分 析，这些常常会用到函数挖掘。这类问题是根据得到的若干有关变量的一组数据， 天津师范大学硕士学位论文 寻找因变量与自变量之间的一个函数，使该函数对那组数据拟合得最好。 1 ) 函数挖掘问题的形式化描述如下： 设 ( t ，y ，) ；毛x ，y ，y ，i i 是给定的输入输出对，这里x ，】，都是实有限 维空间的子集，是指标集；又若，是c ( x ) ( x 上所有连续函数全体) 的一个子 集，p 是定义在乘积空间兀y 上的一个距离，则函数挖掘问题便是确定一个函数 f f 使得式( 1 1 ) 成立： 户( ( 鼍) ) ， 咒) ) p ( 矿( 鼍) ) ， m ) ) ( 1 1 ) 或使得对某给定的 o ，有式( 1 2 ) 成立： 户( 矿( t ) ) ，以 占) ( 1 2 ) 2 ) 函数挖掘通常包括下列步骤n 1 ： ( 1 ) 拟合从一组数据出发确定某些变量之间的定量关系式，即建立函数模型 并估计其中的未知参数； ( 2 ) 变量选择判断哪些自变量的影响是显著的，哪些自变量的影响是不显著 的，将影响显著的自变量选入模型中，而剔除影响不显著的变量； ( 3 ) 估计与检验估计函数模型中的未知参数，并且对模型提出的各种假设进 行验证； ( 4 ) 预测利用所求的函数对一组输入数值进行预测。目标函数可以用回归分 析统计技术建模。许多问题可以用线性回归解决，并且更多的可以对变量进行变 换，使得非线性问题可以转换为线性的来加以处理。 1 2 2 函数挖掘研究现状 函数挖掘( 或符号回归) 问题在各个领域都有很广泛的应用，特别是在预测 领域有着重要的用途，它是从各个领域、各个学科的实际需求中提出的，因此函 数挖掘是一门高度交叉性的学科，也一直是国内外的一个研究热点。自从8 0 年 代起国内外的学者在各个领域结合不同的方法研究函数挖掘，已取得了很多的研 究成果。 函数挖掘过程最困难的阶段是根据观测数据确定模型的结构。传统的函数挖 2 天津师范大学硕士学位论文 掘过程中，函数模型结构确定依赖于个人的经验，特别是在多参数条件下数据空 间呈超曲面状，往往超出人的想象能力，选择一个合理的表达式结构十分困难。 国内外的科学家在这方面做了大量的工作。在计算机发明以前，事物间函数关系 的挖掘是依靠科学家长时间的辛勤工作完成。例如：第谷从事三十年的天文观察， 积累了大量的观察材料，但是并没有发现行星运动的三大定律，而开普勒在第谷 的基础上坚持几十年做大量的数学计算工作，最终做出重大发现。 随着计算机的出现，在数据挖掘领域，已经提出很多方法来自动地进行函数 挖掘，如多元回归、傅立叶变换、神经网络等等硷1 。在具体应用方面，多元回归、 样条插值等主要用于实践工程中，而傅立叶变换、小波变换、神经网络等方法在 信号处理、数据压缩、语音、图像处理表现出良好效果。而神经网络难以表示和 解释，其它方法又往往把寻找的表达式限制在多项式或级数形式之内，大大降低 了可理解性。因此，科学、准确地发现自然规律问题，单纯用数据拟合或函数逼 近方法是无法胜任的，只能寻求新途径，这就需要引入人工智能技术。 后来出现的演化算法是模拟自然界的生物演化过程，借鉴生物界的自然选择 和自然遗传机制而发展起来的一类问题求解的策略和方法。由于演化算法本身具 有的自组织、自适应和自学习等智能特征以及本质的并行性和易于操作、通用性 强等特点，所以演化计算在函数挖掘问题上得到很好的应用。 有研究把遗传算法应用到函数挖掘中口1 ，文献n 5 1 探讨了应用基因表达式编 程进行符号回归( s y m b o l i cr e g r e s s i o n ) 。基因表达式编程( g e n ee x p r e s s i o n p r o g r a m m i n g ，简记g e p ) 是葡萄牙科学家c a n d i d af e r r e i r a 1 提出的一种新的遗 传算法，是遗传计算家族的革命性的新成员，已被成功的应用到函数挖掘、关联 规则提取、因子分解和太阳黑子预测等领域。短短几年时间内，关于g e p 理论研 究得到了广泛地发展，并应用到函数挖掘、分类和仿真等领域。尤其是近三年， 基因表达式编程在国内外的研究热度不断增加，应用更为广泛。主要应用范围包 括：多项式函数关系分解订、频繁函数集挖掘呻3 、中药挖掘四1 、股票分析n0 1 、时 序预测n 、属性约简n 2 1 等。 基因表达式编程具有不需要知道组成要素之间的因果联系，只要提供足够的 观测数据，就可以建立模型，能够发现具有复杂形式的函数等优点。用g e p 进行 函数发现与传统的统计学方法相比具有不需要事先知道数学模型，能够发现具有 3 天津师范大学硕士学位论文 复杂形式的函数的优点。但也存在着一些不足，如存在早熟现象、难以利用先验 知识提高求解效率等缺陷。 多年来，生命现象和生物智能行为一直为科学家所关注，他们从中获得灵感， 创立了许多不同的学说和理论。由于诸多生物系统蕴涵着无比奇妙的机制，可以 为复杂问题求解提供启迪和参考，所以人们从不同的角度去研究生物体系，其中 一个重要的领域就是生物免疫系统。人工免疫系统( a r t i f i c i a li m m u n es y s t e m ， a i s ) 是受生物免疫系统( 主要是人类免疫系统) 各种原理和机制启发而发展的各 类信息处理技术、计算技术及其在工程和科学中应用而产生的各种智能系统的统 称。它在多样性、耐受性、免疫记忆、分布式并行处理、自组织、自学习、自适 应等诸多方面具有强劲优势。 交叉是科技创新的重要源泉。多学科交叉融合是优势学科的发展点、新兴学 科的生长点、重大创新的突破点。针对g e p 算法具有的简单、线性和紧凑、易于 操作以及人工免疫系统的抗体多样性、免疫自我调节、免疫记忆等特点，研究者 将目光聚焦到二者的融合上面，从而实现优势互补。到目前为止，国内进行相关 研究的文献共有两篇n 3 1 4 1 。在前人工作的基础上，本文提出了基于免疫策略的基 因表达式编程算法，即把免疫系统的记忆机制引入到基因表达式编程中，以实现 优势互补，从而避免了g e p 算法易于陷入局部最优的缺陷，提高了进化后期算法 的收敛速度和精度。仿真实验进一步证明了该算法的有效性。 1 3 本文结构和安排 本论文借鉴生命科学中免疫的概念与理论，将免疫记忆机制引入到基因表达 式编程中，从而对函数挖掘的应用进行深入的研究。论文组织安排如下： 第1 章简要介绍了课题研究背景、函数挖掘及其研究现状及本文所做工作和 研究方法。 第2 章概述基因表达式编程，阐述了经典g e p 的各个关键技术，分析了经典 g e p 算法特点。 第3 章提出了基于免疫策略的基因表达式编程方法，简要说明了人工免疫系 统的生物学基础和人工免疫系统，详细阐述了基于免疫策略的基因表达式编程。 针对经典g e p 在保持种群多样性和保护最优解等方面的不足，引入了优良记忆库 4 天津师范大学硕士学位论文 和差评记忆库，并提出了a i g e p 算法。该算法具有保护最优个体，提高局部搜索 能力、减少早熟现象发生的能力。 第4 章为实验分析部分，利用v c + + 编程语言，实现了a i g e p 系统。通过实 验，验证a i g e p 算法的有效性。 第5 章为全文总结以及今后进一步研究的展望。 5 天津师范人学硕士学位论文 第2 章基因表达式编程简介 2 1引言 基因表达式编程由c a n d i d af e r r e i r a 于2 0 0 1 年1 2 月首次提出。基因表达 式编程作为进化计算家族的新成员在继承遗传算法( g e n e t i ca l g o r i t h m ，g a ) 和遗传编程( g e n e t i cp r o g r a m m i n g ) 的思想的基础上，又发展了自己的特性。 文献n 司中描述了g e p 算法的基本框架。 基因表达式编程( g e p ) 的产生来自于遗传算法和遗传程序设计。四川大学的 唐常杰教授对基因表达式编程的起源阐述了如下观点：“遗传算法比喻为父体， 它刚性地使用定长的线性字符串作为遗传物质，采用简单编码解决简单问题；遗 传程序设计比喻为母体，它柔性地使用非线性的，不定长的树结构，采用复杂结 构解决复杂问题；而基因表达式编程继承了父母的优点，它刚柔相济，表现为定 长线性串，易于遗传操作，又间接地对应于柔性的具有非线性结构的树结构，从 而达到了简单编码解决复杂问题的目的，使得在速度上比g a 和g p 提高了 1 0 0 - 6 0 0 0 。图2 1 描述了g a 、g p 和g e p 的关系n 6 1 图2 1g e p 与g a 和g p 的继承关系图 6 天津师范大学硕士学位论文 2 2 编码规则 基因表达式编程遗传操作的基本单位是染色体( c h r o m o s o m e ) ，而遗传信息 载体的最小单位是基因( g e n e ) 。染色体由一个或多个基因构成，基因由线性定 长的字符串构成。g e p 创新地把基因分为头部( h e a d ) 和尾部( t a i l ) 两部分， 头部包含终结符和函数集( f u n c t i o ns e t ) 中的函数，而尾部只包含变量，不包含 函数。因此终结符和函数是构成基因表达式编程的程序元语n 7 i 。 ( 1 ) 终结符集：终结符是提供给系统值的最末端结构。终结符自己提供信息， 但不处理另外的信息。通常，终结符集合包括基因表达式编程程序中的输入，常 量，或者没有参数的函数。 如果用树形结构来表示程序，终结符代表树的叶结点。当程序运行的时候， 这些叶结点，要么接受外部的输入，要么自己就是一个常量，或者自己就能计算 产生一个量。它们向系统中提供信息，以供系统处理。 ( 2 ) 函数集：基因表达式编程中的函数概念相当广泛，它包括系统中的其他 任何非终结符的中间结构。函数集合可以包括与应用有关的问题领域的运算符 号，也可以包括程序设计语言中的程序构件，甚至是表示系统中间层次的一种符 号。常见的函数见表2 1 。 表2 1 函数集中常见的函数 算术运算符+ ，一，等 基本初等函数s i n ，c o s ，i n ，a r c s i n 等 布尔运算符与八，或v ，非 关系运算符 ，等 条件运算符i f - t h e n - e l s e 等 自定义函数 由用户自己定义的函数 下面定理为g e p 遗传操作的封闭性提供了充分条件，即g e p 基本定理： g e p 中，染色体头部( 五) 和尾部( t ) 的长度满足式( 2 1 ) 的良性染色体集合在遗 传操作下封闭，唐常杰等n 町对运算符个数用数学归纳法给出了严格的证明。 t = h x ( n o + l ( 2 1 ) 其中n 表示函数中的最大目数。例如，在一般的数学运算中，对于开方或者 7 天津师范大学硕十学位论文 三角函数，刀= l ：对于加号或乘号，刀= 2 。 采用这种头尾划分的好处在于，一方面整个基因的结构在设定了函数集和头 部长度之后就能够确定；另一方面，整个基因在上面这个公式的前提下一定能够 保证结构上的正确性，而不用担心会产生任何非法的个体。 在基因表达式编程中，按其编码规则，遗传编码染色体是固定长度的线性符 号串。一个染色体可能包含一个或者多个基因。尽管染色体的长度是固定长度的， 但通过特殊的编码形式，使得基因表达式编程的染色体能够表达各种长短不定， 形状各异的表达式。 2 3 表达式树与k 一表达式 基因表达式编程创新性地提出基因型( 染色体) 和表现型( 表达式树) 既分 离又相互转化的模型，克服了g a 和g p 的不足，提高了解决问题的能力和效率。 在g e p 中，基因型即演化实体是染色体( c h r o m o s o m e ) ，染色体实际就是用连接 运算符( l i n ko p e r a t o r ) 连接起来的多个基因( g e n e ) 。基因是由k 一表达式构 成的。一个通常意义下的表达式，例如算术表达式，可以有多种表示方式。而用 表达式树( e x p r e s s i o nt r e e ) 来表示，是表达式最直观、最本质的表达方式。在 进化计算家族中，原始的g p 算法就是将表达式树直接作为遗传编码，遗传操作 也直接作用在表达式树上的。 如果表达式中出现的函数具有确定数量的变量，也可以通过不同的方法将表 达式进行线性化。最常见的线性化方式就是采用先序、中序或者后序遍历序列来 表示表达式。因为运算符优先级和结合顺序的原因，中序遍历并不能完全如实地 反映原表达式，所以，很少有进化算法将中序遍历序列作为遗传编码，并且让遗 传算子操作该序列。而先序和后序遍历序列则能够完全如实地反映原表达式，在 某些改进的遗传编程算法中，采用了先序或者后序遍历序列作为遗传编码。 c a n d i d a 直观地描述了一种很简单的将表达式树线性化方法。这种方法就是 k 一表达式( k - e x p r e s s i o n ) ，它是一种很简单、很直观的遍历表达式树的方法。对 一棵表达式树，按照从上到下，从左到右的顺序遍历，所得到的序列，称为表达 式树的k 一表达式。值得注意的是，表达式树的k 一表达式和先序、后序遍历都存 在很大的差异。例如对于式( 2 2 ) 算术表达式： 8 天津师范大学硕士学位论文 ( 口一6 ) x ( c + d ) ( 2 2 ) 其表达式树如图2 2 所示，而式( 2 2 ) 的先序遍历为：q * - a b + c d ；后序遍历 为：a b - c d + * q ；k 一表达式为：q * - + a b c d 。 同理，只需逆操作即可将k 一表达式转换成表达式树，k 一表达式的开始位置 对应表达式树的根，后面的每个函数为一分枝，每个函数带有一个或多个变量， 变量个数由函数决定。 例如，我们考虑由如下函数集f = q ，+ ，一，) ( 其中q 表示数学开方s q r t 运算) 和终点集为丁= a ，b ) 构成的基因。在这里，n = 2 ；如果我们选择h = 1 5 ，那 么t = 1 5 ( 2 - 1 ) + 1 = 1 6 ；所以整个基因的长度l = 1 5 + 1 6 = 3 1 。 图2 2 式( 2 2 ) 对应的表达式树 下面给出由此构成的一个基因x ( 头部用粗体标识) ： 012 34 56 78 90l2 34 56 7 89 012 345 67 8 9o q ，i c + 一abaqbab + b +bab bab bbababbaaa i + 一 基因头部i + 一 基因尾部_ l 基因表达式编程的基因型( g e n o t y p e ) 是通过连接运算符( l i n ko p e r a t o r ) 连接起来的多个基因所构成的染色体，而g e p 中的表现型( p h e n o t y p e ) 是表达 式树( e x p r e s s i o nt r e e ) 。基因型和表现型相互之间可以转换。要将该基因转换 成相应的表达式树( e x p r e s s i o nt r e e ，e t ) ，只需要按照从左到右的顺序逐个读 取基因中的字符，并按照语法规则和层次顺序构成表达式树。按照以上规则，上 述基因x 可以转化成表达式树( 图2 3 ) ，该e t 进行层次遍历可以得到表达式： ( 口+ 6 ) x ( 口一4 b ) ( 2 3 ) 天津师范大学硕士学位论文 式( 2 3 ) 与图2 3 说明： 1 ) 通过层次遍历就可以在字符串和表达式树之间进行相互转化。 2 ) 对表达式树进行层次遍历得到的字符串称为k 一表达式( k - e x p r e s s i o n ) 。 将图2 3 的表达式树按由上到下，由左到右层次遍历，得到其k 一表达式为： q 木+ 一a b a q b 。本例中，k 一表达式终止于第8 位，而基因终止于第3 0 位( 基因从第 o 位开始) 。如前文所述，g e p 的染色体是固定长度的，由一个或多个等长基因 构成的，基因长度固定。因此，在g e p 中，变化的不是基因的长度，而是k 一表 达式的长度。 图2 3 基因x 的表达式树 3 ) 基因字符串中能够被转化到表达式树中的那些字符组成了o p e n i n g r e a d i n gf r a m e ( o r f ) ，因此o r f 的长度小于等于基因的长度。 4 ) 基因字符串中没能被转化为表达式树的部分称为非编码区域( n o n - c o d i n g r e g i o n ) 。非编码区域看上去虽然不太重要，但这正是g e p 区别于g a 和g p 的地 方。非编码区域的存在为程序进化提供了很大的空间，它使得g e p 无论进行哪一 种遗传操作时，不需要作任何限制，都能生成正确的程序。注意，非编码区并不 是垃圾区，非编码区的信息虽然在当前个体不表现出来，但可能在其后代被表现 出来。 g e p 中的非编码区域在整个进化中起到了很深刻的作用。正是这些非编码区 域的存在使得g e p 在各种遗传算子的作用下不用加入其它约束条件就能产生出 1 0 天津师范大学硕士学位论文 有效的表达式；而g p 由于缺少非编码区域，使得遗传算子作用的时候必须在事 先采用很复杂的约束条件，事后又需要花费大量的时间来检查表达式的有效性。 这就是g e p 在效率上大大优于g p 的重要原因h m 9 。 2 4g e p 基本算法流程图 g e p 的运行流程和g a ，g p 类似，流程图如图2 4 所示。算法中产生一个初 始种群，包含若干个代表不同解答方案的“个体”。而选择则是根据各个染色体 的适应度，使用一定的选择算子，如轮盘赌选择算子，锦标赛选择算子等进行选 择，保证适应度高的个体有更高的选中概率，根据达尔文的“适者生存原则， 让高适应度的个体有更高的机会生存。遗传算子作用于种群，在种群的个体之间 进行遗传操作，产生出新的子代个体。在g a 中遗传算子包含重组、变异两大类： 重组指多个个体之间进行的遗传操作，子代个体中包含多个父代个体的遗传信 息；变异则指单个个体内部进行的遗传操作，子代个体仅包含单个父代个体的遗 传信息。在g e p 中，除了和g a 中类似的单点重组、双点重组、单点变异等以外， g e p 中还包括插串( i n s e r ts e q u e n c e ，i s ) ，根插串( r o o ti n s e r ts e q u e n c e ，r i s ) 等具有独特动作和含义的遗传算子。这些遗传算子使得g e p 具有鲜明的特色。整 个过程周而复始，直到达到一定的结束条件为止( 如找到最优解，达到一定代数， 适应度达到某个值或者运行时间达到预设时间等) 。 2 5f l e p 的研究现状 目前，国际上关于g e p 的研究迅速升温，主要包括对g e p 的机理和应用两方 面的研究。f e r r e i r ac 及她的研究组仍然保持着领先的地位，不仅开发研制了 g e p s o f t 软件并发表了较多文献乜引 2 h 。应用方面将g e p 应用于神经网络领域乜2 j 。 国际上其他研究人员也对g e p 的研究表现了极高的热情。主要的研究集中在应用 领域：如将g e p 应用于分类规则的挖掘心3 1 和应用于时间序列的预测心钔瞳引。 同样国内对g e p 也有了一定的研究，主要的研究队伍是四川大学和中国地质 大学，他们的研究取得了一定的新成果。国内的主要研究也集中在应用领域：如 将g e p 应用于实现智能模型库系统和对股票时间序列数据的挖掘。就目前取得的 天津师范大学硕士学位论文 研究成果来看，对g e p 的研究偏重于应用研究：如将g e p 应用到较新的领域，或 面对具体问题将g e p 与其他经典算法相结合。 图2 4g e p 算法流程图 1 2 结束 天津师范大学硕上学位论文 第3 章基于免疫的基因表达式编程方法的提出 通过第2 章的介绍，我们知道g e p 综合了g a 和g p 的优点，采用固定长度的 线性编码来表示个体，具有编码简单、线性和紧凑、易于进行操作等优点。但它 也存在一些缺陷，如存在早熟现象、难以利用先验知识提高求解效率等。 近年来在生物学领域的研究发现免疫原理对改进和提高基因表达式编程的 性能具有重要的启迪作用一由于实际的生物体免疫系统具备记忆开发( 长期和短 期) 、任务规划、任务有序化分割、模式识别、非预见情况处理、自适应调节等 许多优良功能，免疫行为可以很好地保持多样性一因而能够很好地防止“早熟 现象，有效地提高寻优速度、改善寻优质量，因此，鉴于基因表达式编程存在的 缺陷，我们可以考虑把基于生物免疫系统的免疫机理引入到基因表达式编程中， 形成基于免疫策略的基因表达式编程。 而目前许多有关智能系统的研究都是围绕人脑智能明显的激励及其学习机 制进行的。这些拟人化方法都忽略了与人脑行为方式并无明显相关的另一类智能 系统。我们可以看到自然界中一个很好的例子一生物体的免疫系统具备很高的智 能级( h i g hl e v e lo fi n t e l l i g e n c e ) ，但是它与人脑的行为方式的确没有明显的 联系。 3 1 生物免疫系统 免疫是指机体对感染具有抵抗能力而不患疫病或传染病。免疫系统是生物体 的一个高度进化、复杂的功能系统，它能自适应地识别和排除侵入机体的病毒， 并且具有学习、记忆和自适应调节能力，维护机体内环境的稳定。 生物免疫系统是一个极其复杂的自适应系统。一般意义上讲，生物免疫系统 由免疫器官、免疫组织和多种淋巴细胞组成。而生物免疫学认为，免疫功能主要 是由参与免疫反应的细胞和由其构成的器官来完成的。这种免疫细胞主要有两大 类：一类为淋巴细胞。它们在抗原的激发下能进一步分化成为各种球蛋白的浆细 胞或分化成为致敏淋巴细胞。这类细胞因为对抗原的反应有明显的专一性，所以 是特异性免疫( s p e c i f i ci n l i n u n i t y ) 反应的主要细胞；另一类细胞则具有摄取抗 13 天律师范大学硕士学位论文 原、处理抗原并将处理后的抗原以某种方式提供给淋巴细胞的作用。这主要包括 巨噬细胞、单核细胞和粒细胞等。这类细胞的重要特征是在参与各种非特异性免 疫( n o n s p e c i f i ci m m u n i t y ) 反应的同时，也能积极地参与特异性免疫反应。 3 1 1生物免疫系统的基本理论 生物免疫系统( i m m u n es y s t e m ) 是保护机体免受各种致病细菌侵袭，维护机 体健康的重要的生物系统，其功能就是免疫( i m m u n i t y ) 。免疫是机体的保护性生 理反应，即：通过识别“自己”和“非己”，排除“异物 ( 病原生物及其产物、 衰老的自身细胞、突变生成的异常细胞) ，维持机体内环境平衡。它是人工免疫 算法的生物学基础。 生物免疫系统是一个由众多组织、细胞与分子等构成的复杂系统，为了便于 读者很好地理解免疫系统的主要功能和作用机制，有必要先简单介绍一下免疫系 统中的一些基本概念和术语。主要包括： 1 ) 免疫( i m m u n i t y ) 和免疫应答( i m m u n er e s p o n s e ) 免疫是机体对“自己和“异己( 非己) 识别、应答过程中所产生的生物学 效应的总和，正常情况下是维持内环境稳定的一种生理性功能。换言之：机体识 别非己抗原，对其产生免疫应答并清除之：正常机体对自身组织抗原成分则不产 生免疫应答，即维持耐受。 外部有害病原入侵机体并激活免疫细胞，诱导其发生反应的过程称为免疫应 答。免疫应答分为固有性免疫和获得性免疫两种，前者为机体先天获得，可对病 原进行快速清除；后者特异性识别并清除病原体，具有特异性、记忆、区分自我 与非我、多样性和自我调节等优良特性。获得性免疫所具有的优良特性是人工免 疫系统( a i s ) 隐喻机制的不竭之源。 2 ) 抗原( a n t i g e n ，a g ) 和抗体( a n t i b o d y ，a b ) 抗原指可被t ，b 淋巴细胞识别，并启动特异性免疫应答的物质。抗原具有 两个重要特性：其一是免疫原性，指抗原能够刺激机体产生抗体或致敏淋巴细胞 的能力；其二是抗原性或免疫反应性，指抗原能够与其所诱生的抗体或致敏淋巴 细胞特异性结合的能力。 抗体呈y 字型，其主要功能是识别、清除机体内各种病原性异物( 抗原 1 4 天津师范大学项十学位论女 a n t i g e n ) 。换句话说，当免疫系统受抗原刺激后，b 淋巴细胞转化为浆细胞， 并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体，故又将 其称为免疫球蛋白。 各种抗原性分子都有可被抗体识别的特异性结构，称为抗原决定簇( 表位 e p i t o p e ) ，抗体也存在类似结构，称为独特型( i d i o t o p e ) 。每个b 细胞只分泌一 种类型的抗体，因此是特异的，而通常抗原会呈现几种不同的表位，所以说，一 个抗原可以被几个不同的抗体识别。抗体识别抗原的部分称为抗体决定簇( 对位 p a r a t o p e ) ，叉被称为可变区( v 区) 。图31 ( a ) 为带有几个不同表位的抗原结构； 图31 ( b ) 为抗体及其独特型和对位。”。 蚓3 1 ( a ) 抗原结构陶3 1 ( b ) 抗体结构 3 ) 亲和力 免疫系统中的免疫识别是发生在分子水平的，并且这种识别是基于抗体决定 基和抗原决定基之间的形状互补。发生免疫识别的抗体决定基和抗原决定基在结 构上越互补，结合就越町能发生，结合的力度也就越紧密，这种结合的力度与强 度被称为抗体与抗原之间的亲和力。 抗体与抗原的结合就像一把钥匙开一把锁的关系，钥匙的形状与锁芯必须一 致。当然抗体与抗原在结构上不一定需要完全一致，但也必须在一定程度上匹配。 这样大致匹配具有较高亲和力的8 细胞，就可以通过体细胞高频变异和基因重组 ( 受体编辑) 等途径实现亲和力的成熟，达到与抗原的高度匹配。 4 ) 免疫细胞 免疫应答主要由分布在生物体全身的免疫细胞实现。免疫细胞泛指所有参与 免疫麻答过程的相关细胞，包括吞噬细胞、n k 细胞、淋巴细胞等。本文讨论的 h i s 特性主要涉及淋巴细胞的相关免疫特性。淋巴细胞主要包括b 细胞和t 细胞， 】5 天津师范大学硕十学位论文 它们分布于整个身体，在免疫中起主要作用。 t 细胞的主要功能包括调节其他细胞的活动以及直接袭击宿主感染细胞。其 中辅助性t 细胞的主要作用是激活b 细胞，与抗原结合时分泌作用于b 细胞并帮 助刺激b 细胞的分子。 b 细胞的主要功能是在其表面产生抗体( b - c e l lr e c e p t o r ( a b ) ) ，即在清除 病原体过程中受到刺激，分泌抗体结合抗原，但其发挥免疫作用要受t 辅助细胞 的帮助。 3 1 2 人工免疫系统的仿生机理 免疫是机体的一种特异性反应，通过识别和排除抗原性异物维持机体内环境 的稳定，其功能是通过众多免疫细胞和免疫分子之间的相互作用而实现的，如图 3 2 所示的是经典免疫反应中各因素间的相互关系。免疫系统的免疫应答机制及 其许多重要的功能，如免疫识别、免疫学习和免疫记忆等是免疫学研究的重要内 容，同时，这些显著的特性也在不断地吸引着研究人员从免疫系统中抽取有用的 隐喻机制，开发相应的人工免疫系统用于信息处理和问题求解乜钔。 体内影 因素 ( 激素) 抗原 体外影响 因素 图3 2 免疫反应中各冈素l 司的相互关系 人工免疫系统( a r t i f i c i a li m m u n es y s t e m ，a i s ) 是借鉴、利用生物免疫 系统( 主要是人类免疫系统) 各种原理和机制而发展的各类信息处理技术、计算技 术及其在工程和科学中应用而产生的各种智能系统的统称。人工免疫系统是一个 跨越多学科的研究领域，是与生物免疫系统相对应的工程概念啪3 。 1 ) 免疫识别 1 6 天津师范大学硕七学位论文 现代免疫学认为，机体免疫功能是对抗原刺激的应答，而免疫应答又表现为 免疫系统识别自己和排除非己的能力。被认为是自己( 自己体内组织) 的细胞不会 引发免疫应答，也称为免疫对其是耐受的，只有那些被免疫系统认为是非己( 外 来入侵物质) 的，才会引发免疫应答，最终导致其从生物体内消除。免疫系统在 发挥免疫功能的过程中，识别是重要的前提。一切生物都具有这种能力。 f o r r e s t 等根据免疫识别原理，提出了阴性选择算法，其核心是根据识别的 对象特征进行编码，定义一个自我集合并随机产生一系列检测器，用于检测自我 集合的变化。根据阴性选择原理，若检测集合与自我集合匹配，则完成匹配任务。 免疫识别机理在图像识别、网络入侵检测、异常检测中得到了广泛的应用。 2 ) 免疫记忆 免疫识别过程同时也是一个学习的过程，学习的结果是免疫细胞的个体亲合 度提高、群体规模扩大，并且最优个体以免疫记忆的形式得到保存。免疫记忆是 免疫系统另一重要的特点。当机体接触过某种抗原后再次接触相同抗原时，则抗 体出现的潜伏期较初次应答明显缩短，抗体含量大幅度上升，而且维持时间长， 这种当同一种抗原再次入侵机体时，引起的比初次免疫更强的、更高亲和度的抗 体产生的现象就称为免疫记忆。无论在体液免疫或细胞免疫中均可发生免疫记忆 现象。 抗体 细胞 牛缒 褥次虑镑 貉 一。百i 而去数 灭：阮 图3 3 免疫记忆机制示意图( 免疫系统对牛痘和天花的应答) 下面以免疫系统对牛痘和天花的应答为例，说明免疫记忆机制的作用( 见图 3 3 ) ，该过程体现了疫苗免疫的思想。经过对牛痘的初次应答后，免疫系统保存 了对该病原的记忆信息，而当蛋白质结构与牛痘相似的天花病毒出现时，由于联 1 7 天津师范大学硕士学位论文 想记忆机制的作用，免疫系统同样可以对其进行识别和效应。免疫记忆是人工免 疫系统区别于其它进化算法的重要特性之一。 3 2 人工免疫系统的基本原理 生物免疫系统是一个复杂的白适应系统，可保护人体不受外部病原体侵害， 它不依靠任何中心控制，具有分布式任务处理能力，具有在局部采取行动的智能， 它通过起交流作用的化学信息构成网络，进而形成全局概念。人工免疫系统是模 仿生物免疫系统功能的一种智能方法，它实现了一种受生物免疫系统启发，通过 学习外界物质的自然防御机理的学习技术，提供了噪音忍耐、无教师学习、自组 织、记忆等进化学习机理，因此提供了新颖的解决问题的方法和途径。免疫系统 的理论与应用的研究历史较短。最早与免疫系统相关的理论是澳大利亚学者 b u r n e t 提出的基于生物抗体的克隆选择学说啪1 。最早的免疫系统的模型是j e r n e 于1 9 7 3 年提出的啪1 ，他是基于b u r n e t 的克隆选择学说，开创了独特型网络理论， 并给出了免疫系统的数学框架。目前该算法已经涉及到非线性最优化、组合优化、 控制工程、工业设计和工业生产等诸多领域b ，并表现出较卓越的性能和效率。 于是，对人工免疫系统的研究已经成为一大热点。 3 2 1人工免疫系统的基本术语 免疫概念的提出是受生物自然科学的启发，在原有进化算法理论框架的基础 上引入了一个新的算子一免疫算子( i m m u n eo p e r a t o r ) ，而形成的一个新的进化 理论。前面我们介绍过，在生命科学中免疫功能主要是由参与免疫反应的细胞或 者说由其构成的器官完成的。这种免疫细胞主要有两大类：一类为淋巴细胞。这 类细胞因为对抗原的反应有明显的专一性，所以是特异性免疫( s p e c i f i c i m m u n i t y ) 反应的主要细胞；第二类细胞则具有摄取抗原、处理抗原并将处理后 的抗原以某种方式提供给淋巴细胞的作用，其重要