搜索
基于转基因技术的基因表达式编程1GeneExpressionProgrammingBasedonTransgenesisTechnology张欢唐常杰余弦乔少杰汪锐左劼(四川大学计算机学院成都610065)AbstractTheknowledgeminingbythecurrentGeneExpressionProgramming(GEP)isapassiveprocedure.Peopleonlycanaccepttheresultafterseveralgenerationsofevolution.Thustheevolutionprocesswouldbeoutofcontrol,andthequalityandspeedoftheevolutioncanhardlybeforeseened.EnlightenedbytheconceptofTransgeneofthemodernbiology,thispaperproposestheGeneInjectiontechnologyandthenewideaonTransgenicTechnology,whichguildstheevolutiontrendofeverygenerationtosomeextentbyworkingontheevolutionprocesshenceimprovesresultsqualityandspeedthroughtheeffectofbothnaturalselectandmanualselectduringevolutionprocess.Themaincontributionincludes:(1)Proposestheconceptionsandalgorithmsofgene-divide(M_divide_gene)andgene-dismember(M_dismember_gene);(2)Introducestheconceptionsandalgorithmscalledsingle-gene-evolution(SGE)andgene-segment-evolution(GSE);(3)ProposesandimplementsanapproachcalledTrans-GeneExpressionProgramming(TGEP);(4)ConductsextensiveexperimentstoprovetheeffectivenessofthisapproachandfindstheefficiencyhasbeengreatlyimprovedbyTGEPthanGEPinminingcomplexfunctions.KeywordsGEP,Transgene,gene-divide,gene-dismember,genesegment1基金项目：国家自然科学基金(60473071)，高等学校博士学科点专项科研基金SRFDP(20020610007号)，四川省青年软件创新工程(2004AA0350号)作者简介：张欢(1977－)，男，硕士研究生，研究方向：数据库与知识工程；唐常杰，博士生导师，教授，研究方向：数据库与知识工程，数据挖掘，本文联系作者：唐常杰；余弦,乔少杰,汪锐：硕士研究生；左劼：博士1.引言目前GEP的进化完全依赖其自身能力，人们只能被动接受完全的自然选择的结果。本文提出将转基因的思想引入GEP中，希望能够借此对进化过程助一臂之力。2.相关工作2001年12月，CandidaFerreira在结合了GA和GP思想的基础上正式提出了基因表达式编程(GeneExpressionProgramming,GEP)[4]。所以说GEP是GA和GP的继承和发展。图1[5]形象地表现出了GA,GP和GEP的关系：3背景知识3.1GEP编码规则GEP中的个体称为染色体（Chromosome）[4]，染色体由若干个基因（Gene）通过连接运算符（LinkOperator）连接组成。Gene由头部（hail）和尾部（tail）组成，head包含了函数（Functions）和终结符（Terminals），tail只含有Terminals。设头部长度为h，尾部长度为t，函数中的最大目数为n，则几者之间有关系：t=h(n-1)+1。例1：考虑表达式（（a－b）*（c＋d））1/2。函数集FunctionSet=｛Q，*，－，＋｝，终结符集TerminalSet＝{a，b，c，d}，图2为对应的ET。对该ET进行层次遍历可以得到序列：“Q×－＋abcd”，这个式子又称为K-表达式(K-expression)[4]。若令Gene的|head|=5，n=2，则|tail|=6。由于这里的表达式只有八位，则尾部剩余部分由终结符中的元素任意填充。则Gene的编码可以为“Q*－＋abcdaabc”。3.2GEP中转基因技术的基本思想1.目前GEP的最小遗传单元和变异单元比较小，这样在很多次进化后才得到的优良结果有可能在一次不良变异中毁于一旦，如果能够将这种优秀的基因保存下来，在以后的进化中充分利用前面的结果，则有希望加快收敛速度。2.若目标函数中有比较复杂的因式，当保留了前面的优秀基因后可以有效地化简函数式，从而可以节省挖掘的时间，也有希望发现更加精确的表达式。3.如果能够结合特定问题，在启发性知识引导下向规则强制注入基因组成新规则或公式，具体方法可表现为事先人为对函数表达式的部分内容进行估计，可能会取到意想不到的效果。4.GEP的转基因进化方法4.1转基因进化的基本方法作者在实践中发现，，当进化了一定的时间后，优秀个体中某些基因中极有可能已经进化出了比较好的结构，于是这些基因可以暂时保留下来进行培养。本文提出基因分离和基因肢解的方法来保留这种“优秀”结构。定义1（基因分离M_divide_gene）：将一条染色体中的各个单一基因（G_single）分离出来的操作称为基因分离，相应算法记为M_divide_gene。定义2（基因肢解M_dismember_gene）：将一个G_single在抛弃部分函数和终结符后肢解为若干G_sengment的操作称为基因肢解，相应算法记为M_dismember_gene。这两个基本方法是为将来的转基因进化准备基因组文库（GenomicLibrary）的基础。转基因进化的两个核心算法是下面将介绍的单一基因进化算法（SGE）和基因片段进化算法（GSE）。4.2单一基因进化（SGE）算法SGE（SingleGeneEvolution）的主要思想是从染色体中分离出单一基因，以单一基因为单位分别进化。算法单一基因进化（SGE：SingleGeneEvolution）：输入：染色体集合S_chrom输出：进化后筛选出的基因集合S_gene步骤：1.S_pop_0=PPSGE(S_chrom)；//准备第0代种群集合2.GEP_Evolution(S_pop_0)；//以GEP的方式自由进化3.S_gene=FGSGE(S_pop_0)；//筛选基因4.returnS_gene；算法首先根据前面的进化结果生成新的培养种群集合，各个种群分别进化，然后从结果中再筛选出有价值的基因留待以后的进化使用。4.3基因片段进化（GSE）算法GSE（GeneSegmentEvolution）的主要思想是从基因中分离出基因片段，以基因片段为单位分别进化。算法基因片段进化（GSE：GeneSegmentEvolution）：输入：基因集合S_gene_in输出：进化后筛选出的染色体集合S_chrom步骤：1.S_pop_0=PPGSE(S_gene_in)；//准备第0代种群集合2.GEP_Evolution(S_pop_0)；//以GEP的方式自由进化3.S_chrom=FGGSE(S_pop_0)；//筛选基因4.returnS_chrom；与SGE的不同之处在于，我们认为在一段优良基因中仍然有可能存在“垃圾”，于是希望在更细微的层面（一个基因中的某一段）上寻找其中的“优秀成分”。4.4GEP的转基因进化（TGEP）算法TGEP（Trans-GeneExpressionProgramming）的主要思想是：（1）进化之前先对目标表达式的部分内容进行估计；（2）对进化过程中出现的基因或基因片段进行筛选，将筛选出的部分分别进化。算法GEP的转基因进化（TGEP）输入：训练数据集S_para_org输出：挖掘出的表达式E步骤：1.S_func_candi=InitCandiFuncS()；//估计F在S_func_org之外可能含有的函数2.S_func_candi=S_func_org∪S_func_candi；3.S_para_candi=InitCandiParaS()；//估计F中可能含有的参数形式4.S_para_candi=S_para_org∪S_para_candi；5.pop_org=GenerateOrgPop(S_func_candi,S_para_candi)；/*生成原始种群pop_org：以S_func_candi作为函数集，以S_para_candi作为参数集*/6.pop_0=GEP_Evolution(S_pop_org,K);//以GEP的方式自由进化K代得到新的种群7.E=BestExpress();8.S_chrom_0=TopN(pop_0)；//pop_0中最优的N条染色体9.while（NeedTransgenicEvolution()）{//评价结果：需转基因进化10.S_gene_candi=SGE（S_chrom_0）；11.E=KeepBest()；//保留最优个体并记录最优表达式12.if（!NeedTransgenicEvolution()）break；//评价结果：不需要进一步转基因进化13.S_chrom_0=GSE（S_gene_candi）；14.E=KeepBest()；}15.while（!Terminate()）GEP_Evolution()；//不满足终止条件则普通进化16.E=BestExpress();17.returnE;TGEP的核心思想是通过种群规模在一定程度上的提高以换取时间上的巨大节省。于是我们得出使用TGEP可以取得比较好的效果的结论，其优势远大于劣势。5.实验本文选择Schaffer函数F6[9]作为实验对象：()[]2222122212216001.00.15.0sin5.0),(xxxxxxf++-++=-100≤xi≤100(i=1,2)实验中的x1，x2采用随机化方法得到，y由公式计算得到，总共生成1000组数据。实验平台为：IntelCeleronⅢ1.7G，248M内存，WindowsXPProfessional，VC++6.0。实验采用不同的参数分别对GEP和TGEP作了两组对比实验，每组实验中两种方法各自进行10次。适应度函数为：()()∑∑==-=-=-=mjjmjjjyySSTyySSESSTSSEfitness1212ˆ1，其中,yˆ为变量y关于函数g的估计值。y为变量y的平均值。称SSE为残差平方和,SST为总离差平方和。显然，－∞＜fitness≤1。实验一：对两种方法各自进行10次实验，其中GEP进化50000代，TGEP中的各个转基因培养种群均为连续3000代适应度无增加便停止进化，SGE和GSE各执行一次。TGEP使用的基因组文库为：(1)S_para_candi=S_para_org∪{x1*x1，x2*x2}；S_para_org为观测值；(2)S_func_candi=S_func_org∪｛Q（开方），S（sin），L（log10），E（exp），P（pow）｝其中L、E为有意加入的干扰项；图3GEP与TGEP对F6的进化效果比较（一）实验结果表明：虽然TGEP尚未达到非常优良的效果（当然这主要是由于为了模拟真实的数据挖掘环境，我们没有为这样一个特定的函数指定特定的参数而导致的