（计算机应用技术专业论文）基于gep函数发现的智能模型库关键技术研究.pdf

基于g e p 函数发现的智能模型库关键技术研究 计算机应用技术专业 研究生元昌安指导教师唐常杰 计算机技术广泛而深入的应用对决策支持提出了更高的要求。智能决策支 持系统( i n t e l l i g e n t d e c i s i o n s u p p o r t s y s t e m s ，i d s s ) 应运而生。 模型库予系统是决策支持系统的核心。但传统模型库的建立方法存在以下 缺点： ( 1 ) 需预先确定好模型库中模型的类型，d s s 只能根据样本数据对现有 的模型进行有关参数计算，进而让决策者根据结果来进行预测。这 种模型库缺少了真正意义上的智能寻找模型类型的功能。 ( 2 ) 可能依赖领域的专家经验。如专家系统需要一个内容丰富而全面的 知识库支撑，依靠的是某领域的专家经验，因此，该智能模型库对 先验知识依赖性很强，难以实现真正意义上的智能化。 ( 3 ) 在预先不知模型类型时，需凭经验确定模型类型，含有主观和盲目 因素。 ( 4 ) 传统方法目前不能支持复杂函数关系式和多分段函数关系式等模型 的建立。 ( 5 ) 扩展性较差。针对不同的函数模型类型，在程序实现时就必须有一 个新的程序模块。当模型库要进行扩充，系统就要为该模型增加新 的代码。 为了解决以上问题，本文将基因表达式编程( 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 ) 技术引入智能模型库的研究中。 ， f 基因表达式编程具有极强的函数发现能力和很高的效率，并且在函数发现 时不需要任何先验知识，无需预存函数模型的类型，避免了传统算法建模时事 先选定函数类型的盲目性。 基因表达式编程研究领域尚有许多空白点，如g e p 的理论分析、基于 g e p 属性约简的函数挖掘、基于残差分布适应度g e p 方法等等。本文的工作 是基于这些空白点展开，并将g e p 这种新技术引入到d s s 。 本文主要贡献如下： ( 1 ) 提出并实现了两种数据预处理方法： i 复共线性数据的预处理算法e m d p a ( e m u l t i c o l l i n e a r i t yd a t a p r e p r o c e s s i n ga l g o r i t h m ) ，该方法是针对在函数发现中要处理的数 据具有复共线性时数据的预处理办法 i i 基于h a s h 函数取样的数据预处理算法h s d p a ( h 勰hs a m p l i n gb a s e d d a t a 胁p r o c e s s i i l ga l _ g o r i t h m ) ，其中的取样是在总体数据太庞大时， 为了提高函数发现的效率和样本质量，所采取的抽样技术。 ( 2 ) 针对g e p 理论的不足或空白点，对g e p 的基本概念进行了一系列 的形式化描述。利用马尔可夫链理论，对群体为离散型的g e p 进 行了收敛性分析，证明了g e p 的马尔可夫链收敛性定理。针对群 体为一般型的g e p ，分析了适应度函数的收敛性，并证明了最小残 差平方和依概率收敛定理。在理论上保证了g e p 方法的可靠性和 可行性。 ( 3 ) 提出了显式模型概念和基于g e p 的显式模型挖掘算法( g e p - e x p l i c i tm o d e lm i n i n ga l g o r i t h m ，g e p e i m a ) ，新方法兼容了传统函 数发现算法显式模型的挖掘，实现了系统的易扩展性。同时，通过 实验验证了算法的有效性。 ( 4 ) 根据g e p 函数发现依概率收敛定理，提出了基于g e p 的残差制导 进化算法( g e p r g e a ) ，提高了g e p 算法的效率。并通过3 个实验 与g p 以及其它预测方法进行了对比性实验。实验结果表明，在噪 声数据很小的情况下，三种算法均挖掘出目标函数，但g e p 比g p 的收敛速度提高了2 0 倍，r g e a 比g p 提高了6 0 倍。对于函数类 一 j i 型未知且极为复杂的数据，g e p 和r g e a 在发现理想函数的速度 上要比g p 分别快9 0 0 、1 8 0 0 倍。 ( 5 ) 提出了边际基因、边际适应度、残差分布适应度概念以及基于边际 适应度和残差分布适应度的g e p 算法( g e p m f r d f ) ，算法保证了 残差服从近似正态分布，克服了传统g e p 算法一昧追求残差绝对 值小，忽略残差应满足正态分布的要求，有可能导致系统误差的不 足。提出了基于g e p 的贪婪式属性约简函数挖掘算法( g e pb a s e d g r e e d ya t t r i b u t e r e d u c t i o nf u n c t i o n m i n i n ga l g o r i t h m ，g e p - g a r f m a ) 和基于g e p 的逐步属性约简函数挖掘算法( g e p b a s e ds t e p w i s ea t t r i b u t er e d u c t i o nf u n c t i o nm i n i n ga l g o r i t h m ， g e p s a 砌7 m a ) ，使系统能在自变量很多情况下自动实现属性约 简的函数挖掘功能。通过两个实验验证了算法的有效性。实验表 明：( a ) g e p - g a r f m a 和g e p - s a r f m a 在发现最优函数表达式 时，均能有效地进行属性约简；( bg e p 。s a r f m a 发现的函数表达 式精度与g e p - g a r f m a 方法差不多；( c ) 当自变量个数为2 0 时， g e p - s a r f m a 方法比g e p g a r f m a 快3 0 0 倍；( d ) 使用g e p - s a r f m a 挖掘的函数模型的适应度函数值比传统方法提高 2 4 6 。 ( 6 ) 提出并实现了基于g e p 函数发现的智能模型库系统( g e pb a s e d i n t e l l i g e n tm o d e lb a s es y s t e m ，g e p i n b s ) ，给出了g e p i m b s 系 统与g i s 、d s s 等接口技术。该系统是真正意义的无先验知识的智 能模型库系统，模型的类型和参数的求解均由程序自己来实现。通 过一个真实数据实验验证g e p i m b s 系统在函数挖掘上的有效性， 实验表明，g e p i m b s 系统挖掘的函数模型精度比传统方法提高了 近十五个百分点。 关键词：基因表达式编程智能模型库决策支持系统函数发现 遗传算法收敛性属性约简数据挖掘 i；flj 11 k e l t h er e s e a r c ho nk e yt e c h n i q u e si ni n t e l l i g e n tm o d e lb a s e b a s e do rf u n c t i o nf i n d i n gb yg e p s p e c i a l i t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y p h dc a n d i d a t e ：y u a nc h a n g a n a d v i s o r ：p r o f t a n gc h a n g j i e a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n da p p l i c a t i o n d e c i s i o n s u p p o r ts y s t e m s ( d s s ) w e r ed e m a n d e d t od e a lw i t hm o t ec o m p l e xp r o b l e m s i n t e l l i g e n td e c i s i o ns u p p o r ts y s t e m sg d s s ) h a v ee m e r g e d a st h et ：l n l e sr e q u i r e s u b - s y s t e mo fm o d e lb a s e i sc o l eo fd s s t h et r a d i t i o n a lm e t h o d so f c o n s l r u c t i n gm o d e lb a s eh a v ed e f e c t sa sf o l l o w s ( 1 ) u s e r sm u s tp r e v i o u s l yk n o wt h et y p e so fm o d e l si nt h em o d e lb a s e t h e d s so n l yc a l c u l a t e st h en n k n o w n p a r a m e t e r so ft h em o d e l si nm o d e lb a s e i nt e r m s o ft h es a m p l ed a t a t h e nt h ed e c i s i o n - m a k e rc o u l dp r e d i c t si nt e r m so ft h em o d e l s t h e s em o d e lb a s e sd e p e n do nt h es e l e 州o no ft h et y 】p co ft h em o d e l 。a n dd on o t i m p l e m e n ti n t e l l i g e n t i z a t i o nf o rm o d e lb a s e ( 2 ) t h et r a d i t i o n a li n t e l l i g e n te x p e r tm o d e lb a s ed e p e n d s o ne x p e r t s e x p e r i e n c e s i n s p e c i f i c d o m a i n s u c hm o d e lb a s en e e d sa l la b u n d a n ta n d c o m p r e h e n s i v ek n o w l e d g eb a s et os u p p o r ta n dd e p e n d so ns p e c i a l i s te x p e r i e n c eo f s p e c i a lf i e l d s c o n s e q u e n t l y , t h i s m o d e lb a s ed o e sn o ti m p l e m e n t t r u l y i n t e l l i g e n t i z a f i o m ( 3 ) i f u s e r 8h a v en o tt r a n s c e n d e n tk n o w l e d g ef o rt h ed a t at ob ed i s p o s e d ，t h e y w i l le x p e r i e n t i a l l yd e t e r m i n et h et y p eo ff u n c t i o nm o d e lw i t hs u b j e c t i v i t ya n d b l i n d n e s s ( 4 ) t h et r a d i t i o n a lm e t h o d sc a nn o ta u t o m a t i c a l l yd i s c o v e r yt h ec o m p l e x f u n o t i o n sa n dm u l t i - s e c t i o nf u n c t i o n s ( 5 ) t h et r a d i t i o n a lm o d e lb a s e sa l gw e a ki ne x p a n s i b i l i t y 、, v h e nt h em o d e l b a s en e e d st ob ee x p a n d e d t h es y s t e mm u s tb ea d d e dn e wp r o g r a mc o d e i v 、。#f t os o l v et h e s ep r o b l e m s ，t h i sd i s s e r t a t i o ns t u d i e so nt h ei n t e l l i g e n tb a s eb y u s i n gt h eg e n ee x p r e s s i o nf r o g r a m m i n g ( g e p ) t e c h n o l o g y g e n ee x p r e s s i o np r o g r a m m i n gi san e we f f i c i e n tt o o lt om i n ei n t e r e s t i n g f u n c t i o nf r o ml a r g ed a t as e li tp o s s e s s e ss t r o n ga b i l i t yo ff u n c t i o nd i s c o v e r ya n di s h i g he f f i c i e n c y ，a n dd o e sn o tn e e dp r e - k n o w l e d g ea b o u tt h et y p eo ft h ef u n c t i o n m o d e l t h u si ta v o i d sb l i n d n e s s t h e r ea r em a n yu n - r e s e a r c h e dp r o b l e m si nt h ef i e l d so fg e p s u c h 雒b a s i c t h e o r ya b o u tg e p ，t h ea t t r i b u t er e d u c t i o nf u n c t i o nm i n i n gm e t h o db a s e d o ng e p ， t h eg e pm e t h o db a s e do i lr e m n a n td i s t r i b u t i n gf i t n e s s e t c t h i sd i s s e r t a t i o n s t u d i e s0 1 1t h e s ep r o b l e m sa n di n t r o d u c et h en e wg e pt e c h n o l o g yt od s s t h ec o n t r i b u t i o n so f t h ed i s s e r t a t i o na g et h ef o l l o w i n g ( 1 ) t h i sd i s s e r t a t i o np r o p o s e sa n di m p l e m e n t st w om e t h o d sa b o u t d a t a p r e p r o e e s s i n g i e m u l t i c o l l i n e a r i t yd a t ap r e p r o c e s s i n ga l g o r i t h m ( e - m d p a ) t h e m e t h o di s a p p l i e d t o p r e p r o c e s s d a t aw h e nt h ed a t ah a v e m u l t i c o l l i n e a r i t y i i h a s hs a m p l i n gb a s e dd a t ap r e p r o c e s s i n ga l g o r i t h m ( h s d p a ) t h e m e t h o dp r o v i d e san e ws a m p l i n gt e c h n o l o g y i t c a l li n c r e a s et h e e f f i c i e n c yo ff u n c t i o nf i n d i n ga n di m p r o v et h eq u a l i t yo ft h es a m p l e w h e nt h en u m b e ro fd a t ai sh u g e n e s s ( 2 ) t h i sd i s s e r t a t i o nd e s c r i b e st h eb a s i cc o n c e p t so fg e pf o r m a l l y ，s t u d i e st h e g e n e r a lc o n v e r g e n c eo ft h ed i s c r e t eg e pb yu s i n gm a r k o v c h a i nt h e o r y , p r o v e st h e t h e o r e mo fm a r k o vc o n v e r g e n c eo fg e p , a n a i y s i z e st h ec o n v e r g e n c eo fg e n e r a l g e p ，a n dp r o v e st h et h e o r e mo fc o n v e r g e n c eo ff u n c t i o nf i n d i n gi np r o b a b i l i t y b a s e do rg e p t h ea b o v er e s u l t sg u a r a n t e et h eg e pm e t h o di sr e l i a b l ea n df e a s i b l e i nt h e o r y ( 3 ) t h i sd i s s e r t a t i o np r o p o s e st h ec o n c e p to fe x p l i c i tm o d e la n dg e p e x p l i c i t m o d e lm i n i n ga l g o r i t h m ( g e p e i m a ) t h ec o m p a r i s o ne x p e r i m e n t ss h o wt h a tt h e n e wm e t h o di sc o m p a t i b l et ot h e 自r a d i t i o n a lm e t h o d ss u c ha sl e a s t - s q u a r em e t h o d ，；k -， ，； 、 j t h o w e v e r , g e p e i m ai se a s yt os u b m i tt h en e wt y p eo ft h em o d e lw h i l et h el s m e t h o dm u s t p r o g r a m n e wc o d et os u b m i tt h en e wt y p eo ft h em o d e l ( 4 ) a c c o r d i n gt o t h et h e o r e mo fc o n v e r g e n c eo f f u n c t i o n f i n d i n g i n p r o b a b i l i t yb a s e do ng e p , t h i sd i s s e r t a t i o np r o p o s e sg e pb a s e dr e m n a n t - g u i d e d e v o l u t i o na 螂t h m ( g e p - r g e a ) b ye x t e n s i v e e x p e r i m e n t s o v e rg e n e t i c p r o g r a m m i n g ( g p ) ，g e pa n dg e p - r g e a ，i ts h o w st h a t ( a ) a l la l g o r i t h m sf i n dt h e t a r g e tf u n c t i o nf r o md a t aw i t hl o wn o i s e ；( b ) c o m p a r i n gt h ec o n v e r g e n c es p e e d s ， g e pi s2 0t i m e sf a s t e rt h a ng pa n dg e p r g e ai s6 0t i m e sf a s t e rt h a ng p ；a n d ( c ) f o rv e r yc o m p l e xd a t aw i t hu n k n o w nf u n c t i o nt y p e g e pa n dg e p r g e aa r e r e s p e c t i v e l y9 0 0a n d1 8 0 0t i m e sf a s t e rt h a ng p ( 5 ) n i i sd i s s e r t a t i o np r o p o s e st h ec o n c e p t so f m a r g i n a lg e n e ，m a r g i n a lf i t n e s s r e m n a n td i s t r i b u t i n gf i t n e s s ，a n dr e v i s e df i t n e s sa n dt h ea l g o r i t h m so fg e pb a s e d o nm a r g i n a lf i t n e s sa n dr e m n a n td i s t r i b u t i n gf i t n e s s ( g e p - m f r d f ) ，g e pb a s e d g r e e d ya t t r i b u t er e d u c t i o nf u n c t i o nm i n i n ga l g o r i t h m ( g e p - g a r f m a ) ，a n dg e p b a s e ds t e p w i s ea t t r i b u t er e d u c t i o nf u n c t i o nm i n i n ga l g o r i t h m ( g e p s a r f m ) t h ec o m p a r i s o ne x p e r i m e n t ss h o w t h a t ( a ) b o t hg e p - g a r f m aa n dg e p - s a r f m a c a l le f f e c t i v e l yr e d u c et h ec o n d i t i o n a la t t r i b u t e st of i n dt h eb e s tf u n c t i o ne x p r e s s i o n ( b ) t h ep r e c i s i o no ff u n c t i o ne x p r e s s i o nb yu s i n gg e p s a r f m ai sa p p r o x i m a t e w i t hu s i n gg e p g 川r i ：m aa l g o r i t h m ( c ) g e p sr f m am e t h o di s3 0 0t i m e sf a s t e r t h a ng e p g a r f m ai nt h ec a s eo f2 0i n d e p e n d e n tv a r i a b l e s ( d ) 仉f i t n e s sv a l u eo f t h ef u n c t i o ne x p r e s s i o ng o tb yu s i n gg e p - g a r f m am o d e li s2 4 6 g r e a t e rt h a nt h e t r a d i t i o n a lm e t h o d ( 6 ) t h i sd i s s e r t a t i o np r o p o s e sa n di m # e m e n mg e pb a s e di n t e l l i g e n tm o d e l b a s es y s t e m ( g e p n m s ) 。a n ds t u d i e st h ei n t e r f a c eb e t w e e nt h eg e p e m b sa n d g i s d s s r n l cs y s t e mi sat r u ei n t e l l i g e n tm o d e lb a s ec o n s t r u c t i n gs y s t e m b a s eo n w t i i c kb o t ht h et y p e sa n dp a r a m e t e r so fm o d e la r ed e t e r m i n e da u t o m a t i c a l l y b yt h e s y s t e mi t s e l f m l cc o m p a r i s o ne x p e r i m e n t ss h o wt h a tt h ep r e c i s i o no ft h ef u n c t i o n m o d e lf o u n db yt h eg e p i m b si s i m p r o v e d1 4 9 c o m p a f j e dw i t ht r a d i t i o n a l m e t h o d s v i 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 ；i n t e l l i g e n tm o d e lb a s e ；d e c i s i o n s u p p o r ts y s t e m s ；f u n c d o nf i n d i n g ；g e n e t i ca l g o r i t h m ；c o n v e r g e n c e ； a t t r i b u t er e d u c t i o n ；d a t am i m n g i h ， l 前言 1 前言 1 1 智能模型库技术的研究现状及研究意义 2 0 世纪7 0 年代诞生的决策支持系统( d e c i s i o ns u p p o r ts y s t e m s ，d s s ) 发 展至今已3 0 多年，计算机技术广泛而深入的应用对决策支持提出了更高的要 求。上世纪8 0 年代，决策支持系统吸收了人工智能技术，形成了智能决策支 持系统( i n t e l l i g e n td e c i s i o ns u p p o r ts y s t e m s ，i d s s ) 。它将许多智能技术和 思想引入到决策支持系统之中，以信息技术为手段，应用计算机科学、管理科 学、数理统计、数据挖掘等相关理论和方法，针对结构化、半结构化和非结构 化的问题，为管理人员做出正确决策提供智能人机交互信息系统。实践表明， d s s 的学习能力越强，为人们提供的决策支持就越有效【1 d ”。 与管理信息系统( m i s ) 相比，决策支持系统的特色表现在模型库和模型 库管理系统，它把众多的模型有效地组织和存储起来，通过人机交互功能，实 现模型库和数据库的有机结合。d s s 是以组合模型的形式辅助决策的。 r h s p r a g u e 于1 9 8 0 年提出d s s 系统的体系结构时，就确定了模型库的 地位，d s s 是基于两库( 数据库和模型库) 的。在后来的研究中，学者们又 提出了基于x 库的体系结构【1 7 1 ，模型库在其中具有重要的地位。 模型库子系统是决策支持系统的核心。因为数据表示的是过去已经发生了 的事实，它只是面向过去的，只有利用模型才能把面向过去的数据转变成现在 或将来的可用于决策分析的信息。因此模型库是d s s 中最重要的，也是较难 实现的部分。 模型库及其建立方法的研究，最初集中在研究如何编制模型程序，建立模 型程序包，采用类似数据管理的办法管理模型。模型程序包中各模型程序相对 独立，关系比较松散，不适合于多模型的组合。 2 0 世纪8 0 年代后期到9 0 年代中期，模型的研究重点放在模型的知识表 示和模型的操纵方法两方面，许多学者对面向对象方法的模型管理进行了研 究，该方法能够有效地对模型进行表示和操鲥1 8 - 2 2 1 。 四大学博七学位论文 随着人工智能引入d s s 和对i d s s 研究的深入，学者们对模型的研究注意 力转向智能模型库系统。刘冬云等提出了一个基于f o x p r 0 2 5f o rw i n d o w s 并 且集成了c l i p s 专家系统的功能而开发的智能模型库l 。该智能模型库扩充了 关系数据库系统模型计算和知识推理的功能，可以更好地支持决策。戚百丽等 研究的实用性智能决策支持系统中，设计了以d s s 为主体的i d s s 结构，确立 了知识产生式规则表示形式及相应的推理机制，建造了基于规则的e s 工具， 并把它作为一类智能模型集成于d s s 开发工具之中；同时进行了人工神经网 络模型的研究，设计了以卫勤保障为学习样板的b p 模型，给出了基于规则智 能模型和基于神经网络智能模型的运行实例 2 4 1 ，b i e l ，l a n d 等利用生物学上感 知原理，将智能模型的方法用于多传感器信息的融合上1 2 5 1 。n u t ed o n a l d 等在 建立森林生态决策支持系统的研究中，使用板块结构技术，将多种模型进行融 合，从而实现了在d s s 中嵌入智能模型库技术瞄l 。 以上研究为d s s 和i d s s 的发展作出了一定的贡献。但以上模型库的建立 方法存在以下缺点； ( 1 ) 需预先知道模型库中模型的类型，d s s 只能根据样本数据对现有的模 型进行有关参数计算，进而让决策者根据结果来进行预测。这种模型 库缺少了真正意义上的智能寻找模型类型的功能。 ( 2 ) 依赖领域的专家经验。如专家系统需要一个内容丰富而全面的知识库 支撑，依靠的是某领域的专家经验，因此，该智能模型库对先验知识 依赖性很强，难以实现真正意义上的智能化。 ( 3 ) 预先不知模型类型时，需凭经验确定模型类型，含有主观和盲目因 素。 ( 4 ) 目前不能支持复杂函数关系式和多分段函数关系式等模型的建立。 ( 5 ) 扩展性差。针对不同的函数模型类型，在程序实现时就必须有一个新 的程序模块。当模型库需要扩充，系统就要为该模型增加新的代码。 为了解决以上问题，本文将基因表达式编程技术引入智能模型库的研究 中。 2 ， - 、 1 前言 1 2 基因表达式编程技术的研究现状及研究意义 基因表达式编程( 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 ) 是c a n d i d a f e r r e i r a 于2 0 0 1 提出的 2 0 ，是遗传算法家族的新成员，具有极强的函数发现能 力和很高的效率，并且在函数发现时不需要任何先验知识，无需预存函数模型 的类型，避免了传统算法建模时事先选定函数类型的盲目性。c a n d i d af e r r e i r a 提出g e p 算法后，引起了国内外很多学者的研究兴趣。 g e p 的原创者c a n d i d af e r r e i r a 近几年对g e p 又进行了深入细致的研究， 使用了大量的实验从不同的角度探讨了g e p 各个遗传操作的效率，同时也研 究了g e p 在有关领域的应用，包括分类、神经网络等方面 2 8 - 3 1 1 。 z h o uc h i 等利用g e p 算法对分类规则进行了研究，于2 0 0 3 年在i e e e t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ，v 7 ，n 6 发表了论文“e v o l v i n ga e c t t r a t e a n dc o r n _ p a c tc l a s s i f i c a t i o nr u l e sw i t hg e n ee x p r e s s i o np r o g r a m m i n g ” 3 2 1 其研究 结果表明g e p 算法应用于分类的有效性。 y o r i c kh a r d y 等在国际杂志现代物理学上发表论文“g e n ee x p r e s s i o n p r o g r 删n ga n do n e - d i m e n s i o n a lc h a o t i cm a p s ”，将g e p 应用于一维混沌映 射3 3 1 。 国内的许多学者在g e p 算法的基础上，针对不同应用提出了效率更高和 适应性更强的算法。 z u oj i e 等，利用g e p 技术对关联规则进行了研究，于2 0 0 2 年，在国际会 议w a i m 0 2 上发表了论文m i n i n gp r e d i c a t ea s s o c i a t i o nr u l eb yg e n e e x p r e s s i o np r o g r a m m i n g 剐。 文献 3 5 1 讨论了两种新的基于g e p 的时间序列模型构造方法。一种是传统 的滑动窗口预测法( g e p s w p m ) ，即找到在一个窗口大小内的前后数据之间的 函数关系，然后使用该关系来进行预测。另外一种则是通过分析整个测试数 据，建立关于时间序列的微分方程，然后通过该微分方程进行预测( g e p d e p m ) 。 文献 3 6 1 提出了残差制导进化算法( r g e a ) ，算法的主要思想是对g e p 的 遗传操作进行改进，以使下一代群体中残差平方和小于上一代最小残差平方的 染色体个数尽可能多。算法对几种有可能产生比当前最佳染色体更好的个体的 遗传操作，分配指标任务，即要求该遗传操作在每一代操作中生成的残差平方 四川大学博士学位论文 和小于上一代最小残差平方的染色体个数至少要达到规定的闽值，若没有完 成，则在本代遗传操作中调整其遗传率，重新进行遗传操作。 文献【3 7 1 借鉴生物具有的趋利避害( s e e ka d v a n t a g e ，a v o i dd i s a d v a n t a g e ) 天 性，提出了“弱适应模型”( w e a k - a d a p t i v em o d e o ，设计了在弱适应模型下基 于相对误差计算适应度的算法( r 既认) 。 文献 3 8 1 提出并实现了任意维定义域上的一致表达式和分域表达式的挖掘 方法，提出了g e p u e m ( 一致函数表达式的挖掘) 算法和g e p m e m ( 分域函 数表达式挖掘) 算法以及g e p b d m ( 二域式挖掘) 算法。从而实现了分段函数的 挖掘。 文献 3 9 1 提出了基于转基因技术的基因表达式编程方法，通过注入转基 因，引导进化方向，控制知识发现过程。 文献 4 0 l 对基于重叠表达的多基因进化算法进行了研究，借鉴生物基因片 段重叠表达，引入重叠基因概念，节约了表达空间。 文献 4 1 1 通过回溯策略，对提高基因表达式编程发现知识效率进行了研 究，借鉴生物“返祖现象”，引入回溯检奁点概念和可回溯g e p 算法、设计 了等比递增检查点序列和加速递增检查点序列，约束回溯过程。 以上关于基因表达式编程的国内外研究现状，主要焦点集中在对g e p 算 法的改进上，对g e p 的理论分析基本上是空白，对将g e p 这种新的智能技术 引入到d s s 中也很少涉及。而本文的工作正是基于这两个方面的空白展开 的。 1 3 本文组织 本文在以上研究的基础上，着重对基于基因表达式编程的智能模型库技术 从理论和实践上进行系统的研究。 本文的研究主要集中在数据挖掘的一个分支一预测技术。 分类和预测是数据挖掘的重要分支。在预测一个连续值时，传统方法使用 某种统计建模，发现一个函数表达式模型。传统的统计建模方法，往往被根据 不同的类型进行编码，形成一个模型库进行管理，然后嵌入到决策支持系统 4 ， 最 l 前言 中。本文研究焦点将集中在针对连续值的预测，旨在使用新的g e p 计算技 术，实现真正意义上的智能模型库。 全文其余部分组织如下。 第2 章简介基因表达式编程的基本算法，包括g e p 的染色体结构，适 应度函数( f i t n e s s ) ，g e p 的遗传操作，g e p 基本算法。 第3 章讨论函数发现技术中两种数据预处理技术，包括复共线性数据的 预处理和基于h a s h 函数抽样技术的数据预处理。 第4 章研究基因表达式编程收敛性，包括g e p 的马尔可夫收敛性分析 和g e p 的依概率收敛分析。 第5 章讨论基于基因表达式编程的智能模型库技术框架，包括基于g e p 的智能模型库技术框架、基于g e p 的智能模型库系统的功能和智能模型库 系统与决策支持系统的接口技术。 第6 章研究基于基因表达式编程的智能模型库技术的算法，包括基于 g e p 的显式智能模型的挖掘算法，残差制导进化算法，基于基因表达式编程 的属性约简函数发现算法，并对g e p d e p m 、g e p r e f a 、g e p m e m 算法 进行简介。 文章最后进行总结，并对未来工作进行展望。 5 四川大学博士学位论文 2 基因表达式编程基本概念和术语 基因表达式编程( 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 ) 是c a n d i d a p e r r e i r a 在遗传算法( g e n e t i ca l g o r i t h m ，g a ) 和遗传编程( g e n e t i c p r o g r a w a n i n g ，g p ) 的基础上发展的新概念，首批研究成果于2 0 0 0 年1 2 月在 网上发表，在2 0 0 1 年1 2 月正式发表啪。本章的内容主要来自于文献 2 7 ，4 2 - 4 4 h o l l a n d 及其学生f f ( b a g l e y 等) 于1 9 7 5 年提出了遗传算法后，经过3 0 多 年的发展，遗传算法已经被应用于工农业生产和科学研究的各个领域，演化成 了一个比较成熟的智能计算的一个分支“”1 。 文献 4 3 】的作者用“沃土老树开新花”来描述g e p ，即在“知识发现”这 块沃土里，“遗传计算家族”这棵老树上开出了“基因表达式编程”这朵新 花。 虽然g e p 与g a 和g p 相比在主要步骤上都极为相似，但g e p 克服了g a 与 g p 的不足，更适合于函数关系的挖掘。 文献 4 3 中，作者描述了g e p 、g a 和g p 之间的关系及差异。g a 是线性 b i t 串，定长的，是简单编码解决简单问题；g p 是非线性，树结构，不定长 的，是复杂编码解决复杂问题：g e p 是线性b i t 串，定长的，但表达的是非线 性，树结构，是简单编码解决复杂问题。g e p 继承了g a 的刚性，规矩，快 速，易用和g p 的柔性，易变，多能，比g a ，g p 的效率大大提高。 本章将对g e p 的基本概念、g e p 的染色体结构、g e p 的适应度函数、g e p 的遗传操作以及g e p 的基本算法等进行简要介绍。 2 1 g e p 的染色体结构 g e p 处理的对象可以是单基因或多基因组成的染色体( 基因组) 。基因是 由线性的、固定长度的符号串组成的。尽管染色体是固定长度的，但却能表达 出不同大小和形状的表达树( e x p r e s s i o nt r e e s ，e t s ) 。 6 2 基因表达式编程基本概念和术语 2 1 10 r f 和基因 g e p 中借鉴了生物学的o r f ( o