基于基因表达式编程的智能模型库系统的实现.pdf

第37卷 第3期四 川 大 学 学 报(工 程 科 学 版)Vol.37 No.32005年5月JOURNAL OF SICHUAN UNIVERSITY(ENGINEERINGSCIENCE EDITION)May 2005文章编号:100923087(2005)0320099206基于基因表达式编程的智能模型库系统的实现元昌安1,2,唐常杰1,温远光3,4,胡建军1,彭 京1(1.四川大学 计算机学院,四川 成都610064;2.广西师范学院 信息技术系,广西 南宁530001;3.四川大学 生命科学学院,四川 成都610064;4.广西大学 林学院,广西 南宁530005)摘 要:模型库是决策支持系统(DSS)的重要组成部分。传统的智能模型库系统对先验知识依赖性很强,难以实现真正意义上的智能化。针对这一弱点,提出了显式智能模型,隐式智能模型,显式模型基因的概念,给出了基于GEP的隐式智能模型(Implicit Intelligent Model,IIM)的挖掘算法(GEP-IIMA),在此基础上实现智能模型库系统;研究了隐式智能模型库(IIMB)系统与GIS的接口技术。IIMB是真正意义的无先验知识的智能模型库,其模型的类型和参数的求解均由程序自己来实现。通过比较实验,系统所挖掘的函数模型比传统方法所得模型的精度提高了14.9%。关键词:基因表达式编程;智能模型;隐式;显式;函数挖掘中图分类号:TP311.13文献标识码:AImplementation of Intelligent Model Base System Based onGenetic Expression ProgrammingYUAN Chang2an1,2,TANG Chang2jie1,WEN Yuan2guang3,4,HU Jian2jun1,PENG Jing1(1.School of Computer,Sichuan Univ.,Chengdu 610064,China;2.Dept.of Info.and Tech.,Guangxi Teachers Education Univ.,Nanning 530001,China;3.School of Life Sci.,Sichuan Univ.,Chengdu 610064,China;4.School of Forestry,Guangxi Univ.,Nanning 530001,China)Abstract:Model Base is important to Design Support System.T raditional intelligent model base system dependson transcen2dental knowledge,and it is difficult to authentically implement intelligentization.T o solve the problem,this paper makesfol2lowing contributions:1)Proposes the concepts of Explicit Intelligent Model,Implicit Intelligent Model,and Explicit G ene;2)Proposes Mining Implicit Intelligent Model AlgorithmBased on G ene Expression Programming(GEP2IIMA)and implementsthe intelligent model base system based on GEP2IIMA;3)Studies the interface between the Implicit Intelligent Model Base(IIMB)system and GIS;4)G ives compared experiments.IIMB is indeed an intelligent model base on it both the types andparameters of model are determined automatically by the GEP2IIMA.The comparison experiments show that the precision ofthe function model found by the GEP2IIMA is improved 14.9%than traditional method.Key words:gene expression programming;intelligent model;implicit;explicit;function mining 从大量看似无规则的数据中挖掘出函数关系并收稿日期:2004-12-29基金 项 目:国 家 自 然 科 学 基 金(60473071),973计 划 项 目(2002CB111504),博士点基金(20020610007)及广西自然科学基金(0339039)资助项目作者简介:元昌安(1964-),男,副教授,博士生.研究方向:数据库与知识工程.用于预测是知识发现的一个重要研究方向。模型库是决策支持系统(DSS)的重要组成部分。依靠模型库,决策者使用库中模型做出多种可选决策。传统模型库的建立方法14有下列缺点:1)需预先知道模型库中模型的类型,DSS只能根据样本数据对现有的模型进行有关参数计算,进而让决策者根据结果来进行预测。这种模型库缺少 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.了真正意义上的智能寻找模型类型的功能;2)可能依赖领域的专家经验。文献5中,刘冬云等提出了一个基于FoxPro2.5 for Windows、并且集成了Clips专家系统的功能而开发的智能模型库。该模型库扩充了关系数据库系统模型计算和知识推理的功能,可以更好地支持决策。但众所周之,专家系统需要一个内容丰富而全面的知识库支撑,依靠的是某领域的专家经验,因此,该智能模型库对先验知识依赖性很强,难以实现真正意义上的智能化;3)含有主观和盲目因素,目前不能支持复杂函数关系式和多分段函数关系式等模型的建立;4)扩展性差。针对不同的函数模型类型,在程序实现时就必须有一个新的程序模块。当模型库要进行扩充,系统就要为该模型增加新的代码。Candida Ferreira提出的基因表达式编程(GeneExpression Programming6,简称GEP)是遗传算法家族的新成员,具有极强的函数发现能力和很高的效率,并且在函数发现时不需要任何先验知识,无需预存函数模型的类型,避免了传统算法建模时事先选定函数类型的盲目性。文献79 中,作者们对GEP的基本算法进行改进,分别提出了GEP2SWPM(GEP2Sliding Window Prediction Method)、GEP2DEPM(GEP2Differential Equation Prediction Method)、RGEA(Remnant2Guided Evolution Algorithm)、REFA(RelativeError fitness Algorithm)、GEPUEM(一致函数表达式的挖掘)、GEP2MEM(分域函数表达式挖掘)以及GEP2BDM(二域式挖掘等算法,使GEP算法在处理复杂的数据时,如噪声数据,太阳黑子数据等,更加有效和精确。作者提出基于GEP及其改进算法的隐式智能模型(Implicit Intelligent Model,IIM)建立的算法,并在此基础上实现智能模型库系统。该系统是真正意义的无先验知识的智能模型库,模型的类型和参数的求解均由程序自己来实现。主要贡献如下:1)提出显式智能模型,隐式智能模型,显式模型基因的概念;2)给出基于GEP的显式智能模型和隐式智能模型的挖掘算法;3)提出隐式智能模型库系统的框架;4)研究了隐式智能模型库系统与GIS、DSS等接口技术。1 相关工作GEP的概念及其算法参考文献610。Candida Ferreira提出GEP算法后,很多学者在此基础上,针对不同应用提出了效率更高和适应性更强的算法。文献7讨论了两种新的基于GEP的时间序列模型构造方法。一种是传统的滑动窗口预测法(GEP2SWPM)。另外一种是建立关于时间序列的微分方程,然后通过该微分方程进行预测(GEP2DEPM)。文献8提出了残差制导进化算法(RGEA),其主要思想是对GEP的遗传操作进行改进,以使下一代群体中残差平方和小于上一代最小残差平方的染色体个数尽可能多,从而提高算法进化的效率。文献9借鉴生物具有的趋利避害(seek advan2tage,avoid disadvantage)天性,提出了“弱适应模型”(Weak2Adaptive Model),设计了在弱适应模型下基于相对误差计算适应度的算法(REFA)。从而实现抗噪声的函数挖掘方法。文献10提出并实现了任意维定义域上的分域表达式的挖掘方法,提出了GEP2MEM(分域函数表达式挖掘)算法以及GEP2BDM(二域式挖掘)算法。从而实现了分段函数的挖掘。2 隐式智能模型的挖掘算法本节给出隐式模型的定义并提出隐式智能模型的挖掘算法。2.1 定 义设x为m维变量,y为一维变量,A=(X,Y)(m+1)n为关于变量x,y的一组观测数据,其观测样本数为n。其中,X=(xij)mn,Y=(yj)1n,i=1,2,m;j=1,2,n。定义1(显式模型)设f(b,x)为给定的关于b,x的函数表达式,b=(bi)k1(i=1,2,k)为待定常数。根据样本数据A,按照某种规则确定b,使得y=f(b,x)+,且达到最小,则称f(b,x)为要发现的显式模型(Explicit Model,简称EM)。由EM组成的库称为显式模型库(Explicit Model Base,简称EMB)。显然,显式模型的模型类型是确定的,要求的是模型中所包含的待定常数。定义2(隐式模型)设g(x)是关于x的任意一个函数表达式,根据样本数据A,按照某种规则确定g(x),使得y=g(x)+,且达到最小,则称g(x)为要发现的隐式模型(Implicit Model,简称IM)。由IM组成的库称为隐式模型库(Implicit Mod2el Base,简称IMB)。隐式模型预先不知道模型类型。001四川大学学报(工程科学版)第37卷 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.例1在探讨杉木林的生产力(NPP)与气温(t)的相关模型时,先假定模型类型为:NPP=f(a0,a1,a2,a3,t)+=a0+a1t+a2t2+a3t3+(1)a0,a1,a2,a3为要根据样本数据估计的待定参数。称(1)式为显式模型。例2给定杉木林生产力(NPP)与气温(t)的一组样本数据,根据这组数据发现模型:NPP=g(x)+(2)使尽可能小。称(2)式为隐式模型。命题1IMB=EMB证明:由定义1和定义2知,显式模型只是隐式模型的特例,因而命题成立(例1,例2给出了直观的解释)。使用GEP发现隐式模型,其基因结构参见文献6。下面给出使用GEP发现显式模型时的基因结构。定义3(显式模型基因(EM2Gene)结构)设f(b,x)为待定的显式模型,函数符号集F由f中的所有运算符及初等函数组成,终端符号集T=b1,b2,bk,x1,x2,xm。用3元组表达EM2Gene结构。即:EM2Gene结构=(G,I,R n)。其中,G由F和T中元素组成,I由k个随机整数rnd i(i=0,1,k)组成,且0rnd i n(i=0,1,k)。R n为一随机数组,其元素为n个随机数。rnd i 对应着R n的一个下标。例3例1中f(a0,a1,a2,a3,t)的EM2Gene,其函数符号集F=+,3,终端符号集T=a0,a1,a2,a3,t,t2,t3,与该模型对应的EM2Gene为:+3 3 3a0a1ta2x2a3x33782。设随机数组C=-23.15,30.14,-18.12,22.57,7.31,20.14,-31.12,-1.87,21.10,7.25,该EM2Gene所对应的函数表达式为:22.57-1.87t+21.10t2-18.12t3。2.2 基于GEP的隐式智能模型的挖掘算法(GEP2IIMA)本小节要讨论如何运用GEP基本算法及其改进算法实现IIM的挖掘。算法1 基于GEP的隐式智能模型的挖掘算法(GEP2IIMA)输入:样本数据A输出:函数模型表达式g(x)Begin 确定GEP进化过程的基本参数:训练样本数、测试样本数、函数集、群体数、基因头长度、每个染色体的基因数、连接基因的操作符、适应度函数类型(含自定义类型)、变异率、交叉率、IS移位率、RIS移位率;if(挖掘显式模型)GEP2EIMA();/调用GEP2EIMA算法else if(剔除噪声数据的函数模型挖掘)REFA();/调用REFA算法Else if(分域表达式的函数模型挖掘)GEP2MEM();/调用GEP2MEM算法Else if(复杂数据的函数模型挖掘)RGEA()/MC2GEP();/调用RGEA算法或多群体GEP算法(MC2GEP)ELSEGEP2DEPM()/TG2GEP();/调用GEP2EIMA算法或转基因GEP算法(TG2GEP);返回所挖掘出的最佳函数模型表达式g(x)及其复相关系数R;End.说明:算法1针对用户不同的要求及其数据的特点,调用了相应的基于GEP的改进算法。算法GEP2EIMA用于显式模型的挖掘,目的是实现显式模型挖掘的可扩展性,并兼容了传统的显式模型的挖掘算法。REFA主要用于需要剔除噪声数据的函数挖掘;GEP2MEM用于样本数据在不同域呈现不同规律情况,实现分段函数的挖掘;RGEA和MC2GEP算法的主要优点是效率高;而GEP2DEPM和TG2GEP算法的主要优点是精度高。算法2基于GEP的显式智能模型的挖掘(GEP2EIMA)输入:显式模型f(b,x),随机数组下标个数,随机数组取值范围输出:显式模型的待定常数b的值及f(b,x)对应的复相关系数RBegin 根据f(b,x),确定EM2Gene结构,包括函数符号集,终端符号集等;创建基于EM2Gene结构的初始化群体;计算每个个体的适应度函数;while(最大适应度没有达到要求或迭代次数(即进化的代数)没有达到预定值)遗传操作产生下一代:()保留最好个体;()选择操作(Select);()复制(Replication);101第3期元昌安,等:基于基因表达式编程的智能模型库系统的实现 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.()变异(Mulation);()1-点重组(One2Point Re2combination)、2-点重组(Two2Point Recombination)、基因重组(Gene Recombination);说明:算法2因为要保持EM2Gene的结构,所以遗传操作没有移位(Transposition)操作。另外,变异操作也只针对EM2Gene的常量位置和随机整数位置进行。算法REFA、RGEA、GEP2DEPM、GEP2MEM细节参见文献710。多群体GEP算法(MC2GEP)和转基因GEP算法(TGGEP)作者另文介绍其技术细节,本文只简要介绍它们的基本思想。TG2GEP:把生物工程中转基因思想引入基于GEP的知识发现系统,提取基因,封装,分类和定位,建立可转移知识基因库。(a)对基因分类,如(1-x+x2/2-x3/6)作为衰减基因(模拟e-x),(1+x+x2/2+x3/6)作为周期性基因(模拟sin(x),1-(1-x+x2/2-x3/6)可作为渐进基因,等等;(b)对潜藏在训练数据的基因,用传统数据挖掘的聚类和特征提取方法提取,并标明其功能。在GEP进化中利用转移知识基因库中的基因克服早熟现象和提高所挖掘的函数模型的精度。MC2GEP:GEP的进化过程针对多群体进行,并对多群体引入并行技术和多群体之间的优良个体交叉等技术,以提高GEP的效率和克服早熟现象。该算法对解决计算量非常大的,如分布式水文生态模型,一类问题具有重要意义。算法提供选择的适应度函数有下列5种:1)RESR(Relative Error with Selection Range);2)AESR(Absolute Error with Selection Range);3)R2square;4)MSE(mean squared error);5)自定义(Custom FitnessFunction)。以上适应度函数类型用户可根据实际情况选用,在对样本数据缺少先验知识的情况下,一般选用R-square;RESR和AESR是在需要限定样本数据的理论值与目标值之间的误差时才使用。MSE直观地反应了理论值与目标值之间的差异,常被用来和其它适应度函数配合使用。在系统中,无论用户选用哪一种适应度函数,系统都将给出所得函数模型的复相关系数,便于用户直观分析函数模型的精度,以及与传统方法所求出的显式模型进行精度上的比较。2.3 隐式智能模型库系统的框架IIMB管理系统实现框架参见图1。图1IIMB管理系统实现框架图Fig.1Framework of the IIMB Management System3 隐式智能模型库系统与DSS的接口技术在进行973计划子课题“植被与水文耦合变化对全球变化的响应及其预测”的研究时,作者开发了一个基于GIS平台Mapinfo专业版的“目标流域植被与水文地理信息决策支持系统(VHGISDSS)”,其框架见图2。在该系统中,需要嵌入智能模型库系统,针对目标流域的数据,挖掘出高精度的分布式模型,供决策者调用分析相关问题。下面介绍IIMB系统与DSS之间的接口问题。1)Matlab程序与其它开发工具的接口IIMB系统的界面是在VC环境下开发的,其算法实现是使用Matlab开发的。Matlab程序不能脱离其环境运行,可使用MathT ools公司推出的Matcom解决接口问题。201四川大学学报(工程科学版)第37卷 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.图2VHGISDSS框架图Fig.2Framework of the VHGISDSSMatcom是一个从Matlab到C+的编译器,它可以节省用户的运算时间和内存要求。MathT ools公司利用Matcom技术编写了Mideva工具软件,它可以借用C+编译器将Matlab下的m2文件转换为可被其它开发工具调用的DLL,也可编译成独立的标准可执行文件,不需装载任何附加产品。2)IIMB系统与GIS之间的接口IIMB系统与GIS平台开发的程序之间的接口可通过两种方式实现。(a)编写出应用程序并编译为IIMB.exe,然后在Mapinfo中使用运行外部程序的方式:RUN PRO2GRAM“IIMB.EXE”(b)使用OLE或DDE的方式,使C+开发的IIMB应用程序与Mapinfo集成。4 实 验给出一个来自于真实数据的对比性实验。试验 平 台 为:CPU=PIV 1.8 G,OS=Win2dows2000,VC+。实验的数据取自文献11表1。文献11研究了杉木净初级生产力(NPP)与气候变量(t)的相关模型,该文利用最小二乘法得出二者相关函数表达式如下:NPP=-38.80+5.43310-4t+0.4806t2-1.80310-2t3(3)相关系数R=0.7062,模型精度P=66.44%。其中,模型精度按(4)式计算:P=1n6ni=1(1-|NPPi-PiNPPi|)(4)其中,NPPi表示第i个样本的生产力NPP值,pi为根据(3)式计算的预测值。针对文献11 表1的数据,GEP2IIMA求出的NPP关于t的函数关系式为:NPP=sin(2+t-sin(t)+sin(2tsin(t)-t+1)+log(2t3+t2sin(t)+1.5sin(t)/t-5sin(t)(5)相关系数R=0.9035,P=81.34%。图3为杉木生产力与年平均气温的关系图,从图中可以看出,GEP2IIMA所得模型的预测值与真实数据的吻合度明显高于文献11的模型,模型精度提高了14.9%。图3 杉木林生产力预测图Fig.3Prediction of the productivity of cunninghamialanceolata plantation 从以上实验可看出,GEP2IIMA算法针对实际的数据具有强大的函数发现能力,尤其是对这些数据没有任何先验知识的情况下,研究者由于确定模型类型的盲目性,传统方法所确定的模型精度往往较低,而GEP2IIMA算法由于其发现函数的自动化程度高,搜索空间广,可以挖掘出精度较高的函数模型,从而可以使一些研究领域的研究深度加深、解决复杂问题的能力和智能化程度大大提高,如植被与水301第3期元昌安,等:基于基因表达式编程的智能模型库系统的实现 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.文耦合变化对全球变化的响应及其预测、股票预测等复杂数据的模拟和预测等。5 总 结提出显式智能模型,隐式智能模型,显式模型基因的概念以及基于GEP及其改进算法的隐式智能模型(Implicit Intelligent Model,IIM)的算法,在此基础上实现智能模型库系统并研究了隐式智能模型库系统与GIS、DSS等接口技术。IIMB系统是真正意义的无先验知识的智能模型库,模型的类型和参数的求解均由程序自己来实现。通过实验,系统在函数发现中取得了良好的性能。作者还发现GEP及其改进算法,具有属性约简的函数发现功能。今后的工作中,将致力于研究基于GEP的属性约简的函数发现算法。参考文献:1Hernndez J Z,Cuena J,Serrano J M.An intelligent model forreal time private traffic management in urban networks:the flu2ids/critic approachA.11thEURO-Mini Conference on Artifi2cial Intelligence in Transportation Systems and Science,and 7thEURO WorkingGroupMeeting onTransportation.1999,Helsinki.2Nute D,Potter W D,Maier F.Intelligent model management in aforest ecosystem management decision support systemA.Inte2grated Assessment and Decision Support Proceedings of the FirstBiennial Meeting on the International Environmental Modelingand Software Society,IEMSs C.Switzerland:University ofLugano,2002,3:396401.3Ju Chunhua,Wang Guangming,Chen Xiao.The research ofmodel base systemfor DSSon commerceJ.Journal of SystemsEngineering,1997,15(3):1216.琚春华,王光明,陈晓.商业决策支持系统的模型库系统研究J.系统工程,1997,15(3):1216.4Chang Jinyi,Zhang Yuanzhi.Study of monitoring and manage2ment of fragile ecosystem decision support systemJ.RemoteSensing Technology and Application,2001,16(4):224227.常晋义,张渊智.生态环境监测与管理决策支持系统的研究J.遥感技术与应用,2001,16(4):224227.5 Liu Dongyun,Deng Tieqing.Study and design of intelligentmode base tool FoxModJ.Computer System Application,1998,(3):2325.刘冬云,邓铁清.智能模型库工具FoxMod的研究与设计J.计算机系统应用,1998,(3):2325.6Ferreira C.Gene expression programming:a new adaptive algo2rithm for solving problemsJ.Complex Systems,2001,13(2):87129.7Zuo Jie,Tang Changjie,Li Chuan,et al.Time series predictionbased on gene expression programming A.LNCS(LectureNotes In Computer science)C.WAIM04(International Con2ference for Web Information Age 2004),Springer Verlag BerlingHeidelberg,2004,3129:5564.8 Yuan Changan,Tang Changjie,Zuo Jie,et al.Function miningbased on gene expression programmingconvergency analysisand remnant2guided evolution algorithmJ.Joural of Sichuan U2niversity(Engineering Science Edition),2004,36(6):100105.元昌安,唐常杰,左 吉 力,等.基于基因表达式编程的函数挖掘-收敛性分析与残差制导进化算法J.四川大学学报(工程科学版),2004,36(6):100105.9Duan Lei,Tang ChangJie,Zuo Jie,et al.An anti2noise methodfor function mining based on GEPJ.Jornal of Computer Re2search and Development,2004,41(10):16841689.段 磊,唐常杰,左 吉 力.基于基因表达式编程的抗噪声数据的函数挖掘方法J.计算机研究与发展,2004,41(10):16841689.10Huang Xiaodong,Tang Changjie,Li Zhi,et al.Mining functionsrelationship based on gene expression programmingJ.Journalof Software,2004,15(suppl.):96105.黄晓冬,唐常杰,李 智,等.基于基因表达式编程挖掘函数关系J.软件学报,2004,15(增刊):96105.11Wen Yuanguang,Yuan Changan,Liu Shirong,et al.Distribu2tion and simulation of actual productivity of cunninghamia lance2olata plantation in ChinaJ.Guangxi Sciences,1995,2(2):5662.温远光,元昌安,刘世荣,等.中国杉木林气候生产力的分布及模拟J.广西科学,1995,2(2):5662.(编辑 杨 蓓)401四川大学学报(工程科学版)第37卷 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.