资源描述：
《提高基因表达式编程发现知识效率的回溯策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2006年4月四川大学学报(自然科学版)Apr.2006第43卷第2期JournalofSichuanUniversity(NaturalScienceEdition)Vol.43No.2文章编号:049026756(2006)0220299206提高基因表达式编程发现知识效率的回溯策略钟义啸,唐常杰,陈 宇,段 磊,魏大刚(四川大学计算机学院,成都610065)摘要:传统基因表达式编程(GEP)编码简单,适应性强,但可能陷入局部最优的“早熟”陷阱.因此,作者借鉴生物界的“返祖现象”,提出了基于回溯的基因表达式编
2、程方法.主要工作包括:(1)在传统GEP算法中引入回溯机制,提出基于回溯策略的GEP算法GEPBS(GEPwithBacktrackingStrategy);(2)提出回溯检查点概念,设计等比递增检查点序列和加速递增检查点序列,约束回溯过程;(3)扩充基于回溯的GEP算法,设计了退化因子(RF),提出了按比例回溯策略GEPPBS(GEPwithProportionalBacktrackingStrategy);(4)通过两个实验验证了新算法的有效性,在相同条件下较传统算法的适应度最大提高了49.2%,成功率最高提
3、高了4倍.关键词:回溯策略;等比递增检查点序列;加速递增检查点序列;退化因子中图法分类号:TP311.13文献标识码:A1 引言基因表达式编程作为一种通用的自适应式随机搜索算法,能够在缺乏先验知识的情况下挖掘出较为准确的公式,以较强的普适性和较高的精确度在很多应用领域取得很好的实际效果,但它具有未成熟收敛的“先天缺陷”.由于算法思想基于随机搜索,进化过程可能较早地进入一个局部最优的分支,而无法取得全局最优解,这种未成熟收敛现象会影响实验的效能,阻碍数据中的知识、规律被有效地发掘.为解决传统GEP方法容易陷入局部最
4、优解的问题,我们做了以下探索:将回溯机制引入传统GEP算法,提出基于回溯的GEP算法GEPBS,提高了知识发现效率;提出回溯检查点概念,并设计两种检查点序列,约束回溯过程;扩充基于回溯的GEP方法,提出按比例回溯策略,避免丢失有利的中间结果;通过实验验证了新算法的有效性.2 相关工作和背景知识2.1 相关工作基因表达式编程GEP(GeneExpressionProgramming)是近年来出现的新算法,结合了Darwin的适者生存理论和随机交换理论,模仿生物进化过程对问题进行优化求解.适者生存理论消除了解空间中的
5、不适[1]应因素,随机交换理论利用原有解中的知识加速对优化解的搜索过程.GEP融合了遗传算法及遗传编程的优点,通过简单紧凑的编码能解决复杂的应用问题.CandidaFerreira于2001年正式发表GEP的首[2][3,4]批研究成果后受到学术界的高度关注,一批研究成果相继问世.文[5]将GEP应用于谓词关联规则挖掘上(PAGEP),并从理论上证明了GEP中基因编码的有效性;文[6]对函数发现的特点进行分析,提出在任意维定义域上的一致表达式挖掘UEM和分域表达式挖掘MEM,并从理论上给出MEM成功率的证明;文[
6、7]把函数挖掘的目标引申到函数集上,提出描述能力更强的函数挖掘对象———频繁函数集,并提出收稿日期:2005205223基金项目:国家自然科学基金(60473071);高等学校博士学科点专项科研基金SRFDP(20020610007);四川省青年软件创新工程(2004AA0350)作者简介:钟义啸(1980-),女,2003级硕士研究生.300四川大学学报(自然科学版)第43卷更加灵活的可配置频繁函数集挖掘算法CFFSDA和用户制导的基于约束的可配置频繁函数集挖掘算法.文[8]提出GEP的弱适应模型和带内集,带外
7、集概念,设计了在弱适应模型下基于相对误差计算适应度的算法REFA.2.2GEP相关概念GEP中染色体(Chromosome)作为承载遗传信息的基因型实体,表达式树ET(ExpressionTree)作为信息的表现形式,两者可以无二义地互相转化.GEP的染色体为定长线性字符串,由一个或多个基因(Gene)组成.按照定义,基因头部长度head和尾部的长度tail之间应遵循如下函数关系:
8、tail
9、=
10、head
11、×(n-1)+1其中n为函数集合中所有运算符的最大目数.文[5]证明了在这个规则约束下,GEP的遗传操作总能
12、产生有效基因,有效地解决了GP中可能产生语义上不合法的表达式的问题.GEP中常用的适应度函数有两种,如式(1)和式(2).Ctfi=∑(M-C(i,j)-T(j))(1)j=1CtC(i,j)-T(j)fi=∑M-·100(2)j=1T(j)式(1)和式(2)分别为基于绝对误差和相对误差的适应度评价函数.每代的进化结果经适应度函数评价后,适应度高的个体被保留并有更高机会繁
