基于基因表达式编程函数挖掘和时间序列分析关键技术研究.pdf

-y-9 9 3 7 9四川I 大学硕士学位论文题目基王基固麦鲨盘缠程函数撞握塑瞳闻崖到佥板差毽堇盔研究作者避完成日期垄Q Q 鱼生垒旦羔量日专i F9 9 3 7 6 9基于基因表达式编程函数挖掘和时间序列分析关键技术研究计算机应用专业研究生：陈字指导教师：唐常杰摘要数据挖掘作为多领域的交叉学科，是近2 0 年来数据库界研究的热点；进化计算模型不需要太多领域知识和建立先验模型，在处理复杂的数据挖掘问题中得到了广泛的青睐。在函数挖掘和时间序列分析的问题中，取得了很大的成功。函数挖掘和时间序列分析的实践已经暴露出传统G E P 的缺陷：如难以挖掘分段函数和难以制定时间序列分析的嵌入维度等。在前人的工作基础上，本文结合了统计学和小波分析的方法，对G E P 在函数挖掘和时间序列分析的缺陷做出了一系列的改进。本文的主要工作和贡献如下：I)分析了G E P 用于分段函数挖掘存在的问题，提出了基于小波的函数分段点发现算法。该算法通过对待拟合数据进行离散小波变换，对小波细节系数进行分析，能够比较准确的发现分段函数的分段点的所在，从而使得G E P 能够快速准确地挖掘分段函数。2)在统计学理论的基础上提出了根据自相关系数将时间序列分为强变化时间序列和弱变化时间序列，并提出了基于I 卜步相关序列制定时间序列嵌入维度的算法。对于强变化时间序列提出了差分平均预测方法。通过对时间序列作一次差分的预处理后进行预测，取得了比原始G E P 方法更好的预测效果。对于弱变化时间序列提出了菲波那契加权平均滑动窗口预测的方法，通过菲波那契线性滤波器滤波后进行预测，取得了比原始G E P方法更为准确的预测结果。3)在小波变换的基础上，提出了针对强变化时间序列的基于小波近似系数的嵌入维度制定算法和针对弱变化时间序列的基于小波细节系数的嵌入维度制定算法。提出了两种基于小波滤波的G E P 时间序列预测方法：基于B 峙e-M a s s a r t 阈值策略的小波滤波预测方法和基于S t e i n 无偏估计阈值策略的小波滤波预测方法。这两种方法有效地滤除了时间序列中的噪声数据，使数据更为平滑，有效地提高了G E P 时间序列预测的准确度。4)通过一系列的实验验证了本文提出的所有方法的有效性，证明使用这些方法能够提高G E P 函数挖掘和时间序列分析的准确性。本文的组织如下：第一节函数发现和时间序列分析背景。成果和不足；第二节介绍了数据挖掘、进化计算和小波分析的基本概念，术语和方法。第三节提出了基于小波分析的G E P 分段函数挖掘方法；第四节提出了基于N 步相关序列G E P 时间序列的分析方法，给出了四种新的预测方法。第五节通过一系列的实验验证了本文提出了所有方法的有效性。关键词：基因表达式编程函数挖掘时间序列分段函数小波近似系数细节系数自相关系数N-步相关序列嵌入维度T h er e s e a r c ho fk e yt e c h n i q u e sf o rf u n c t i o nm i n i n ga n dt i m es e r i e sa n a l y s i sb yG e n eE x p r e s s i o nP r o g r a m m i n gS c h o o lo f C o m p u t e rS c i e n c eG r a d u a t e C H E NY uS u p e r v i s o r：T A N GC h a n g j i eA b s t r a c tD a t aM i n i n g,a sac r o s s-d i s c i p l i n e,h a sr e c e i v e dp l e n t yo fa t t e n t i o n si 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 w od e c a d e s A m o n gv a r i o u sd a t am i n i n gt e c h n o l o g i e s，E v o l u t i o nC o m p u t i n gh a sb e e nw i d e l ya p p l i e di nc o m p l e xp r o b l e mh a n d l i n gb 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 n O rm o d e l P a r t i c u l a r l y,a p p l y i n gG e n eE x p r e s s i o nP r o g r a m m i n gt of u n c t i o nm i n i n ga n dt i m es e r i e sa n a l y s i sh a sw o nb i gS U C C e s s 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 ri n s t a n c e,i ti sd i f f i c u l tt om i n es e g m e n t e df u n c t i o na n dt od e c i d et h ee m b e d d i n gd i m e n s i o nf o rt i m es e r i e s B a s e do ne x i s t i n gr e s e a r c h,t h i st h e s i sc o m b i n e sG E Pw i t hs t a t i s t i c sa n dw a v e l e ta n a l y s i st of o r maf e wn e wm e t h o d sf o rf u n c t i o nm i n i n ga n dt i m es e r i e sp r e d i c t i o n T h em a i nr 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)A n a l y s e st h ed i s a d v a n t a g e so fo r i g i n a lG E Pi ns e g m e n t e df u n c t i o nm i n i n ga n dp r o p o s e sW a v e l e t b a s e dS e g m e n tP o i r r tF i n d i n gA l g o r i t h m T h i sa l g o r i t h ma p p l i e sad i s c r e t ew a v e l e tt r a n s f o r m a t i o no nt r a i n i n gd a t a T h r o u g ha na n a l y s i so nw a v e l e td e t a i lc o e f f i c i e n t s i tc a nd i s c o v e rt h es e g m e n tp o i n t so fs e g m e n t e df u n c t i o n sa n dh e n c ee n a b l eG E Pt om i n es c g m e m e df u n c t i o n se f f e c t i v e l y 2)P r o p o s e ss e l f-c o r r e l a t i o nc o e f f i c i e n t sb a s e dm e t h o dt oc l a s s i f yt i m es e r i e si n t oS e v e r eV i b r a t e d-t i m eS e r i e sa n dM i l dV i b r a t e dT i m eS e r i e s，a n df u r t h e r m o r e，p r o p o s e sE m b e d d i n gD i m e n s i o nD e c i s i o nA l g o r i t h mb a s e do nN-s t e pc o r r e l a t i o ns e r i e s T oc o p ew i t hS e v e r eV i b r a t e dn m eS e r i e s,t h i st h e s i sp r o p o s e sD i f f e r e n c eA v e r a g eP r e d i c t i o nM e t h o d,w h i c hc a no b t a i nam O r ea c c u r a t er e s u l t st h a no r i g i n a lG E Pt h r o u g had i f f e r e n c eo p e r a t i o no nt i m es e r i e sd a t a；T od e a lw i t hM i l dV i b r a t e dT i m eS e r i e s，T h i ss t u d ya d v a n c e sF i b o n a c c i-W e i g h t e dA v e r a g eS l i d i n gW i n d o wP r e d i c t i o nM e t h o d,w h i c hc a nr e a c hh i g h e ra c c u r a c yt h a no r i g i n a lG E Pt h r o u 曲al i n e a rF i b o n a c c if i l t e rf o rt i m es e r i e sd a t a 3 1P r o p o s e sa ne m b e d d i n gd i m e n s i o nd e c i d i n ga l g o r i t h mb a s e d0 1 1 _ w a v e l e ta p p r o x i m a t ec o e f f i c i e n t st oh a n d l eS e v e r eV i b r a t e dT i m eS e r i e sa n da n o t h e ra l g o r i t h mb a s e do nw a v e l e td e t a i lc o e 伍c i e n t st oh a n d l eM i l dV i b r a t e dT i m eS e r i e s P u t sf o r w a r dt w ot i m es e r i e sp r e d i c a t i n gm e t h o d sb a s e do i l w a v e l e tf i l t e r i n g,B i r g e-M a s s a r tT h r e s h o l db a s e dW a v e l e tF i l t e r i n gP r e d i c a t i n gM e t h o da sw e l la sS t e i nS U R ET h r e s h o l db a s e dW a v e l e tF i l t e r i n gP r e d i c a t i n gM e t h o d T h e s et w om e t h o d sf i k e rn o i s ed a t ai nt i m es e r i e sa n dm a k et h ed a t as m o o t h e r,a n dh e n c ei m p r o v et h ep r e d i c a t i o np r e c i s i o n。硼_ l i st h e s i so r g a n i z e da sf o l l o w s S e c t i o nli n t r o d u c e st h eb a c k g r o u n d，a c h i e v e m e n t sa n dI i m i t a t i o n so ff u n c t i o nm i n i n ga n dt i m es e r i e sp r e d i c a t i o n；S e c t i o n2b r i e f l yi n t r o d u c e st h eb a s i ct e r m i n o l o g ya n dm e t h o d o l o g yo fd a t am i n i n g,e v o l u t i o nc o m p u t i n ga n d w a v e l e ta n a l y s i s；S e c t i o n3p r o p o s e saW a v e l e t-b a s e dS e g m e n tP o i n tF i n d i n gA l g o r i t h mf o rG E Pt om i n es e g m e n t e df u n c t i o n s；S e c t i o n4p r o p o s e sE m b e d d i n gD i m e n s i o nD e c i s i o nA l g o r i t h mb a s e do nN-s t e pc o r r e l a t i o ns e r i e sa n da d d i t i o n a l l yf o u rn o v e lp r e d i c a t i n gm e t h o d s S e c t i o n5d e m o n s t r a t e st h ee 彘e t i v e n e s so fa l It h em e t h o d si nt h i sp a p e rb ye x t e n s i v ee x p e r i m e n t s K e yw o r d s：G e n eE x p r e s s i o nP r o g r a m m i n g,F u n e t i o nM i n i n g,T i m eS e r i e s，S e g m e n t e dF u n c t i o n,W a v e l e t，A p p r o x i m a t eC o e f f i c i e n t s,D e t a i lC o e f f i c i e n t s,S e l f-C o r r e l a t i o nC o e f f i c i e n t s，N-s t e pC o r r e l a t i o nS e r i e s，E m b e d d i n gD i m e n s i o n1 引言函数挖掘，作为一个既古老又年轻的领域一直吸引着无数研究者的目光。哲学认为：世界是一个普遍联系的整体，其运动受一定规律的支配。千百年来，人们在认识世界，改造世界的过程中不断地认识和发现新的规律，并把这些规律运用于实践，进一步推动认识世界和改造世界的过程。牛顿从天体运动观测数据中发现了万有引力定律，实际上就是一个函数挖掘的过程，其结果进一步推动了其他场力的计算和分析。在计算机发明以前，人们对函数的发现主要依靠多年不懈的辛勤工作加上一些突发的灵感。例如法拉第发现电磁感应定律就是在做了数十年实验后，在一次偶然的事件中获得了灵感而得到的。随着人们对数学和统计学研究的不断深入，人们提出了最小二乘法(L e a s tS q u a r eF i t t i l l g)等一系列函数发现的方法，在函数发现领域取得了很大的进步。进入2 0 世纪中后期，随着计算机技术的不断发展，计算机技术被不断运用到了各个领域，极大地推动了各个领域的发展。在函数发现领域，在用计算机实现了以往的方法的同时，随着生物技术的发展，仿生计算开始被运用到函数发现领域，并取得了巨大的成功。神经网络，遗传算法等新方法的提出，为函数发现提供了一系列行之有效的方法。2 0 0 1 年葡萄牙学者C f i n d i d a在遗传算法(G e n e t i c A 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,G 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)技术，它既有G A 简单的表达结构，又有G P 能处理较为复杂问题的特点。将G E P应用于函数发现领域获得了比G A 和G P 更大的成功，它不仅能发现更为复杂的函数，而且其运行速度也比G P 快1 0 0-6 0 0 0 0 倍【1 3 1。用G E P 进行函数发现与传统的统计学方法相比具有不需要事先知道数学模型，能够发现具有复杂形式的函数的优点，但也存在着一些不足，比如对于分段函数难以进行有效的挖掘。针对这个问题，本文提出了基于小波变换的分段点发现算法，较为有效地解决了分段函数挖掘的问题。时间序列分析作为一类特殊的函数发现问题，相比于常见的函数发现问2f题，时间序列分析有数学模型难以建立，在数学模型建立后又难以进行参数估计等特殊困难。基因表达式编程(G E P)应用于时间序列分析虽然能解决一部分的问题，但也存在着嵌入维度难以制定的问题。针对这一问题，本文提出了根据自相关系数划分时间序列的办法，将时间序列分为强变化时间序列和弱变化时间序列。并且分而治之，对强变化时间序列和弱变化时间序列分别提出了基于N 步相关序列的嵌入维度制定算法和基于小波细节系数的嵌入维制定算法，在此基础上还提出了菲波那契加权平均预测法，差分平均预测法以及基于S t e i n 无偏估计阈值策略的小波滤波预测法和基于B i r g e M a s s a r t阂值策略的小波滤波预测法，取得了比传统的G E P 滑动窗口预测法更好的结果。2 背景知识2 1 数据挖掘简介自从2 0 世纪6 0 年代以来，数据库和信息技术已经从原始的文件处理演化为了复杂的，功能强大的数据库系统。经过几十年的发展，数据库已经由最初的层次和网状数据库发展到了关系数据库，面向对象数据库，其功能由简单走向复杂，由单机走向网络，其容量也由小到大。数据库系统的各种问题，如分布性，多样性和数据共享问题都得到了广泛的研究，取得了很大的进展，数据库现在在商务，医学，科研等方面都得到了广泛的应用。随着I n t e m e t 的普及，数据库也成为了网络数据，多媒体信息的存储介质，其内容和容量都得到了极大的丰富。数据的丰富使得人们对于数据的理解变得困难。大量的未被理船的数据被描述为“数据丰富，但信息贫乏。”以几何级数增长的海量数据存放在大型的数据库中，在没有强有力的工具帮助下，理解它们已经远远超出了人们的能力；而且在这些海量的数据库还存在着一些噪声甚至是错误，这也会对人们理解数据造成不小的困难。，需要是发明之母。数据挖掘技术于上世纪8 0 年代诞生了。数据挖掘旨在从海量数据中提取人们通常难以觉察，但又是感兴趣的知识，并将这些知识运用于决策支持的过程【1 I t 2 1。许多人把数据挖掘视为另一个常用术语知识发现(K D D)的同义词，而另一部分人只是把数据挖掘视为数据库中知识发现过程中的基本步骤。数据挖掘的任务一般可以分为两类：描述和预测。描述性挖掘任务的刻画数据数据库中数据的一半特性，而预测性挖掘任务在当前数据上进行推断，以进行预测。数据挖掘的功能以及它们可以发现的模式类型如下所述【1】【2 1：1)概念，类推述：特征化和区分。数据特征化是目标类数据的一般特征或特性的汇总。数据区分是将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。2)关联规则分析(3】；关联规则是形如“X Y”的形式，含义为“满足x 中条件的数据库元组多半也满足Y 条件。”关联规则一般还有支持度和置信度两个描述参数，表明了X Y 同时发生的频率和x 发生后Y 发生的可信程度。关联规则挖掘被广泛地用在事务数据库中，挖掘出一些不为人知的规律，用于决策支持。例如：使用关联规则挖掘得出了“啤酒尿布”的关联规则，为超级市场的货物摆放提供了很好的建议。3)分类和预测【l】：分类即是把数据按照一定的标准分为若干类的过程，又称为有监督学习。首先，通过对训练集中的对象的分析，建立一个模型，并用这个模型对还未分类的对象进行分类。4)聚类分析【1】：聚类分析又称无监督学习。与分类不同的是，聚类要划分的类是未知的，即是在没有训练集的条件下，把对象分组成几个类，使类内的相似度大而类间相似度小。5)孤立点分析 1】：孤立点分析即是找出一些数据对象，它们与数据的一般行为和模型不一致。虽然在大部分数据挖掘应用中将它们视为噪声或异常而丢弃。然而，在一些应用(如欺诈检测)中，罕见的事件可能比正常出现的更有关注价值。数据挖掘是一门交叉学科，它涉及数据库技术，统计学，人工智能，模式识别，机器学习，高性能计算，神经网络和数据可视化等。随着数据挖掘技术被广泛地应用于生物，物理，医学等各个领域，与各个领域的领域知识加以结合，解决了很多问题，获得了很多用以前的办法难以发现的知识，同时，也遇到了很多特殊的问题，对研究者和开发者提出了巨大的挑战。数据挖掘是当前数据库中最重要也是最有前途的研究前沿之一。2 2 函数挖掘技术简介函数挖掘是一门既古老又年轻的学科，其主要任务就是从观测数据中找出一个能够刻画观测数据规律的函数来指导实践。函数挖掘又称为符号回归(S y m b o l i cR e g r e s s i o n,s R)，传统的符号回归方法得主要步骤为【4 l：1)建立数学模型：根据观测数据估计，估计变量之间的定量关系式，确定相应的数学模型(如线性，非线性等)。2)参数估计与验证：估计选定模型中未知参数，并对模型提出的各种假没进行验证。3)预N-利用挖掘出的函数对一组新的数据进行预测。函数挖掘的经典统计学方法是最小二乘法；郎假定随机变量Y(因变量)和随机变量X(字变量)满足Y=Q+1 3 X 的线性关系，这里的线性关系可能是直线、平面或超平面。最小二乘法可以求得相应的a 和B，使得相应残差平方和最小。在线性模型的基础上，人们又提出了用非线性的多项式模型来拟合观测数据。通过对变量进行变换，可以将非线性模型转换为线性模型，用最小二乘法求出系数。另外，人们还提出了广义线性模型，如对数回归和泊松回归来船决更为复杂的问题。2 3 时间序列分析简介时间序列是按时间次序排列的随机变量序列。时问序列分析旨在通过对已有的时间序列数据进行分析，建立较好的数学模型，对未来的数据进行预测。时间序列分析是概率统计学科中应用性较强的一个分支，在金融经济、气象水文、信号处理、机械振动等诸多领域有着广泛的应用。传统的时间序列分析主要是基于统计学的方法，经过多年的不懈研究，已经形成了一个比较完整的理论系统，许多理论结果对时间都有重要的指导意义。经过多年的研究和实践，人们提出了许多有效的模型：如自回归模型A 默n)，滑动平均模型M A(m)，自回归滑动平均模型M m A(n m)以及非平稳的A l l Y A(r t,m)模型等嘲【6 l。这些模型的特点是都属于线性模型，即假定时间序列都是由随机变量的线性组合得到的。虽然在实现上比较简单，具有很好的可操作性，但是毕竟与实际不太相符，先验地假设时间序列是线性模型毕竞有些武断。在过去的几十年中，研究者们又纷纷提出了一系列行之有效的新方法，比如径向基函数网络，傅里叶分析，小波分析等，取得了更好的效果。最近数年，随着仿生算法的兴起，很多新的办法被应用到了时间序列分析中。随着神经网络(N e u t r a lN e t w o r k)的兴起，不少研究者都把它运用在时间序列分析上，提出了很多有用的模型1 7 1 1 8 1。而随着进化计算的兴起，研究者也把进化计算应用到了时间序列分析上：G e o r g e G，S 提出了一种基于遗传算法(G e n e t i cA l g o r i t h m,G A)的时间序列预测模型来预测太阳黑子问题 9 1 1 0 1 1 1】。康立三等人则利用遗传编程(G e n e t i c P r o g r a m m i n g,G P)构建了常微分方程组来解决时间序列预测问题【1 2 1。但是，G A 由于其简单的结构而无法应付复杂的问题，G P 则由于其不规则的树形结构而在变异过程中会产生大量的无效表达式，从而使G P 变得效率很低1 1 3 1 1 1 4 1。2 0 0 1 年，葡萄牙学者C a n d i d aF e r r e i r a 在G A 和G P 的基础上提出了基因表达式编程(G o n eE x p r e s s i o nP r o g r a n u n i n g,G E P)1 1 3 11 1 4 1 ”】这一崭新的方法，采用了基因型和表示型相分离而又互相转化的创举，克服了G A 难以应付复杂问题和G P 效率低下的缺点。C f i n d i d a 将G E P 运用在函数发现，分类分析以及时间序列分析等问题中，在更短的时间内取得了比G A 和G P 更好的效果。6研究者又在函数挖掘的基础上结合关联规则中的频繁项集的概念提出了频繁函数集挖掘，从而拓展了G E P 函数挖掘的能力。时间序列分析问题可以简单地描述如下：按时间次序排列的随机变量J 芋列x l，x 2，X 3 称为时间序列。如果用X 1。X Z，x N 分别表示x 1，X 2，)(N 的观测值，则称x l，x 2，x N 为x l，x 2，)(N 的N 个观测样本。时间序列分析的任务在于通过对观测样本的分析，建立一个尽可能合理的模型，然后用这个模型去解释观测样本的统计规律，并预报未来的数据。其基本的思想是“过去+现状一未来”。2 4 时间序列分析的基本术语和方法本质上，时间序列分析问题是一类特殊的符号回归问题。旨在寻找一个模型，该模型是兼容于若干自变量的若干观测值多元函数。其中自变量的数目称为嵌入维度(E m b e d d i n gD i m e n s i o n)。在数据处理中，在两个被处理的观测数据之间忽略的观测数据的个数，称为时间延迟(D e l a yT i m e)p 4 l ”l。如果它等于l，表示时间序列的每个观测数据都会被处理，如果它大于1，表示一些观测数据将会被跳过。在本文中所有的时间序列分析问题都取时间延迟为l。滑动窗口预测法是时间序列分析中最常用方法，其基本思想是=对于一个育n 个数据的时间序列，给定历史长度l l，寻找一个公式使得对任意的砜(n-h+l m n)，计算预测值X=t X。h，X m h n，X+a，X。0h ms n使得x 的预测值和真实值的差别尽量小。这个差别可以用绝对误差，相对误差和相关系数等标准来度最。整个滑动窗口的预测过程可以描述为一个长度为m+l 的窗口在时间序列数据上滑动，通过窗口中的前的h 个数据来顶测第l l+1 个数据。其中h 的大小即是我们在前面提到的嵌入维度。7f2，5 1G E P 的基因型和表现型基因表达式编程由C f i n d i d aF e r r e i r a 于2 0 0 1 年1 2 月首次提出。G E P 在继承遗传算法(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)的思想的基础上，创新性地提出基因型(染色体)和表现型(表达式树)既分离又相互转化的模型，克服了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)。基因，和G A 相同，是线性的定长的字符串，然而G E P 创新地把字符串分为头部(H e a d)年q 尾部(T a n)两部分，头部包含变量集(V a r i a b l es e t)中的变量和函数集(F u n c t i o nS e t)中的函数，而尾部只包含变量。头尾长度(分别记为h，t)有如下关系：t=h(n-1 卜l(2-1)其中，n 为函数集中所有函数的最大目数，即函数能接收的最多的参数个数。比如“+”的且数为2，而“f(x)=-x”的目数为1。所以如果有F u n e t i o a S e t=a n d,o r,n o t l，则该F u n c t i o n S a 的n=2。G E P 中的表现型是表达式树(E x p r e s s i o nT r e e)。它和基因型之间可以相互转化。在文献【1 7 中证明了，只要基因型的头部和尾部长度满足公式(2 一1)，就能够保证基因型能够在经过一系列的遗传算子操作之后仍能够转化为表现型。表现型和基因型相互转化的的方法简言之，就是对表达式树进行从上到下，从左至右的层次遍历，就可以得到相应的字符串(基因型)；而将字符串进行逆操作就可以待到相应的表达式树。例2 1 设有有如下的单基因染色体(基因头部长为4，Q 代表开平方运算)：0 1 2 3 4 5 6 7 8Q+一十a b c d e8其对应的表达式和表达式树如图2 1 所示：图2 1 表明：图2 1 代数表达式与表达式1)通过层次遍历就可以在字符串和表达式树之间相互转化。2)对表达式树进行层次遍历得到的字符串称为K 一表达式(K-E x p r e s s i o n)。3)基因字符串中能够被转化到表达式树的中的那些字符组成了O p e n i n gR 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 gr e g i o n)。非编码区域看上去虽然不太重要，但是这正是G E P 区别于G A 和G P 的地方。非编码区域虽然在本次解码中不会彼用到，但是在以后的变异过(d+P)4+(b c)图2 2 变异后非编码区域成为了程中很可能被用到。比如发生在位置0 的变异将“Q”变成了“+”，则整个表达式树变成了图2 的形式。图2 2 表明，一旦发生了变异，原本在非编码区域的变量e 就进入了O R F，成为了表达式的有效部分。G E P 中的非编码区域在整个进化中起到了很深刻的作用。这是这些非编码区域的存在使得G E P 在各种遗传算子的作用下不用加入其它约束条件就能产生出有效的表达式；而G P由于缺少非编码区域，使得遗传算子作用的时候必须在事先采用很复杂的约束条件，事后又需要花费大量的时间来检查表达式的育效性。这就是G E P 在9效率上大大优于G P 的重要原因【1 3 1【1 4 1。2 5 2G E P 的遗传算子和适应度函数由于G E P 的基因型结构类似于G A，因此其遗传算子也类似于G A。G E P的主要遗传算子如下【l s l：变异算子(M u t a t i o n)；变异算子作用于单个染色体上，将染色体中的每一位进行随机测试，当满足一定的变异概率P m(通常选用00 4 4)，就将这一位随机的变成另外一个符号。为了保证G E P 染色体的组织结构不变，发生在头部的变异，变异位可以变成函数集和变量集的任意符号，而发生在尾部的变异则只能填入变量集中的变量。插串算子(I n s e r t i o nS e q u e n c e，I S)：是G E P 所特有的遗传算子。它随机在基因中选择一段子串，然后将该子串插入到头部的随机指定的一个位置(但不能是第1 个位置)，将头部的其他符号向后顺延，超过头部长度的编码将被截去。根插串算子(R o o t I n s e r t i o nS e q u e n c e，R I S)：从头部的随机选择的一个位置开始向后扫描，找到第一个函数，然后以该位置为起始，选择一段子串，将该子串插入到第1 个位置，头部编码依次后移，超过头部的部分被截去。如果扫描过程没有找到函数，则不做任何事情。单点重组算子(O n e-p o i n tR e c o m b i n a t i o n)；在两个父代染色体上，随机选择一个交叉位置，互换交叉点后面的染色体部分，得到两个子代染色体。双点重组算子(T w o p o i n tR e c o m b i n a t i o n)：和单点重组算子一样，双点重组算子也是作用在两个父代染色体上。在父代染色体上随机选择两个交叉点，然后互换交叉点之间的染色体部分。基因重组算子(G e n e R e c o m b i n a t i o n)：适用于多基因的染色体，其实是双点重组算子的特殊情况。该算子随机选择一个位置的基因，然后交换两个父代染色体的相对应位置的基因。从上面我们可以知道，这些算子的使用具有很少的限制，而按照这些算子进行操作，可以保证G E P 组织结构不变，即可以保证G E P 的基因型始终能够解码为表现型。1 0，根据c a。i d aF。m 打。的实验，我们得知在这些遗传算子中，变异算子是R e l a t t v e E r r o r F i t n e s s：窆_|华l o o I)(2-3)J 1 1I1 JIC o r r e l a t i o n C o e f f i c i e n t F i t n e s s：1 一S S E(2-4)S S i j其中，s s E-y O,，-5,，)2，S S T=Z 厂_)2式(2-2)和(2 3)中的M 称为选捧范围(r a n g eo fs e l e c t i o n),J 1 1,1 是数据个数，c j为对于第j 各数据用G E P 得出的公式所预测的值，T J 为第j 个目标值。从公式中可以很容易看出，绝对误差适应度和相对误差适应度的最大值都是n M，而相关系数适应度的最大值是l。2 5 3G E P 的运行流程G E P 的运行流程和G A、G P 类似，流程图如图2 3 所示【1 0 1【1 3 1：图2 3O E P 的流程图1 2I，在整个G E P 的流程中，创建初始种群的染色体是一今随机生成染色体字2 6 小波分析简介小波最先在工程中被地球物理学家用来分析通过爆炸方法产生的人造地震数据，以便找油、探矿等。小波，顾名思义就是“小的波”。一个小的波本质上生成和衰减子一个有限的时间周期内。小波函数一种的数学描述是：积分为零且平方可积的函数，在实际应用中，我们一般选用平方积分为1。小波有两个函数，即尺度函数中和小波函数v，这两个函数产生了组可以用于分辑和重构信号的函数族。常用的小波有H a a r 小波，D a u b e c h i e s 小波，C o i f l e t 小波，M o r l