学到老Never too old to learn分享 http://blog.sciencenet.cn/u/tangchangjie

博文

达尔文、孟德尔与老愚公的会盟:基因表达式编程--趣味数据挖之十 精选

已有 27978 次阅读 2012-2-16 08:48 |个人分类:科普札记|系统分类:科普集锦|关键词:数据挖掘,基因表达式编程,遗传算法,遗传编程,达尔文,孟德尔,愚公,| 达尔文, 数据挖掘, 遗传算法, 基因表达式编程, 遗传编程

达尔文、孟德尔与老愚公的会盟:基因表达式编程--趣味数据挖之十

1 GEP的速度魅力 在本系列之九的末尾提到,基因表达式编程GEPGene Expression Programming)是一种数据挖掘工具,是进化计算家族中较新的成员。在很多应用中,GEP比更传统的进化算法2-4个数量级[1,2,3];在实践中还发现,在某些特定场合,比传统方法快5-6个数量级,甚至更多。目前一些学校把GEP作为计算机专业及相关专业的硕博士选修课程。

GEP的速度魅力太吸引人了,12年前,关于GEP的简单信息在网上刚露头角,两周后,我们研究团队中,处于选题饥饿的博士生们读到了它,团队立刻跟踪研究,十多年来,得到过多个科学基金支持,至今还不疲不倦,无怨无悔,只因为它太奇妙,太快了。

为诠释这些稍难的内容,从过去的课程PPT中取了若干现成素材,任重而文短,作为科普博文,只能给出大致的轮廓。

 

2 GEP不是什么,又是什么 GEP不是生物工程,不是生命科学。发明人Ferreira, Candida 把它称为 Biologically Inspired Computing,(生物灵感激发的计算),它是一种数据挖掘的工具。在Candida的专著[2]中,第一章介绍了生物基因学的基本概念和常识,仅作它山之石,GEP借用了生命科学中基因,染色体等概念和进化的框架,作数据挖掘,用于发现公式、规则或规律。

 GEP可以做什么? 实践表明,非计算机专业的硕士生或博士生,经过几周或几个月的学习可以用现成的GEP系统挖掘多种表达式(数学方程、公式,以及逻辑规则),从而也能挖掘逻辑规则表达的关联规则、分类规则、聚类规则等。例如发现太阳黑子规律,发现开普勒定律,设计门电路……,我们课题组还提出过一个新应用:作传统意义的因式分解,特别地,当给定多项式是质因式(在整数环上不可分解的多项式),如果强迫分解,也能做近似分解;表1给了一些示意,技术细节参见文献[4]

           

输入:指定的或随机产生的测试函数

输出:GEP分解的结果多项式集

2x6-x5-5x4+8x3+1

2.00x3+3.00x2–1.00x+1.00; 1.00x3-2.00x2+1.00x+1.00

12x7+2x6+27x5+52x4+24x3+70x2+39x+5

2.99x2-1.00x+5.00;  4.00x2+6.01x+0.98;

1.00x3-1.00x2+1.99x+1.00

2x10+x9-x8+18x7-46x6+87x5-58x4+79x3-90x2 +34x-24

1.00x2-2.01x+2.00;1.00x3-0.99x2+3.00x-4

2.00x2+0.98x+2.99; 1.02x3+3.00x2+1.00

1  GEP作因式分解

GEP使用者的感觉 -- 学当袁隆平。GEP的使用者的感觉就好像是动植物良种培育专家,好像在学当袁隆平,只不过培育的不是水稻,而是公式、规则和方程,良种就是真实、无噪声的(训练)数据;过程中有成功也有失败。失败了,修改方案或参数再来一次,被培育对象在电脑中进化,几秒钟进化几千代,几分钟,或几小时,进化几百万代; 实验室中没有严寒酷暑,不像袁隆平那样辛苦。

下面将比较GEP及其前辈算法GA(遗传算法 Genetic Algorithm)和 GP(遗传编程 Genetic Programming);先说差别,后说共性。

 

    3  差别在何处? 编码有代沟。

   GEP和与其前辈遗传算法(GA)和 遗传编程(GP)的差别表现在遗传物质编码方式。上文用非编码形式介绍过公式 1 + x4    5 – x的杂交和变异,回忆相关要点:

杂交 1 + x4 ,   5 - x ,施加以换头术,交换红蓝部分, 可以杂交出  5+ x4  1-x

变异:在染色体中插入、删除、或修改 符号或符号片段。  6+x7 中的“+”变为“*”,得到 6*x7

 3.1 遗传算法(GA)的编码—线性串,简单编码解决简单问题 GA直接把进化对象编码成01之称的线性串,表2 示意了公式编码以及杂交(换头术):        

公式

编码

杂交(交换前k位)k=6

杂交后,解码出的公式

1+x4

1100101010

1011011010

5+x4

-x

1011011110

1100101110

1 - x

2 GA的编码,杂交和变异

GA编码简单,适合计算机处理,但语义不丰富。是 简单编码解决简单问题

 

3.2 遗传编程(GP)的编码 – 树结构,复杂编码解决复杂问题

GP把进化对象(例如公式)编码成树。为简单,图1 示意了二叉树,基本数据结构是节点三元组:(节点号,左儿子指针,右儿子指针);通过指针适当地链接一组节点,组成从根节点开始的树。

图中语义多。理解有窍门由下而上,逐步归约。例如:左边的黄色部分,从b开始,其父节点是开平方运算Sqrt ,合起来表示 b1/2 ;类似地,右边黄色部分 可由下而上归约,得到:(b/c/a

GP的杂交 例如,把左图和右图中的黄色部分交换。(像不像器官对移?)

GP的变异: 例如,把左图中 a 突变为 x+y

GA相比,GP采用了复杂的树结构,可以表达复杂的语义,是 复杂编码解决复杂问题

1,遗传编程GP的编码,杂交和变异

 

3.3 GA和GP编码的致命缺点-遗传手术下存活率低  GAGP的遗传手术太残酷,杂交好像器官对换,变异中的插、删、改手术好像长瘤,截肢,器官移植,在这些很酷(Cool和残酷)的手术下, 大多数对象都死亡或伤残了,浪费了计算机的时空资源。

 

3.4 GA和GP的爱情结晶:GEP

Candida Ferreira融合了遗传算法(GA)和遗传编程(GP)的 优势,创造性地提出了基因表达式编程GEP。下图中给出了GAGP杂交产生GEP的框架:

2  基因表达式编程 GEP继承了遗传算法GA和遗传编程GP的优势

 

GEP 继承了父亲GA的有刚性和规范,韬光养晦,藏复杂之树于简单之串,易作遗传操作,快速 

GEP 继承了母亲GP的柔性和多变多能,语义(感情)丰富;

GEP 向生物科学借鉴并实现了更多概念,如多基因染色体、如基因的表达、如中性区中隐形的继承和变异。最重要的是,GEP的巧妙编码使其成为不死鸟,在残酷的基因手术下能全部存活,这是GEPGA,GP的速度普遍提高2-4个数量级的最重要原因。

其奇妙而简单的编码称为基因表达式,将在在第5节详细解析,现保留一点美好的悬念。

 

4 家族共性:达尔文的进化框架,孟德尔的遗传规律,摩尔根的基因变异,老愚公的移山精神。
     GAGPGEP,乃至整个进化计算家族,闪耀着先贤和哲人的思想火花,有下列共性:达尔文的进化框架,孟德尔的遗传规律,摩尔根的基因变异,还有老愚公的移山精神。

算法思想和框架(粗可只看图,细则看解释) 3是遗传算法GA的进化流程,如果把其中编码方式换为GP的树,或GEP的基因表达式,就得到GPGEP的流程。与上文( 趣味数据挖掘之九 )的通例相比,图3稍细致一些:

3 遗传算法的编码和进化流程示意图

 

图1的解释(初读时,不妨跳过)中给出了编码进化的流程,初始化的三个函数 ,与进化目标y=x+sin(x)的戴劳展式相差甚远,标注框中是编码前的公式,编码成为01的串。下面跟着红色的编号(1)-(6),略作说明:

(1)初始解,离谜底y=x+sin(x)较远;(2)三个公式编码成为01串联(图是示意性的);(3)交叉,两个公式的编码实施换头术,得到后代C1C2(4)公式6+X7 变异成为6*x7   (5) 编码解码成为公式,计算误差(适应度)

(6) 轮盘赌,可比喻为庙会上的“转糖饼”游戏,轮盘的转与停是随机过程,以此决定奖励品种,颇有点“费厄泼赖”,貌似公平;而庄家实则在扇区面积上做文章,成本低的品种被选中的机会越大(对应于进化计算中的术语:适应度越大),例如,图3中的轮盘赌来自“转糖饼”游戏,其中的“糖龙”与“糖虎” 成本高,对应的扇区小,指针停在这里的机会少;而小糖饼成本低,对应的扇区大,指针停在这里的机会多,小奖多而大奖少,从而维护了庄家的利益;

(7)检查终止条件,如果没有达到终止条件,进入下一代循环,这里表现了愚公移山故事中的“子子孙孙是没有穷尽的”。

 

 5 简单编码解决复杂问题-简单而奇妙的基因表达式编码   

下图示意了GEP编码思路:图中有三个等价的表达:基因表达式,语法树和数学表达式:

4 三个等价表达,基因表达式,语法树,数学表达式

知识解释:从语法树中,从叶到根归约

 减号下面有,ab, 归约得到a-b;

加号下面有,ab, 归约得到a+b;

处理乘法符号,归约得到(a-b)* (c+d),      (如程序语言中,*表示乘法);

处理开平方符号Q,得到数学达式 ((a-b) * (c+d))1/2

 

知识表达。按计算的优先级(如先乘除,后加减)展开,先算的在下,后算的在上,最后算的为根

 

编码过程 语法树中, 从上到下,从左到右,把符号写成一串(解码程序只需几十行)。

 

解码过程:从左到右,按指标生育,按次序表达,两个要点:

(a)节点按指标生育开方只有一个参数,就只有子节点,+-*/有两个参数, 有两个子节点,If-Then-Else(或缩写为ITE)是一个运算的名称,有三个参数,即ITE节点有三个子节点。

(b)表达式中符号按次序表达。从基因表达式第一个符号开始表达:

首先表达Q(开方):Q只需一个参数,建立以Q为根的树(此时,图中只有一个根节点Q)

开平方运算Q需要一个被操作数(儿子),表达式中下一个符号是X(乘法),X被表达为Q的儿子

乘法运算X 需要两个被操作数(儿子),表达式中下两个符号“-”和“+”,二者作X的儿子节点,于是“-”和“+”被表达;

减号- 需要两个被操作数,表达式中下两个符号是a b,二者作减号的儿子, a b已被表达为a-b;

加号+ 需要两个被操作数,表达式中下两个符号是c d,二者作加号的儿子, c d已被表达 c+d.

叶节点上全是常数,不再需要被操作对象了, 表达完毕。

 

基因材料的 供过于求供不应求 细心地读者会发现红色的xyz没有被表达,这种供过于求是好现象,模拟了生物基因中的中性区。如果供不应求,例如一个“+”号需要两个被操作数,基因表达中没有或只有一个被操作数,指向被操作数指针是空指针或者乱指针,将引起程序崩溃。

“平时看不见,偶尔露峥嵘”,中性区与隐性遗传,和生物基因中的中性区类似,中性区默默无闻地参加并积累着遗传和变异,但其对应的性状暂时没有表达出来。例如,图5中,xy 是隐形基因,因为他们的父节点是常量a,而a不需要参数。假定有朝一日,符号a变异成为“+”,则“+”有两个生育指标,就把 x+y 表达出来了,原来结果中的这一个a会被(x+y)取代,最后结果变为((x+y-b)* (c+d))1/2   ,如图5. 人群中的隔代遗传现象不知是否有类似解释,请专家指正。

 

 

 

 

图5 中性区“平时看不见,偶尔露峥嵘”

 

基因表达式编程的编码之妙:F.Cadidda 发明了基因表达式编程的编码方法, 其最大的特点是:

1形串实树,藏复杂内容于平凡形式参加遗传操作时,以线性串的平凡姿态,存储简单,处理快捷;解释语义时,用树的形式表达深刻的语义。

(2)生命力强,永不死亡,前面说过,在GA和GP中,染色体在残酷的遗传手术(如换头,挖心,加瘤)下大量死亡(有时,存活的不到1%),程序要花大量时间和空间去检查存活性,极大制约的进化的速度和质量,下面的定理将说明,基因表达式在遗传操作下永不死亡 。

 

 6 Candida的直觉和基因表达式基本定理  获得了生物化学博士学位的Ferreira Candida有深厚生物医学背景,,在发明 GEP时候,她凭直觉采用了巧妙的  形“串”实“树”的数据结构,给出了下列两个宽松的约束:

a 内容约束:分成头尾两部分,头部可算符与参数;尾部不含算符,只有参数;

(b)  长度约束如果头长h,尾长t,计算符号最大目数(参数个数)为n,则须满足t=h(n-1)+1  。

Ferreira Candida直观感觉到,只要满足上述两条约束,头部的计算符号按生育指标索取子节点,在表达部分就有足够的被操作数供表达,不会出现供不应求的现象(而没有给证明或说明)。

供不应求对应于程序中使用未分配的指针或盲指针,例如,设P1和P2是指向参数的指针,做下列加法:

*P1) + (*P2,其中P1P2 未分配的指针 或 盲指针,则可能引起程序崩溃或计算错误。

 

   2002年,我们的研究团队用数学归纳法严格地证明了:只要染色体满足上述两个(宽松的)约束, 则在任意残酷基因手术下,染色体永不死亡(参见文献[5])

这个定理有时被称为GEP基本定理,它给出了GEP可行可信的理论依据。 

 

科学家和工程师的好工具。对于实验科学家和工程师,如果想自己开发一套GEP挖掘系统,需要半年或一年以上的学习(时间依赖于相关基础);如果使用现成的商品化的GEP系统,只需要几周的学习;这有点像造一个程序语言和使用程序语言的差别。程序语言即便简单如BASIC,也需要一定时间的学习,学好用好一个较复杂的语言(如C)要一年以上的学习和实践。

在网上搜索Ferreira Candida 或GEP ,可以得到更多的信息,可以查到他们的公司和软件产品。也容易查到国内外研究者的成果和进展。

使用现成的系统,经过不太长时间的学习,可从自己的实验数据中挖掘经验公式、类似于发现类似于太阳黑子规律、类似与开普勒定律的数学方程、设计门电路,还可以挖掘关联规则、分类规则、聚类规则、 逻辑规则,等等。

 

下篇博文,拟讨论数据挖掘的十大算法以及十大问题。

 

参考文献

[1] Ferreira Candida, Complete reference for the first GEP paper, (12/5/2001). Gene Expression Programming: A New Adaptive

    Algorithm        for Solving Problems, Complex Systems, 13 (2): 87 – 129 2000.12

[2] Ferreira Candida ,. Gene Expression Programming, First Edition, Printed and Bounded in Portugal, Angra doHeroismo,

      Portugal, 2002. Deposito legal n0 187498/02 (第一本GEP专著)

[3] Candida Ferreira, Gene Expression Programming: Mathematical Modeling by an Artificial

   Intelligence (Studies in Computational Intelligence),Publisher: Springer; 2nd edition

   (July 11, 2006).

[4]汪锐,唐常杰,段磊,陈宇,廖勇, 基于基因表达式的的多项式函数关系分解,计算机研究与发展,

    VOl.41. No.10 , Oct.2004 (Suppl.) P.442-447.

 [5] Zuo Jie, Tang Changjie and Zhang Tianqing"Mining Predicate Association Rule by

     Gene ExpressionProgramming", WAIM02 (International Conference for Web Information Age 2002).

     LNCS (Lecture Notes In Computer science) Vol.2419, pp.92-103,edited by, Springer Verlag

     Berling Heidelberg  2002.8,ISBN


 相关博文

   1“被打北大的关联--- 趣味数据挖掘系列之 

   2 烤鸭、面饼和甜面酱之朴素关联---趣味数据挖掘系列之二 

   3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之

   4 巧挖科学博客之均击量公式,兼谈干预规则----趣味数据挖掘之四 

   5 听妈妈讲 过去的故事,分房与分类-----趣味数据挖掘之五 

   6 借水浒传故事,释决策树思路---趣味数据挖掘之六

   7 团拜会和鸡尾酒会上的聚类趣味数据挖掘之七

   8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八

   9 灯谜、外星殖民、愚公移山和进化计算---趣味数据挖掘之九

   10 达尔文、孟德尔与老愚公会盟:基因表达式编程--趣味数据挖之十

   11 十大算法展辉煌,十大问题现锦绣---趣味数据挖掘之十一 

   12 数据挖掘中的趣味哲学---趣味数据挖掘之十二 

 

          其它系列博文的入口      唐常杰博客主页       科学博客主页 



 

 



http://blog.sciencenet.cn/blog-287179-537914.html

上一篇:火热春运今又是,换了空间
下一篇:十大算法展辉煌历史,十大问题引锦绣前程---趣味数据挖掘之十一

59 刘全慧 章迅来 刘学凯 赵继慧 李华芬 毛宁 陈威华 谢鑫 钟炳 苏德辰 许培扬 吴飞鹏 金小伟 李学宽 郭桅 董文娜 袁君云 元云芬 石东兴 封力军 刘广明 曹聪 马丽滨 江贺 刘文 黄秀清 吕喆 武夷山 赵凤光 李伟钢 傅云义 陈波 袁泽俊 吴顺凡 黄晓磊 杨学祥 张南希 鲍海飞 单博炜 高建国 杨秀海 杨晓慧 井然哲 陈斌 杨正瓴 曾新林 李宇斌 汤奔阳 周春雷 李欣海 化柏林 邹晓辉 宋铁成 wangguofengw zhanghongmin79 wnagjiho hangzhou dulizhi95 taiga

该博文允许注册用户评论 请点击登录 评论 (63 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-4-9 08:28

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部