（计算机应用技术专业论文）基因表达式编程算法的研究与应用.pdf

上海大学硕士学位论文 摘要 进化计算是当前人工智能、知识工程、数据挖掘中的研究热点。遗传算法和 遗传编程，是众多进化计算模型中的两个最典型的模型。e c a n d i d a 于2 0 0 1 年草 创了新的进化计算模型基因表达式编程( g e p ，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 既具有遗传算法的简单性，又具有遗传编程的功能，在对很多问题的求解 效率上，比普通的遗传编程高4 - 6 个数量级。e c a n d i d a 在草创的同时，留下了 大量的理论空白，技术缺陷和遗憾之处。 生物学研究的深入为基因表达式编程提供了良好的研究基础，而随着地下空 间开发新技术隧道盾构施工带来的挑战，又为基因表达式编程提供了广阔的 应用舞台。 本文在前人工作的基础上对基因表达式编程的核心技术进行了研究，并探讨 了g e p 在隧道盾构施工中的应用。主要成果和贡献如下： ( 1 ) 对基本的g e p 算法中关键参数、常数集、符号集等设置对公式发现的影 响和规律进行了理论分析和实验证明。 ( 2 ) 引入生物学中的转基因技术和小生境技术，提出g e p 的改进算法i a ( i m p r o v e d a l g o r i t h m ) 和基于队的改进算法i a ，大大提高了g e p 算法用于公 式发现的精度和速度。 ( 3 ) 把i a 成功地运用在双圆盾构地面沉降的横向和纵向公式发现上，通过 与历史工程数据的比对，证明了通过i a 算法得到的地面沉降公式对工程数据具 有很好的拟合度，充分反映了双圆盾构的地面沉降规律一 关键词：公式发现，基因表达式编程，进化计算，盾构法隧道 v t 上海大学硕士学位论文 a b s t r a c t e v o l u t i o n a r yc o m p u t a t i o ni s ah o tp o i n ti nt h er e s e a r c ha r e ao fa r t i f i c i a l i n t e l l i g e n c e , k n o w l e d g ee n g i n e e r i n ga n dd a t am i n i n g g e n e t i ca l g o r i t h ma n d g e n e t i cp r o g r a m m i n ga r et h em o s ti m p o r t a n tc o m p u t a t i o nm o d e l si ne v o l u t i o n a r y c o m p u t a t i o n i n2 0 0 1 ，e c a n d i d ap r o p o s e da n e we v o l u t i o n a r yc o m p u t a t i o nm e t h o d n a m e dg 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 ) g e pi sa ss i m p l ea 8g e n e t i ca l g o r i t h m , a n da sf u n c t i o n a la sg e n e t i cp r o g r a m m i n g b u tf o rt h em o s tp r o b l e m s ，g e pi sm u c h f a s t e rt h a ng e n e t i cp r o g r a m m i n gi n2t o4m a g n i t u d e s w h i l ec r e a t i n gn e w c o n c e p t s a n da l g o r i t h m s ，ec a n d i d al e f ts o m et h e o r e t i ci s s u e sa so p e np r o b l e m s h ea l s ou s e d m a n yp r o p e r t i e sw i t h o u tp r o o f s o m ec o n j e c t u r e sa r es t i l ll i s ti nt h ef i r s tb o o ka b o u t g e pw r i t t e nb yec a n d i d a t h ed e v e l o p m e n to fb i o l o g i c a lt h e o r ya n di n t e l l i g e n c et e c h n o l o g yb r i n g sn e w i d e a sa n dg r e a to p p o r t u n i t i e sf o rg e ea l s ot h en e wr e q u i r e m e n to fe x p l o r i n g u n d e r g r o u n ds p a c e ，e g s h i e l dt u n n e l i n ge n g i n e e r i n g ，b r i n g sab r o a da r e n af o rt h e a p p l i c a t i o no f g e p t h i sp a p e rt r yt oa n s w e rt h e s ep r o b l e m sb a s e do no u rr e s e a r c ho ng e et h em a i n r e s u l t sa n dc o n t r i b u t i o n sa r ea sf o l l o w s ： ( 1 ) g i v e sr i g o r o u sa n a l y s i sa n de x p e r i m e n tp r o o fo nt h ei n f l u e n c ea n dr o l eo f s e t t i n gt h ek e yp a r a m e t e r s ，c o n s t a n ts e t , a n do p e r a t o rs e ti ng e e ( 2 ) w i t ht h eg e n et r a n s f e r r i n gt e c h n o l o g ya n dn i c h et e c h n o l o g y , t h en e w a l g o r i t h m si a ( i m p r o v e da l g o r i t h m ) a n di t se n h a n c e da l g o r i t h mi a a l ep r o p o s e dt o g r e a t l ye n h a n c et h ep r e c i s i o na n ds p e e do f f o r m u l ad i s c o v e r i n g ( 3 ) i a i ss u c c e s s f u l l ya p p l i e dt os e l f - s e a r c h i n gf o r m u l ao ft h eh o r i z o n t a la n d v e r t i c a ls e t t l e m e n tc u r v ef o rd o t ( d o u b l e ot u b e ) s h i e l dt u n n e l i n g c o m p a r ew i t h t h eh i s t o r i c a le n g i n e e r i n gd a t a , t h ef o r m u l ai sp r o v e dt of i tt h ea c t u a ld a t ac l o s e l ya n d r e f l e c tt h er u l eo f g r o u n ds e t t l e m e n ts u c c e s s f u l l y k e y w o r d s ：f o r m u l ad i s c o v e r 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 ，e v o l u t i o n c o m p u t a t i o n , s h i e l dt u n n e l i n g 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其它人已发表 或撰写过的研究成果。参与同一工作的其它同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名： 益岛日期：堡z i ：堡 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名： 生品 导师签 争 施 乡 上海大学硕士学位论文 1 1 公式发现问题介绍 第一章绪论 数据是人们进行科学计算和工程设计的主要依据，分析数据是一项十分重要 的工作。为了能够在实际问题中应用，需要直观地了解数据之间的关系，即将大 量数据归纳为一个抽象的公式，由已知有限个输入输出对 ( x 。y ：) ：i = 1 ，2 ， n 来模拟系统的行为，这就是建模问题。模型具有普遍性和规律性的特点，可以 进行数据的预测和分析隐含于数据间的系统特征。在科学发展史上，各种物理学、 化学、天文学中的自然规律如牛顿三大定律、万有引力定律、开普勒行星运行定 律等都是著名科学家对大量的实验数据进行深入的研究，最后得到了自然规律。 因此，如何迅速而准确地发现其中有用的信息，以预测模式和发现趋势，已成为 一个关键性的研究课题。 公式发现问题被定义如下： 给出一组观测数据，d = ( x 。y 。) j 置r “，y 。胄，i = 1 , 2 ，) ) 搜寻公式厂 定义为： 厂：r ”寸r ( 1 1 ) 使得 i 厂( z ) 一乃iz 0( 1 2 ) 依据公式发现定义，可以认为 ( 置，m ) ；置r n , y l r ，i d 是给定的输入输 出对，其中zy 都是有限维空间上的子集，f 是数据索引集。若f 是c ( 筋的一 个子集，f ( 肋是z 上所有连续函数的全体，p 是定义在乘积空间兀j ，上的距 离，则建模问题便是确定一个函数厂f 使得对任意的厂ef 有： p ( 厂( 置) ，饥) ) p ( 厂( z ) ) ， y 。) ) ( i 3 ) 成立，或使得对任意的s 0 有： p ( 厂( x ，) ) ， y 。) ) ( 1 4 ) 上海大学硕士学位论文 从式1 4 可知，公式发现问题也可以看成是寻找最小值的优化问题： m i n p ( f ( x , ) ， y 。) ) ( 1 5 ) 可见，一些用于解决优化问题的方法可能也可以移植用于解决公式发现问题。 1 2 主要研究方法 最早的时候公式发现一般是由该领域有经验的工程师来完成的。随着计算 机的出现，数据拟合技术得到了发展。数据拟合方法是数值计算的重要分枝，它 利用科学实验中得出的大量测量数据，去求得自变量与因变量的一个近似公式。 这种公式统一表示为代数多项式形式，它的系数由最d , - - 乘原理建立正规方程组 求出。代数多项式存在的一个问题是，当它的次数增大时，线性方程组系数行列 式会出现“病态”( 即行列式元素微小变化引起解的大变化) 。为此数值计算学者 提出了采用正交多项式的方法来逼近实验数据，这种方法使逼近公式的效果大为 提高。可以说，数据拟合方法是能对一般实验数据找到满足精度的逼近公式：数 据拟合方法虽然能解决一些实际问题，但是它把寻找公式的范围限制在多项式形 式之内。正交多项式一般表示都很复杂，如勒让德多项式，它是由多个多项式组 成，每个多项式的系数都不相同，且多项式次数随精度逐渐增加。因此，正交多 项式表示的逼近公式对使用者来说很不直观。 随着人工智能技术的发展，近1 0 年来，公式发现技术得到发展。目前常用 的分析方法有：回归分析、遗传算法( g a ) 、遗传规划( g p ) 和基因表达式编程 ( g e p ) 。比较典型的系统有：科学定律发现系统b a c o n 、数学概念发现系统a m 等“1 。 1 2 1 回归分析 回归分析是使用最早的数据建模方法，它根据事先给定的数据模型结构， 再利用数据样本对模型参数进行回归分析。但是如何选择合适的模型结构是回归 分析中最为困难的问题。结合人工智能技术和统计学理论建立的机器发现系统， 人们建立了b a c o n 和f d d ( f o r m u l ad i s c o v e r yf r o md a t a ) 等系统。这些系统采 用启发式信息指导下的空间数据搜索，在发现过程中定义理论项为中间概念，使 函数简化并控制发现过程。 b a c o n 系统是运用人工智能技术从实验数据中寻找其规律性比较成功的一 2 上海大学硕士学位论文 个系统。它运用数据驱动方法，使用的规则空间与假设空间是分开的。规则空间 包括若干精炼算子，通过精炼算子修改假设。所谓精炼算子就是修改假设空间的 予程序，每个精炼算子以特定的方式修改假设空间。整个学习程序由多个精炼算 子组成，系统使用探索知识对提供的训练集进行分析，决定选用哪个精炼算子。 b a c 0 n 系统的思想是反复地考察数据并使用精炼算子创造新项。直到创造的这些 项中有一个是常数时为止，最终形成表达式。 经验公式发现系统f d d 是我国应用人工智能的机器发现技术和数值计算中 的曲线拟合技术以及可视化技术结合起来自行研制的系统。f d d 系统的基本思想 是利用人工智能启发式搜索原型函数、寻找具有最佳线性逼近关系的原型函数， 并结合曲线拟合技术及可视化技术来寻找数据问的规律性。 1 2 ，2 遗传算法 将生物现象应用到人工领域的仿生学己经越来越被人们看好。将生物进化过 程应用到人工智能领域，也是一个越来越被看好的方向。这方面的研究形成了进 化计算这一广阔的分支。在数量众多的进化计算算法中，各种算法都以生物进化 作为算法的背景，但是，每一种算法都具有自己的特点，有的侧重于生物个体的 变异，有的侧重于个体之间的杂交，有的主要利用每一个个体自身进行搜索，具 有较强的局部搜索能力，而有的主要利用群体间个体之间的相互影响，具有较强 的全局搜索能力。在这些算法中，目前使用最广泛，研究最彻底的是遗传算法。1 。 h o l l a n d 及其它的学生们( b a g l e y 等) 于1 9 7 5 年提出了遗传算法( g e n e t i c a l g o r i t h m ) ，并给出了著名的模式定理。“”。到了8 0 年代末，g o l d b e r g 对一系 列研究工作进行了归纳总结。逐渐认识到在机器学习的研究中，为了获得一个好 的学习算法仅靠单个策略建立和改进是不够的，还要依赖于一个包含许多候选策 略的群体的繁殖。研究结果最终形成了现代遗传算法的基本框架“1 。其特色是高 度并行，随机，自适应，健壮。特别适合于处理复杂问题( 如n p 问题的近似解) 和非线性问题。最早的遗传算法称为标准遗传算法，后来人们对标准遗传算法进 行了大量改进，使得遗传算法能够得到更加广泛的应用。这些改进的遗传算法不 但提出了很多有自己特色的特性，也大量融入了其它一些进化计算算法的特点， 这使得它们与别的进化计算算法的界限变得比较模糊了。比较有特色的非标准遗 传算法有w h i t l e y 的g e n i t o r 系统，g r e f e n s t e t t e 的s a m u e l 系统”1 ，d a v i s 上海大学硕士学位论文 的遗传算法。，m i c h a 1 e w i c z 的进化程序。1 ，e s h e l m a n 的c h c 算法 ”：k o z a 的 遗传编程“1 1 ，以及c a n d i d a 的基因表达式编型”1 。实际上，有一些非标准的遗传 算法已经和标准遗传算法在实现、功能及主要应用范围等方面都发生了重大变 化，人们也把这些算法看成一种新的算法来进行研究。最典型的代表是遗传编程 和基因表达式编程。 标准遗传算法使用确定长度的二进制位串作为遗传编码，即个体的染色体。 通常为了解决函数优化问题，需要将位串按照一定的长度进行划分，每一段表示 一个分量，然后利用位段译码函数映射到每一个分量的定义域中。在其它一些应 用中，则需要对二进制位串进行编码，使其代表相应问题领域的特定意义。在标 准遗传算法中，最重要的遗传操作是重组算子，有些文献也称为杂交，或者交叉 算子。重组算子以一定的概率，即重组概率，作用在两个父代染色体上，产生两 个新的子代染色体。重组的概率一般都选择得比较大，在( 0 6 ，1 0 ) 之间。重组 算子中最重要的是单点重组算子。当进行单点重组算子操作的时候，随机产生一 个交叉点，然后，交换交叉点后的染色体部分，形成两个子代染色体。通过选择 更多的交叉点，并交替地交换交叉点之间的位段，可以将单点重组扩展到m 点重 组算子。另外，也有人提出一些其它的重组算子，比较有特色的是一致重组算子 “”。一致重组算子把两个父代的位串上的每一位都执行一个随机判定来决定是否 交换信息。 变异算子也被标准遗传算法所采用，但它一般被看成是辅助算子。变异算子 作用在单个染色体上，以一定的概率，即变异概率改变位串上的每一位，变异概 率一般都选择得比较小，通常在 0 0 0 1 ，0 0 1 之间，并且不依赖于目标变量的位 数和位串的总长。变异算子在标准遗传算法中被认为是次要的算子，这和其它两 个独立提出的进化计算算法，进化规划，进化策略都不一样。标准遗传算法认为， 变异算子的作用主要在于保持种群的多样性，防止种群过早地收敛到同一个，或 者相似的染色体上( 这种现象称为早熟现象，是遗传算法研究中的一个重要问 题) ，而不承担主要的进化动力的作用。 标准遗传算法中采用的是一种依据概率复制的选择算子。每一个个体被选择 复制到下一代的概率由该个体的适应度值决定。适应度值高的个体被选择的可能 性高，适应度值低的个体被选择的可能性低。常用的选择算子有比例选择、锦标 4 上海大学硕士学位论文 赛选择等等。比例选择算子让选择概率和适应度成正比，适应度值低于一定的阈 值的个体选择概率为0 。通常认为，比例选择算子有较强的选择能力，容易使标 准遗传算法以太快的速度收敛到局部最优。另外一种使用较多的选择算子是锦标 赛选择算子。锦标赛选择算子指定一个联赛规模n ，然后每次随机从父代种群中 选择n 个个体进行联赛，n 个个体中适应度最大的个体被选择复制，然后再进行 下次联赛，选择下一个子代个体。由于锦标赛选择算子每次进行联赛的时候，只 比较个体之间的相对适应度，因此，这是一种相对选择算子。联赛规模越小，锦 标赛选择算子的选择压力越弱，适应度较低的个体越有机会被选择复制到下一 代。总的来说，锦标赛选择算子对克服标准遗传算法中常见的早熟现象有很显著 的作用，因此，在很多实际应用中，常常采用锦标赛选择算子。 遗传算法已经得到了广泛应用。采用遗传算法解决旅行商问题是一个非常成 功的例子。遗传算法所能解决的旅行商问题的规模已经远远超过普通确定性算法 所能解答的规模。在作业调度、自动控制和机器学习等领域遗传算法也有非凡表 现。在实际工程应用中，通用电器公司和r e n s s e l a e r 综合技术学院的研究人员 成功地将遗传算法应用到了一种商业客机等使用的高函道比喷气发动机的涡轮 设计之中“”。 1 2 3 遗传编程 遗传算法的最重要特征之一，是采用经过编码的符号串作为个体的遗传编 码。特别是，标准遗传算法采用了定长的二进制编码来表示染色体结构。这种表 示形式具有通用性好、遗传操作非常简单等特点。针对不同问题，各种改进的遗 传算法编码方法能解决很多具体问题。 遗传编程( g e n e t i cp r o g r a n m i n g ，g p ) ，也称为遗传程序设计，或遗传规划， 是在遗传算法的基础上发展起来的，它采用了一种全新的个体描述方法，其实质 是采用层次结构来描述解决问题的计算机程序。因此，遗传编程是程序自动生成 技术的利器。 在遗传编程中，构成染色体结构的主要元素是函数集合和变常量集合。染 色体结构在初始化以及进化的过程中，根据问题的具体要求，在指定的函数集合 和变常量集合中选定符号构成树形结构的程序。树形结构的遗传编码是遗传编 程的重要特征。 上海大学硕士学位论文 作为进化计算的成员，遗传编程中也有一系列的遗传算子，例如，重组算子， 变异算子等等。这些遗传算子直接作用在树形结构中，例如，常用的重组算子随 机选定两棵父代个体的程序树中的节点，然后交换以选定节点为根节点的子树。 由于遗传编程能处理树形的程序结构，所以遗传编程己经被广泛应用于优化 控制、符号回归和公式发现等领域。虽然遗传编程有很广阔的前景，但它也存在 很多不足，例如它直接处理树形结构，效率低下、代码膨胀、影响搜索效率等等。 1 2 4 基因表达式编程 从形式上，g e p 和遗传算法类似，是一种进化计算方法，但是g e p 采用了个 体表现型和不同的遗传编码设计思路，即等长线性符号编码 2 0 l 。由于编码特别 巧妙，使得遗传操作非常简单，基本类似于标准遗传算法的遗传操作。从功能上， g e p 和遗传编程类似，能发现揭示问题本质的规则、公式，以及描述问题解答 过程的程序等等。由于g e p 综合了遗传算法和遗传编程两者之间的优点，g e p 的创始人c a n d i d a 声称，g e p 在解决复杂问题的时候，比传统的遗传编程方法效 率高出4 - - 6 个数量级【2 7 】。从这个角度上看，g e p 算法应该算是有一重大进步的 算法，堪称是新一代的进化计算算法。 第二章将着重介绍和分析g e p 的基本方法。 1 3 小结 本章主要介绍了什么是公式发现问题，以及常用的公式发现方法。分析和 比较了回归分析、遗传算法( g a ) 、遗传规划( g p ) 和基因表达式编程( g e p ) 四 种方法的优劣。 6 上海大学硕士学位论文 第二章基因表达式编程的基本方法 2 1 基因表达式编程的编码方式 在g e p 中，随机产生的初始种群由一个个染色体构成。每个染色体采用固定 长度的线性编码来表示。染色体由若干个基因组成，基因之间通过二元运算符( 通 常是加减乘除) 连接组成。”。 g e p 编码中每个基因的长度是固定的，基因由前端的有效k 表达式和后面的 填充部分组成。为了保证基因编码的有效性，编码被分为头部( h e a d ) 、尾部( t a i l ) 及常数域( d c ) 三部分，头部可以出现运算符和变量，而尾部只能出现变量。设头 部的长度为h ，容易证明，在运算符最多只有2 个操作数的情况下( 数学表达式 中通常是这样) ，只要尾部长度t = h + l 就能保证编码的前k ( 1 k 编码总长n ) 个符号组成一个有效的k 表达式，即不会出现运算符找不到操作数的情况“”。常 数域中可以存放用户希望出现在挖掘出的公式中的一些常数，也可以是在挖掘过 程中随机产生的常数。 例如：头部长度为9 ，尾部长度为1 0 ，随机产生的某个基因编码如下： + + ? 木乖? b ? 木x x y x x x x y y y 0 2 3 l 其中： 常数数组为 2 ，8 ，4 ，5 ，常数域中的0 2 3 1 表示公式中的常数在常数数组中的 位置； ? 表示常数； b 表示运算符s i n ； 那么，从上往下，从左往右可解析成如下表达式树( e x p r e s s i o nt r e e ，e t ) 如图2 1 所示： 7 上海大学硕士学位论文 图2 1 表达式树( e t ) 这棵表达式树的语义即为5 s i n x + 4 x y + 2 。 2 基因表达式编程的流程 基因表达式编程算法分为五个步骤“”： s t e p l 算法参数设置，初始化染色体群 s t e p 2 计算每个染色体的适应度函数( 即将染色体编码翻译成公式后和数 据的拟合程度) ，判断是否结束条件，满足结束，不满足转向s t e p 3 s t e p 3 遗传操作产生下一代： ( 1 ) 保留最好个体： ( 2 ) 进行各类遗传操作，包括：选择、复制、变异、插串、基因重组等。 s t e p 4 转至o s t e p 2 。 注：算法结束条件为最大适应度达到要求或者进化的代数达到预定值。 2 3 算法分析 2 3 1 编码中常数项集产生与选取 在传统的g e p 算法中，常数项集中的常数随机产生。为了提高公式的物理意 义，本文提出在常数数组中存放与待挖掘公式所处的领域有关的常数，人工设定 这些常数被选入常数项集中的概率。系统在初始化常数项集时，如果未选中常数 数组中的常数，则随机产生常数填充到常数项集中。下面通过如式2 1 所示物理 上海大学硕士学位论文 公式 吼+ 三 ( 2 1 ) 产生含正态分布噪声的1 5 组样例数据，用上述两种不同的常数项产生方式做了 两组试验进行对比，每组重复试验2 0 次。 当常数项随机产生时，取挖掘出的适应度最大的函数公式，如式2 2 所示； 把待挖掘公式所处的领域中经常出现的常数，如重力加速度g ( 9 8 ) ，圆周率 疗( 3 1 4 ) 放入常数数组中，设置这些常数被选中成为常数项的概率为0 5 ，取挖 掘出的适应度最大的函数公式，如式2 3 所示。 4 4 1 9 7 妒+ o 6 7 9 9 8 + y + q 8 5 4 9 + x + y n x ) + 2 + b ( y ) ( 2 2 ) b 1 3 1 4 ) + x ”b ( + b ( 爹一x ) + 0 5 9 8v 从式2 2 中看不出任何的物理意义，很难做出科学的解释。而式2 3 中9 8 是重 力加速度，挖掘出的公式已经和原物理公式s = o 5 * g * t 2 菲常接近，物理意义也 很明确。因此，在常数数组中人为选取部分与待挖掘公式所处的领域有关的常数， 将使挖掘出的公式的物理意义更加明确和容易理解。 2 3 2 适应度函数的选取 “适者生存”是生物在自然选择下进化的基本法则，适应度( f i t n e s s ) 是度 量物种对环境的适应能力的指标，适应度函数用来计算各基因所对应个体的适应 度，适应度函数的好坏直接影响着整个遗传操作的方向。 根据函数表达式的特点，我们设计了两种适应度函数，第一种适应度函数 ( n s r ) 的构造要点如下： 对于第j 个染色体， f l ( i ) = ( 2 4 ) 其中： 白表示根据第j 个染色体对应的函数表达式利用第个样本中的交量数据 求得的函数值； 9 上海大学硕士学位论文 乃表示第- ，个样本中包含的实际测得的该目标函数值的真实值； 为样本数量。 因此理想状态下，最大的适应度值为1 。 第2 种适应度函数( r s r ) 设计要点如下： 对于第j 个染色体： f 2 ( i ) ：蔓( m 二竖掣1 0 0 ) ( 2 5 ) = ( m j 掣+ l o o ) ( 2 5 ) j 。l1 其中： 白表示根据第j 个染色体对应的函数表达式利用第个样本中的变量数据 求得的函数值； 乃表示第个样本中包含的实际测得的该目标函数值的真实值； n 则为样本数量： 肘取2 0 0 0 。 因此，理想状态下，最大的适应度值为m * n 。 以采用与2 3 1 中同样的数据，分别用n s r 和r s r 两种适应度函数做2 0 组 试验。 * 剃 2 0 墨冀 1 5 要塞窑l o 譬嚣 5 罂骧0 团 5 1 0 时间段( s ) 图2 2 平均误差对比图线 从图2 2 可以明显看出，在有噪声的数据挖掘环境中，两种适应度函数起的 效果是明显不同的，采用f 1 作为适应度函数的效果明显高于采用f 2 的。 2 4 公式发现过程中存在的问题 第一个问题是如何提取和保留公式中有用的片断，使公式中良好的特性得以 继承。对基于遗传原理的公式发现方法，常采用的是染色体和表达式树相结合的 方法进行公式描述。染色体的描述方法被称为基因型，而表达树的表示方法被称 1 0 上海大学硕士学位论文 为表现型。以g e p 算法为倒，代数表达式( 2 6 ) a b 。d 4 2 z - g - e c 可以描述成表现型，见树状图2 3 ： ( 2 6 ) 图2 3 树状图 这里“q ”表示平方根函数。通过对树状图从左至右，从上到下的层次遍历 得到的基因型染色体表示如图2 4 ： | + | q ( ) c 一( a b ) de 图2 4g e p 串 可以看出，通过规则可以非常方便地实现染色体和树的互相转换，利用染色 体的线性结构进行遗传操作；利用树状图，进行公式的展示。但是这种映射关系 也存在着一个问题，一些公式中原来在一起的片断，例如a * b ，被分开放置，在 遗传过程中不利于对公式子结构的保护。 第二个问题是有关公式发现的基准问题和评判标准难以定义，因此如何客观 地判断一个公式发现方法的好坏存在一定的争议。目前的主要方法分为两种，一 种是寻找一些有代表意义的公式生成数据进行模拟，另一种方法是根据科学史上 的真实测试数据进行公式发现的模拟。 上海大学硕士学位论文 2 5 小结 本章分析了在利用g e p 算法进行公式发现时参数应当如何设置，以及在公 式发现过程中，g e p 算法自身存在的不足之处。为进一步改进g e p 算法、提高 公式发现的速度和精度奠定了基础。 1 2 上海大学硕士学位论文 第三章基因表达式编程的改进 3 。1 转基因技术的引入 就g e p 的进化过程来看，它是自由放任的，完全依赖其自身能力进化。一 旦程序开始运行，整个种群就处于失控状态，进化质量和速度难以预知，人们只 能被动接受完全的自然选择的结果。而g e p 进化的基础是在解空间上大范围地 随机搜索，在复杂函数的发现时有时会进化得相当艰难。因此当在某种情况下 g e p 自身进化出现困难时，如何对进化过程助一臂之力，是一个值得研究的问 题。 3 1 1 生物工程中的转基因技术 转基因技术1 叼就是将人工分离和修饰过的基因导入到目的生物体的基因组 中，从而达到改造生物的目的。当转入的基因整合到染色体上或基因组中以后， 这些基因就会与寄主生物的遗传物质一起向子代传递，并产生应有的生物学功 能。科学家利用现代生物技术的方法，将所需要的基因进行定位，分离克隆，然 后再将这个目的基因，通过载体转移到目标生物品种中去。主要研究步骤为： ( 1 ) 分离需要研究的目的基因或要分析的d n a 片段； ( 2 ) 在体外进行d n a 重组，即将外源d n a 片段连接到能自我复制又带有 选择标记的载体上： ( 3 ) 将重组的d n a 转移到受体细胞： ( 4 ) 筛选出含有目的d n a 的受体细胞克隆； ( 5 ) 将目的基因克隆到表达载体上，转入受体细胞进行表达，产生人们需要 的基因产物。 我们希望能够将这种技术引入到g e p 中，从而改善g e p 的进化能力。 3 1 2 基因编码方式的改进 染色体结构可以分为两个部分，一个部分是恒定区，而另一个部分是可变 区。因此可以将基因编码分为两个部分g 区和c 区。g 区则存放公式的结构，而 上海大学硕士学位论文 c 区存放公式中的一些系数，即常数。这两个区域被连接并用一个线性串表示， 见图3 1 。 图3 1 染色体的结构 对于表达公式结构的g 区，为了和代数表达式建立对应关系，借鉴g e p 的 方法通过树状图进行映射，但是与g e p 不同的是，g e p 采用的是从左到右“层序 存放”形成树状图，而现在采用深度优先1 的“根序存放”形成树状图。以图 2 3 为例，采用深度优先的方法，得到的g 区的基因的编码表达形式如图3 2 ： + f a 哆 c q d 多 图3 2 改进后的基因串( g 区) 可以看出，在公式中比较接近的内容片断。如：a * b 、d - c 在染色体串型表达 式中依旧在一起，这样就比较容易进行片断的提取和继承了。 对于树状结点图，如果个树结点最大允许的叶结点为m 个，很容易证明， 如果该树有k 个结点，那么总的结点数不大于m * k + i 。因此，当运算符的最大 目数已知和运算符个数确定的前提下，那么基因编码的g 区的长度就能被确定。 例如，已知运算符集( + ，一，母，q ，e ) 中的最大目数是两目，其中q 表示平 方根，e 为自然数为底的指数表达式，要求公式中最多含有5 个运算符，g 区的 长度为1 1 。为了确保生成的公式有效，要求串的第一位为运算符。图3 3 显示 了部分随机产生染色体串的g 区部分。 ( a ) ( b ) ( c ) 图3 3g 区举饲 1 4 上海大学硕士学位论文 对应的表达式树结构图见3 4 。 ( c ) 图3 4g 区表达式树举例 从图3 3 到3 4 可以看出，将串结构从前往后翻译到树结构时，当树结构已 经表达完整时，后面位点所代表的内容将被忽略。例如：图3 3 ( a ) 的内容被完 全映射成了表达式树，而图3 3 ( b ) 和图3 3 ( c ) 只是串结构前面的有效部分被映 上海大学硕士学位论文 射成了树结构。 基因编码的c 区是用于说明公式中的常数项的具体内容。如果g 区长度为l ， 其中运算符个数为k ，它所对应的c 区长度为l _ k ，这样保证了公式中的每一位 系数都能对应到c 区中的一位。 3 1 3 优良基因片段库的建立 优良基因片段( v a l u a b l ef r a g m e n t ，v f ) 集合初始来源分为两个部分，一个部 分来源于与该公式有关的领域知识，例如：挖掘一个与能量有关的公式，按照经 验可能与速度的平方有关，那么就可以把 w 作为v f 分子。另一部分则随机产 生。 v f 的集合不是一成不变的，随着染色体的进化过程进行动态更新。当种群进 化停滞代数大于v f 集合更新代数的阈值时，v f 集合根据强度进行调整。v f 的强 度i 计算公式见式( 3 1 ) 。 f i d ( v 巧，爿包) 厂( 爿包) o o o d ( a b , ) = 旦- 一 ( 3 1 ) 砌d ( 晖，4 包) f ( a b l ) f l 其中： v f j ：第j 个v f ； a b ，：第i 个染色体； f ( a b 。) ：a b ，的适应度； ，：第j 个v f 的强度； n ：种群中染色体的数量； 只耐( v f j , a b f ) ：判断喝串是否在a b r 串中，如果在a b ，串中，返回1 ，否 则返回05 g o o d ( a b ，) ：判断a b ，是否属于优秀染色体集合。 v f 集合准备进行调整时，候选的v f 是从优秀的基因编码片断中进行选取的。 3 1 4 算子描述 进化算子是所有进化算法的核心，不同的算子设计对进化将产生极大的影 1 6 上簿大学硬士学垃论史 响。下面对改进后的g e p 中的不同算子操作进行描述。 1 ) 选择和复制 选择与复制的依据是适应度的值，采用轮盘赌加精英保留法策略来完成，由 于染色体之间的差异非常大，所以计算得到的适应度值的差距也非常大，如果直 接用染色体的适应度作为比例计算的依据，可能会导致只有一个染色体被选择、 复制，从而导致进化过程过早收敛。因此，在进行复制比例计算时，没有直接选 择适应度的值，而是根据适应度值的排序计算，见式( 3 2 ) 兄：( n - r a n k ( a b , ) ) 2 ( 3 2 ) f f 2 冒 其中： a b i ：第i 个染色体； 冠：第i 个染色体复制比例； 1 7 ：种群中染色体的数量： r a n k c 4 b ，) ：染色体在种群中的排位，适应度越高，排位数越小。 2 ) 变异 变异可以发生在染色体的任何部位。然而，染色体的结构组织必须保持完整 无缺。在g 区，头部的符号只能进行操作符变异，而染色体其它位置的符号都可 以变成别的符号( 运算符、变量或常量) ，但是必须保证变异结束后整个染色体 的操作符的个数不变；在c 区，只能进行常数项位置的变异。这样。染色体的结 构组织被保留下来，并且所有经变异生成的新个体在结构上都是正确的编排。 例如，考虑每个染色体进行双点变异的情况，设染色体如表3 1 所示： 表3 1 变异前染色体 l 位置 1234s67 89 0 l23 45 6 7 l 编码qi ?x ? ? 2 3 l378 假设变异位置选择为位置3 和8 ，统计变异点的操作符数为1 。因此，这两 个变异点的变异值也必须满足操作符数为1 的限制条件。如果位置3 的“ ”变 成了“x ”：位置8 的“x ”变成了“”得到新的染色体，见表3 2 ： 上海大学硕士学位论文 表3 2 变异后染色体 l 位置l 23 4 5b7 8901234567 l 编码q| ? ?23l奢7窖 3 ) v f 串替换 按照v f 的强度和v f 串替换率，进行染色体的更新。v f 串替换的起始位置选 择与v f 的长度和染色体g 区的长度有关，如果g 区的长度为l ，而v f 串长度是 m ，那么可以选择的位置范围在1 到l - m 之间。如果v f 的起始字符不是运算符， 那么可以选择的位置范围缩小到在2 到l - m 之间。 以表3 。l 表示的染色体为例，假设选择的位置是1 ，v f 分子的内容是e - x ， 那么v f 替换后的染色体为见表3 3 。 表3 ，3v f 替换后染色体 i 位置 12345678g0 l 2 3456 7 i 编码 e? 岔3l乎78 口 一 替换后的染色体进行运算符个数的校验，如果运算符的个数与设定要求不一 致，通过强制变异进行调整，以满足限制条件。 4 ) v f 串插入 按照v f 的强度和v f 串插入率，进行染色体的更新。v f 串插入的起始位置选 择的范围与v f 串替换相同。以表3 1 表示的染色体为例，假设选择的位置是5 ， v f 分子的内容是e - x ，那么v f 插入后的染色体为见表3 4 。 表3 4v f 插入后染色体 l 位置 123456789 0 12345 67 十 8 | 编码oe ? 23l3 7 u 校验调整( 变异) l 位置1234 5 6789 0l 2 3 4s6 7 f s 编码口 | e?2童l3， 插串后的染色体进行运算符个数的校验，如果运算符的个数与设定要求不一 致，通过强制变异进行调整。可以采取变异措施是：如果运算符个数大于规定运 算符，选择离插入串尾部最近的运算符( 不包括插入串部分) 进行变异为操作数： 上海大学硕士学位论文 如果运算符个数小于规定运算符，选择离插入串头部最近的操作数( 不包括插入 串部分) 进行变异为运算符。 5 ) 移位 算法中可移位的元素是一些染色体的片段，这些片断可以被激活并跳到染色 体的其它部位。移位可以发生在g 段，也可以发生在c 段，但不能在这两段之间 发生互相之间的移位。以表3 1 表示的染色体为例，假设移位点位是g 段的3 到5 ，移入的位置是2 ，那么移位后的染色体为见表3 5 。 表3 ，5 移位后染色体 l 位置 l2345678 9o1 2 34567 l 编码q ? ?2 3l378 e 6 ) 交换 算法中可以进行两个元素的交换。与移位相同，交换可以发生在g 段，也可 以发生在c 段，但不能在这两段之间发生互相之间的移位。以表3 1 表示的染色 体为例，假设交换点位是g 段的3 和7 的位置，那么交换后的染色体为见表3 6 。 表3 6 交换后染色体 i 位置123456 7 89o1234567 i 编码q| ?2 3i客78 7 ) 常数集更新 由于公式的优劣除了与公式的结构形式有关以外，和公式中的常数的选取也 有着密切的联系。如果得到的公式结构很好，但是公式的系数不正确，那么该公 式的适应度也不高，很容易被忽视，从而不能得到有效的继承。因此在算法的操 作算子中设置了常数项的变异算子，进行常数项集更新。但是这个特殊的算子并 不是每一代都运行，只在停滞代数大于常数集更新代数的阈值运行。项集中常数 交异的概率与其每个常数在优秀个体中使用的比例有关，使用比例越高的常数， 其变异率越低。 1 9 上海大学硕士学位论文 3 1 5 算法实现 算法的流程如下： s t e p l ：算法参数初始化 基本参数设定、包括单条染色体的运算符数、染色体数目、v f 数目、最大 运行代数、最大允许相同运算代数、v f 集合更新代数阈值、变异概率、v f 串替 换概率、v f 串插入概率、移位概率、交换概率和常数集更新代数阈值。 s t e p 2 ：群体初始化 v f 初始化，染色体初始化。 s t e p 3 ：计算染色体的适应度 分别计算种群中n 个染色体的亲和度，选出优秀染色体。 s t e p 4 ：结束判断 更新运行代数和停滞代数； 如果停滞代数大于最大允许相同运算代数或者运行代数大于最大运行代数 程序转向s t e p 9 ，否则返回s t e p 5 。 s t e p 5 ：调整v f 强度 根据新的记忆种群，调整集合中各个片段解( v f ) 强度值。 s t e p 6 ：v f 集合调整 如果停滞代数大于v f 集合更新代数阈值，进行v f 集合调整，转向s t e p 8 ； s t e p 7 ：常数项集合调整 如果停滞代数大于常数项集合更新代数闽值，进行常数项集合调整。 s t e p 8 ：染色体进化 包括染色体的选择和复制、变异，v f 串替换，v f 串插入，移位和交换操作。 s t e p 9 ：结束 整个算法的步骤演